mod.rs source code [crates/hashbrown-0.14.3/src/raw/mod.rs]

1	use crate::alloc::alloc::{handle_alloc_error, Layout};
2	use crate::scopeguard::{guard, ScopeGuard};
3	use crate::TryReserveError;
4	use core::iter::FusedIterator;
5	use core::marker::PhantomData;
6	use core::mem;
7	use core::mem::MaybeUninit;
8	use core::ptr::NonNull;
9	use core::{hint, ptr};
10
11	cfg_if! {
12	// Use the SSE2 implementation if possible: it allows us to scan 16 buckets
13	// at once instead of 8. We don't bother with AVX since it would require
14	// runtime dispatch and wouldn't gain us much anyways: the probability of
15	// finding a match drops off drastically after the first few buckets.
16	//
17	// I attempted an implementation on ARM using NEON instructions, but it
18	// turns out that most NEON instructions have multi-cycle latency, which in
19	// the end outweighs any gains over the generic implementation.
20	if #[cfg(all(
21	target_feature = "sse2",
22	any(target_arch = "x86", target_arch = "x86_64"),
23	not(miri),
24	))] {
25	mod sse2;
26	use sse2 as imp;
27	} else if #[cfg(all(
28	target_arch = "aarch64",
29	target_feature = "neon",
30	// NEON intrinsics are currently broken on big-endian targets.
31	// See https://github.com/rust-lang/stdarch/issues/1484.
32	target_endian = "little",
33	not(miri),
34	))] {
35	mod neon;
36	use neon as imp;
37	} else {
38	mod generic;
39	use generic as imp;
40	}
41	}
42
43	mod alloc;
44	pub(crate) use self::alloc::{do_alloc, Allocator, Global};
45
46	mod bitmask;
47
48	use self::bitmask::BitMaskIter;
49	use self::imp::Group;
50
51	// Branch prediction hint. This is currently only available on nightly but it
52	// consistently improves performance by 10-15%.
53	#[cfg(not(feature = "nightly"))]
54	use core::convert::identity as likely;
55	#[cfg(not(feature = "nightly"))]
56	use core::convert::identity as unlikely;
57	#[cfg(feature = "nightly")]
58	use core::intrinsics::{likely, unlikely};
59
60	// FIXME: use strict provenance functions once they are stable.
61	// Implement it with a transmute for now.
62	#[inline(always)]
63	#[allow(clippy::useless_transmute)] // clippy is wrong, cast and transmute are different here
64	fn invalid_mut<T>(addr: usize) -> *mut T {
65	unsafe { core::mem::transmute(src:addr) }
66	}
67
68	#[inline]
69	unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
70	to.offset_from(origin:from) as usize
71	}
72
73	/// Whether memory allocation errors should return an error or abort.
74	#[derive(Copy, Clone)]
75	enum Fallibility {
76	Fallible,
77	Infallible,
78	}
79
80	impl Fallibility {
81	/// Error to return on capacity overflow.
82	#[cfg_attr(feature = "inline-more", inline)]
83	fn capacity_overflow(self) -> TryReserveError {
84	match self {
85	Fallibility::Fallible => TryReserveError::CapacityOverflow,
86	Fallibility::Infallible => panic!("Hash table capacity overflow"),
87	}
88	}
89
90	/// Error to return on allocation error.
91	#[cfg_attr(feature = "inline-more", inline)]
92	fn alloc_err(self, layout: Layout) -> TryReserveError {
93	match self {
94	Fallibility::Fallible => TryReserveError::AllocError { layout },
95	Fallibility::Infallible => handle_alloc_error(layout),
96	}
97	}
98	}
99
100	trait SizedTypeProperties: Sized {
101	const IS_ZERO_SIZED: bool = mem::size_of::<Self>() == `0`;
102	const NEEDS_DROP: bool = mem::needs_drop::<Self>();
103	}
104
105	impl<T> SizedTypeProperties for T {}
106
107	/// Control byte value for an empty bucket.
108	const EMPTY: u8 = `0b1111_1111`;
109
110	/// Control byte value for a deleted bucket.
111	const DELETED: u8 = `0b1000_0000`;
112
113	/// Checks whether a control byte represents a full bucket (top bit is clear).
114	#[inline]
115	fn is_full(ctrl: u8) -> bool {
116	ctrl & `0x80` == `0`
117	}
118
119	/// Checks whether a control byte represents a special value (top bit is set).
120	#[inline]
121	fn is_special(ctrl: u8) -> bool {
122	ctrl & `0x80` != `0`
123	}
124
125	/// Checks whether a special control value is EMPTY (just check 1 bit).
126	#[inline]
127	fn special_is_empty(ctrl: u8) -> bool {
128	debug_assert!(is_special(ctrl));
129	ctrl & `0x01` != `0`
130	}
131
132	/// Primary hash function, used to select the initial bucket to probe from.
133	#[inline]
134	#[allow(clippy::cast_possible_truncation)]
135	fn h1(hash: u64) -> usize {
136	// On 32-bit platforms we simply ignore the higher hash bits.
137	hash as usize
138	}
139
140	// Constant for h2 function that grabing the top 7 bits of the hash.
141	const MIN_HASH_LEN: usize = if mem::size_of::<usize>() < mem::size_of::<u64>() {
142	mem::size_of::<usize>()
143	} else {
144	mem::size_of::<u64>()
145	};
146
147	/// Secondary hash function, saved in the low 7 bits of the control byte.
148	#[inline]
149	#[allow(clippy::cast_possible_truncation)]
150	fn h2(hash: u64) -> u8 {
151	// Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
152	// value, some hash functions (such as FxHash) produce a usize result
153	// instead, which means that the top 32 bits are 0 on 32-bit platforms.
154	// So we use MIN_HASH_LEN constant to handle this.
155	let top7: u64 = hash >> (MIN_HASH_LEN * `8` - `7`);
156	(top7 & `0x7f`) as u8 // truncation
157	}
158
159	/// Probe sequence based on triangular numbers, which is guaranteed (since our
160	/// table size is a power of two) to visit every group of elements exactly once.
161	///
162	/// A triangular probe has us jump by 1 more group every time. So first we
163	/// jump by 1 group (meaning we just continue our linear scan), then 2 groups
164	/// (skipping over 1 group), then 3 groups (skipping over 2 groups), and so on.
165	///
166	/// Proof that the probe will visit every group in the table:
167	/// <https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/>
168	struct ProbeSeq {
169	pos: usize,
170	stride: usize,
171	}
172
173	impl ProbeSeq {
174	#[inline]
175	fn move_next(&mut self, bucket_mask: usize) {
176	// We should have found an empty bucket by now and ended the probe.
177	debug_assert!(
178	self.stride <= bucket_mask,
179	"Went past end of probe sequence"
180	);
181
182	self.stride += Group::WIDTH;
183	self.pos += self.stride;
184	self.pos &= bucket_mask;
185	}
186	}
187
188	/// Returns the number of buckets needed to hold the given number of items,
189	/// taking the maximum load factor into account.
190	///
191	/// Returns `None` if an overflow occurs.
192	// Workaround for emscripten bug emscripten-core/emscripten-fastcomp#258
193	#[cfg_attr(target_os = "emscripten", inline(never))]
194	#[cfg_attr(not(target_os = "emscripten"), inline)]
195	fn capacity_to_buckets(cap: usize) -> Option<usize> {
196	debug_assert_ne!(cap, `0`);
197
198	// For small tables we require at least 1 empty bucket so that lookups are
199	// guaranteed to terminate if an element doesn't exist in the table.
200	if cap < `8` {
201	// We don't bother with a table size of 2 buckets since that can only
202	// hold a single element. Instead we skip directly to a 4 bucket table
203	// which can hold 3 elements.
204	return Some(if cap < `4` { `4` } else { `8` });
205	}
206
207	// Otherwise require 1/8 buckets to be empty (87.5% load)
208	//
209	// Be careful when modifying this, calculate_layout relies on the
210	// overflow check here.
211	let adjusted_cap: usize = cap.checked_mul(`8`)? / `7`;
212
213	// Any overflows will have been caught by the checked_mul. Also, any
214	// rounding errors from the division above will be cleaned up by
215	// next_power_of_two (which can't overflow because of the previous division).
216	Some(adjusted_cap.next_power_of_two())
217	}
218
219	/// Returns the maximum effective capacity for the given bucket mask, taking
220	/// the maximum load factor into account.
221	#[inline]
222	fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
223	if bucket_mask < `8` {
224	// For tables with 1/2/4/8 buckets, we always reserve one empty slot.
225	// Keep in mind that the bucket mask is one less than the bucket count.
226	bucket_mask
227	} else {
228	// For larger tables we reserve 12.5% of the slots as empty.
229	((bucket_mask + `1`) / `8`) * `7`
230	}
231	}
232
233	/// Helper which allows the max calculation for ctrl_align to be statically computed for each T
234	/// while keeping the rest of `calculate_layout_for` independent of `T`
235	#[derive(Copy, Clone)]
236	struct TableLayout {
237	size: usize,
238	ctrl_align: usize,
239	}
240
241	impl TableLayout {
242	#[inline]
243	const fn new<T>() -> Self {
244	let layout = Layout::new::<T>();
245	Self {
246	size: layout.size(),
247	ctrl_align: if layout.align() > Group::WIDTH {
248	layout.align()
249	} else {
250	Group::WIDTH
251	},
252	}
253	}
254
255	#[inline]
256	fn calculate_layout_for(self, buckets: usize) -> Option<(Layout, usize)> {
257	debug_assert!(buckets.is_power_of_two());
258
259	let TableLayout { size, ctrl_align } = self;
260	// Manual layout calculation since Layout methods are not yet stable.
261	let ctrl_offset =
262	size.checked_mul(buckets)?.checked_add(ctrl_align - `1`)? & !(ctrl_align - `1`);
263	let len = ctrl_offset.checked_add(buckets + Group::WIDTH)?;
264
265	// We need an additional check to ensure that the allocation doesn't
266	// exceed `isize::MAX` (https://github.com/rust-lang/rust/pull/95295).
267	if len > isize::MAX as usize - (ctrl_align - `1`) {
268	return None;
269	}
270
271	Some((
272	unsafe { Layout::from_size_align_unchecked(len, ctrl_align) },
273	ctrl_offset,
274	))
275	}
276	}
277
278	/// A reference to an empty bucket into which an can be inserted.
279	pub struct InsertSlot {
280	index: usize,
281	}
282
283	/// A reference to a hash table bucket containing a `T`.
284	///
285	/// This is usually just a pointer to the element itself. However if the element
286	/// is a ZST, then we instead track the index of the element in the table so
287	/// that `erase` works properly.
288	pub struct Bucket<T> {
289	// Actually it is pointer to next element than element itself
290	// this is needed to maintain pointer arithmetic invariants
291	// keeping direct pointer to element introduces difficulty.
292	// Using `NonNull` for variance and niche layout
293	ptr: NonNull<T>,
294	}
295
296	// This Send impl is needed for rayon support. This is safe since Bucket is
297	// never exposed in a public API.
298	unsafe impl<T> Send for Bucket<T> {}
299
300	impl<T> Clone for Bucket<T> {
301	#[inline]
302	fn clone(&self) -> Self {
303	Self { ptr: self.ptr }
304	}
305	}
306
307	impl<T> Bucket<T> {
308	/// Creates a [`Bucket`] that contain pointer to the data.
309	/// The pointer calculation is performed by calculating the
310	/// offset from given `base` pointer (convenience for
311	/// `base.as_ptr().sub(index)`).
312	///
313	/// `index` is in units of `T`; e.g., an `index` of 3 represents a pointer
314	/// offset of `3 size_of::<T>()` bytes.*
315	///
316	/// If the `T` is a ZST, then we instead track the index of the element
317	/// in the table so that `erase` works properly (return
318	/// `NonNull::new_unchecked((index + 1) as mut T)`)*
319	///
320	/// # Safety
321	///
322	/// If `mem::size_of::<T>() != 0`, then the safety rules are directly derived
323	/// from the safety rules for [`<mut T>::sub`] method of `mut T` and the safety
324	/// rules of [`NonNull::new_unchecked`] function.
325	///
326	/// Thus, in order to uphold the safety contracts for the [`<mut T>::sub`] method*
327	/// and [`NonNull::new_unchecked`] function, as well as for the correct
328	/// logic of the work of this crate, the following rules are necessary and
329	/// sufficient:
330	///
331	/// the `base` pointer must not be `dangling` and must points to the*
332	/// end of the first `value element` from the `data part` of the table, i.e.
333	/// must be the pointer that returned by [`RawTable::data_end`] or by
334	/// [`RawTableInner::data_end<T>`];
335	///
336	/// `index` must not be greater than `RawTableInner.bucket_mask`, i.e.*
337	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)`
338	/// must be no greater than the number returned by the function
339	/// [`RawTable::buckets`] or [`RawTableInner::buckets`].
340	///
341	/// If `mem::size_of::<T>() == 0`, then the only requirement is that the
342	/// `index` must not be greater than `RawTableInner.bucket_mask`, i.e.
343	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)`
344	/// must be no greater than the number returned by the function
345	/// [`RawTable::buckets`] or [`RawTableInner::buckets`].
346	///
347	/// [`Bucket`]: crate::raw::Bucket
348	/// [`<mut T>::sub`]: https://doc.rust-lang.org/core/primitive.pointer.html#method.sub-1*
349	/// [`NonNull::new_unchecked`]: https://doc.rust-lang.org/stable/std/ptr/struct.NonNull.html#method.new_unchecked
350	/// [`RawTable::data_end`]: crate::raw::RawTable::data_end
351	/// [`RawTableInner::data_end<T>`]: RawTableInner::data_end<T>
352	/// [`RawTable::buckets`]: crate::raw::RawTable::buckets
353	/// [`RawTableInner::buckets`]: RawTableInner::buckets
354	#[inline]
355	unsafe fn from_base_index(base: NonNull<T>, index: usize) -> Self {
356	// If mem::size_of::<T>() != 0 then return a pointer to an `element` in
357	// the data part of the table (we start counting from "0", so that
358	// in the expression T[last], the "last" index actually one less than the
359	// "buckets" number in the table, i.e. "last = RawTableInner.bucket_mask"):
360	//
361	// `from_base_index(base, 1).as_ptr()` returns a pointer that
362	// points here in the data part of the table
363	// (to the start of T1)
364	// \|
365	// \| `base: NonNull<T>` must point here
366	// \| (to the end of T0 or to the start of C0)
367	// v v
368	// [Padding], Tlast, ..., \|T1\|, T0, \|C0, C1, ..., Clast
369	// ^
370	// `from_base_index(base, 1)` returns a pointer
371	// that points here in the data part of the table
372	// (to the end of T1)
373	//
374	// where: T0...Tlast - our stored data; C0...Clast - control bytes
375	// or metadata for data.
376	let ptr = if T::IS_ZERO_SIZED {
377	// won't overflow because index must be less than length (bucket_mask)
378	// and bucket_mask is guaranteed to be less than `isize::MAX`
379	// (see TableLayout::calculate_layout_for method)
380	invalid_mut(index + `1`)
381	} else {
382	base.as_ptr().sub(index)
383	};
384	Self {
385	ptr: NonNull::new_unchecked(ptr),
386	}
387	}
388
389	/// Calculates the index of a [`Bucket`] as distance between two pointers
390	/// (convenience for `base.as_ptr().offset_from(self.ptr.as_ptr()) as usize`).
391	/// The returned value is in units of T: the distance in bytes divided by
392	/// [`core::mem::size_of::<T>()`].
393	///
394	/// If the `T` is a ZST, then we return the index of the element in
395	/// the table so that `erase` works properly (return `self.ptr.as_ptr() as usize - 1`).
396	///
397	/// This function is the inverse of [`from_base_index`].
398	///
399	/// # Safety
400	///
401	/// If `mem::size_of::<T>() != 0`, then the safety rules are directly derived
402	/// from the safety rules for [`<const T>::offset_from`] method of `const T`.
403	///
404	/// Thus, in order to uphold the safety contracts for [`<const T>::offset_from`]*
405	/// method, as well as for the correct logic of the work of this crate, the
406	/// following rules are necessary and sufficient:
407	///
408	/// `base` contained pointer must not be `dangling` and must point to the*
409	/// end of the first `element` from the `data part` of the table, i.e.
410	/// must be a pointer that returns by [`RawTable::data_end`] or by
411	/// [`RawTableInner::data_end<T>`];
412	///
413	/// `self` also must not contain dangling pointer;*
414	///
415	/// both `self` and `base` must be created from the same* [`RawTable`]
416	/// (or [`RawTableInner`]).
417	///
418	/// If `mem::size_of::<T>() == 0`, this function is always safe.
419	///
420	/// [`Bucket`]: crate::raw::Bucket
421	/// [`from_base_index`]: crate::raw::Bucket::from_base_index
422	/// [`RawTable::data_end`]: crate::raw::RawTable::data_end
423	/// [`RawTableInner::data_end<T>`]: RawTableInner::data_end<T>
424	/// [`RawTable`]: crate::raw::RawTable
425	/// [`RawTableInner`]: RawTableInner
426	/// [`<const T>::offset_from`]: https://doc.rust-lang.org/nightly/core/primitive.pointer.html#method.offset_from*
427	#[inline]
428	unsafe fn to_base_index(&self, base: NonNull<T>) -> usize {
429	// If mem::size_of::<T>() != 0 then return an index under which we used to store the
430	// `element` in the data part of the table (we start counting from "0", so
431	// that in the expression T[last], the "last" index actually is one less than the
432	// "buckets" number in the table, i.e. "last = RawTableInner.bucket_mask").
433	// For example for 5th element in table calculation is performed like this:
434	//
435	// mem::size_of::<T>()
436	// \|
437	// \| `self = from_base_index(base, 5)` that returns pointer
438	// \| that points here in tha data part of the table
439	// \| (to the end of T5)
440	// \| \| `base: NonNull<T>` must point here
441	// v \| (to the end of T0 or to the start of C0)
442	// /???\ v v
443	// [Padding], Tlast, ..., \|T10\|, ..., T5\|, T4, T3, T2, T1, T0, \|C0, C1, C2, C3, C4, C5, ..., C10, ..., Clast
444	// \__________ __________/
445	// \/
446	// `bucket.to_base_index(base)` = 5
447	// (base.as_ptr() as usize - self.ptr.as_ptr() as usize) / mem::size_of::<T>()
448	//
449	// where: T0...Tlast - our stored data; C0...Clast - control bytes or metadata for data.
450	if T::IS_ZERO_SIZED {
451	// this can not be UB
452	self.ptr.as_ptr() as usize - `1`
453	} else {
454	offset_from(base.as_ptr(), self.ptr.as_ptr())
455	}
456	}
457
458	/// Acquires the underlying raw pointer `mut T` to `data`.*
459	///
460	/// # Note
461	///
462	/// If `T` is not [`Copy`], do not use `mut T` methods that can cause calling the*
463	/// destructor of `T` (for example the [`<mut T>::drop_in_place`] method), because*
464	/// for properly dropping the data we also need to clear `data` control bytes. If we
465	/// drop data, but do not clear `data control byte` it leads to double drop when
466	/// [`RawTable`] goes out of scope.
467	///
468	/// If you modify an already initialized `value`, so [`Hash`] and [`Eq`] on the new
469	/// `T` value and its borrowed form must* match those for the old `T` value, as the map*
470	/// will not re-evaluate where the new value should go, meaning the value may become
471	/// "lost" if their location does not reflect their state.
472	///
473	/// [`RawTable`]: crate::raw::RawTable
474	/// [`<mut T>::drop_in_place`]: https://doc.rust-lang.org/core/primitive.pointer.html#method.drop_in_place*
475	/// [`Hash`]: https://doc.rust-lang.org/core/hash/trait.Hash.html
476	/// [`Eq`]: https://doc.rust-lang.org/core/cmp/trait.Eq.html
477	///
478	/// # Examples
479	///
480	/// ```
481	/// # #[cfg(feature = "raw")]
482	/// # fn test() {
483	/// use core::hash::{BuildHasher, Hash};
484	/// use hashbrown::raw::{Bucket, RawTable};
485	///
486	/// type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;
487	///
488	/// fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
489	/// use core::hash::Hasher;
490	/// let mut state = hash_builder.build_hasher();
491	/// key.hash(&mut state);
492	/// state.finish()
493	/// }
494	///
495	/// let hash_builder = NewHashBuilder::default();
496	/// let mut table = RawTable::new();
497	///
498	/// let value = ("a", `100`);
499	/// let hash = make_hash(&hash_builder, &value.0);
500	///
501	/// table.insert(hash, value.clone(), \|val\| make_hash(&hash_builder, &val.0));
502	///
503	/// let bucket: Bucket<(&str, i32)> = table.find(hash, \|(k1, _)\| k1 == &value.0).unwrap();
504	///
505	/// assert_eq!(unsafe { &*bucket.as_ptr() }, &("a", `100`));
506	/// # }
507	/// # fn main() {
508	/// # #[cfg(feature = "raw")]
509	/// # test()
510	/// # }
511	/// ```
512	#[inline]
513	pub fn as_ptr(&self) -> *mut T {
514	if T::IS_ZERO_SIZED {
515	// Just return an arbitrary ZST pointer which is properly aligned
516	// invalid pointer is good enough for ZST
517	invalid_mut(mem::align_of::<T>())
518	} else {
519	unsafe { self.ptr.as_ptr().sub(`1`) }
520	}
521	}
522
523	/// Create a new [`Bucket`] that is offset from the `self` by the given
524	/// `offset`. The pointer calculation is performed by calculating the
525	/// offset from `self` pointer (convenience for `self.ptr.as_ptr().sub(offset)`).
526	/// This function is used for iterators.
527	///
528	/// `offset` is in units of `T`; e.g., a `offset` of 3 represents a pointer
529	/// offset of `3 size_of::<T>()` bytes.*
530	///
531	/// # Safety
532	///
533	/// If `mem::size_of::<T>() != 0`, then the safety rules are directly derived
534	/// from the safety rules for [`<mut T>::sub`] method of `mut T` and safety
535	/// rules of [`NonNull::new_unchecked`] function.
536	///
537	/// Thus, in order to uphold the safety contracts for [`<mut T>::sub`] method*
538	/// and [`NonNull::new_unchecked`] function, as well as for the correct
539	/// logic of the work of this crate, the following rules are necessary and
540	/// sufficient:
541	///
542	/// `self` contained pointer must not be `dangling`;*
543	///
544	/// `self.to_base_index() + ofset` must not be greater than `RawTableInner.bucket_mask`,*
545	/// i.e. `(self.to_base_index() + ofset) <= RawTableInner.bucket_mask` or, in other
546	/// words, `self.to_base_index() + ofset + 1` must be no greater than the number returned
547	/// by the function [`RawTable::buckets`] or [`RawTableInner::buckets`].
548	///
549	/// If `mem::size_of::<T>() == 0`, then the only requirement is that the
550	/// `self.to_base_index() + ofset` must not be greater than `RawTableInner.bucket_mask`,
551	/// i.e. `(self.to_base_index() + ofset) <= RawTableInner.bucket_mask` or, in other words,
552	/// `self.to_base_index() + ofset + 1` must be no greater than the number returned by the
553	/// function [`RawTable::buckets`] or [`RawTableInner::buckets`].
554	///
555	/// [`Bucket`]: crate::raw::Bucket
556	/// [`<mut T>::sub`]: https://doc.rust-lang.org/core/primitive.pointer.html#method.sub-1*
557	/// [`NonNull::new_unchecked`]: https://doc.rust-lang.org/stable/std/ptr/struct.NonNull.html#method.new_unchecked
558	/// [`RawTable::buckets`]: crate::raw::RawTable::buckets
559	/// [`RawTableInner::buckets`]: RawTableInner::buckets
560	#[inline]
561	unsafe fn next_n(&self, offset: usize) -> Self {
562	let ptr = if T::IS_ZERO_SIZED {
563	// invalid pointer is good enough for ZST
564	invalid_mut(self.ptr.as_ptr() as usize + offset)
565	} else {
566	self.ptr.as_ptr().sub(offset)
567	};
568	Self {
569	ptr: NonNull::new_unchecked(ptr),
570	}
571	}
572
573	/// Executes the destructor (if any) of the pointed-to `data`.
574	///
575	/// # Safety
576	///
577	/// See [`ptr::drop_in_place`] for safety concerns.
578	///
579	/// You should use [`RawTable::erase`] instead of this function,
580	/// or be careful with calling this function directly, because for
581	/// properly dropping the data we need also clear `data` control bytes.
582	/// If we drop data, but do not erase `data control byte` it leads to
583	/// double drop when [`RawTable`] goes out of scope.
584	///
585	/// [`ptr::drop_in_place`]: https://doc.rust-lang.org/core/ptr/fn.drop_in_place.html
586	/// [`RawTable`]: crate::raw::RawTable
587	/// [`RawTable::erase`]: crate::raw::RawTable::erase
588	#[cfg_attr(feature = "inline-more", inline)]
589	pub(crate) unsafe fn drop(&self) {
590	self.as_ptr().drop_in_place();
591	}
592
593	/// Reads the `value` from `self` without moving it. This leaves the
594	/// memory in `self` unchanged.
595	///
596	/// # Safety
597	///
598	/// See [`ptr::read`] for safety concerns.
599	///
600	/// You should use [`RawTable::remove`] instead of this function,
601	/// or be careful with calling this function directly, because compiler
602	/// calls its destructor when readed `value` goes out of scope. It
603	/// can cause double dropping when [`RawTable`] goes out of scope,
604	/// because of not erased `data control byte`.
605	///
606	/// [`ptr::read`]: https://doc.rust-lang.org/core/ptr/fn.read.html
607	/// [`RawTable`]: crate::raw::RawTable
608	/// [`RawTable::remove`]: crate::raw::RawTable::remove
609	#[inline]
610	pub(crate) unsafe fn read(&self) -> T {
611	self.as_ptr().read()
612	}
613
614	/// Overwrites a memory location with the given `value` without reading
615	/// or dropping the old value (like [`ptr::write`] function).
616	///
617	/// # Safety
618	///
619	/// See [`ptr::write`] for safety concerns.
620	///
621	/// # Note
622	///
623	/// [`Hash`] and [`Eq`] on the new `T` value and its borrowed form must* match*
624	/// those for the old `T` value, as the map will not re-evaluate where the new
625	/// value should go, meaning the value may become "lost" if their location
626	/// does not reflect their state.
627	///
628	/// [`ptr::write`]: https://doc.rust-lang.org/core/ptr/fn.write.html
629	/// [`Hash`]: https://doc.rust-lang.org/core/hash/trait.Hash.html
630	/// [`Eq`]: https://doc.rust-lang.org/core/cmp/trait.Eq.html
631	#[inline]
632	pub(crate) unsafe fn write(&self, val: T) {
633	self.as_ptr().write(val);
634	}
635
636	/// Returns a shared immutable reference to the `value`.
637	///
638	/// # Safety
639	///
640	/// See [`NonNull::as_ref`] for safety concerns.
641	///
642	/// [`NonNull::as_ref`]: https://doc.rust-lang.org/core/ptr/struct.NonNull.html#method.as_ref
643	///
644	/// # Examples
645	///
646	/// ```
647	/// # #[cfg(feature = "raw")]
648	/// # fn test() {
649	/// use core::hash::{BuildHasher, Hash};
650	/// use hashbrown::raw::{Bucket, RawTable};
651	///
652	/// type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;
653	///
654	/// fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
655	/// use core::hash::Hasher;
656	/// let mut state = hash_builder.build_hasher();
657	/// key.hash(&mut state);
658	/// state.finish()
659	/// }
660	///
661	/// let hash_builder = NewHashBuilder::default();
662	/// let mut table = RawTable::new();
663	///
664	/// let value: (&str, String) = ("A pony", "is a small horse".to_owned());
665	/// let hash = make_hash(&hash_builder, &value.0);
666	///
667	/// table.insert(hash, value.clone(), \|val\| make_hash(&hash_builder, &val.0));
668	///
669	/// let bucket: Bucket<(&str, String)> = table.find(hash, \|(k, _)\| k == &value.0).unwrap();
670	///
671	/// assert_eq!(
672	/// unsafe { bucket.as_ref() },
673	/// &("A pony", "is a small horse".to_owned())
674	/// );
675	/// # }
676	/// # fn main() {
677	/// # #[cfg(feature = "raw")]
678	/// # test()
679	/// # }
680	/// ```
681	#[inline]
682	pub unsafe fn as_ref<'a>(&self) -> &'a T {
683	&*self.as_ptr()
684	}
685
686	/// Returns a unique mutable reference to the `value`.
687	///
688	/// # Safety
689	///
690	/// See [`NonNull::as_mut`] for safety concerns.
691	///
692	/// # Note
693	///
694	/// [`Hash`] and [`Eq`] on the new `T` value and its borrowed form must* match*
695	/// those for the old `T` value, as the map will not re-evaluate where the new
696	/// value should go, meaning the value may become "lost" if their location
697	/// does not reflect their state.
698	///
699	/// [`NonNull::as_mut`]: https://doc.rust-lang.org/core/ptr/struct.NonNull.html#method.as_mut
700	/// [`Hash`]: https://doc.rust-lang.org/core/hash/trait.Hash.html
701	/// [`Eq`]: https://doc.rust-lang.org/core/cmp/trait.Eq.html
702	///
703	/// # Examples
704	///
705	/// ```
706	/// # #[cfg(feature = "raw")]
707	/// # fn test() {
708	/// use core::hash::{BuildHasher, Hash};
709	/// use hashbrown::raw::{Bucket, RawTable};
710	///
711	/// type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;
712	///
713	/// fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
714	/// use core::hash::Hasher;
715	/// let mut state = hash_builder.build_hasher();
716	/// key.hash(&mut state);
717	/// state.finish()
718	/// }
719	///
720	/// let hash_builder = NewHashBuilder::default();
721	/// let mut table = RawTable::new();
722	///
723	/// let value: (&str, String) = ("A pony", "is a small horse".to_owned());
724	/// let hash = make_hash(&hash_builder, &value.0);
725	///
726	/// table.insert(hash, value.clone(), \|val\| make_hash(&hash_builder, &val.0));
727	///
728	/// let bucket: Bucket<(&str, String)> = table.find(hash, \|(k, _)\| k == &value.0).unwrap();
729	///
730	/// unsafe {
731	/// bucket
732	/// .as_mut()
733	/// .1
734	/// .push_str(" less than 147 cm at the withers")
735	/// };
736	/// assert_eq!(
737	/// unsafe { bucket.as_ref() },
738	/// &(
739	/// "A pony",
740	/// "is a small horse less than 147 cm at the withers".to_owned()
741	/// )
742	/// );
743	/// # }
744	/// # fn main() {
745	/// # #[cfg(feature = "raw")]
746	/// # test()
747	/// # }
748	/// ```
749	#[inline]
750	pub unsafe fn as_mut<'a>(&self) -> &'a mut T {
751	&mut *self.as_ptr()
752	}
753
754	/// Copies `size_of<T>` bytes from `other` to `self`. The source
755	/// and destination may not* overlap.*
756	///
757	/// # Safety
758	///
759	/// See [`ptr::copy_nonoverlapping`] for safety concerns.
760	///
761	/// Like [`read`], `copy_nonoverlapping` creates a bitwise copy of `T`, regardless of
762	/// whether `T` is [`Copy`]. If `T` is not [`Copy`], using both* the values*
763	/// in the region beginning at `self` and the region beginning at `other` can
764	/// [violate memory safety].
765	///
766	/// # Note
767	///
768	/// [`Hash`] and [`Eq`] on the new `T` value and its borrowed form must* match*
769	/// those for the old `T` value, as the map will not re-evaluate where the new
770	/// value should go, meaning the value may become "lost" if their location
771	/// does not reflect their state.
772	///
773	/// [`ptr::copy_nonoverlapping`]: https://doc.rust-lang.org/core/ptr/fn.copy_nonoverlapping.html
774	/// [`read`]: https://doc.rust-lang.org/core/ptr/fn.read.html
775	/// [violate memory safety]: https://doc.rust-lang.org/std/ptr/fn.read.html#ownership-of-the-returned-value
776	/// [`Hash`]: https://doc.rust-lang.org/core/hash/trait.Hash.html
777	/// [`Eq`]: https://doc.rust-lang.org/core/cmp/trait.Eq.html
778	#[cfg(feature = "raw")]
779	#[inline]
780	pub unsafe fn copy_from_nonoverlapping(&self, other: &Self) {
781	self.as_ptr().copy_from_nonoverlapping(other.as_ptr(), `1`);
782	}
783	}
784
785	/// A raw hash table with an unsafe API.
786	pub struct RawTable<T, A: Allocator = Global> {
787	table: RawTableInner,
788	alloc: A,
789	// Tell dropck that we own instances of T.
790	marker: PhantomData<T>,
791	}
792
793	/// Non-generic part of `RawTable` which allows functions to be instantiated only once regardless
794	/// of how many different key-value types are used.
795	struct RawTableInner {
796	// Mask to get an index from a hash value. The value is one less than the
797	// number of buckets in the table.
798	bucket_mask: usize,
799
800	// [Padding], T1, T2, ..., Tlast, C1, C2, ...
801	// ^ points here
802	ctrl: NonNull<u8>,
803
804	// Number of elements that can be inserted before we need to grow the table
805	growth_left: usize,
806
807	// Number of elements in the table, only really used by len()
808	items: usize,
809	}
810
811	impl<T> RawTable<T, Global> {
812	/// Creates a new empty hash table without allocating any memory.
813	///
814	/// In effect this returns a table with exactly 1 bucket. However we can
815	/// leave the data pointer dangling since that bucket is never written to
816	/// due to our load factor forcing us to always have at least 1 free bucket.
817	#[inline]
818	pub const fn new() -> Self {
819	Self {
820	table: RawTableInner::NEW,
821	alloc: Global,
822	marker: PhantomData,
823	}
824	}
825
826	/// Attempts to allocate a new hash table with at least enough capacity
827	/// for inserting the given number of elements without reallocating.
828	#[cfg(feature = "raw")]
829	pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
830	Self::try_with_capacity_in(capacity, Global)
831	}
832
833	/// Allocates a new hash table with at least enough capacity for inserting
834	/// the given number of elements without reallocating.
835	pub fn with_capacity(capacity: usize) -> Self {
836	Self::with_capacity_in(capacity, Global)
837	}
838	}
839
840	impl<T, A: Allocator> RawTable<T, A> {
841	const TABLE_LAYOUT: TableLayout = TableLayout::new::<T>();
842
843	/// Creates a new empty hash table without allocating any memory, using the
844	/// given allocator.
845	///
846	/// In effect this returns a table with exactly 1 bucket. However we can
847	/// leave the data pointer dangling since that bucket is never written to
848	/// due to our load factor forcing us to always have at least 1 free bucket.
849	#[inline]
850	pub const fn new_in(alloc: A) -> Self {
851	Self {
852	table: RawTableInner::NEW,
853	alloc,
854	marker: PhantomData,
855	}
856	}
857
858	/// Allocates a new hash table with the given number of buckets.
859	///
860	/// The control bytes are left uninitialized.
861	#[cfg_attr(feature = "inline-more", inline)]
862	unsafe fn new_uninitialized(
863	alloc: A,
864	buckets: usize,
865	fallibility: Fallibility,
866	) -> Result<Self, TryReserveError> {
867	debug_assert!(buckets.is_power_of_two());
868
869	Ok(Self {
870	table: RawTableInner::new_uninitialized(
871	&alloc,
872	Self::TABLE_LAYOUT,
873	buckets,
874	fallibility,
875	)?,
876	alloc,
877	marker: PhantomData,
878	})
879	}
880
881	/// Attempts to allocate a new hash table using the given allocator, with at least enough
882	/// capacity for inserting the given number of elements without reallocating.
883	#[cfg(feature = "raw")]
884	pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
885	Ok(Self {
886	table: RawTableInner::fallible_with_capacity(
887	&alloc,
888	Self::TABLE_LAYOUT,
889	capacity,
890	Fallibility::Fallible,
891	)?,
892	alloc,
893	marker: PhantomData,
894	})
895	}
896
897	/// Allocates a new hash table using the given allocator, with at least enough capacity for
898	/// inserting the given number of elements without reallocating.
899	pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
900	Self {
901	table: RawTableInner::with_capacity(&alloc, Self::TABLE_LAYOUT, capacity),
902	alloc,
903	marker: PhantomData,
904	}
905	}
906
907	/// Returns a reference to the underlying allocator.
908	#[inline]
909	pub fn allocator(&self) -> &A {
910	&self.alloc
911	}
912
913	/// Returns pointer to one past last `data` element in the the table as viewed from
914	/// the start point of the allocation.
915	///
916	/// The caller must ensure that the `RawTable` outlives the returned [`NonNull<T>`],
917	/// otherwise using it may result in [`undefined behavior`].
918	///
919	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
920	#[inline]
921	pub fn data_end(&self) -> NonNull<T> {
922	// SAFETY: `self.table.ctrl` is `NonNull`, so casting it is safe
923	//
924	// `self.table.ctrl.as_ptr().cast()` returns pointer that
925	// points here (to the end of `T0`)
926	// ∨
927	// [Pad], T_n, ..., T1, T0, \|CT0, CT1, ..., CT_n\|, CTa_0, CTa_1, ..., CTa_m
928	// \________ ________/
929	// \/
930	// `n = buckets - 1`, i.e. `RawTable::buckets() - 1`
931	//
932	// where: T0...T_n - our stored data;
933	// CT0...CT_n - control bytes or metadata for `data`.
934	// CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
935	// with loading `Group` bytes from the heap works properly, even if the result
936	// of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
937	// `RawTableInner::set_ctrl` function.
938	//
939	// P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
940	// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
941	unsafe { NonNull::new_unchecked(self.table.ctrl.as_ptr().cast()) }
942	}
943
944	/// Returns pointer to start of data table.
945	#[inline]
946	#[cfg(any(feature = "raw", feature = "nightly"))]
947	pub unsafe fn data_start(&self) -> NonNull<T> {
948	NonNull::new_unchecked(self.data_end().as_ptr().wrapping_sub(self.buckets()))
949	}
950
951	/// Return the information about memory allocated by the table.
952	///
953	/// `RawTable` allocates single memory block to store both data and metadata.
954	/// This function returns allocation size and alignment and the beginning of the area.
955	/// These are the arguments which will be passed to `dealloc` when the table is dropped.
956	///
957	/// This function might be useful for memory profiling.
958	#[inline]
959	#[cfg(feature = "raw")]
960	pub fn allocation_info(&self) -> (NonNull<u8>, Layout) {
961	// SAFETY: We use the same `table_layout` that was used to allocate
962	// this table.
963	unsafe { self.table.allocation_info_or_zero(Self::TABLE_LAYOUT) }
964	}
965
966	/// Returns the index of a bucket from a `Bucket`.
967	#[inline]
968	pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize {
969	bucket.to_base_index(self.data_end())
970	}
971
972	/// Returns a pointer to an element in the table.
973	///
974	/// The caller must ensure that the `RawTable` outlives the returned [`Bucket<T>`],
975	/// otherwise using it may result in [`undefined behavior`].
976	///
977	/// # Safety
978	///
979	/// If `mem::size_of::<T>() != 0`, then the caller of this function must observe the
980	/// following safety rules:
981	///
982	/// The table must already be allocated;*
983	///
984	/// The `index` must not be greater than the number returned by the* [`RawTable::buckets`]
985	/// function, i.e. `(index + 1) <= self.buckets()`.
986	///
987	/// It is safe to call this function with index of zero (`index == 0`) on a table that has
988	/// not been allocated, but using the returned [`Bucket`] results in [`undefined behavior`].
989	///
990	/// If `mem::size_of::<T>() == 0`, then the only requirement is that the `index` must
991	/// not be greater than the number returned by the [`RawTable::buckets`] function, i.e.
992	/// `(index + 1) <= self.buckets()`.
993	///
994	/// [`RawTable::buckets`]: RawTable::buckets
995	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
996	#[inline]
997	pub unsafe fn bucket(&self, index: usize) -> Bucket<T> {
998	// If mem::size_of::<T>() != 0 then return a pointer to the `element` in the `data part` of the table
999	// (we start counting from "0", so that in the expression T[n], the "n" index actually one less than
1000	// the "buckets" number of our `RawTable`, i.e. "n = RawTable::buckets() - 1"):
1001	//
1002	// `table.bucket(3).as_ptr()` returns a pointer that points here in the `data`
1003	// part of the `RawTable`, i.e. to the start of T3 (see `Bucket::as_ptr`)
1004	// \|
1005	// \| `base = self.data_end()` points here
1006	// \| (to the start of CT0 or to the end of T0)
1007	// v v
1008	// [Pad], T_n, ..., \|T3\|, T2, T1, T0, \|CT0, CT1, CT2, CT3, ..., CT_n, CTa_0, CTa_1, ..., CTa_m
1009	// ^ \__________ __________/
1010	// `table.bucket(3)` returns a pointer that points \/
1011	// here in the `data` part of the `RawTable` (to additional control bytes
1012	// the end of T3) `m = Group::WIDTH - 1`
1013	//
1014	// where: T0...T_n - our stored data;
1015	// CT0...CT_n - control bytes or metadata for `data`;
1016	// CTa_0...CTa_m - additional control bytes (so that the search with loading `Group` bytes from
1017	// the heap works properly, even if the result of `h1(hash) & self.table.bucket_mask`
1018	// is equal to `self.table.bucket_mask`). See also `RawTableInner::set_ctrl` function.
1019	//
1020	// P.S. `h1(hash) & self.table.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
1021	// of buckets is a power of two, and `self.table.bucket_mask = self.buckets() - 1`.
1022	debug_assert_ne!(self.table.bucket_mask, `0`);
1023	debug_assert!(index < self.buckets());
1024	Bucket::from_base_index(self.data_end(), index)
1025	}
1026
1027	/// Erases an element from the table without dropping it.
1028	#[cfg_attr(feature = "inline-more", inline)]
1029	unsafe fn erase_no_drop(&mut self, item: &Bucket<T>) {
1030	let index = self.bucket_index(item);
1031	self.table.erase(index);
1032	}
1033
1034	/// Erases an element from the table, dropping it in place.
1035	#[cfg_attr(feature = "inline-more", inline)]
1036	#[allow(clippy::needless_pass_by_value)]
1037	pub unsafe fn erase(&mut self, item: Bucket<T>) {
1038	// Erase the element from the table first since drop might panic.
1039	self.erase_no_drop(&item);
1040	item.drop();
1041	}
1042
1043	/// Finds and erases an element from the table, dropping it in place.
1044	/// Returns true if an element was found.
1045	#[cfg(feature = "raw")]
1046	#[cfg_attr(feature = "inline-more", inline)]
1047	pub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool {
1048	// Avoid `Option::map` because it bloats LLVM IR.
1049	if let Some(bucket) = self.find(hash, eq) {
1050	unsafe {
1051	self.erase(bucket);
1052	}
1053	`true`
1054	} else {
1055	`false`
1056	}
1057	}
1058
1059	/// Removes an element from the table, returning it.
1060	///
1061	/// This also returns an `InsertSlot` pointing to the newly free bucket.
1062	#[cfg_attr(feature = "inline-more", inline)]
1063	#[allow(clippy::needless_pass_by_value)]
1064	pub unsafe fn remove(&mut self, item: Bucket<T>) -> (T, InsertSlot) {
1065	self.erase_no_drop(&item);
1066	(
1067	item.read(),
1068	InsertSlot {
1069	index: self.bucket_index(&item),
1070	},
1071	)
1072	}
1073
1074	/// Finds and removes an element from the table, returning it.
1075	#[cfg_attr(feature = "inline-more", inline)]
1076	pub fn remove_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<T> {
1077	// Avoid `Option::map` because it bloats LLVM IR.
1078	match self.find(hash, eq) {
1079	Some(bucket) => Some(unsafe { self.remove(bucket).0 }),
1080	None => None,
1081	}
1082	}
1083
1084	/// Marks all table buckets as empty without dropping their contents.
1085	#[cfg_attr(feature = "inline-more", inline)]
1086	pub fn clear_no_drop(&mut self) {
1087	self.table.clear_no_drop();
1088	}
1089
1090	/// Removes all elements from the table without freeing the backing memory.
1091	#[cfg_attr(feature = "inline-more", inline)]
1092	pub fn clear(&mut self) {
1093	if self.is_empty() {
1094	// Special case empty table to avoid surprising O(capacity) time.
1095	return;
1096	}
1097	// Ensure that the table is reset even if one of the drops panic
1098	let mut self_ = guard(self, \|self_\| self_.clear_no_drop());
1099	unsafe {
1100	// SAFETY: ScopeGuard sets to zero the `items` field of the table
1101	// even in case of panic during the dropping of the elements so
1102	// that there will be no double drop of the elements.
1103	self_.table.drop_elements::<T>();
1104	}
1105	}
1106
1107	/// Shrinks the table to fit `max(self.len(), min_size)` elements.
1108	#[cfg_attr(feature = "inline-more", inline)]
1109	pub fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64) {
1110	// Calculate the minimal number of elements that we need to reserve
1111	// space for.
1112	let min_size = usize::max(self.table.items, min_size);
1113	if min_size == `0` {
1114	let mut old_inner = mem::replace(&mut self.table, RawTableInner::NEW);
1115	unsafe {
1116	// SAFETY:
1117	// 1. We call the function only once;
1118	// 2. We know for sure that `alloc` and `table_layout` matches the [`Allocator`]
1119	// and [`TableLayout`] that were used to allocate this table.
1120	// 3. If any elements' drop function panics, then there will only be a memory leak,
1121	// because we have replaced the inner table with a new one.
1122	old_inner.drop_inner_table::<T, _>(&self.alloc, Self::TABLE_LAYOUT);
1123	}
1124	return;
1125	}
1126
1127	// Calculate the number of buckets that we need for this number of
1128	// elements. If the calculation overflows then the requested bucket
1129	// count must be larger than what we have right and nothing needs to be
1130	// done.
1131	let min_buckets = match capacity_to_buckets(min_size) {
1132	Some(buckets) => buckets,
1133	None => return,
1134	};
1135
1136	// If we have more buckets than we need, shrink the table.
1137	if min_buckets < self.buckets() {
1138	// Fast path if the table is empty
1139	if self.table.items == `0` {
1140	let new_inner =
1141	RawTableInner::with_capacity(&self.alloc, Self::TABLE_LAYOUT, min_size);
1142	let mut old_inner = mem::replace(&mut self.table, new_inner);
1143	unsafe {
1144	// SAFETY:
1145	// 1. We call the function only once;
1146	// 2. We know for sure that `alloc` and `table_layout` matches the [`Allocator`]
1147	// and [`TableLayout`] that were used to allocate this table.
1148	// 3. If any elements' drop function panics, then there will only be a memory leak,
1149	// because we have replaced the inner table with a new one.
1150	old_inner.drop_inner_table::<T, _>(&self.alloc, Self::TABLE_LAYOUT);
1151	}
1152	} else {
1153	// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
1154	unsafe {
1155	// SAFETY:
1156	// 1. We know for sure that `min_size >= self.table.items`.
1157	// 2. The [`RawTableInner`] must already have properly initialized control bytes since
1158	// we will never expose RawTable::new_uninitialized in a public API.
1159	if self
1160	.resize(min_size, hasher, Fallibility::Infallible)
1161	.is_err()
1162	{
1163	// SAFETY: The result of calling the `resize` function cannot be an error
1164	// because `fallibility == Fallibility::Infallible.
1165	hint::unreachable_unchecked()
1166	}
1167	}
1168	}
1169	}
1170	}
1171
1172	/// Ensures that at least `additional` items can be inserted into the table
1173	/// without reallocation.
1174	#[cfg_attr(feature = "inline-more", inline)]
1175	pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) {
1176	if unlikely(additional > self.table.growth_left) {
1177	// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
1178	unsafe {
1179	// SAFETY: The [`RawTableInner`] must already have properly initialized control
1180	// bytes since we will never expose RawTable::new_uninitialized in a public API.
1181	if self
1182	.reserve_rehash(additional, hasher, Fallibility::Infallible)
1183	.is_err()
1184	{
1185	// SAFETY: All allocation errors will be caught inside `RawTableInner::reserve_rehash`.
1186	hint::unreachable_unchecked()
1187	}
1188	}
1189	}
1190	}
1191
1192	/// Tries to ensure that at least `additional` items can be inserted into
1193	/// the table without reallocation.
1194	#[cfg_attr(feature = "inline-more", inline)]
1195	pub fn try_reserve(
1196	&mut self,
1197	additional: usize,
1198	hasher: impl Fn(&T) -> u64,
1199	) -> Result<(), TryReserveError> {
1200	if additional > self.table.growth_left {
1201	// SAFETY: The [`RawTableInner`] must already have properly initialized control
1202	// bytes since we will never expose RawTable::new_uninitialized in a public API.
1203	unsafe { self.reserve_rehash(additional, hasher, Fallibility::Fallible) }
1204	} else {
1205	Ok(())
1206	}
1207	}
1208
1209	/// Out-of-line slow path for `reserve` and `try_reserve`.
1210	///
1211	/// # Safety
1212	///
1213	/// The [`RawTableInner`] must have properly initialized control bytes,
1214	/// otherwise calling this function results in [`undefined behavior`]
1215	///
1216	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1217	#[cold]
1218	#[inline(never)]
1219	unsafe fn reserve_rehash(
1220	&mut self,
1221	additional: usize,
1222	hasher: impl Fn(&T) -> u64,
1223	fallibility: Fallibility,
1224	) -> Result<(), TryReserveError> {
1225	unsafe {
1226	// SAFETY:
1227	// 1. We know for sure that `alloc` and `layout` matches the [`Allocator`] and
1228	// [`TableLayout`] that were used to allocate this table.
1229	// 2. The `drop` function is the actual drop function of the elements stored in
1230	// the table.
1231	// 3. The caller ensures that the control bytes of the `RawTableInner`
1232	// are already initialized.
1233	self.table.reserve_rehash_inner(
1234	&self.alloc,
1235	additional,
1236	&\|table, index\| hasher(table.bucket::<T>(index).as_ref()),
1237	fallibility,
1238	Self::TABLE_LAYOUT,
1239	if T::NEEDS_DROP {
1240	Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
1241	} else {
1242	None
1243	},
1244	)
1245	}
1246	}
1247
1248	/// Allocates a new table of a different size and moves the contents of the
1249	/// current table into it.
1250	///
1251	/// # Safety
1252	///
1253	/// The [`RawTableInner`] must have properly initialized control bytes,
1254	/// otherwise calling this function results in [`undefined behavior`]
1255	///
1256	/// The caller of this function must ensure that `capacity >= self.table.items`
1257	/// otherwise:
1258	///
1259	/// If `self.table.items != 0`, calling of this function with `capacity`*
1260	/// equal to 0 (`capacity == 0`) results in [`undefined behavior`].
1261	///
1262	/// If `capacity_to_buckets(capacity) < Group::WIDTH` and*
1263	/// `self.table.items > capacity_to_buckets(capacity)`
1264	/// calling this function results in [`undefined behavior`].
1265	///
1266	/// If `capacity_to_buckets(capacity) >= Group::WIDTH` and*
1267	/// `self.table.items > capacity_to_buckets(capacity)`
1268	/// calling this function are never return (will go into an
1269	/// infinite loop).
1270	///
1271	/// See [`RawTableInner::find_insert_slot`] for more information.
1272	///
1273	/// [`RawTableInner::find_insert_slot`]: RawTableInner::find_insert_slot
1274	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1275	unsafe fn resize(
1276	&mut self,
1277	capacity: usize,
1278	hasher: impl Fn(&T) -> u64,
1279	fallibility: Fallibility,
1280	) -> Result<(), TryReserveError> {
1281	// SAFETY:
1282	// 1. The caller of this function guarantees that `capacity >= self.table.items`.
1283	// 2. We know for sure that `alloc` and `layout` matches the [`Allocator`] and
1284	// [`TableLayout`] that were used to allocate this table.
1285	// 3. The caller ensures that the control bytes of the `RawTableInner`
1286	// are already initialized.
1287	self.table.resize_inner(
1288	&self.alloc,
1289	capacity,
1290	&\|table, index\| hasher(table.bucket::<T>(index).as_ref()),
1291	fallibility,
1292	Self::TABLE_LAYOUT,
1293	)
1294	}
1295
1296	/// Inserts a new element into the table, and returns its raw bucket.
1297	///
1298	/// This does not check if the given element already exists in the table.
1299	#[cfg_attr(feature = "inline-more", inline)]
1300	pub fn insert(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> Bucket<T> {
1301	unsafe {
1302	// SAFETY:
1303	// 1. The [`RawTableInner`] must already have properly initialized control bytes since
1304	// we will never expose `RawTable::new_uninitialized` in a public API.
1305	//
1306	// 2. We reserve additional space (if necessary) right after calling this function.
1307	let mut slot = self.table.find_insert_slot(hash);
1308
1309	// We can avoid growing the table once we have reached our load factor if we are replacing
1310	// a tombstone. This works since the number of EMPTY slots does not change in this case.
1311	//
1312	// SAFETY: The function is guaranteed to return [`InsertSlot`] that contains an index
1313	// in the range `0..=self.buckets()`.
1314	let old_ctrl = *self.table.ctrl(slot.index);
1315	if unlikely(self.table.growth_left == `0` && special_is_empty(old_ctrl)) {
1316	self.reserve(`1`, hasher);
1317	// SAFETY: We know for sure that `RawTableInner` has control bytes
1318	// initialized and that there is extra space in the table.
1319	slot = self.table.find_insert_slot(hash);
1320	}
1321
1322	self.insert_in_slot(hash, slot, value)
1323	}
1324	}
1325
1326	/// Attempts to insert a new element without growing the table and return its raw bucket.
1327	///
1328	/// Returns an `Err` containing the given element if inserting it would require growing the
1329	/// table.
1330	///
1331	/// This does not check if the given element already exists in the table.
1332	#[cfg(feature = "raw")]
1333	#[cfg_attr(feature = "inline-more", inline)]
1334	pub fn try_insert_no_grow(&mut self, hash: u64, value: T) -> Result<Bucket<T>, T> {
1335	unsafe {
1336	match self.table.prepare_insert_no_grow(hash) {
1337	Ok(index) => {
1338	let bucket = self.bucket(index);
1339	bucket.write(value);
1340	Ok(bucket)
1341	}
1342	Err(()) => Err(value),
1343	}
1344	}
1345	}
1346
1347	/// Inserts a new element into the table, and returns a mutable reference to it.
1348	///
1349	/// This does not check if the given element already exists in the table.
1350	#[cfg_attr(feature = "inline-more", inline)]
1351	pub fn insert_entry(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> &mut T {
1352	unsafe { self.insert(hash, value, hasher).as_mut() }
1353	}
1354
1355	/// Inserts a new element into the table, without growing the table.
1356	///
1357	/// There must be enough space in the table to insert the new element.
1358	///
1359	/// This does not check if the given element already exists in the table.
1360	#[cfg_attr(feature = "inline-more", inline)]
1361	#[cfg(any(feature = "raw", feature = "rustc-internal-api"))]
1362	pub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
1363	let (index, old_ctrl) = self.table.prepare_insert_slot(hash);
1364	let bucket = self.table.bucket(index);
1365
1366	// If we are replacing a DELETED entry then we don't need to update
1367	// the load counter.
1368	self.table.growth_left -= special_is_empty(old_ctrl) as usize;
1369
1370	bucket.write(value);
1371	self.table.items += `1`;
1372	bucket
1373	}
1374
1375	/// Temporary removes a bucket, applying the given function to the removed
1376	/// element and optionally put back the returned value in the same bucket.
1377	///
1378	/// Returns `true` if the bucket still contains an element
1379	///
1380	/// This does not check if the given bucket is actually occupied.
1381	#[cfg_attr(feature = "inline-more", inline)]
1382	pub unsafe fn replace_bucket_with<F>(&mut self, bucket: Bucket<T>, f: F) -> bool
1383	where
1384	F: FnOnce(T) -> Option<T>,
1385	{
1386	let index = self.bucket_index(&bucket);
1387	let old_ctrl = *self.table.ctrl(index);
1388	debug_assert!(self.is_bucket_full(index));
1389	let old_growth_left = self.table.growth_left;
1390	let item = self.remove(bucket).0;
1391	if let Some(new_item) = f(item) {
1392	self.table.growth_left = old_growth_left;
1393	self.table.set_ctrl(index, old_ctrl);
1394	self.table.items += `1`;
1395	self.bucket(index).write(new_item);
1396	`true`
1397	} else {
1398	`false`
1399	}
1400	}
1401
1402	/// Searches for an element in the table. If the element is not found,
1403	/// returns `Err` with the position of a slot where an element with the
1404	/// same hash could be inserted.
1405	///
1406	/// This function may resize the table if additional space is required for
1407	/// inserting an element.
1408	#[inline]
1409	pub fn find_or_find_insert_slot(
1410	&mut self,
1411	hash: u64,
1412	mut eq: impl FnMut(&T) -> bool,
1413	hasher: impl Fn(&T) -> u64,
1414	) -> Result<Bucket<T>, InsertSlot> {
1415	self.reserve(`1`, hasher);
1416
1417	unsafe {
1418	// SAFETY:
1419	// 1. We know for sure that there is at least one empty `bucket` in the table.
1420	// 2. The [`RawTableInner`] must already have properly initialized control bytes since we will
1421	// never expose `RawTable::new_uninitialized` in a public API.
1422	// 3. The `find_or_find_insert_slot_inner` function returns the `index` of only the full bucket,
1423	// which is in the range `0..self.buckets()` (since there is at least one empty `bucket` in
1424	// the table), so calling `self.bucket(index)` and `Bucket::as_ref` is safe.
1425	match self
1426	.table
1427	.find_or_find_insert_slot_inner(hash, &mut \|index\| eq(self.bucket(index).as_ref()))
1428	{
1429	// SAFETY: See explanation above.
1430	Ok(index) => Ok(self.bucket(index)),
1431	Err(slot) => Err(slot),
1432	}
1433	}
1434	}
1435
1436	/// Inserts a new element into the table in the given slot, and returns its
1437	/// raw bucket.
1438	///
1439	/// # Safety
1440	///
1441	/// `slot` must point to a slot previously returned by
1442	/// `find_or_find_insert_slot`, and no mutation of the table must have
1443	/// occurred since that call.
1444	#[inline]
1445	pub unsafe fn insert_in_slot(&mut self, hash: u64, slot: InsertSlot, value: T) -> Bucket<T> {
1446	let old_ctrl = *self.table.ctrl(slot.index);
1447	self.table.record_item_insert_at(slot.index, old_ctrl, hash);
1448
1449	let bucket = self.bucket(slot.index);
1450	bucket.write(value);
1451	bucket
1452	}
1453
1454	/// Searches for an element in the table.
1455	#[inline]
1456	pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
1457	unsafe {
1458	// SAFETY:
1459	// 1. The [`RawTableInner`] must already have properly initialized control bytes since we
1460	// will never expose `RawTable::new_uninitialized` in a public API.
1461	// 1. The `find_inner` function returns the `index` of only the full bucket, which is in
1462	// the range `0..self.buckets()`, so calling `self.bucket(index)` and `Bucket::as_ref`
1463	// is safe.
1464	let result = self
1465	.table
1466	.find_inner(hash, &mut \|index\| eq(self.bucket(index).as_ref()));
1467
1468	// Avoid `Option::map` because it bloats LLVM IR.
1469	match result {
1470	// SAFETY: See explanation above.
1471	Some(index) => Some(self.bucket(index)),
1472	None => None,
1473	}
1474	}
1475	}
1476
1477	/// Gets a reference to an element in the table.
1478	#[inline]
1479	pub fn get(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T> {
1480	// Avoid `Option::map` because it bloats LLVM IR.
1481	match self.find(hash, eq) {
1482	Some(bucket) => Some(unsafe { bucket.as_ref() }),
1483	None => None,
1484	}
1485	}
1486
1487	/// Gets a mutable reference to an element in the table.
1488	#[inline]
1489	pub fn get_mut(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&mut T> {
1490	// Avoid `Option::map` because it bloats LLVM IR.
1491	match self.find(hash, eq) {
1492	Some(bucket) => Some(unsafe { bucket.as_mut() }),
1493	None => None,
1494	}
1495	}
1496
1497	/// Attempts to get mutable references to `N` entries in the table at once.
1498	///
1499	/// Returns an array of length `N` with the results of each query.
1500	///
1501	/// At most one mutable reference will be returned to any entry. `None` will be returned if any
1502	/// of the hashes are duplicates. `None` will be returned if the hash is not found.
1503	///
1504	/// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to
1505	/// the `i`th key to be looked up.
1506	pub fn get_many_mut<const N: usize>(
1507	&mut self,
1508	hashes: [u64; N],
1509	eq: impl FnMut(usize, &T) -> bool,
1510	) -> Option<[&'_ mut T; N]> {
1511	unsafe {
1512	let ptrs = self.get_many_mut_pointers(hashes, eq)?;
1513
1514	for (i, &cur) in ptrs.iter().enumerate() {
1515	if ptrs[..i].iter().any(\|&prev\| ptr::eq::<T>(prev, cur)) {
1516	return None;
1517	}
1518	}
1519	// All bucket are distinct from all previous buckets so we're clear to return the result
1520	// of the lookup.
1521
1522	// TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
1523	Some(mem::transmute_copy(&ptrs))
1524	}
1525	}
1526
1527	pub unsafe fn get_many_unchecked_mut<const N: usize>(
1528	&mut self,
1529	hashes: [u64; N],
1530	eq: impl FnMut(usize, &T) -> bool,
1531	) -> Option<[&'_ mut T; N]> {
1532	let ptrs = self.get_many_mut_pointers(hashes, eq)?;
1533	Some(mem::transmute_copy(&ptrs))
1534	}
1535
1536	unsafe fn get_many_mut_pointers<const N: usize>(
1537	&mut self,
1538	hashes: [u64; N],
1539	mut eq: impl FnMut(usize, &T) -> bool,
1540	) -> Option<[*mut T; N]> {
1541	// TODO use `MaybeUninit::uninit_array` here instead once that's stable.
1542	let mut outs: MaybeUninit<[*mut T; N]> = MaybeUninit::uninit();
1543	let outs_ptr = outs.as_mut_ptr();
1544
1545	for (i, &hash) in hashes.iter().enumerate() {
1546	let cur = self.find(hash, \|k\| eq(i, k))?;
1547	(outs_ptr).get_unchecked_mut(i) = cur.as_mut();
1548	}
1549
1550	// TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
1551	Some(outs.assume_init())
1552	}
1553
1554	/// Returns the number of elements the map can hold without reallocating.
1555	///
1556	/// This number is a lower bound; the table might be able to hold
1557	/// more, but is guaranteed to be able to hold at least this many.
1558	#[inline]
1559	pub fn capacity(&self) -> usize {
1560	self.table.items + self.table.growth_left
1561	}
1562
1563	/// Returns the number of elements in the table.
1564	#[inline]
1565	pub fn len(&self) -> usize {
1566	self.table.items
1567	}
1568
1569	/// Returns `true` if the table contains no elements.
1570	#[inline]
1571	pub fn is_empty(&self) -> bool {
1572	self.len() == `0`
1573	}
1574
1575	/// Returns the number of buckets in the table.
1576	#[inline]
1577	pub fn buckets(&self) -> usize {
1578	self.table.bucket_mask + `1`
1579	}
1580
1581	/// Checks whether the bucket at `index` is full.
1582	///
1583	/// # Safety
1584	///
1585	/// The caller must ensure `index` is less than the number of buckets.
1586	#[inline]
1587	pub unsafe fn is_bucket_full(&self, index: usize) -> bool {
1588	self.table.is_bucket_full(index)
1589	}
1590
1591	/// Returns an iterator over every element in the table. It is up to
1592	/// the caller to ensure that the `RawTable` outlives the `RawIter`.
1593	/// Because we cannot make the `next` method unsafe on the `RawIter`
1594	/// struct, we have to make the `iter` method unsafe.
1595	#[inline]
1596	pub unsafe fn iter(&self) -> RawIter<T> {
1597	// SAFETY:
1598	// 1. The caller must uphold the safety contract for `iter` method.
1599	// 2. The [`RawTableInner`] must already have properly initialized control bytes since
1600	// we will never expose RawTable::new_uninitialized in a public API.
1601	self.table.iter()
1602	}
1603
1604	/// Returns an iterator over occupied buckets that could match a given hash.
1605	///
1606	/// `RawTable` only stores 7 bits of the hash value, so this iterator may
1607	/// return items that have a hash value different than the one provided. You
1608	/// should always validate the returned values before using them.
1609	///
1610	/// It is up to the caller to ensure that the `RawTable` outlives the
1611	/// `RawIterHash`. Because we cannot make the `next` method unsafe on the
1612	/// `RawIterHash` struct, we have to make the `iter_hash` method unsafe.
1613	#[cfg_attr(feature = "inline-more", inline)]
1614	#[cfg(feature = "raw")]
1615	pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<T> {
1616	RawIterHash::new(self, hash)
1617	}
1618
1619	/// Returns an iterator which removes all elements from the table without
1620	/// freeing the memory.
1621	#[cfg_attr(feature = "inline-more", inline)]
1622	pub fn drain(&mut self) -> RawDrain<'_, T, A> {
1623	unsafe {
1624	let iter = self.iter();
1625	self.drain_iter_from(iter)
1626	}
1627	}
1628
1629	/// Returns an iterator which removes all elements from the table without
1630	/// freeing the memory.
1631	///
1632	/// Iteration starts at the provided iterator's current location.
1633	///
1634	/// It is up to the caller to ensure that the iterator is valid for this
1635	/// `RawTable` and covers all items that remain in the table.
1636	#[cfg_attr(feature = "inline-more", inline)]
1637	pub unsafe fn drain_iter_from(&mut self, iter: RawIter<T>) -> RawDrain<'_, T, A> {
1638	debug_assert_eq!(iter.len(), self.len());
1639	RawDrain {
1640	iter,
1641	table: mem::replace(&mut self.table, RawTableInner::NEW),
1642	orig_table: NonNull::from(&mut self.table),
1643	marker: PhantomData,
1644	}
1645	}
1646
1647	/// Returns an iterator which consumes all elements from the table.
1648	///
1649	/// Iteration starts at the provided iterator's current location.
1650	///
1651	/// It is up to the caller to ensure that the iterator is valid for this
1652	/// `RawTable` and covers all items that remain in the table.
1653	pub unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T, A> {
1654	debug_assert_eq!(iter.len(), self.len());
1655
1656	let allocation = self.into_allocation();
1657	RawIntoIter {
1658	iter,
1659	allocation,
1660	marker: PhantomData,
1661	}
1662	}
1663
1664	/// Converts the table into a raw allocation. The contents of the table
1665	/// should be dropped using a `RawIter` before freeing the allocation.
1666	#[cfg_attr(feature = "inline-more", inline)]
1667	pub(crate) fn into_allocation(self) -> Option<(NonNull<u8>, Layout, A)> {
1668	let alloc = if self.table.is_empty_singleton() {
1669	None
1670	} else {
1671	// Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
1672	let (layout, ctrl_offset) =
1673	match Self::TABLE_LAYOUT.calculate_layout_for(self.table.buckets()) {
1674	Some(lco) => lco,
1675	None => unsafe { hint::unreachable_unchecked() },
1676	};
1677	Some((
1678	unsafe { NonNull::new_unchecked(self.table.ctrl.as_ptr().sub(ctrl_offset)) },
1679	layout,
1680	unsafe { ptr::read(&self.alloc) },
1681	))
1682	};
1683	mem::forget(self);
1684	alloc
1685	}
1686	}
1687
1688	unsafe impl<T, A: Allocator> Send for RawTable<T, A>
1689	where
1690	T: Send,
1691	A: Send,
1692	{
1693	}
1694	unsafe impl<T, A: Allocator> Sync for RawTable<T, A>
1695	where
1696	T: Sync,
1697	A: Sync,
1698	{
1699	}
1700
1701	impl RawTableInner {
1702	const NEW: Self = RawTableInner::new();
1703
1704	/// Creates a new empty hash table without allocating any memory.
1705	///
1706	/// In effect this returns a table with exactly 1 bucket. However we can
1707	/// leave the data pointer dangling since that bucket is never accessed
1708	/// due to our load factor forcing us to always have at least 1 free bucket.
1709	#[inline]
1710	const fn new() -> Self {
1711	Self {
1712	// Be careful to cast the entire slice to a raw pointer.
1713	ctrl: unsafe { NonNull::new_unchecked(ptr:Group::static_empty() as *const _ as *mut u8) },
1714	bucket_mask: `0`,
1715	items: `0`,
1716	growth_left: `0`,
1717	}
1718	}
1719	}
1720
1721	impl RawTableInner {
1722	/// Allocates a new [`RawTableInner`] with the given number of buckets.
1723	/// The control bytes and buckets are left uninitialized.
1724	///
1725	/// # Safety
1726	///
1727	/// The caller of this function must ensure that the `buckets` is power of two
1728	/// and also initialize all control bytes of the length `self.bucket_mask + 1 +
1729	/// Group::WIDTH` with the [`EMPTY`] bytes.
1730	///
1731	/// See also [`Allocator`] API for other safety concerns.
1732	///
1733	/// [`Allocator`]: https://doc.rust-lang.org/alloc/alloc/trait.Allocator.html
1734	#[cfg_attr(feature = "inline-more", inline)]
1735	unsafe fn new_uninitialized<A>(
1736	alloc: &A,
1737	table_layout: TableLayout,
1738	buckets: usize,
1739	fallibility: Fallibility,
1740	) -> Result<Self, TryReserveError>
1741	where
1742	A: Allocator,
1743	{
1744	debug_assert!(buckets.is_power_of_two());
1745
1746	// Avoid `Option::ok_or_else` because it bloats LLVM IR.
1747	let (layout, ctrl_offset) = match table_layout.calculate_layout_for(buckets) {
1748	Some(lco) => lco,
1749	None => return Err(fallibility.capacity_overflow()),
1750	};
1751
1752	let ptr: NonNull<u8> = match do_alloc(alloc, layout) {
1753	Ok(block) => block.cast(),
1754	Err(_) => return Err(fallibility.alloc_err(layout)),
1755	};
1756
1757	// SAFETY: null pointer will be caught in above check
1758	let ctrl = NonNull::new_unchecked(ptr.as_ptr().add(ctrl_offset));
1759	Ok(Self {
1760	ctrl,
1761	bucket_mask: buckets - `1`,
1762	items: `0`,
1763	growth_left: bucket_mask_to_capacity(buckets - `1`),
1764	})
1765	}
1766
1767	/// Attempts to allocate a new [`RawTableInner`] with at least enough
1768	/// capacity for inserting the given number of elements without reallocating.
1769	///
1770	/// All the control bytes are initialized with the [`EMPTY`] bytes.
1771	#[inline]
1772	fn fallible_with_capacity<A>(
1773	alloc: &A,
1774	table_layout: TableLayout,
1775	capacity: usize,
1776	fallibility: Fallibility,
1777	) -> Result<Self, TryReserveError>
1778	where
1779	A: Allocator,
1780	{
1781	if capacity == `0` {
1782	Ok(Self::NEW)
1783	} else {
1784	// SAFETY: We checked that we could successfully allocate the new table, and then
1785	// initialized all control bytes with the constant `EMPTY` byte.
1786	unsafe {
1787	let buckets =
1788	capacity_to_buckets(capacity).ok_or_else(\|\| fallibility.capacity_overflow())?;
1789
1790	let result = Self::new_uninitialized(alloc, table_layout, buckets, fallibility)?;
1791	// SAFETY: We checked that the table is allocated and therefore the table already has
1792	// `self.bucket_mask + 1 + Group::WIDTH` number of control bytes (see TableLayout::calculate_layout_for)
1793	// so writing `self.num_ctrl_bytes() == bucket_mask + 1 + Group::WIDTH` bytes is safe.
1794	result.ctrl(`0`).write_bytes(EMPTY, result.num_ctrl_bytes());
1795
1796	Ok(result)
1797	}
1798	}
1799	}
1800
1801	/// Allocates a new [`RawTableInner`] with at least enough capacity for inserting
1802	/// the given number of elements without reallocating.
1803	///
1804	/// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program
1805	/// in case of allocation error. Use [`fallible_with_capacity`] instead if you want to
1806	/// handle memory allocation failure.
1807	///
1808	/// All the control bytes are initialized with the [`EMPTY`] bytes.
1809	///
1810	/// [`fallible_with_capacity`]: RawTableInner::fallible_with_capacity
1811	/// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
1812	fn with_capacity<A>(alloc: &A, table_layout: TableLayout, capacity: usize) -> Self
1813	where
1814	A: Allocator,
1815	{
1816	// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
1817	match Self::fallible_with_capacity(alloc, table_layout, capacity, Fallibility::Infallible) {
1818	Ok(table_inner) => table_inner,
1819	// SAFETY: All allocation errors will be caught inside `RawTableInner::new_uninitialized`.
1820	Err(_) => unsafe { hint::unreachable_unchecked() },
1821	}
1822	}
1823
1824	/// Fixes up an insertion slot returned by the [`RawTableInner::find_insert_slot_in_group`] method.
1825	///
1826	/// In tables smaller than the group width (`self.buckets() < Group::WIDTH`), trailing control
1827	/// bytes outside the range of the table are filled with [`EMPTY`] entries. These will unfortunately
1828	/// trigger a match of [`RawTableInner::find_insert_slot_in_group`] function. This is because
1829	/// the `Some(bit)` returned by `group.match_empty_or_deleted().lowest_set_bit()` after masking
1830	/// (`(probe_seq.pos + bit) & self.bucket_mask`) may point to a full bucket that is already occupied.
1831	/// We detect this situation here and perform a second scan starting at the beginning of the table.
1832	/// This second scan is guaranteed to find an empty slot (due to the load factor) before hitting the
1833	/// trailing control bytes (containing [`EMPTY`] bytes).
1834	///
1835	/// If this function is called correctly, it is guaranteed to return [`InsertSlot`] with an
1836	/// index of an empty or deleted bucket in the range `0..self.buckets()` (see `Warning` and
1837	/// `Safety`).
1838	///
1839	/// # Warning
1840	///
1841	/// The table must have at least 1 empty or deleted `bucket`, otherwise if the table is less than
1842	/// the group width (`self.buckets() < Group::WIDTH`) this function returns an index outside of the
1843	/// table indices range `0..self.buckets()` (`0..=self.bucket_mask`). Attempt to write data at that
1844	/// index will cause immediate [`undefined behavior`].
1845	///
1846	/// # Safety
1847	///
1848	/// The safety rules are directly derived from the safety rules for [`RawTableInner::ctrl`] method.
1849	/// Thus, in order to uphold those safety contracts, as well as for the correct logic of the work
1850	/// of this crate, the following rules are necessary and sufficient:
1851	///
1852	/// The* [`RawTableInner`] must have properly initialized control bytes otherwise calling this
1853	/// function results in [`undefined behavior`].
1854	///
1855	/// This function must only be used on insertion slots found by* [`RawTableInner::find_insert_slot_in_group`]
1856	/// (after the `find_insert_slot_in_group` function, but before insertion into the table).
1857	///
1858	/// The `index` must not be greater than the `self.bucket_mask`, i.e. `(index + 1) <= self.buckets()`*
1859	/// (this one is provided by the [`RawTableInner::find_insert_slot_in_group`] function).
1860	///
1861	/// Calling this function with an index not provided by [`RawTableInner::find_insert_slot_in_group`]
1862	/// may result in [`undefined behavior`] even if the index satisfies the safety rules of the
1863	/// [`RawTableInner::ctrl`] function (`index < self.bucket_mask + 1 + Group::WIDTH`).
1864	///
1865	/// [`RawTableInner::ctrl`]: RawTableInner::ctrl
1866	/// [`RawTableInner::find_insert_slot_in_group`]: RawTableInner::find_insert_slot_in_group
1867	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1868	#[inline]
1869	unsafe fn fix_insert_slot(&self, mut index: usize) -> InsertSlot {
1870	// SAFETY: The caller of this function ensures that `index` is in the range `0..=self.bucket_mask`.
1871	if unlikely(self.is_bucket_full(index)) {
1872	debug_assert!(self.bucket_mask < Group::WIDTH);
1873	// SAFETY:
1874	//
1875	// Since the caller of this function ensures that the control bytes are properly*
1876	// initialized and `ptr = self.ctrl(0)` points to the start of the array of control
1877	// bytes, therefore: `ctrl` is valid for reads, properly aligned to `Group::WIDTH`
1878	// and points to the properly initialized control bytes (see also
1879	// `TableLayout::calculate_layout_for` and `ptr::read`);
1880	//
1881	// Because the caller of this function ensures that the index was provided by the*
1882	// `self.find_insert_slot_in_group()` function, so for for tables larger than the
1883	// group width (self.buckets() >= Group::WIDTH), we will never end up in the given
1884	// branch, since `(probe_seq.pos + bit) & self.bucket_mask` in `find_insert_slot_in_group`
1885	// cannot return a full bucket index. For tables smaller than the group width, calling
1886	// the `unwrap_unchecked` function is also safe, as the trailing control bytes outside
1887	// the range of the table are filled with EMPTY bytes (and we know for sure that there
1888	// is at least one FULL bucket), so this second scan either finds an empty slot (due to
1889	// the load factor) or hits the trailing control bytes (containing EMPTY).
1890	index = Group::load_aligned(self.ctrl(`0`))
1891	.match_empty_or_deleted()
1892	.lowest_set_bit()
1893	.unwrap_unchecked();
1894	}
1895	InsertSlot { index }
1896	}
1897
1898	/// Finds the position to insert something in a group.
1899	///
1900	/// This may have false positives and must be fixed up with `fix_insert_slot`
1901	/// before it's used.**
1902	///
1903	/// The function is guaranteed to return the index of an empty or deleted [`Bucket`]
1904	/// in the range `0..self.buckets()` (`0..=self.bucket_mask`).
1905	#[inline]
1906	fn find_insert_slot_in_group(&self, group: &Group, probe_seq: &ProbeSeq) -> Option<usize> {
1907	let bit = group.match_empty_or_deleted().lowest_set_bit();
1908
1909	if likely(bit.is_some()) {
1910	// This is the same as `(probe_seq.pos + bit) % self.buckets()` because the number
1911	// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
1912	Some((probe_seq.pos + bit.unwrap()) & self.bucket_mask)
1913	} else {
1914	None
1915	}
1916	}
1917
1918	/// Searches for an element in the table, or a potential slot where that element could
1919	/// be inserted (an empty or deleted [`Bucket`] index).
1920	///
1921	/// This uses dynamic dispatch to reduce the amount of code generated, but that is
1922	/// eliminated by LLVM optimizations.
1923	///
1924	/// This function does not make any changes to the `data` part of the table, or any
1925	/// changes to the `items` or `growth_left` field of the table.
1926	///
1927	/// The table must have at least 1 empty or deleted `bucket`, otherwise, if the
1928	/// `eq: &mut dyn FnMut(usize) -> bool` function does not return `true`, this function
1929	/// will never return (will go into an infinite loop) for tables larger than the group
1930	/// width, or return an index outside of the table indices range if the table is less
1931	/// than the group width.
1932	///
1933	/// This function is guaranteed to provide the `eq: &mut dyn FnMut(usize) -> bool`
1934	/// function with only `FULL` buckets' indices and return the `index` of the found
1935	/// element (as `Ok(index)`). If the element is not found and there is at least 1
1936	/// empty or deleted [`Bucket`] in the table, the function is guaranteed to return
1937	/// [InsertSlot] with an index in the range `0..self.buckets()`, but in any case,
1938	/// if this function returns [`InsertSlot`], it will contain an index in the range
1939	/// `0..=self.buckets()`.
1940	///
1941	/// # Safety
1942	///
1943	/// The [`RawTableInner`] must have properly initialized control bytes otherwise calling
1944	/// this function results in [`undefined behavior`].
1945	///
1946	/// Attempt to write data at the [`InsertSlot`] returned by this function when the table is
1947	/// less than the group width and if there was not at least one empty or deleted bucket in
1948	/// the table will cause immediate [`undefined behavior`]. This is because in this case the
1949	/// function will return `self.bucket_mask + 1` as an index due to the trailing [`EMPTY]
1950	/// control bytes outside the table range.
1951	///
1952	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1953	#[inline]
1954	unsafe fn find_or_find_insert_slot_inner(
1955	&self,
1956	hash: u64,
1957	eq: &mut dyn FnMut(usize) -> bool,
1958	) -> Result<usize, InsertSlot> {
1959	let mut insert_slot = None;
1960
1961	let h2_hash = h2(hash);
1962	let mut probe_seq = self.probe_seq(hash);
1963
1964	loop {
1965	// SAFETY:
1966	// Caller of this function ensures that the control bytes are properly initialized.*
1967	//
1968	// `ProbeSeq.pos` cannot be greater than `self.bucket_mask = self.buckets() - 1`*
1969	// of the table due to masking with `self.bucket_mask` and also because mumber of
1970	// buckets is a power of two (see `self.probe_seq` function).
1971	//
1972	// Even if `ProbeSeq.pos` returns `position == self.bucket_mask`, it is safe to*
1973	// call `Group::load` due to the extended control bytes range, which is
1974	// `self.bucket_mask + 1 + Group::WIDTH` (in fact, this means that the last control
1975	// byte will never be read for the allocated table);
1976	//
1977	// Also, even if `RawTableInner` is not already allocated, `ProbeSeq.pos` will*
1978	// always return "0" (zero), so Group::load will read unaligned `Group::static_empty()`
1979	// bytes, which is safe (see RawTableInner::new).
1980	let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };
1981
1982	for bit in group.match_byte(h2_hash) {
1983	let index = (probe_seq.pos + bit) & self.bucket_mask;
1984
1985	if likely(eq(index)) {
1986	return Ok(index);
1987	}
1988	}
1989
1990	// We didn't find the element we were looking for in the group, try to get an
1991	// insertion slot from the group if we don't have one yet.
1992	if likely(insert_slot.is_none()) {
1993	insert_slot = self.find_insert_slot_in_group(&group, &probe_seq);
1994	}
1995
1996	// Only stop the search if the group contains at least one empty element.
1997	// Otherwise, the element that we are looking for might be in a following group.
1998	if likely(group.match_empty().any_bit_set()) {
1999	// We must have found a insert slot by now, since the current group contains at
2000	// least one. For tables smaller than the group width, there will still be an
2001	// empty element in the current (and only) group due to the load factor.
2002	unsafe {
2003	// SAFETY:
2004	// Caller of this function ensures that the control bytes are properly initialized.*
2005	//
2006	// We use this function with the slot / index found by `self.find_insert_slot_in_group`*
2007	return Err(self.fix_insert_slot(insert_slot.unwrap_unchecked()));
2008	}
2009	}
2010
2011	probe_seq.move_next(self.bucket_mask);
2012	}
2013	}
2014
2015	/// Searches for an empty or deleted bucket which is suitable for inserting a new
2016	/// element and sets the hash for that slot. Returns an index of that slot and the
2017	/// old control byte stored in the found index.
2018	///
2019	/// This function does not check if the given element exists in the table. Also,
2020	/// this function does not check if there is enough space in the table to insert
2021	/// a new element. Caller of the funtion must make ensure that the table has at
2022	/// least 1 empty or deleted `bucket`, otherwise this function will never return
2023	/// (will go into an infinite loop) for tables larger than the group width, or
2024	/// return an index outside of the table indices range if the table is less than
2025	/// the group width.
2026	///
2027	/// If there is at least 1 empty or deleted `bucket` in the table, the function is
2028	/// guaranteed to return an `index` in the range `0..self.buckets()`, but in any case,
2029	/// if this function returns an `index` it will be in the range `0..=self.buckets()`.
2030	///
2031	/// This function does not make any changes to the `data` parts of the table,
2032	/// or any changes to the the `items` or `growth_left` field of the table.
2033	///
2034	/// # Safety
2035	///
2036	/// The safety rules are directly derived from the safety rules for the
2037	/// [`RawTableInner::set_ctrl_h2`] and [`RawTableInner::find_insert_slot`] methods.
2038	/// Thus, in order to uphold the safety contracts for that methods, as well as for
2039	/// the correct logic of the work of this crate, you must observe the following rules
2040	/// when calling this function:
2041	///
2042	/// The* [`RawTableInner`] has already been allocated and has properly initialized
2043	/// control bytes otherwise calling this function results in [`undefined behavior`].
2044	///
2045	/// The caller of this function must ensure that the "data" parts of the table*
2046	/// will have an entry in the returned index (matching the given hash) right
2047	/// after calling this function.
2048	///
2049	/// Attempt to write data at the `index` returned by this function when the table is
2050	/// less than the group width and if there was not at least one empty or deleted bucket in
2051	/// the table will cause immediate [`undefined behavior`]. This is because in this case the
2052	/// function will return `self.bucket_mask + 1` as an index due to the trailing [`EMPTY]
2053	/// control bytes outside the table range.
2054	///
2055	/// The caller must independently increase the `items` field of the table, and also,
2056	/// if the old control byte was [`EMPTY`], then decrease the table's `growth_left`
2057	/// field, and do not change it if the old control byte was [`DELETED`].
2058	///
2059	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
2060	/// or saving `element` from / into the [`RawTable`] / [`RawTableInner`].
2061	///
2062	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2063	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2064	/// [`RawTableInner::ctrl`]: RawTableInner::ctrl
2065	/// [`RawTableInner::set_ctrl_h2`]: RawTableInner::set_ctrl_h2
2066	/// [`RawTableInner::find_insert_slot`]: RawTableInner::find_insert_slot
2067	#[inline]
2068	unsafe fn prepare_insert_slot(&mut self, hash: u64) -> (usize, u8) {
2069	// SAFETY: Caller of this function ensures that the control bytes are properly initialized.
2070	let index: usize = self.find_insert_slot(hash).index;
2071	// SAFETY:
2072	// 1. The `find_insert_slot` function either returns an `index` less than or
2073	// equal to `self.buckets() = self.bucket_mask + 1` of the table, or never
2074	// returns if it cannot find an empty or deleted slot.
2075	// 2. The caller of this function guarantees that the table has already been
2076	// allocated
2077	let old_ctrl = *self.ctrl(index);
2078	self.set_ctrl_h2(index, hash);
2079	(index, old_ctrl)
2080	}
2081
2082	/// Searches for an empty or deleted bucket which is suitable for inserting
2083	/// a new element, returning the `index` for the new [`Bucket`].
2084	///
2085	/// This function does not make any changes to the `data` part of the table, or any
2086	/// changes to the `items` or `growth_left` field of the table.
2087	///
2088	/// The table must have at least 1 empty or deleted `bucket`, otherwise this function
2089	/// will never return (will go into an infinite loop) for tables larger than the group
2090	/// width, or return an index outside of the table indices range if the table is less
2091	/// than the group width.
2092	///
2093	/// If there is at least 1 empty or deleted `bucket` in the table, the function is
2094	/// guaranteed to return [`InsertSlot`] with an index in the range `0..self.buckets()`,
2095	/// but in any case, if this function returns [`InsertSlot`], it will contain an index
2096	/// in the range `0..=self.buckets()`.
2097	///
2098	/// # Safety
2099	///
2100	/// The [`RawTableInner`] must have properly initialized control bytes otherwise calling
2101	/// this function results in [`undefined behavior`].
2102	///
2103	/// Attempt to write data at the [`InsertSlot`] returned by this function when the table is
2104	/// less than the group width and if there was not at least one empty or deleted bucket in
2105	/// the table will cause immediate [`undefined behavior`]. This is because in this case the
2106	/// function will return `self.bucket_mask + 1` as an index due to the trailing [`EMPTY]
2107	/// control bytes outside the table range.
2108	///
2109	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2110	#[inline]
2111	unsafe fn find_insert_slot(&self, hash: u64) -> InsertSlot {
2112	let mut probe_seq = self.probe_seq(hash);
2113	loop {
2114	// SAFETY:
2115	// Caller of this function ensures that the control bytes are properly initialized.*
2116	//
2117	// `ProbeSeq.pos` cannot be greater than `self.bucket_mask = self.buckets() - 1`*
2118	// of the table due to masking with `self.bucket_mask` and also because mumber of
2119	// buckets is a power of two (see `self.probe_seq` function).
2120	//
2121	// Even if `ProbeSeq.pos` returns `position == self.bucket_mask`, it is safe to*
2122	// call `Group::load` due to the extended control bytes range, which is
2123	// `self.bucket_mask + 1 + Group::WIDTH` (in fact, this means that the last control
2124	// byte will never be read for the allocated table);
2125	//
2126	// Also, even if `RawTableInner` is not already allocated, `ProbeSeq.pos` will*
2127	// always return "0" (zero), so Group::load will read unaligned `Group::static_empty()`
2128	// bytes, which is safe (see RawTableInner::new).
2129	let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };
2130
2131	let index = self.find_insert_slot_in_group(&group, &probe_seq);
2132	if likely(index.is_some()) {
2133	// SAFETY:
2134	// Caller of this function ensures that the control bytes are properly initialized.*
2135	//
2136	// We use this function with the slot / index found by `self.find_insert_slot_in_group`*
2137	unsafe {
2138	return self.fix_insert_slot(index.unwrap_unchecked());
2139	}
2140	}
2141	probe_seq.move_next(self.bucket_mask);
2142	}
2143	}
2144
2145	/// Searches for an element in a table, returning the `index` of the found element.
2146	/// This uses dynamic dispatch to reduce the amount of code generated, but it is
2147	/// eliminated by LLVM optimizations.
2148	///
2149	/// This function does not make any changes to the `data` part of the table, or any
2150	/// changes to the `items` or `growth_left` field of the table.
2151	///
2152	/// The table must have at least 1 empty `bucket`, otherwise, if the
2153	/// `eq: &mut dyn FnMut(usize) -> bool` function does not return `true`,
2154	/// this function will also never return (will go into an infinite loop).
2155	///
2156	/// This function is guaranteed to provide the `eq: &mut dyn FnMut(usize) -> bool`
2157	/// function with only `FULL` buckets' indices and return the `index` of the found
2158	/// element as `Some(index)`, so the index will always be in the range
2159	/// `0..self.buckets()`.
2160	///
2161	/// # Safety
2162	///
2163	/// The [`RawTableInner`] must have properly initialized control bytes otherwise calling
2164	/// this function results in [`undefined behavior`].
2165	///
2166	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2167	#[inline(always)]
2168	unsafe fn find_inner(&self, hash: u64, eq: &mut dyn FnMut(usize) -> bool) -> Option<usize> {
2169	let h2_hash = h2(hash);
2170	let mut probe_seq = self.probe_seq(hash);
2171
2172	loop {
2173	// SAFETY:
2174	// Caller of this function ensures that the control bytes are properly initialized.*
2175	//
2176	// `ProbeSeq.pos` cannot be greater than `self.bucket_mask = self.buckets() - 1`*
2177	// of the table due to masking with `self.bucket_mask`.
2178	//
2179	// Even if `ProbeSeq.pos` returns `position == self.bucket_mask`, it is safe to*
2180	// call `Group::load` due to the extended control bytes range, which is
2181	// `self.bucket_mask + 1 + Group::WIDTH` (in fact, this means that the last control
2182	// byte will never be read for the allocated table);
2183	//
2184	// Also, even if `RawTableInner` is not already allocated, `ProbeSeq.pos` will*
2185	// always return "0" (zero), so Group::load will read unaligned `Group::static_empty()`
2186	// bytes, which is safe (see RawTableInner::new_in).
2187	let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };
2188
2189	for bit in group.match_byte(h2_hash) {
2190	// This is the same as `(probe_seq.pos + bit) % self.buckets()` because the number
2191	// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2192	let index = (probe_seq.pos + bit) & self.bucket_mask;
2193
2194	if likely(eq(index)) {
2195	return Some(index);
2196	}
2197	}
2198
2199	if likely(group.match_empty().any_bit_set()) {
2200	return None;
2201	}
2202
2203	probe_seq.move_next(self.bucket_mask);
2204	}
2205	}
2206
2207	/// Prepares for rehashing data in place (that is, without allocating new memory).
2208	/// Converts all full index `control bytes` to `DELETED` and all `DELETED` control
2209	/// bytes to `EMPTY`, i.e. performs the following conversion:
2210	///
2211	/// - `EMPTY` control bytes -> `EMPTY`;
2212	/// - `DELETED` control bytes -> `EMPTY`;
2213	/// - `FULL` control bytes -> `DELETED`.
2214	///
2215	/// This function does not make any changes to the `data` parts of the table,
2216	/// or any changes to the the `items` or `growth_left` field of the table.
2217	///
2218	/// # Safety
2219	///
2220	/// You must observe the following safety rules when calling this function:
2221	///
2222	/// The* [`RawTableInner`] has already been allocated;
2223	///
2224	/// The caller of this function must convert the `DELETED` bytes back to `FULL`*
2225	/// bytes when re-inserting them into their ideal position (which was impossible
2226	/// to do during the first insert due to tombstones). If the caller does not do
2227	/// this, then calling this function may result in a memory leak.
2228	///
2229	/// The* [`RawTableInner`] must have properly initialized control bytes otherwise
2230	/// calling this function results in [`undefined behavior`].
2231	///
2232	/// Calling this function on a table that has not been allocated results in
2233	/// [`undefined behavior`].
2234	///
2235	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
2236	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
2237	///
2238	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2239	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2240	#[allow(clippy::mut_mut)]
2241	#[inline]
2242	unsafe fn prepare_rehash_in_place(&mut self) {
2243	// Bulk convert all full control bytes to DELETED, and all DELETED control bytes to EMPTY.
2244	// This effectively frees up all buckets containing a DELETED entry.
2245	//
2246	// SAFETY:
2247	// 1. `i` is guaranteed to be within bounds since we are iterating from zero to `buckets - 1`;
2248	// 2. Even if `i` will be `i == self.bucket_mask`, it is safe to call `Group::load_aligned`
2249	// due to the extended control bytes range, which is `self.bucket_mask + 1 + Group::WIDTH`;
2250	// 3. The caller of this function guarantees that [`RawTableInner`] has already been allocated;
2251	// 4. We can use `Group::load_aligned` and `Group::store_aligned` here since we start from 0
2252	// and go to the end with a step equal to `Group::WIDTH` (see TableLayout::calculate_layout_for).
2253	for i in (`0`..self.buckets()).step_by(Group::WIDTH) {
2254	let group = Group::load_aligned(self.ctrl(i));
2255	let group = group.convert_special_to_empty_and_full_to_deleted();
2256	group.store_aligned(self.ctrl(i));
2257	}
2258
2259	// Fix up the trailing control bytes. See the comments in set_ctrl
2260	// for the handling of tables smaller than the group width.
2261	//
2262	// SAFETY: The caller of this function guarantees that [`RawTableInner`]
2263	// has already been allocated
2264	if unlikely(self.buckets() < Group::WIDTH) {
2265	// SAFETY: We have `self.bucket_mask + 1 + Group::WIDTH` number of control bytes,
2266	// so copying `self.buckets() == self.bucket_mask + 1` bytes with offset equal to
2267	// `Group::WIDTH` is safe
2268	self.ctrl(`0`)
2269	.copy_to(self.ctrl(Group::WIDTH), self.buckets());
2270	} else {
2271	// SAFETY: We have `self.bucket_mask + 1 + Group::WIDTH` number of
2272	// control bytes,so copying `Group::WIDTH` bytes with offset equal
2273	// to `self.buckets() == self.bucket_mask + 1` is safe
2274	self.ctrl(`0`)
2275	.copy_to(self.ctrl(self.buckets()), Group::WIDTH);
2276	}
2277	}
2278
2279	/// Returns an iterator over every element in the table.
2280	///
2281	/// # Safety
2282	///
2283	/// If any of the following conditions are violated, the result
2284	/// is [`undefined behavior`]:
2285	///
2286	/// The caller has to ensure that the `RawTableInner` outlives the*
2287	/// `RawIter`. Because we cannot make the `next` method unsafe on
2288	/// the `RawIter` struct, we have to make the `iter` method unsafe.
2289	///
2290	/// The* [`RawTableInner`] must have properly initialized control bytes.
2291	///
2292	/// The type `T` must be the actual type of the elements stored in the table,
2293	/// otherwise using the returned [`RawIter`] results in [`undefined behavior`].
2294	///
2295	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2296	#[inline]
2297	unsafe fn iter<T>(&self) -> RawIter<T> {
2298	// SAFETY:
2299	// 1. Since the caller of this function ensures that the control bytes
2300	// are properly initialized and `self.data_end()` points to the start
2301	// of the array of control bytes, therefore: `ctrl` is valid for reads,
2302	// properly aligned to `Group::WIDTH` and points to the properly initialized
2303	// control bytes.
2304	// 2. `data` bucket index in the table is equal to the `ctrl` index (i.e.
2305	// equal to zero).
2306	// 3. We pass the exact value of buckets of the table to the function.
2307	//
2308	// `ctrl` points here (to the start
2309	// of the first control byte `CT0`)
2310	// ∨
2311	// [Pad], T_n, ..., T1, T0, \|CT0, CT1, ..., CT_n\|, CTa_0, CTa_1, ..., CTa_m
2312	// \________ ________/
2313	// \/
2314	// `n = buckets - 1`, i.e. `RawTableInner::buckets() - 1`
2315	//
2316	// where: T0...T_n - our stored data;
2317	// CT0...CT_n - control bytes or metadata for `data`.
2318	// CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
2319	// with loading `Group` bytes from the heap works properly, even if the result
2320	// of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
2321	// `RawTableInner::set_ctrl` function.
2322	//
2323	// P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
2324	// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2325	let data = Bucket::from_base_index(self.data_end(), `0`);
2326	RawIter {
2327	// SAFETY: See explanation above
2328	iter: RawIterRange::new(self.ctrl.as_ptr(), data, self.buckets()),
2329	items: self.items,
2330	}
2331	}
2332
2333	/// Executes the destructors (if any) of the values stored in the table.
2334	///
2335	/// # Note
2336	///
2337	/// This function does not erase the control bytes of the table and does
2338	/// not make any changes to the `items` or `growth_left` fields of the
2339	/// table. If necessary, the caller of this function must manually set
2340	/// up these table fields, for example using the [`clear_no_drop`] function.
2341	///
2342	/// Be careful during calling this function, because drop function of
2343	/// the elements can panic, and this can leave table in an inconsistent
2344	/// state.
2345	///
2346	/// # Safety
2347	///
2348	/// The type `T` must be the actual type of the elements stored in the table,
2349	/// otherwise calling this function may result in [`undefined behavior`].
2350	///
2351	/// If `T` is a type that should be dropped and the table is not empty,
2352	/// calling this function more than once results in [`undefined behavior`].
2353	///
2354	/// If `T` is not [`Copy`], attempting to use values stored in the table after
2355	/// calling this function may result in [`undefined behavior`].
2356	///
2357	/// It is safe to call this function on a table that has not been allocated,
2358	/// on a table with uninitialized control bytes, and on a table with no actual
2359	/// data but with `Full` control bytes if `self.items == 0`.
2360	///
2361	/// See also [`Bucket::drop`] / [`Bucket::as_ptr`] methods, for more information
2362	/// about of properly removing or saving `element` from / into the [`RawTable`] /
2363	/// [`RawTableInner`].
2364	///
2365	/// [`Bucket::drop`]: Bucket::drop
2366	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2367	/// [`clear_no_drop`]: RawTableInner::clear_no_drop
2368	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2369	unsafe fn drop_elements<T>(&mut self) {
2370	// Check that `self.items != 0`. Protects against the possibility
2371	// of creating an iterator on an table with uninitialized control bytes.
2372	if T::NEEDS_DROP && self.items != `0` {
2373	// SAFETY: We know for sure that RawTableInner will outlive the
2374	// returned `RawIter` iterator, and the caller of this function
2375	// must uphold the safety contract for `drop_elements` method.
2376	for item in self.iter::<T>() {
2377	// SAFETY: The caller must uphold the safety contract for
2378	// `drop_elements` method.
2379	item.drop();
2380	}
2381	}
2382	}
2383
2384	/// Executes the destructors (if any) of the values stored in the table and than
2385	/// deallocates the table.
2386	///
2387	/// # Note
2388	///
2389	/// Calling this function automatically makes invalid (dangling) all instances of
2390	/// buckets ([`Bucket`]) and makes invalid (dangling) the `ctrl` field of the table.
2391	///
2392	/// This function does not make any changes to the `bucket_mask`, `items` or `growth_left`
2393	/// fields of the table. If necessary, the caller of this function must manually set
2394	/// up these table fields.
2395	///
2396	/// # Safety
2397	///
2398	/// If any of the following conditions are violated, the result is [`undefined behavior`]:
2399	///
2400	/// Calling this function more than once;*
2401	///
2402	/// The type `T` must be the actual type of the elements stored in the table.*
2403	///
2404	/// The `alloc` must be the same* [`Allocator`] as the `Allocator` that was used
2405	/// to allocate this table.
2406	///
2407	/// The `table_layout` must be the same* [`TableLayout`] as the `TableLayout` that
2408	/// was used to allocate this table.
2409	///
2410	/// The caller of this function should pay attention to the possibility of the
2411	/// elements' drop function panicking, because this:
2412	///
2413	/// May leave the table in an inconsistent state;*
2414	///
2415	/// Memory is never deallocated, so a memory leak may occur.*
2416	///
2417	/// Attempt to use the `ctrl` field of the table (dereference) after calling this
2418	/// function results in [`undefined behavior`].
2419	///
2420	/// It is safe to call this function on a table that has not been allocated,
2421	/// on a table with uninitialized control bytes, and on a table with no actual
2422	/// data but with `Full` control bytes if `self.items == 0`.
2423	///
2424	/// See also [`RawTableInner::drop_elements`] or [`RawTableInner::free_buckets`]
2425	/// for more information.
2426	///
2427	/// [`RawTableInner::drop_elements`]: RawTableInner::drop_elements
2428	/// [`RawTableInner::free_buckets`]: RawTableInner::free_buckets
2429	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2430	unsafe fn drop_inner_table<T, A: Allocator>(&mut self, alloc: &A, table_layout: TableLayout) {
2431	if !self.is_empty_singleton() {
2432	unsafe {
2433	// SAFETY: The caller must uphold the safety contract for `drop_inner_table` method.
2434	self.drop_elements::<T>();
2435	// SAFETY:
2436	// 1. We have checked that our table is allocated.
2437	// 2. The caller must uphold the safety contract for `drop_inner_table` method.
2438	self.free_buckets(alloc, table_layout);
2439	}
2440	}
2441	}
2442
2443	/// Returns a pointer to an element in the table (convenience for
2444	/// `Bucket::from_base_index(self.data_end::<T>(), index)`).
2445	///
2446	/// The caller must ensure that the `RawTableInner` outlives the returned [`Bucket<T>`],
2447	/// otherwise using it may result in [`undefined behavior`].
2448	///
2449	/// # Safety
2450	///
2451	/// If `mem::size_of::<T>() != 0`, then the safety rules are directly derived from the
2452	/// safety rules of the [`Bucket::from_base_index`] function. Therefore, when calling
2453	/// this function, the following safety rules must be observed:
2454	///
2455	/// The table must already be allocated;*
2456	///
2457	/// The `index` must not be greater than the number returned by the* [`RawTableInner::buckets`]
2458	/// function, i.e. `(index + 1) <= self.buckets()`.
2459	///
2460	/// The type `T` must be the actual type of the elements stored in the table, otherwise*
2461	/// using the returned [`Bucket`] may result in [`undefined behavior`].
2462	///
2463	/// It is safe to call this function with index of zero (`index == 0`) on a table that has
2464	/// not been allocated, but using the returned [`Bucket`] results in [`undefined behavior`].
2465	///
2466	/// If `mem::size_of::<T>() == 0`, then the only requirement is that the `index` must
2467	/// not be greater than the number returned by the [`RawTable::buckets`] function, i.e.
2468	/// `(index + 1) <= self.buckets()`.
2469	///
2470	/// ```none
2471	/// If mem::size_of::<T>() != 0 then return a pointer to the `element` in the `data part` of the table
2472	/// (we start counting from "0", so that in the expression T[n], the "n" index actually one less than
2473	/// the "buckets" number of our `RawTableInner`, i.e. "n = RawTableInner::buckets() - 1"):
2474	///
2475	/// `table.bucket(3).as_ptr()` returns a pointer that points here in the `data`
2476	/// part of the `RawTableInner`, i.e. to the start of T3 (see [`Bucket::as_ptr`])
2477	/// \|
2478	/// \| `base = table.data_end::<T>()` points here
2479	/// \| (to the start of CT0 or to the end of T0)
2480	/// v v
2481	/// [Pad], T_n, ..., \|T3\|, T2, T1, T0, \|CT0, CT1, CT2, CT3, ..., CT_n, CTa_0, CTa_1, ..., CTa_m
2482	/// ^ \__________ __________/
2483	/// `table.bucket(3)` returns a pointer that points \/
2484	/// here in the `data` part of the `RawTableInner` additional control bytes
2485	/// (to the end of T3) `m = Group::WIDTH - 1`
2486	///
2487	/// where: T0...T_n - our stored data;
2488	/// CT0...CT_n - control bytes or metadata for `data`;
2489	/// CTa_0...CTa_m - additional control bytes (so that the search with loading `Group` bytes from
2490	/// the heap works properly, even if the result of `h1(hash) & self.bucket_mask`
2491	/// is equal to `self.bucket_mask`). See also `RawTableInner::set_ctrl` function.
2492	///
2493	/// P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
2494	/// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2495	/// ```
2496	///
2497	/// [`Bucket::from_base_index`]: Bucket::from_base_index
2498	/// [`RawTableInner::buckets`]: RawTableInner::buckets
2499	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2500	#[inline]
2501	unsafe fn bucket<T>(&self, index: usize) -> Bucket<T> {
2502	debug_assert_ne!(self.bucket_mask, `0`);
2503	debug_assert!(index < self.buckets());
2504	Bucket::from_base_index(self.data_end(), index)
2505	}
2506
2507	/// Returns a raw `mut u8` pointer to the start of the `data` element in the table*
2508	/// (convenience for `self.data_end::<u8>().as_ptr().sub((index + 1) size_of)`).*
2509	///
2510	/// The caller must ensure that the `RawTableInner` outlives the returned `mut u8`,*
2511	/// otherwise using it may result in [`undefined behavior`].
2512	///
2513	/// # Safety
2514	///
2515	/// If any of the following conditions are violated, the result is [`undefined behavior`]:
2516	///
2517	/// The table must already be allocated;*
2518	///
2519	/// The `index` must not be greater than the number returned by the* [`RawTableInner::buckets`]
2520	/// function, i.e. `(index + 1) <= self.buckets()`;
2521	///
2522	/// The `size_of` must be equal to the size of the elements stored in the table;*
2523	///
2524	/// ```none
2525	/// If mem::size_of::<T>() != 0 then return a pointer to the `element` in the `data part` of the table
2526	/// (we start counting from "0", so that in the expression T[n], the "n" index actually one less than
2527	/// the "buckets" number of our `RawTableInner`, i.e. "n = RawTableInner::buckets() - 1"):
2528	///
2529	/// `table.bucket_ptr(3, mem::size_of::<T>())` returns a pointer that points here in the
2530	/// `data` part of the `RawTableInner`, i.e. to the start of T3
2531	/// \|
2532	/// \| `base = table.data_end::<u8>()` points here
2533	/// \| (to the start of CT0 or to the end of T0)
2534	/// v v
2535	/// [Pad], T_n, ..., \|T3\|, T2, T1, T0, \|CT0, CT1, CT2, CT3, ..., CT_n, CTa_0, CTa_1, ..., CTa_m
2536	/// \__________ __________/
2537	/// \/
2538	/// additional control bytes
2539	/// `m = Group::WIDTH - 1`
2540	///
2541	/// where: T0...T_n - our stored data;
2542	/// CT0...CT_n - control bytes or metadata for `data`;
2543	/// CTa_0...CTa_m - additional control bytes (so that the search with loading `Group` bytes from
2544	/// the heap works properly, even if the result of `h1(hash) & self.bucket_mask`
2545	/// is equal to `self.bucket_mask`). See also `RawTableInner::set_ctrl` function.
2546	///
2547	/// P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
2548	/// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2549	/// ```
2550	///
2551	/// [`RawTableInner::buckets`]: RawTableInner::buckets
2552	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2553	#[inline]
2554	unsafe fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8 {
2555	debug_assert_ne!(self.bucket_mask, `0`);
2556	debug_assert!(index < self.buckets());
2557	let base: *mut u8 = self.data_end().as_ptr();
2558	base.sub((index + `1`) * size_of)
2559	}
2560
2561	/// Returns pointer to one past last `data` element in the the table as viewed from
2562	/// the start point of the allocation (convenience for `self.ctrl.cast()`).
2563	///
2564	/// This function actually returns a pointer to the end of the `data element` at
2565	/// index "0" (zero).
2566	///
2567	/// The caller must ensure that the `RawTableInner` outlives the returned [`NonNull<T>`],
2568	/// otherwise using it may result in [`undefined behavior`].
2569	///
2570	/// # Note
2571	///
2572	/// The type `T` must be the actual type of the elements stored in the table, otherwise
2573	/// using the returned [`NonNull<T>`] may result in [`undefined behavior`].
2574	///
2575	/// ```none
2576	/// `table.data_end::<T>()` returns pointer that points here
2577	/// (to the end of `T0`)
2578	/// ∨
2579	/// [Pad], T_n, ..., T1, T0, \|CT0, CT1, ..., CT_n\|, CTa_0, CTa_1, ..., CTa_m
2580	/// \________ ________/
2581	/// \/
2582	/// `n = buckets - 1`, i.e. `RawTableInner::buckets() - 1`
2583	///
2584	/// where: T0...T_n - our stored data;
2585	/// CT0...CT_n - control bytes or metadata for `data`.
2586	/// CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
2587	/// with loading `Group` bytes from the heap works properly, even if the result
2588	/// of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
2589	/// `RawTableInner::set_ctrl` function.
2590	///
2591	/// P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
2592	/// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2593	/// ```
2594	///
2595	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2596	#[inline]
2597	fn data_end<T>(&self) -> NonNull<T> {
2598	unsafe {
2599	// SAFETY: `self.ctrl` is `NonNull`, so casting it is safe
2600	NonNull::new_unchecked(self.ctrl.as_ptr().cast())
2601	}
2602	}
2603
2604	/// Returns an iterator-like object for a probe sequence on the table.
2605	///
2606	/// This iterator never terminates, but is guaranteed to visit each bucket
2607	/// group exactly once. The loop using `probe_seq` must terminate upon
2608	/// reaching a group containing an empty bucket.
2609	#[inline]
2610	fn probe_seq(&self, hash: u64) -> ProbeSeq {
2611	ProbeSeq {
2612	// This is the same as `hash as usize % self.buckets()` because the number
2613	// of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2614	pos: h1(hash) & self.bucket_mask,
2615	stride: `0`,
2616	}
2617	}
2618
2619	/// Returns the index of a bucket for which a value must be inserted if there is enough rooom
2620	/// in the table, otherwise returns error
2621	#[cfg(feature = "raw")]
2622	#[inline]
2623	unsafe fn prepare_insert_no_grow(&mut self, hash: u64) -> Result<usize, ()> {
2624	let index = self.find_insert_slot(hash).index;
2625	let old_ctrl = *self.ctrl(index);
2626	if unlikely(self.growth_left == `0` && special_is_empty(old_ctrl)) {
2627	Err(())
2628	} else {
2629	self.record_item_insert_at(index, old_ctrl, hash);
2630	Ok(index)
2631	}
2632	}
2633
2634	#[inline]
2635	unsafe fn record_item_insert_at(&mut self, index: usize, old_ctrl: u8, hash: u64) {
2636	self.growth_left -= usize::from(special_is_empty(old_ctrl));
2637	self.set_ctrl_h2(index, hash);
2638	self.items += `1`;
2639	}
2640
2641	#[inline]
2642	fn is_in_same_group(&self, i: usize, new_i: usize, hash: u64) -> bool {
2643	let probe_seq_pos = self.probe_seq(hash).pos;
2644	let probe_index =
2645	\|pos: usize\| (pos.wrapping_sub(probe_seq_pos) & self.bucket_mask) / Group::WIDTH;
2646	probe_index(i) == probe_index(new_i)
2647	}
2648
2649	/// Sets a control byte to the hash, and possibly also the replicated control byte at
2650	/// the end of the array.
2651	///
2652	/// This function does not make any changes to the `data` parts of the table,
2653	/// or any changes to the the `items` or `growth_left` field of the table.
2654	///
2655	/// # Safety
2656	///
2657	/// The safety rules are directly derived from the safety rules for [`RawTableInner::set_ctrl`]
2658	/// method. Thus, in order to uphold the safety contracts for the method, you must observe the
2659	/// following rules when calling this function:
2660	///
2661	/// The* [`RawTableInner`] has already been allocated;
2662	///
2663	/// The `index` must not be greater than the `RawTableInner.bucket_mask`, i.e.*
2664	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)` must
2665	/// be no greater than the number returned by the function [`RawTableInner::buckets`].
2666	///
2667	/// Calling this function on a table that has not been allocated results in [`undefined behavior`].
2668	///
2669	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
2670	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
2671	///
2672	/// [`RawTableInner::set_ctrl`]: RawTableInner::set_ctrl
2673	/// [`RawTableInner::buckets`]: RawTableInner::buckets
2674	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2675	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2676	#[inline]
2677	unsafe fn set_ctrl_h2(&mut self, index: usize, hash: u64) {
2678	// SAFETY: The caller must uphold the safety rules for the [`RawTableInner::set_ctrl_h2`]
2679	self.set_ctrl(index, h2(hash));
2680	}
2681
2682	/// Replaces the hash in the control byte at the given index with the provided one,
2683	/// and possibly also replicates the new control byte at the end of the array of control
2684	/// bytes, returning the old control byte.
2685	///
2686	/// This function does not make any changes to the `data` parts of the table,
2687	/// or any changes to the the `items` or `growth_left` field of the table.
2688	///
2689	/// # Safety
2690	///
2691	/// The safety rules are directly derived from the safety rules for [`RawTableInner::set_ctrl_h2`]
2692	/// and [`RawTableInner::ctrl`] methods. Thus, in order to uphold the safety contracts for both
2693	/// methods, you must observe the following rules when calling this function:
2694	///
2695	/// The* [`RawTableInner`] has already been allocated;
2696	///
2697	/// The `index` must not be greater than the `RawTableInner.bucket_mask`, i.e.*
2698	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)` must
2699	/// be no greater than the number returned by the function [`RawTableInner::buckets`].
2700	///
2701	/// Calling this function on a table that has not been allocated results in [`undefined behavior`].
2702	///
2703	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
2704	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
2705	///
2706	/// [`RawTableInner::set_ctrl_h2`]: RawTableInner::set_ctrl_h2
2707	/// [`RawTableInner::buckets`]: RawTableInner::buckets
2708	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2709	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2710	#[inline]
2711	unsafe fn replace_ctrl_h2(&mut self, index: usize, hash: u64) -> u8 {
2712	// SAFETY: The caller must uphold the safety rules for the [`RawTableInner::replace_ctrl_h2`]
2713	let prev_ctrl = *self.ctrl(index);
2714	self.set_ctrl_h2(index, hash);
2715	prev_ctrl
2716	}
2717
2718	/// Sets a control byte, and possibly also the replicated control byte at
2719	/// the end of the array.
2720	///
2721	/// This function does not make any changes to the `data` parts of the table,
2722	/// or any changes to the the `items` or `growth_left` field of the table.
2723	///
2724	/// # Safety
2725	///
2726	/// You must observe the following safety rules when calling this function:
2727	///
2728	/// The* [`RawTableInner`] has already been allocated;
2729	///
2730	/// The `index` must not be greater than the `RawTableInner.bucket_mask`, i.e.*
2731	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)` must
2732	/// be no greater than the number returned by the function [`RawTableInner::buckets`].
2733	///
2734	/// Calling this function on a table that has not been allocated results in [`undefined behavior`].
2735	///
2736	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
2737	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
2738	///
2739	/// [`RawTableInner::buckets`]: RawTableInner::buckets
2740	/// [`Bucket::as_ptr`]: Bucket::as_ptr
2741	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2742	#[inline]
2743	unsafe fn set_ctrl(&mut self, index: usize, ctrl: u8) {
2744	// Replicate the first Group::WIDTH control bytes at the end of
2745	// the array without using a branch. If the tables smaller than
2746	// the group width (self.buckets() < Group::WIDTH),
2747	// `index2 = Group::WIDTH + index`, otherwise `index2` is:
2748	//
2749	// - If index >= Group::WIDTH then index == index2.
2750	// - Otherwise index2 == self.bucket_mask + 1 + index.
2751	//
2752	// The very last replicated control byte is never actually read because
2753	// we mask the initial index for unaligned loads, but we write it
2754	// anyways because it makes the set_ctrl implementation simpler.
2755	//
2756	// If there are fewer buckets than Group::WIDTH then this code will
2757	// replicate the buckets at the end of the trailing group. For example
2758	// with 2 buckets and a group size of 4, the control bytes will look
2759	// like this:
2760	//
2761	// Real \| Replicated
2762	// ---------------------------------------------
2763	// \| [A] \| [B] \| [EMPTY] \| [EMPTY] \| [A] \| [B] \|
2764	// ---------------------------------------------
2765
2766	// This is the same as `(index.wrapping_sub(Group::WIDTH)) % self.buckets() + Group::WIDTH`
2767	// because the number of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
2768	let index2 = ((index.wrapping_sub(Group::WIDTH)) & self.bucket_mask) + Group::WIDTH;
2769
2770	// SAFETY: The caller must uphold the safety rules for the [`RawTableInner::set_ctrl`]
2771	*self.ctrl(index) = ctrl;
2772	*self.ctrl(index2) = ctrl;
2773	}
2774
2775	/// Returns a pointer to a control byte.
2776	///
2777	/// # Safety
2778	///
2779	/// For the allocated [`RawTableInner`], the result is [`Undefined Behavior`],
2780	/// if the `index` is greater than the `self.bucket_mask + 1 + Group::WIDTH`.
2781	/// In that case, calling this function with `index == self.bucket_mask + 1 + Group::WIDTH`
2782	/// will return a pointer to the end of the allocated table and it is useless on its own.
2783	///
2784	/// Calling this function with `index >= self.bucket_mask + 1 + Group::WIDTH` on a
2785	/// table that has not been allocated results in [`Undefined Behavior`].
2786	///
2787	/// So to satisfy both requirements you should always follow the rule that
2788	/// `index < self.bucket_mask + 1 + Group::WIDTH`
2789	///
2790	/// Calling this function on [`RawTableInner`] that are not already allocated is safe
2791	/// for read-only purpose.
2792	///
2793	/// See also [`Bucket::as_ptr()`] method, for more information about of properly removing
2794	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
2795	///
2796	/// [`Bucket::as_ptr()`]: Bucket::as_ptr()
2797	/// [`Undefined Behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2798	#[inline]
2799	unsafe fn ctrl(&self, index: usize) -> *mut u8 {
2800	debug_assert!(index < self.num_ctrl_bytes());
2801	// SAFETY: The caller must uphold the safety rules for the [`RawTableInner::ctrl`]
2802	self.ctrl.as_ptr().add(index)
2803	}
2804
2805	#[inline]
2806	fn buckets(&self) -> usize {
2807	self.bucket_mask + `1`
2808	}
2809
2810	/// Checks whether the bucket at `index` is full.
2811	///
2812	/// # Safety
2813	///
2814	/// The caller must ensure `index` is less than the number of buckets.
2815	#[inline]
2816	unsafe fn is_bucket_full(&self, index: usize) -> bool {
2817	debug_assert!(index < self.buckets());
2818	is_full(*self.ctrl(index))
2819	}
2820
2821	#[inline]
2822	fn num_ctrl_bytes(&self) -> usize {
2823	self.bucket_mask + `1` + Group::WIDTH
2824	}
2825
2826	#[inline]
2827	fn is_empty_singleton(&self) -> bool {
2828	self.bucket_mask == `0`
2829	}
2830
2831	/// Attempts to allocate a new hash table with at least enough capacity
2832	/// for inserting the given number of elements without reallocating,
2833	/// and return it inside ScopeGuard to protect against panic in the hash
2834	/// function.
2835	///
2836	/// # Note
2837	///
2838	/// It is recommended (but not required):
2839	///
2840	/// That the new table's `capacity` be greater than or equal to `self.items`.*
2841	///
2842	/// The `alloc` is the same* [`Allocator`] as the `Allocator` used
2843	/// to allocate this table.
2844	///
2845	/// The `table_layout` is the same* [`TableLayout`] as the `TableLayout` used
2846	/// to allocate this table.
2847	///
2848	/// If `table_layout` does not match the `TableLayout` that was used to allocate
2849	/// this table, then using `mem::swap` with the `self` and the new table returned
2850	/// by this function results in [`undefined behavior`].
2851	///
2852	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2853	#[allow(clippy::mut_mut)]
2854	#[inline]
2855	fn prepare_resize<'a, A>(
2856	&self,
2857	alloc: &'a A,
2858	table_layout: TableLayout,
2859	capacity: usize,
2860	fallibility: Fallibility,
2861	) -> Result<crate::scopeguard::ScopeGuard<Self, impl FnMut(&mut Self) + 'a>, TryReserveError>
2862	where
2863	A: Allocator,
2864	{
2865	debug_assert!(self.items <= capacity);
2866
2867	// Allocate and initialize the new table.
2868	let new_table =
2869	RawTableInner::fallible_with_capacity(alloc, table_layout, capacity, fallibility)?;
2870
2871	// The hash function may panic, in which case we simply free the new
2872	// table without dropping any elements that may have been copied into
2873	// it.
2874	//
2875	// This guard is also used to free the old table on success, see
2876	// the comment at the bottom of this function.
2877	Ok(guard(new_table, move \|self_\| {
2878	if !self_.is_empty_singleton() {
2879	// SAFETY:
2880	// 1. We have checked that our table is allocated.
2881	// 2. We know for sure that the `alloc` and `table_layout` matches the
2882	// [`Allocator`] and [`TableLayout`] used to allocate this table.
2883	unsafe { self_.free_buckets(alloc, table_layout) };
2884	}
2885	}))
2886	}
2887
2888	/// Reserves or rehashes to make room for `additional` more elements.
2889	///
2890	/// This uses dynamic dispatch to reduce the amount of
2891	/// code generated, but it is eliminated by LLVM optimizations when inlined.
2892	///
2893	/// # Safety
2894	///
2895	/// If any of the following conditions are violated, the result is
2896	/// [`undefined behavior`]:
2897	///
2898	/// The `alloc` must be the same* [`Allocator`] as the `Allocator` used
2899	/// to allocate this table.
2900	///
2901	/// The `layout` must be the same* [`TableLayout`] as the `TableLayout`
2902	/// used to allocate this table.
2903	///
2904	/// The `drop` function (`fn(mut u8)`) must be the actual drop function of
2905	/// the elements stored in the table.
2906	///
2907	/// The* [`RawTableInner`] must have properly initialized control bytes.
2908	///
2909	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2910	#[allow(clippy::inline_always)]
2911	#[inline(always)]
2912	unsafe fn reserve_rehash_inner<A>(
2913	&mut self,
2914	alloc: &A,
2915	additional: usize,
2916	hasher: &dyn Fn(&mut Self, usize) -> u64,
2917	fallibility: Fallibility,
2918	layout: TableLayout,
2919	drop: Option<fn(*mut u8)>,
2920	) -> Result<(), TryReserveError>
2921	where
2922	A: Allocator,
2923	{
2924	// Avoid `Option::ok_or_else` because it bloats LLVM IR.
2925	let new_items = match self.items.checked_add(additional) {
2926	Some(new_items) => new_items,
2927	None => return Err(fallibility.capacity_overflow()),
2928	};
2929	let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
2930	if new_items <= full_capacity / `2` {
2931	// Rehash in-place without re-allocating if we have plenty of spare
2932	// capacity that is locked up due to DELETED entries.
2933
2934	// SAFETY:
2935	// 1. We know for sure that `[`RawTableInner`]` has already been allocated
2936	// (since new_items <= full_capacity / 2);
2937	// 2. The caller ensures that `drop` function is the actual drop function of
2938	// the elements stored in the table.
2939	// 3. The caller ensures that `layout` matches the [`TableLayout`] that was
2940	// used to allocate this table.
2941	// 4. The caller ensures that the control bytes of the `RawTableInner`
2942	// are already initialized.
2943	self.rehash_in_place(hasher, layout.size, drop);
2944	Ok(())
2945	} else {
2946	// Otherwise, conservatively resize to at least the next size up
2947	// to avoid churning deletes into frequent rehashes.
2948	//
2949	// SAFETY:
2950	// 1. We know for sure that `capacity >= self.items`.
2951	// 2. The caller ensures that `alloc` and `layout` matches the [`Allocator`] and
2952	// [`TableLayout`] that were used to allocate this table.
2953	// 3. The caller ensures that the control bytes of the `RawTableInner`
2954	// are already initialized.
2955	self.resize_inner(
2956	alloc,
2957	usize::max(new_items, full_capacity + `1`),
2958	hasher,
2959	fallibility,
2960	layout,
2961	)
2962	}
2963	}
2964
2965	/// Returns an iterator over full buckets indices in the table.
2966	///
2967	/// # Safety
2968	///
2969	/// Behavior is undefined if any of the following conditions are violated:
2970	///
2971	/// The caller has to ensure that the `RawTableInner` outlives the*
2972	/// `FullBucketsIndices`. Because we cannot make the `next` method
2973	/// unsafe on the `FullBucketsIndices` struct, we have to make the
2974	/// `full_buckets_indices` method unsafe.
2975	///
2976	/// The* [`RawTableInner`] must have properly initialized control bytes.
2977	#[inline(always)]
2978	unsafe fn full_buckets_indices(&self) -> FullBucketsIndices {
2979	// SAFETY:
2980	// 1. Since the caller of this function ensures that the control bytes
2981	// are properly initialized and `self.ctrl(0)` points to the start
2982	// of the array of control bytes, therefore: `ctrl` is valid for reads,
2983	// properly aligned to `Group::WIDTH` and points to the properly initialized
2984	// control bytes.
2985	// 2. The value of `items` is equal to the amount of data (values) added
2986	// to the table.
2987	//
2988	// `ctrl` points here (to the start
2989	// of the first control byte `CT0`)
2990	// ∨
2991	// [Pad], T_n, ..., T1, T0, \|CT0, CT1, ..., CT_n\|, Group::WIDTH
2992	// \________ ________/
2993	// \/
2994	// `n = buckets - 1`, i.e. `RawTableInner::buckets() - 1`
2995	//
2996	// where: T0...T_n - our stored data;
2997	// CT0...CT_n - control bytes or metadata for `data`.
2998	let ctrl = NonNull::new_unchecked(self.ctrl(`0`));
2999
3000	FullBucketsIndices {
3001	// Load the first group
3002	// SAFETY: See explanation above.
3003	current_group: Group::load_aligned(ctrl.as_ptr()).match_full().into_iter(),
3004	group_first_index: `0`,
3005	ctrl,
3006	items: self.items,
3007	}
3008	}
3009
3010	/// Allocates a new table of a different size and moves the contents of the
3011	/// current table into it.
3012	///
3013	/// This uses dynamic dispatch to reduce the amount of
3014	/// code generated, but it is eliminated by LLVM optimizations when inlined.
3015	///
3016	/// # Safety
3017	///
3018	/// If any of the following conditions are violated, the result is
3019	/// [`undefined behavior`]:
3020	///
3021	/// The `alloc` must be the same* [`Allocator`] as the `Allocator` used
3022	/// to allocate this table;
3023	///
3024	/// The `layout` must be the same* [`TableLayout`] as the `TableLayout`
3025	/// used to allocate this table;
3026	///
3027	/// The* [`RawTableInner`] must have properly initialized control bytes.
3028	///
3029	/// The caller of this function must ensure that `capacity >= self.items`
3030	/// otherwise:
3031	///
3032	/// If `self.items != 0`, calling of this function with `capacity == 0`*
3033	/// results in [`undefined behavior`].
3034	///
3035	/// If `capacity_to_buckets(capacity) < Group::WIDTH` and*
3036	/// `self.items > capacity_to_buckets(capacity)` calling this function
3037	/// results in [`undefined behavior`].
3038	///
3039	/// If `capacity_to_buckets(capacity) >= Group::WIDTH` and*
3040	/// `self.items > capacity_to_buckets(capacity)` calling this function
3041	/// are never return (will go into an infinite loop).
3042	///
3043	/// Note: It is recommended (but not required) that the new table's `capacity`
3044	/// be greater than or equal to `self.items`. In case if `capacity <= self.items`
3045	/// this function can never return. See [`RawTableInner::find_insert_slot`] for
3046	/// more information.
3047	///
3048	/// [`RawTableInner::find_insert_slot`]: RawTableInner::find_insert_slot
3049	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3050	#[allow(clippy::inline_always)]
3051	#[inline(always)]
3052	unsafe fn resize_inner<A>(
3053	&mut self,
3054	alloc: &A,
3055	capacity: usize,
3056	hasher: &dyn Fn(&mut Self, usize) -> u64,
3057	fallibility: Fallibility,
3058	layout: TableLayout,
3059	) -> Result<(), TryReserveError>
3060	where
3061	A: Allocator,
3062	{
3063	// SAFETY: We know for sure that `alloc` and `layout` matches the [`Allocator`] and [`TableLayout`]
3064	// that were used to allocate this table.
3065	let mut new_table = self.prepare_resize(alloc, layout, capacity, fallibility)?;
3066
3067	// SAFETY: We know for sure that RawTableInner will outlive the
3068	// returned `FullBucketsIndices` iterator, and the caller of this
3069	// function ensures that the control bytes are properly initialized.
3070	for full_byte_index in self.full_buckets_indices() {
3071	// This may panic.
3072	let hash = hasher(self, full_byte_index);
3073
3074	// SAFETY:
3075	// We can use a simpler version of insert() here since:
3076	// 1. There are no DELETED entries.
3077	// 2. We know there is enough space in the table.
3078	// 3. All elements are unique.
3079	// 4. The caller of this function guarantees that `capacity > 0`
3080	// so `new_table` must already have some allocated memory.
3081	// 5. We set `growth_left` and `items` fields of the new table
3082	// after the loop.
3083	// 6. We insert into the table, at the returned index, the data
3084	// matching the given hash immediately after calling this function.
3085	let (new_index, _) = new_table.prepare_insert_slot(hash);
3086
3087	// SAFETY:
3088	//
3089	// `src` is valid for reads of `layout.size` bytes, since the*
3090	// table is alive and the `full_byte_index` is guaranteed to be
3091	// within bounds (see `FullBucketsIndices::next_impl`);
3092	//
3093	// `dst` is valid for writes of `layout.size` bytes, since the*
3094	// caller ensures that `table_layout` matches the [`TableLayout`]
3095	// that was used to allocate old table and we have the `new_index`
3096	// returned by `prepare_insert_slot`.
3097	//
3098	// Both `src` and `dst` are properly aligned.*
3099	//
3100	// Both `src` and `dst` point to different region of memory.*
3101	ptr::copy_nonoverlapping(
3102	self.bucket_ptr(full_byte_index, layout.size),
3103	new_table.bucket_ptr(new_index, layout.size),
3104	layout.size,
3105	);
3106	}
3107
3108	// The hash function didn't panic, so we can safely set the
3109	// `growth_left` and `items` fields of the new table.
3110	new_table.growth_left -= self.items;
3111	new_table.items = self.items;
3112
3113	// We successfully copied all elements without panicking. Now replace
3114	// self with the new table. The old table will have its memory freed but
3115	// the items will not be dropped (since they have been moved into the
3116	// new table).
3117	// SAFETY: The caller ensures that `table_layout` matches the [`TableLayout`]
3118	// that was used to allocate this table.
3119	mem::swap(self, &mut new_table);
3120
3121	Ok(())
3122	}
3123
3124	/// Rehashes the contents of the table in place (i.e. without changing the
3125	/// allocation).
3126	///
3127	/// If `hasher` panics then some the table's contents may be lost.
3128	///
3129	/// This uses dynamic dispatch to reduce the amount of
3130	/// code generated, but it is eliminated by LLVM optimizations when inlined.
3131	///
3132	/// # Safety
3133	///
3134	/// If any of the following conditions are violated, the result is [`undefined behavior`]:
3135	///
3136	/// The `size_of` must be equal to the size of the elements stored in the table;*
3137	///
3138	/// The `drop` function (`fn(mut u8)`) must be the actual drop function of
3139	/// the elements stored in the table.
3140	///
3141	/// The* [`RawTableInner`] has already been allocated;
3142	///
3143	/// The* [`RawTableInner`] must have properly initialized control bytes.
3144	///
3145	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3146	#[allow(clippy::inline_always)]
3147	#[cfg_attr(feature = "inline-more", inline(always))]
3148	#[cfg_attr(not(feature = "inline-more"), inline)]
3149	unsafe fn rehash_in_place(
3150	&mut self,
3151	hasher: &dyn Fn(&mut Self, usize) -> u64,
3152	size_of: usize,
3153	drop: Option<fn(*mut u8)>,
3154	) {
3155	// If the hash function panics then properly clean up any elements
3156	// that we haven't rehashed yet. We unfortunately can't preserve the
3157	// element since we lost their hash and have no way of recovering it
3158	// without risking another panic.
3159	self.prepare_rehash_in_place();
3160
3161	let mut guard = guard(self, move \|self_\| {
3162	if let Some(drop) = drop {
3163	for i in `0`..self_.buckets() {
3164	if *self_.ctrl(i) == DELETED {
3165	self_.set_ctrl(i, EMPTY);
3166	drop(self_.bucket_ptr(i, size_of));
3167	self_.items -= `1`;
3168	}
3169	}
3170	}
3171	self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items;
3172	});
3173
3174	// At this point, DELETED elements are elements that we haven't
3175	// rehashed yet. Find them and re-insert them at their ideal
3176	// position.
3177	'outer: for i in `0`..guard.buckets() {
3178	if *guard.ctrl(i) != DELETED {
3179	continue;
3180	}
3181
3182	let i_p = guard.bucket_ptr(i, size_of);
3183
3184	'inner: loop {
3185	// Hash the current item
3186	let hash = hasher(*guard, i);
3187
3188	// Search for a suitable place to put it
3189	//
3190	// SAFETY: Caller of this function ensures that the control bytes
3191	// are properly initialized.
3192	let new_i = guard.find_insert_slot(hash).index;
3193
3194	// Probing works by scanning through all of the control
3195	// bytes in groups, which may not be aligned to the group
3196	// size. If both the new and old position fall within the
3197	// same unaligned group, then there is no benefit in moving
3198	// it and we can just continue to the next item.
3199	if likely(guard.is_in_same_group(i, new_i, hash)) {
3200	guard.set_ctrl_h2(i, hash);
3201	continue 'outer;
3202	}
3203
3204	let new_i_p = guard.bucket_ptr(new_i, size_of);
3205
3206	// We are moving the current item to a new position. Write
3207	// our H2 to the control byte of the new position.
3208	let prev_ctrl = guard.replace_ctrl_h2(new_i, hash);
3209	if prev_ctrl == EMPTY {
3210	guard.set_ctrl(i, EMPTY);
3211	// If the target slot is empty, simply move the current
3212	// element into the new slot and clear the old control
3213	// byte.
3214	ptr::copy_nonoverlapping(i_p, new_i_p, size_of);
3215	continue 'outer;
3216	} else {
3217	// If the target slot is occupied, swap the two elements
3218	// and then continue processing the element that we just
3219	// swapped into the old slot.
3220	debug_assert_eq!(prev_ctrl, DELETED);
3221	ptr::swap_nonoverlapping(i_p, new_i_p, size_of);
3222	continue 'inner;
3223	}
3224	}
3225	}
3226
3227	guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items;
3228
3229	mem::forget(guard);
3230	}
3231
3232	/// Deallocates the table without dropping any entries.
3233	///
3234	/// # Note
3235	///
3236	/// This function must be called only after [`drop_elements`](RawTableInner::drop_elements),
3237	/// else it can lead to leaking of memory. Also calling this function automatically
3238	/// makes invalid (dangling) all instances of buckets ([`Bucket`]) and makes invalid
3239	/// (dangling) the `ctrl` field of the table.
3240	///
3241	/// # Safety
3242	///
3243	/// If any of the following conditions are violated, the result is [`Undefined Behavior`]:
3244	///
3245	/// The* [`RawTableInner`] has already been allocated;
3246	///
3247	/// The `alloc` must be the same* [`Allocator`] as the `Allocator` that was used
3248	/// to allocate this table.
3249	///
3250	/// The `table_layout` must be the same* [`TableLayout`] as the `TableLayout` that was used
3251	/// to allocate this table.
3252	///
3253	/// See also [`GlobalAlloc::dealloc`] or [`Allocator::deallocate`] for more information.
3254	///
3255	/// [`Undefined Behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3256	/// [`GlobalAlloc::dealloc`]: https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html#tymethod.dealloc
3257	/// [`Allocator::deallocate`]: https://doc.rust-lang.org/alloc/alloc/trait.Allocator.html#tymethod.deallocate
3258	#[inline]
3259	unsafe fn free_buckets<A>(&mut self, alloc: &A, table_layout: TableLayout)
3260	where
3261	A: Allocator,
3262	{
3263	// SAFETY: The caller must uphold the safety contract for `free_buckets`
3264	// method.
3265	let (ptr, layout) = self.allocation_info(table_layout);
3266	alloc.deallocate(ptr, layout);
3267	}
3268
3269	/// Returns a pointer to the allocated memory and the layout that was used to
3270	/// allocate the table.
3271	///
3272	/// # Safety
3273	///
3274	/// Caller of this function must observe the following safety rules:
3275	///
3276	/// The* [`RawTableInner`] has already been allocated, otherwise
3277	/// calling this function results in [`undefined behavior`]
3278	///
3279	/// The `table_layout` must be the same* [`TableLayout`] as the `TableLayout`
3280	/// that was used to allocate this table. Failure to comply with this condition
3281	/// may result in [`undefined behavior`].
3282	///
3283	/// See also [`GlobalAlloc::dealloc`] or [`Allocator::deallocate`] for more information.
3284	///
3285	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3286	/// [`GlobalAlloc::dealloc`]: https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html#tymethod.dealloc
3287	/// [`Allocator::deallocate`]: https://doc.rust-lang.org/alloc/alloc/trait.Allocator.html#tymethod.deallocate
3288	#[inline]
3289	unsafe fn allocation_info(&self, table_layout: TableLayout) -> (NonNull<u8>, Layout) {
3290	debug_assert!(
3291	!self.is_empty_singleton(),
3292	"this function can only be called on non-empty tables"
3293	);
3294
3295	// Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
3296	let (layout, ctrl_offset) = match table_layout.calculate_layout_for(self.buckets()) {
3297	Some(lco) => lco,
3298	None => unsafe { hint::unreachable_unchecked() },
3299	};
3300	(
3301	// SAFETY: The caller must uphold the safety contract for `allocation_info` method.
3302	unsafe { NonNull::new_unchecked(self.ctrl.as_ptr().sub(ctrl_offset)) },
3303	layout,
3304	)
3305	}
3306
3307	/// Returns a pointer to the allocated memory and the layout that was used to
3308	/// allocate the table. If [`RawTableInner`] has not been allocated, this
3309	/// function return `dangling` pointer and `()` (unit) layout.
3310	///
3311	/// # Safety
3312	///
3313	/// The `table_layout` must be the same [`TableLayout`] as the `TableLayout`
3314	/// that was used to allocate this table. Failure to comply with this condition
3315	/// may result in [`undefined behavior`].
3316	///
3317	/// See also [`GlobalAlloc::dealloc`] or [`Allocator::deallocate`] for more information.
3318	///
3319	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3320	/// [`GlobalAlloc::dealloc`]: https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html#tymethod.dealloc
3321	/// [`Allocator::deallocate`]: https://doc.rust-lang.org/alloc/alloc/trait.Allocator.html#tymethod.deallocate
3322	#[cfg(feature = "raw")]
3323	unsafe fn allocation_info_or_zero(&self, table_layout: TableLayout) -> (NonNull<u8>, Layout) {
3324	if self.is_empty_singleton() {
3325	(NonNull::dangling(), Layout::new::<()>())
3326	} else {
3327	// SAFETY:
3328	// 1. We have checked that our table is allocated.
3329	// 2. The caller ensures that `table_layout` matches the [`TableLayout`]
3330	// that was used to allocate this table.
3331	unsafe { self.allocation_info(table_layout) }
3332	}
3333	}
3334
3335	/// Marks all table buckets as empty without dropping their contents.
3336	#[inline]
3337	fn clear_no_drop(&mut self) {
3338	if !self.is_empty_singleton() {
3339	unsafe {
3340	self.ctrl(`0`).write_bytes(EMPTY, self.num_ctrl_bytes());
3341	}
3342	}
3343	self.items = `0`;
3344	self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
3345	}
3346
3347	/// Erases the [`Bucket`]'s control byte at the given index so that it does not
3348	/// triggered as full, decreases the `items` of the table and, if it can be done,
3349	/// increases `self.growth_left`.
3350	///
3351	/// This function does not actually erase / drop the [`Bucket`] itself, i.e. it
3352	/// does not make any changes to the `data` parts of the table. The caller of this
3353	/// function must take care to properly drop the `data`, otherwise calling this
3354	/// function may result in a memory leak.
3355	///
3356	/// # Safety
3357	///
3358	/// You must observe the following safety rules when calling this function:
3359	///
3360	/// The* [`RawTableInner`] has already been allocated;
3361	///
3362	/// It must be the full control byte at the given position;*
3363	///
3364	/// The `index` must not be greater than the `RawTableInner.bucket_mask`, i.e.*
3365	/// `index <= RawTableInner.bucket_mask` or, in other words, `(index + 1)` must
3366	/// be no greater than the number returned by the function [`RawTableInner::buckets`].
3367	///
3368	/// Calling this function on a table that has not been allocated results in [`undefined behavior`].
3369	///
3370	/// Calling this function on a table with no elements is unspecified, but calling subsequent
3371	/// functions is likely to result in [`undefined behavior`] due to overflow subtraction
3372	/// (`self.items -= 1 cause overflow when self.items == 0`).
3373	///
3374	/// See also [`Bucket::as_ptr`] method, for more information about of properly removing
3375	/// or saving `data element` from / into the [`RawTable`] / [`RawTableInner`].
3376	///
3377	/// [`RawTableInner::buckets`]: RawTableInner::buckets
3378	/// [`Bucket::as_ptr`]: Bucket::as_ptr
3379	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3380	#[inline]
3381	unsafe fn erase(&mut self, index: usize) {
3382	debug_assert!(self.is_bucket_full(index));
3383
3384	// This is the same as `index.wrapping_sub(Group::WIDTH) % self.buckets()` because
3385	// the number of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.
3386	let index_before = index.wrapping_sub(Group::WIDTH) & self.bucket_mask;
3387	// SAFETY:
3388	// - The caller must uphold the safety contract for `erase` method;
3389	// - `index_before` is guaranteed to be in range due to masking with `self.bucket_mask`
3390	let empty_before = Group::load(self.ctrl(index_before)).match_empty();
3391	let empty_after = Group::load(self.ctrl(index)).match_empty();
3392
3393	// Inserting and searching in the map is performed by two key functions:
3394	//
3395	// - The `find_insert_slot` function that looks up the index of any `EMPTY` or `DELETED`
3396	// slot in a group to be able to insert. If it doesn't find an `EMPTY` or `DELETED`
3397	// slot immediately in the first group, it jumps to the next `Group` looking for it,
3398	// and so on until it has gone through all the groups in the control bytes.
3399	//
3400	// - The `find_inner` function that looks for the index of the desired element by looking
3401	// at all the `FULL` bytes in the group. If it did not find the element right away, and
3402	// there is no `EMPTY` byte in the group, then this means that the `find_insert_slot`
3403	// function may have found a suitable slot in the next group. Therefore, `find_inner`
3404	// jumps further, and if it does not find the desired element and again there is no `EMPTY`
3405	// byte, then it jumps further, and so on. The search stops only if `find_inner` function
3406	// finds the desired element or hits an `EMPTY` slot/byte.
3407	//
3408	// Accordingly, this leads to two consequences:
3409	//
3410	// - The map must have `EMPTY` slots (bytes);
3411	//
3412	// - You can't just mark the byte to be erased as `EMPTY`, because otherwise the `find_inner`
3413	// function may stumble upon an `EMPTY` byte before finding the desired element and stop
3414	// searching.
3415	//
3416	// Thus it is necessary to check all bytes after and before the erased element. If we are in
3417	// a contiguous `Group` of `FULL` or `DELETED` bytes (the number of `FULL` or `DELETED` bytes
3418	// before and after is greater than or equal to `Group::WIDTH`), then we must mark our byte as
3419	// `DELETED` in order for the `find_inner` function to go further. On the other hand, if there
3420	// is at least one `EMPTY` slot in the `Group`, then the `find_inner` function will still stumble
3421	// upon an `EMPTY` byte, so we can safely mark our erased byte as `EMPTY` as well.
3422	//
3423	// Finally, since `index_before == (index.wrapping_sub(Group::WIDTH) & self.bucket_mask) == index`
3424	// and given all of the above, tables smaller than the group width (self.buckets() < Group::WIDTH)
3425	// cannot have `DELETED` bytes.
3426	//
3427	// Note that in this context `leading_zeros` refers to the bytes at the end of a group, while
3428	// `trailing_zeros` refers to the bytes at the beginning of a group.
3429	let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
3430	DELETED
3431	} else {
3432	self.growth_left += `1`;
3433	EMPTY
3434	};
3435	// SAFETY: the caller must uphold the safety contract for `erase` method.
3436	self.set_ctrl(index, ctrl);
3437	self.items -= `1`;
3438	}
3439	}
3440
3441	impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> {
3442	fn clone(&self) -> Self {
3443	if self.table.is_empty_singleton() {
3444	Self::new_in(self.alloc.clone())
3445	} else {
3446	unsafe {
3447	// Avoid `Result::ok_or_else` because it bloats LLVM IR.
3448	//
3449	// SAFETY: This is safe as we are taking the size of an already allocated table
3450	// and therefore сapacity overflow cannot occur, `self.table.buckets()` is power
3451	// of two and all allocator errors will be caught inside `RawTableInner::new_uninitialized`.
3452	let mut new_table = match Self::new_uninitialized(
3453	self.alloc.clone(),
3454	self.table.buckets(),
3455	Fallibility::Infallible,
3456	) {
3457	Ok(table) => table,
3458	Err(_) => hint::unreachable_unchecked(),
3459	};
3460
3461	// Cloning elements may fail (the clone function may panic). But we don't
3462	// need to worry about uninitialized control bits, since:
3463	// 1. The number of items (elements) in the table is zero, which means that
3464	// the control bits will not be readed by Drop function.
3465	// 2. The `clone_from_spec` method will first copy all control bits from
3466	// `self` (thus initializing them). But this will not affect the `Drop`
3467	// function, since the `clone_from_spec` function sets `items` only after
3468	// successfully clonning all elements.
3469	new_table.clone_from_spec(self);
3470	new_table
3471	}
3472	}
3473	}
3474
3475	fn clone_from(&mut self, source: &Self) {
3476	if source.table.is_empty_singleton() {
3477	let mut old_inner = mem::replace(&mut self.table, RawTableInner::NEW);
3478	unsafe {
3479	// SAFETY:
3480	// 1. We call the function only once;
3481	// 2. We know for sure that `alloc` and `table_layout` matches the [`Allocator`]
3482	// and [`TableLayout`] that were used to allocate this table.
3483	// 3. If any elements' drop function panics, then there will only be a memory leak,
3484	// because we have replaced the inner table with a new one.
3485	old_inner.drop_inner_table::<T, _>(&self.alloc, Self::TABLE_LAYOUT);
3486	}
3487	} else {
3488	unsafe {
3489	// Make sure that if any panics occurs, we clear the table and
3490	// leave it in an empty state.
3491	let mut self_ = guard(self, \|self_\| {
3492	self_.clear_no_drop();
3493	});
3494
3495	// First, drop all our elements without clearing the control
3496	// bytes. If this panics then the scope guard will clear the
3497	// table, leaking any elements that were not dropped yet.
3498	//
3499	// This leak is unavoidable: we can't try dropping more elements
3500	// since this could lead to another panic and abort the process.
3501	//
3502	// SAFETY: If something gets wrong we clear our table right after
3503	// dropping the elements, so there is no double drop, since `items`
3504	// will be equal to zero.
3505	self_.table.drop_elements::<T>();
3506
3507	// If necessary, resize our table to match the source.
3508	if self_.buckets() != source.buckets() {
3509	let new_inner = match RawTableInner::new_uninitialized(
3510	&self_.alloc,
3511	Self::TABLE_LAYOUT,
3512	source.buckets(),
3513	Fallibility::Infallible,
3514	) {
3515	Ok(table) => table,
3516	Err(_) => hint::unreachable_unchecked(),
3517	};
3518	// Replace the old inner with new uninitialized one. It's ok, since if something gets
3519	// wrong `ScopeGuard` will initialize all control bytes and leave empty table.
3520	let mut old_inner = mem::replace(&mut self_.table, new_inner);
3521	if !old_inner.is_empty_singleton() {
3522	// SAFETY:
3523	// 1. We have checked that our table is allocated.
3524	// 2. We know for sure that `alloc` and `table_layout` matches
3525	// the [`Allocator`] and [`TableLayout`] that were used to allocate this table.
3526	old_inner.free_buckets(&self_.alloc, Self::TABLE_LAYOUT);
3527	}
3528	}
3529
3530	// Cloning elements may fail (the clone function may panic), but the `ScopeGuard`
3531	// inside the `clone_from_impl` function will take care of that, dropping all
3532	// cloned elements if necessary. Our `ScopeGuard` will clear the table.
3533	self_.clone_from_spec(source);
3534
3535	// Disarm the scope guard if cloning was successful.
3536	ScopeGuard::into_inner(self_);
3537	}
3538	}
3539	}
3540	}
3541
3542	/// Specialization of `clone_from` for `Copy` types
3543	trait RawTableClone {
3544	unsafe fn clone_from_spec(&mut self, source: &Self);
3545	}
3546	impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
3547	default_fn! {
3548	#[cfg_attr(feature = "inline-more", inline)]
3549	unsafe fn clone_from_spec(&mut self, source: &Self) {
3550	self.clone_from_impl(source);
3551	}
3552	}
3553	}
3554	#[cfg(feature = "nightly")]
3555	impl<T: Copy, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
3556	#[cfg_attr(feature = "inline-more", inline)]
3557	unsafe fn clone_from_spec(&mut self, source: &Self) {
3558	source
3559	.table
3560	.ctrl(`0`)
3561	.copy_to_nonoverlapping(self.table.ctrl(`0`), self.table.num_ctrl_bytes());
3562	source
3563	.data_start()
3564	.as_ptr()
3565	.copy_to_nonoverlapping(self.data_start().as_ptr(), self.table.buckets());
3566
3567	self.table.items = source.table.items;
3568	self.table.growth_left = source.table.growth_left;
3569	}
3570	}
3571
3572	impl<T: Clone, A: Allocator + Clone> RawTable<T, A> {
3573	/// Common code for clone and clone_from. Assumes:
3574	/// - `self.buckets() == source.buckets()`.
3575	/// - Any existing elements have been dropped.
3576	/// - The control bytes are not initialized yet.
3577	#[cfg_attr(feature = "inline-more", inline)]
3578	unsafe fn clone_from_impl(&mut self, source: &Self) {
3579	// Copy the control bytes unchanged. We do this in a single pass
3580	source
3581	.table
3582	.ctrl(`0`)
3583	.copy_to_nonoverlapping(self.table.ctrl(`0`), self.table.num_ctrl_bytes());
3584
3585	// The cloning of elements may panic, in which case we need
3586	// to make sure we drop only the elements that have been
3587	// cloned so far.
3588	let mut guard = guard((`0`, &mut *self), \|(index, self_)\| {
3589	if T::NEEDS_DROP {
3590	for i in `0`..=*index {
3591	if self_.is_bucket_full(i) {
3592	self_.bucket(i).drop();
3593	}
3594	}
3595	}
3596	});
3597
3598	for from in source.iter() {
3599	let index = source.bucket_index(&from);
3600	let to = guard.1.bucket(index);
3601	to.write(from.as_ref().clone());
3602
3603	// Update the index in case we need to unwind.
3604	guard.0 = index;
3605	}
3606
3607	// Successfully cloned all items, no need to clean up.
3608	mem::forget(guard);
3609
3610	self.table.items = source.table.items;
3611	self.table.growth_left = source.table.growth_left;
3612	}
3613
3614	/// Variant of `clone_from` to use when a hasher is available.
3615	#[cfg(feature = "raw")]
3616	pub fn clone_from_with_hasher(&mut self, source: &Self, hasher: impl Fn(&T) -> u64) {
3617	// If we have enough capacity in the table, just clear it and insert
3618	// elements one by one. We don't do this if we have the same number of
3619	// buckets as the source since we can just copy the contents directly
3620	// in that case.
3621	if self.table.buckets() != source.table.buckets()
3622	&& bucket_mask_to_capacity(self.table.bucket_mask) >= source.len()
3623	{
3624	self.clear();
3625
3626	let mut guard_self = guard(&mut *self, \|self_\| {
3627	// Clear the partially copied table if a panic occurs, otherwise
3628	// items and growth_left will be out of sync with the contents
3629	// of the table.
3630	self_.clear();
3631	});
3632
3633	unsafe {
3634	for item in source.iter() {
3635	// This may panic.
3636	let item = item.as_ref().clone();
3637	let hash = hasher(&item);
3638
3639	// We can use a simpler version of insert() here since:
3640	// - there are no DELETED entries.
3641	// - we know there is enough space in the table.
3642	// - all elements are unique.
3643	let (index, _) = guard_self.table.prepare_insert_slot(hash);
3644	guard_self.bucket(index).write(item);
3645	}
3646	}
3647
3648	// Successfully cloned all items, no need to clean up.
3649	mem::forget(guard_self);
3650
3651	self.table.items = source.table.items;
3652	self.table.growth_left -= source.table.items;
3653	} else {
3654	self.clone_from(source);
3655	}
3656	}
3657	}
3658
3659	impl<T, A: Allocator + Default> Default for RawTable<T, A> {
3660	#[inline]
3661	fn default() -> Self {
3662	Self::new_in(alloc:Default::default())
3663	}
3664	}
3665
3666	#[cfg(feature = "nightly")]
3667	unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawTable<T, A> {
3668	#[cfg_attr(feature = "inline-more", inline)]
3669	fn drop(&mut self) {
3670	unsafe {
3671	// SAFETY:
3672	// 1. We call the function only once;
3673	// 2. We know for sure that `alloc` and `table_layout` matches the [`Allocator`]
3674	// and [`TableLayout`] that were used to allocate this table.
3675	// 3. If the drop function of any elements fails, then only a memory leak will occur,
3676	// and we don't care because we are inside the `Drop` function of the `RawTable`,
3677	// so there won't be any table left in an inconsistent state.
3678	self.table
3679	.drop_inner_table::<T, _>(&self.alloc, Self::TABLE_LAYOUT);
3680	}
3681	}
3682	}
3683	#[cfg(not(feature = "nightly"))]
3684	impl<T, A: Allocator> Drop for RawTable<T, A> {
3685	#[cfg_attr(feature = "inline-more", inline)]
3686	fn drop(&mut self) {
3687	unsafe {
3688	// SAFETY:
3689	// 1. We call the function only once;
3690	// 2. We know for sure that `alloc` and `table_layout` matches the [`Allocator`]
3691	// and [`TableLayout`] that were used to allocate this table.
3692	// 3. If the drop function of any elements fails, then only a memory leak will occur,
3693	// and we don't care because we are inside the `Drop` function of the `RawTable`,
3694	// so there won't be any table left in an inconsistent state.
3695	self.table
3696	.drop_inner_table::<T, _>(&self.alloc, Self::TABLE_LAYOUT);
3697	}
3698	}
3699	}
3700
3701	impl<T, A: Allocator> IntoIterator for RawTable<T, A> {
3702	type Item = T;
3703	type IntoIter = RawIntoIter<T, A>;
3704
3705	#[cfg_attr(feature = "inline-more", inline)]
3706	fn into_iter(self) -> RawIntoIter<T, A> {
3707	unsafe {
3708	let iter: RawIter = self.iter();
3709	self.into_iter_from(iter)
3710	}
3711	}
3712	}
3713
3714	/// Iterator over a sub-range of a table. Unlike `RawIter` this iterator does
3715	/// not track an item count.
3716	pub(crate) struct RawIterRange<T> {
3717	// Mask of full buckets in the current group. Bits are cleared from this
3718	// mask as each element is processed.
3719	current_group: BitMaskIter,
3720
3721	// Pointer to the buckets for the current group.
3722	data: Bucket<T>,
3723
3724	// Pointer to the next group of control bytes,
3725	// Must be aligned to the group size.
3726	next_ctrl: *const u8,
3727
3728	// Pointer one past the last control byte of this range.
3729	end: *const u8,
3730	}
3731
3732	impl<T> RawIterRange<T> {
3733	/// Returns a `RawIterRange` covering a subset of a table.
3734	///
3735	/// # Safety
3736	///
3737	/// If any of the following conditions are violated, the result is
3738	/// [`undefined behavior`]:
3739	///
3740	/// `ctrl` must be [valid] for reads, i.e. table outlives the `RawIterRange`;*
3741	///
3742	/// `ctrl` must be properly aligned to the group size (Group::WIDTH);*
3743	///
3744	/// `ctrl` must point to the array of properly initialized control bytes;*
3745	///
3746	/// `data` must be the* [`Bucket`] at the `ctrl` index in the table;
3747	///
3748	/// the value of `len` must be less than or equal to the number of table buckets,*
3749	/// and the returned value of `ctrl.as_ptr().add(len).offset_from(ctrl.as_ptr())`
3750	/// must be positive.
3751	///
3752	/// The `ctrl.add(len)` pointer must be either in bounds or one*
3753	/// byte past the end of the same [allocated table].
3754	///
3755	/// The `len` must be a power of two.*
3756	///
3757	/// [valid]: https://doc.rust-lang.org/std/ptr/index.html#safety
3758	/// [`undefined behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3759	#[cfg_attr(feature = "inline-more", inline)]
3760	unsafe fn new(ctrl: *const u8, data: Bucket<T>, len: usize) -> Self {
3761	debug_assert_ne!(len, `0`);
3762	debug_assert_eq!(ctrl as usize % Group::WIDTH, `0`);
3763	// SAFETY: The caller must uphold the safety rules for the [`RawIterRange::new`]
3764	let end = ctrl.add(len);
3765
3766	// Load the first group and advance ctrl to point to the next group
3767	// SAFETY: The caller must uphold the safety rules for the [`RawIterRange::new`]
3768	let current_group = Group::load_aligned(ctrl).match_full();
3769	let next_ctrl = ctrl.add(Group::WIDTH);
3770
3771	Self {
3772	current_group: current_group.into_iter(),
3773	data,
3774	next_ctrl,
3775	end,
3776	}
3777	}
3778
3779	/// Splits a `RawIterRange` into two halves.
3780	///
3781	/// Returns `None` if the remaining range is smaller than or equal to the
3782	/// group width.
3783	#[cfg_attr(feature = "inline-more", inline)]
3784	#[cfg(feature = "rayon")]
3785	pub(crate) fn split(mut self) -> (Self, Option<RawIterRange<T>>) {
3786	unsafe {
3787	if self.end <= self.next_ctrl {
3788	// Nothing to split if the group that we are current processing
3789	// is the last one.
3790	(self, None)
3791	} else {
3792	// len is the remaining number of elements after the group that
3793	// we are currently processing. It must be a multiple of the
3794	// group size (small tables are caught by the check above).
3795	let len = offset_from(self.end, self.next_ctrl);
3796	debug_assert_eq!(len % Group::WIDTH, `0`);
3797
3798	// Split the remaining elements into two halves, but round the
3799	// midpoint down in case there is an odd number of groups
3800	// remaining. This ensures that:
3801	// - The tail is at least 1 group long.
3802	// - The split is roughly even considering we still have the
3803	// current group to process.
3804	let mid = (len / `2`) & !(Group::WIDTH - `1`);
3805
3806	let tail = Self::new(
3807	self.next_ctrl.add(mid),
3808	self.data.next_n(Group::WIDTH).next_n(mid),
3809	len - mid,
3810	);
3811	debug_assert_eq!(
3812	self.data.next_n(Group::WIDTH).next_n(mid).ptr,
3813	tail.data.ptr
3814	);
3815	debug_assert_eq!(self.end, tail.end);
3816	self.end = self.next_ctrl.add(mid);
3817	debug_assert_eq!(self.end.add(Group::WIDTH), tail.next_ctrl);
3818	(self, Some(tail))
3819	}
3820	}
3821	}
3822
3823	/// # Safety
3824	/// If DO_CHECK_PTR_RANGE is false, caller must ensure that we never try to iterate
3825	/// after yielding all elements.
3826	#[cfg_attr(feature = "inline-more", inline)]
3827	unsafe fn next_impl<const DO_CHECK_PTR_RANGE: bool>(&mut self) -> Option<Bucket<T>> {
3828	loop {
3829	if let Some(index) = self.current_group.next() {
3830	return Some(self.data.next_n(index));
3831	}
3832
3833	if DO_CHECK_PTR_RANGE && self.next_ctrl >= self.end {
3834	return None;
3835	}
3836
3837	// We might read past self.end up to the next group boundary,
3838	// but this is fine because it only occurs on tables smaller
3839	// than the group size where the trailing control bytes are all
3840	// EMPTY. On larger tables self.end is guaranteed to be aligned
3841	// to the group size (since tables are power-of-two sized).
3842	self.current_group = Group::load_aligned(self.next_ctrl).match_full().into_iter();
3843	self.data = self.data.next_n(Group::WIDTH);
3844	self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
3845	}
3846	}
3847
3848	/// Folds every element into an accumulator by applying an operation,
3849	/// returning the final result.
3850	///
3851	/// `fold_impl()` takes three arguments: the number of items remaining in
3852	/// the iterator, an initial value, and a closure with two arguments: an
3853	/// 'accumulator', and an element. The closure returns the value that the
3854	/// accumulator should have for the next iteration.
3855	///
3856	/// The initial value is the value the accumulator will have on the first call.
3857	///
3858	/// After applying this closure to every element of the iterator, `fold_impl()`
3859	/// returns the accumulator.
3860	///
3861	/// # Safety
3862	///
3863	/// If any of the following conditions are violated, the result is
3864	/// [`Undefined Behavior`]:
3865	///
3866	/// The* [`RawTableInner`] / [`RawTable`] must be alive and not moved,
3867	/// i.e. table outlives the `RawIterRange`;
3868	///
3869	/// The provided `n` value must match the actual number of items*
3870	/// in the table.
3871	///
3872	/// [`Undefined Behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
3873	#[allow(clippy::while_let_on_iterator)]
3874	#[cfg_attr(feature = "inline-more", inline)]
3875	unsafe fn fold_impl<F, B>(mut self, mut n: usize, mut acc: B, mut f: F) -> B
3876	where
3877	F: FnMut(B, Bucket<T>) -> B,
3878	{
3879	loop {
3880	while let Some(index) = self.current_group.next() {
3881	// The returned `index` will always be in the range `0..Group::WIDTH`,
3882	// so that calling `self.data.next_n(index)` is safe (see detailed explanation below).
3883	debug_assert!(n != `0`);
3884	let bucket = self.data.next_n(index);
3885	acc = f(acc, bucket);
3886	n -= `1`;
3887	}
3888
3889	if n == `0` {
3890	return acc;
3891	}
3892
3893	// SAFETY: The caller of this function ensures that:
3894	//
3895	// 1. The provided `n` value matches the actual number of items in the table;
3896	// 2. The table is alive and did not moved.
3897	//
3898	// Taking the above into account, we always stay within the bounds, because:
3899	//
3900	// 1. For tables smaller than the group width (self.buckets() <= Group::WIDTH),
3901	// we will never end up in the given branch, since we should have already
3902	// yielded all the elements of the table.
3903	//
3904	// 2. For tables larger than the group width. The the number of buckets is a
3905	// power of two (2 ^ n), Group::WIDTH is also power of two (2 ^ k). Sinse
3906	// `(2 ^ n) > (2 ^ k)`, than `(2 ^ n) % (2 ^ k) = 0`. As we start from the
3907	// the start of the array of control bytes, and never try to iterate after
3908	// getting all the elements, the last `self.current_group` will read bytes
3909	// from the `self.buckets() - Group::WIDTH` index. We know also that
3910	// `self.current_group.next()` will always retun indices within the range
3911	// `0..Group::WIDTH`.
3912	//
3913	// Knowing all of the above and taking into account that we are synchronizing
3914	// the `self.data` index with the index we used to read the `self.current_group`,
3915	// the subsequent `self.data.next_n(index)` will always return a bucket with
3916	// an index number less than `self.buckets()`.
3917	//
3918	// The last `self.next_ctrl`, whose index would be `self.buckets()`, will never
3919	// actually be read, since we should have already yielded all the elements of
3920	// the table.
3921	self.current_group = Group::load_aligned(self.next_ctrl).match_full().into_iter();
3922	self.data = self.data.next_n(Group::WIDTH);
3923	self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
3924	}
3925	}
3926	}
3927
3928	// We make raw iterators unconditionally Send and Sync, and let the PhantomData
3929	// in the actual iterator implementations determine the real Send/Sync bounds.
3930	unsafe impl<T> Send for RawIterRange<T> {}
3931	unsafe impl<T> Sync for RawIterRange<T> {}
3932
3933	impl<T> Clone for RawIterRange<T> {
3934	#[cfg_attr(feature = "inline-more", inline)]
3935	fn clone(&self) -> Self {
3936	Self {
3937	data: self.data.clone(),
3938	next_ctrl: self.next_ctrl,
3939	current_group: self.current_group,
3940	end: self.end,
3941	}
3942	}
3943	}
3944
3945	impl<T> Iterator for RawIterRange<T> {
3946	type Item = Bucket<T>;
3947
3948	#[cfg_attr(feature = "inline-more", inline)]
3949	fn next(&mut self) -> Option<Bucket<T>> {
3950	unsafe {
3951	// SAFETY: We set checker flag to true.
3952	self.next_impl::<`true`>()
3953	}
3954	}
3955
3956	#[inline]
3957	fn size_hint(&self) -> (usize, Option<usize>) {
3958	// We don't have an item count, so just guess based on the range size.
3959	let remaining_buckets: usize = if self.end > self.next_ctrl {
3960	unsafe { offset_from(self.end, self.next_ctrl) }
3961	} else {
3962	`0`
3963	};
3964
3965	// Add a group width to include the group we are currently processing.
3966	(`0`, Some(Group::WIDTH + remaining_buckets))
3967	}
3968	}
3969
3970	impl<T> FusedIterator for RawIterRange<T> {}
3971
3972	/// Iterator which returns a raw pointer to every full bucket in the table.
3973	///
3974	/// For maximum flexibility this iterator is not bound by a lifetime, but you
3975	/// must observe several rules when using it:
3976	/// - You must not free the hash table while iterating (including via growing/shrinking).
3977	/// - It is fine to erase a bucket that has been yielded by the iterator.
3978	/// - Erasing a bucket that has not yet been yielded by the iterator may still
3979	/// result in the iterator yielding that bucket (unless `reflect_remove` is called).
3980	/// - It is unspecified whether an element inserted after the iterator was
3981	/// created will be yielded by that iterator (unless `reflect_insert` is called).
3982	/// - The order in which the iterator yields bucket is unspecified and may
3983	/// change in the future.
3984	pub struct RawIter<T> {
3985	pub(crate) iter: RawIterRange<T>,
3986	items: usize,
3987	}
3988
3989	impl<T> RawIter<T> {
3990	/// Refresh the iterator so that it reflects a removal from the given bucket.
3991	///
3992	/// For the iterator to remain valid, this method must be called once
3993	/// for each removed bucket before `next` is called again.
3994	///
3995	/// This method should be called _before_ the removal is made. It is not necessary to call this
3996	/// method if you are removing an item that this iterator yielded in the past.
3997	#[cfg(feature = "raw")]
3998	pub unsafe fn reflect_remove(&mut self, b: &Bucket<T>) {
3999	self.reflect_toggle_full(b, `false`);
4000	}
4001
4002	/// Refresh the iterator so that it reflects an insertion into the given bucket.
4003	///
4004	/// For the iterator to remain valid, this method must be called once
4005	/// for each insert before `next` is called again.
4006	///
4007	/// This method does not guarantee that an insertion of a bucket with a greater
4008	/// index than the last one yielded will be reflected in the iterator.
4009	///
4010	/// This method should be called _after_ the given insert is made.
4011	#[cfg(feature = "raw")]
4012	pub unsafe fn reflect_insert(&mut self, b: &Bucket<T>) {
4013	self.reflect_toggle_full(b, `true`);
4014	}
4015
4016	/// Refresh the iterator so that it reflects a change to the state of the given bucket.
4017	#[cfg(feature = "raw")]
4018	unsafe fn reflect_toggle_full(&mut self, b: &Bucket<T>, is_insert: bool) {
4019	if b.as_ptr() > self.iter.data.as_ptr() {
4020	// The iterator has already passed the bucket's group.
4021	// So the toggle isn't relevant to this iterator.
4022	return;
4023	}
4024
4025	if self.iter.next_ctrl < self.iter.end
4026	&& b.as_ptr() <= self.iter.data.next_n(Group::WIDTH).as_ptr()
4027	{
4028	// The iterator has not yet reached the bucket's group.
4029	// We don't need to reload anything, but we do need to adjust the item count.
4030
4031	if cfg!(debug_assertions) {
4032	// Double-check that the user isn't lying to us by checking the bucket state.
4033	// To do that, we need to find its control byte. We know that self.iter.data is
4034	// at self.iter.next_ctrl - Group::WIDTH, so we work from there:
4035	let offset = offset_from(self.iter.data.as_ptr(), b.as_ptr());
4036	let ctrl = self.iter.next_ctrl.sub(Group::WIDTH).add(offset);
4037	// This method should be called _before_ a removal, or _after_ an insert,
4038	// so in both cases the ctrl byte should indicate that the bucket is full.
4039	assert!(is_full(*ctrl));
4040	}
4041
4042	if is_insert {
4043	self.items += `1`;
4044	} else {
4045	self.items -= `1`;
4046	}
4047
4048	return;
4049	}
4050
4051	// The iterator is at the bucket group that the toggled bucket is in.
4052	// We need to do two things:
4053	//
4054	// - Determine if the iterator already yielded the toggled bucket.
4055	// If it did, we're done.
4056	// - Otherwise, update the iterator cached group so that it won't
4057	// yield a to-be-removed bucket, or _will_ yield a to-be-added bucket.
4058	// We'll also need to update the item count accordingly.
4059	if let Some(index) = self.iter.current_group.0.lowest_set_bit() {
4060	let next_bucket = self.iter.data.next_n(index);
4061	if b.as_ptr() > next_bucket.as_ptr() {
4062	// The toggled bucket is "before" the bucket the iterator would yield next. We
4063	// therefore don't need to do anything --- the iterator has already passed the
4064	// bucket in question.
4065	//
4066	// The item count must already be correct, since a removal or insert "prior" to
4067	// the iterator's position wouldn't affect the item count.
4068	} else {
4069	// The removed bucket is an upcoming bucket. We need to make sure it does _not_
4070	// get yielded, and also that it's no longer included in the item count.
4071	//
4072	// NOTE: We can't just reload the group here, both since that might reflect
4073	// inserts we've already passed, and because that might inadvertently unset the
4074	// bits for _other_ removals. If we do that, we'd have to also decrement the
4075	// item count for those other bits that we unset. But the presumably subsequent
4076	// call to reflect for those buckets might _also_ decrement the item count.
4077	// Instead, we _just_ flip the bit for the particular bucket the caller asked
4078	// us to reflect.
4079	let our_bit = offset_from(self.iter.data.as_ptr(), b.as_ptr());
4080	let was_full = self.iter.current_group.flip(our_bit);
4081	debug_assert_ne!(was_full, is_insert);
4082
4083	if is_insert {
4084	self.items += `1`;
4085	} else {
4086	self.items -= `1`;
4087	}
4088
4089	if cfg!(debug_assertions) {
4090	if b.as_ptr() == next_bucket.as_ptr() {
4091	// The removed bucket should no longer be next
4092	debug_assert_ne!(self.iter.current_group.0.lowest_set_bit(), Some(index));
4093	} else {
4094	// We should not have changed what bucket comes next.
4095	debug_assert_eq!(self.iter.current_group.0.lowest_set_bit(), Some(index));
4096	}
4097	}
4098	}
4099	} else {
4100	// We must have already iterated past the removed item.
4101	}
4102	}
4103
4104	unsafe fn drop_elements(&mut self) {
4105	if T::NEEDS_DROP && self.items != `0` {
4106	for item in self {
4107	item.drop();
4108	}
4109	}
4110	}
4111	}
4112
4113	impl<T> Clone for RawIter<T> {
4114	#[cfg_attr(feature = "inline-more", inline)]
4115	fn clone(&self) -> Self {
4116	Self {
4117	iter: self.iter.clone(),
4118	items: self.items,
4119	}
4120	}
4121	}
4122
4123	impl<T> Iterator for RawIter<T> {
4124	type Item = Bucket<T>;
4125
4126	#[cfg_attr(feature = "inline-more", inline)]
4127	fn next(&mut self) -> Option<Bucket<T>> {
4128	// Inner iterator iterates over buckets
4129	// so it can do unnecessary work if we already yielded all items.
4130	if self.items == `0` {
4131	return None;
4132	}
4133
4134	let nxt = unsafe {
4135	// SAFETY: We check number of items to yield using `items` field.
4136	self.iter.next_impl::<`false`>()
4137	};
4138
4139	debug_assert!(nxt.is_some());
4140	self.items -= `1`;
4141
4142	nxt
4143	}
4144
4145	#[inline]
4146	fn size_hint(&self) -> (usize, Option<usize>) {
4147	(self.items, Some(self.items))
4148	}
4149
4150	#[inline]
4151	fn fold<B, F>(self, init: B, f: F) -> B
4152	where
4153	Self: Sized,
4154	F: FnMut(B, Self::Item) -> B,
4155	{
4156	unsafe { self.iter.fold_impl(self.items, init, f) }
4157	}
4158	}
4159
4160	impl<T> ExactSizeIterator for RawIter<T> {}
4161	impl<T> FusedIterator for RawIter<T> {}
4162
4163	/// Iterator which returns an index of every full bucket in the table.
4164	///
4165	/// For maximum flexibility this iterator is not bound by a lifetime, but you
4166	/// must observe several rules when using it:
4167	/// - You must not free the hash table while iterating (including via growing/shrinking).
4168	/// - It is fine to erase a bucket that has been yielded by the iterator.
4169	/// - Erasing a bucket that has not yet been yielded by the iterator may still
4170	/// result in the iterator yielding index of that bucket.
4171	/// - It is unspecified whether an element inserted after the iterator was
4172	/// created will be yielded by that iterator.
4173	/// - The order in which the iterator yields indices of the buckets is unspecified
4174	/// and may change in the future.
4175	pub(crate) struct FullBucketsIndices {
4176	// Mask of full buckets in the current group. Bits are cleared from this
4177	// mask as each element is processed.
4178	current_group: BitMaskIter,
4179
4180	// Initial value of the bytes' indices of the current group (relative
4181	// to the start of the control bytes).
4182	group_first_index: usize,
4183
4184	// Pointer to the current group of control bytes,
4185	// Must be aligned to the group size (Group::WIDTH).
4186	ctrl: NonNull<u8>,
4187
4188	// Number of elements in the table.
4189	items: usize,
4190	}
4191
4192	impl FullBucketsIndices {
4193	/// Advances the iterator and returns the next value.
4194	///
4195	/// # Safety
4196	///
4197	/// If any of the following conditions are violated, the result is
4198	/// [`Undefined Behavior`]:
4199	///
4200	/// The* [`RawTableInner`] / [`RawTable`] must be alive and not moved,
4201	/// i.e. table outlives the `FullBucketsIndices`;
4202	///
4203	/// It never tries to iterate after getting all elements.*
4204	///
4205	/// [`Undefined Behavior`]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
4206	#[inline(always)]
4207	unsafe fn next_impl(&mut self) -> Option<usize> {
4208	loop {
4209	if let Some(index) = self.current_group.next() {
4210	// The returned `self.group_first_index + index` will always
4211	// be in the range `0..self.buckets()`. See explanation below.
4212	return Some(self.group_first_index + index);
4213	}
4214
4215	// SAFETY: The caller of this function ensures that:
4216	//
4217	// 1. It never tries to iterate after getting all the elements;
4218	// 2. The table is alive and did not moved;
4219	// 3. The first `self.ctrl` pointed to the start of the array of control bytes.
4220	//
4221	// Taking the above into account, we always stay within the bounds, because:
4222	//
4223	// 1. For tables smaller than the group width (self.buckets() <= Group::WIDTH),
4224	// we will never end up in the given branch, since we should have already
4225	// yielded all the elements of the table.
4226	//
4227	// 2. For tables larger than the group width. The the number of buckets is a
4228	// power of two (2 ^ n), Group::WIDTH is also power of two (2 ^ k). Sinse
4229	// `(2 ^ n) > (2 ^ k)`, than `(2 ^ n) % (2 ^ k) = 0`. As we start from the
4230	// the start of the array of control bytes, and never try to iterate after
4231	// getting all the elements, the last `self.ctrl` will be equal to
4232	// the `self.buckets() - Group::WIDTH`, so `self.current_group.next()`
4233	// will always contains indices within the range `0..Group::WIDTH`,
4234	// and subsequent `self.group_first_index + index` will always return a
4235	// number less than `self.buckets()`.
4236	self.ctrl = NonNull::new_unchecked(self.ctrl.as_ptr().add(Group::WIDTH));
4237
4238	// SAFETY: See explanation above.
4239	self.current_group = Group::load_aligned(self.ctrl.as_ptr())
4240	.match_full()
4241	.into_iter();
4242	self.group_first_index += Group::WIDTH;
4243	}
4244	}
4245	}
4246
4247	impl Iterator for FullBucketsIndices {
4248	type Item = usize;
4249
4250	/// Advances the iterator and returns the next value. It is up to
4251	/// the caller to ensure that the `RawTable` outlives the `FullBucketsIndices`,
4252	/// because we cannot make the `next` method unsafe.
4253	#[inline(always)]
4254	fn next(&mut self) -> Option<usize> {
4255	// Return if we already yielded all items.
4256	if self.items == `0` {
4257	return None;
4258	}
4259
4260	let nxt = unsafe {
4261	// SAFETY:
4262	// 1. We check number of items to yield using `items` field.
4263	// 2. The caller ensures that the table is alive and has not moved.
4264	self.next_impl()
4265	};
4266
4267	debug_assert!(nxt.is_some());
4268	self.items -= `1`;
4269
4270	nxt
4271	}
4272
4273	#[inline(always)]
4274	fn size_hint(&self) -> (usize, Option<usize>) {
4275	(self.items, Some(self.items))
4276	}
4277	}
4278
4279	impl ExactSizeIterator for FullBucketsIndices {}
4280	impl FusedIterator for FullBucketsIndices {}
4281
4282	/// Iterator which consumes a table and returns elements.
4283	pub struct RawIntoIter<T, A: Allocator = Global> {
4284	iter: RawIter<T>,
4285	allocation: Option<(NonNull<u8>, Layout, A)>,
4286	marker: PhantomData<T>,
4287	}
4288
4289	impl<T, A: Allocator> RawIntoIter<T, A> {
4290	#[cfg_attr(feature = "inline-more", inline)]
4291	pub fn iter(&self) -> RawIter<T> {
4292	self.iter.clone()
4293	}
4294	}
4295
4296	unsafe impl<T, A: Allocator> Send for RawIntoIter<T, A>
4297	where
4298	T: Send,
4299	A: Send,
4300	{
4301	}
4302	unsafe impl<T, A: Allocator> Sync for RawIntoIter<T, A>
4303	where
4304	T: Sync,
4305	A: Sync,
4306	{
4307	}
4308
4309	#[cfg(feature = "nightly")]
4310	unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawIntoIter<T, A> {
4311	#[cfg_attr(feature = "inline-more", inline)]
4312	fn drop(&mut self) {
4313	unsafe {
4314	// Drop all remaining elements
4315	self.iter.drop_elements();
4316
4317	// Free the table
4318	if let Some((ptr, layout, ref alloc)) = self.allocation {
4319	alloc.deallocate(ptr, layout);
4320	}
4321	}
4322	}
4323	}
4324	#[cfg(not(feature = "nightly"))]
4325	impl<T, A: Allocator> Drop for RawIntoIter<T, A> {
4326	#[cfg_attr(feature = "inline-more", inline)]
4327	fn drop(&mut self) {
4328	unsafe {
4329	// Drop all remaining elements
4330	self.iter.drop_elements();
4331
4332	// Free the table
4333	if let Some((ptr: NonNull, layout: Layout, ref alloc: &A)) = self.allocation {
4334	alloc.deallocate(ptr, layout);
4335	}
4336	}
4337	}
4338	}
4339
4340	impl<T, A: Allocator> Iterator for RawIntoIter<T, A> {
4341	type Item = T;
4342
4343	#[cfg_attr(feature = "inline-more", inline)]
4344	fn next(&mut self) -> Option<T> {
4345	unsafe { Some(self.iter.next()?.read()) }
4346	}
4347
4348	#[inline]
4349	fn size_hint(&self) -> (usize, Option<usize>) {
4350	self.iter.size_hint()
4351	}
4352	}
4353
4354	impl<T, A: Allocator> ExactSizeIterator for RawIntoIter<T, A> {}
4355	impl<T, A: Allocator> FusedIterator for RawIntoIter<T, A> {}
4356
4357	/// Iterator which consumes elements without freeing the table storage.
4358	pub struct RawDrain<'a, T, A: Allocator = Global> {
4359	iter: RawIter<T>,
4360
4361	// The table is moved into the iterator for the duration of the drain. This
4362	// ensures that an empty table is left if the drain iterator is leaked
4363	// without dropping.
4364	table: RawTableInner,
4365	orig_table: NonNull<RawTableInner>,
4366
4367	// We don't use a &'a mut RawTable<T> because we want RawDrain to be
4368	// covariant over T.
4369	marker: PhantomData<&'a RawTable<T, A>>,
4370	}
4371
4372	impl<T, A: Allocator> RawDrain<'_, T, A> {
4373	#[cfg_attr(feature = "inline-more", inline)]
4374	pub fn iter(&self) -> RawIter<T> {
4375	self.iter.clone()
4376	}
4377	}
4378
4379	unsafe impl<T, A: Allocator> Send for RawDrain<'_, T, A>
4380	where
4381	T: Send,
4382	A: Send,
4383	{
4384	}
4385	unsafe impl<T, A: Allocator> Sync for RawDrain<'_, T, A>
4386	where
4387	T: Sync,
4388	A: Sync,
4389	{
4390	}
4391
4392	impl<T, A: Allocator> Drop for RawDrain<'_, T, A> {
4393	#[cfg_attr(feature = "inline-more", inline)]
4394	fn drop(&mut self) {
4395	unsafe {
4396	// Drop all remaining elements. Note that this may panic.
4397	self.iter.drop_elements();
4398
4399	// Reset the contents of the table now that all elements have been
4400	// dropped.
4401	self.table.clear_no_drop();
4402
4403	// Move the now empty table back to its original location.
4404	self.orig_table
4405	.as_ptr()
4406	.copy_from_nonoverlapping(&self.table, count:`1`);
4407	}
4408	}
4409	}
4410
4411	impl<T, A: Allocator> Iterator for RawDrain<'_, T, A> {
4412	type Item = T;
4413
4414	#[cfg_attr(feature = "inline-more", inline)]
4415	fn next(&mut self) -> Option<T> {
4416	unsafe {
4417	let item: Bucket = self.iter.next()?;
4418	Some(item.read())
4419	}
4420	}
4421
4422	#[inline]
4423	fn size_hint(&self) -> (usize, Option<usize>) {
4424	self.iter.size_hint()
4425	}
4426	}
4427
4428	impl<T, A: Allocator> ExactSizeIterator for RawDrain<'_, T, A> {}
4429	impl<T, A: Allocator> FusedIterator for RawDrain<'_, T, A> {}
4430
4431	/// Iterator over occupied buckets that could match a given hash.
4432	///
4433	/// `RawTable` only stores 7 bits of the hash value, so this iterator may return
4434	/// items that have a hash value different than the one provided. You should
4435	/// always validate the returned values before using them.
4436	///
4437	/// For maximum flexibility this iterator is not bound by a lifetime, but you
4438	/// must observe several rules when using it:
4439	/// - You must not free the hash table while iterating (including via growing/shrinking).
4440	/// - It is fine to erase a bucket that has been yielded by the iterator.
4441	/// - Erasing a bucket that has not yet been yielded by the iterator may still
4442	/// result in the iterator yielding that bucket.
4443	/// - It is unspecified whether an element inserted after the iterator was
4444	/// created will be yielded by that iterator.
4445	/// - The order in which the iterator yields buckets is unspecified and may
4446	/// change in the future.
4447	pub struct RawIterHash<T> {
4448	inner: RawIterHashInner,
4449	_marker: PhantomData<T>,
4450	}
4451
4452	struct RawIterHashInner {
4453	// See `RawTableInner`'s corresponding fields for details.
4454	// We can't store a `const RawTableInner` as it would get*
4455	// invalidated by the user calling `&mut` methods on `RawTable`.
4456	bucket_mask: usize,
4457	ctrl: NonNull<u8>,
4458
4459	// The top 7 bits of the hash.
4460	h2_hash: u8,
4461
4462	// The sequence of groups to probe in the search.
4463	probe_seq: ProbeSeq,
4464
4465	group: Group,
4466
4467	// The elements within the group with a matching h2-hash.
4468	bitmask: BitMaskIter,
4469	}
4470
4471	impl<T> RawIterHash<T> {
4472	#[cfg_attr(feature = "inline-more", inline)]
4473	#[cfg(feature = "raw")]
4474	unsafe fn new<A: Allocator>(table: &RawTable<T, A>, hash: u64) -> Self {
4475	RawIterHash {
4476	inner: RawIterHashInner::new(&table.table, hash),
4477	_marker: PhantomData,
4478	}
4479	}
4480	}
4481	impl RawIterHashInner {
4482	#[cfg_attr(feature = "inline-more", inline)]
4483	#[cfg(feature = "raw")]
4484	unsafe fn new(table: &RawTableInner, hash: u64) -> Self {
4485	let h2_hash: u8 = h2(hash);
4486	let probe_seq: ProbeSeq = table.probe_seq(hash);
4487	let group: Group = Group::load(ptr:table.ctrl(index:probe_seq.pos));
4488	let bitmask: BitMaskIter = group.match_byte(h2_hash).into_iter();
4489
4490	RawIterHashInner {
4491	bucket_mask: table.bucket_mask,
4492	ctrl: table.ctrl,
4493	h2_hash,
4494	probe_seq,
4495	group,
4496	bitmask,
4497	}
4498	}
4499	}
4500
4501	impl<T> Iterator for RawIterHash<T> {
4502	type Item = Bucket<T>;
4503
4504	fn next(&mut self) -> Option<Bucket<T>> {
4505	unsafe {
4506	match self.inner.next() {
4507	Some(index: usize) => {
4508	// Can't use `RawTable::bucket` here as we don't have
4509	// an actual `RawTable` reference to use.
4510	debug_assert!(index <= self.inner.bucket_mask);
4511	let bucket: Bucket = Bucket::from_base_index(self.inner.ctrl.cast(), index);
4512	Some(bucket)
4513	}
4514	None => None,
4515	}
4516	}
4517	}
4518	}
4519
4520	impl Iterator for RawIterHashInner {
4521	type Item = usize;
4522
4523	fn next(&mut self) -> Option<Self::Item> {
4524	unsafe {
4525	loop {
4526	if let Some(bit) = self.bitmask.next() {
4527	let index = (self.probe_seq.pos + bit) & self.bucket_mask;
4528	return Some(index);
4529	}
4530	if likely(self.group.match_empty().any_bit_set()) {
4531	return None;
4532	}
4533	self.probe_seq.move_next(self.bucket_mask);
4534
4535	// Can't use `RawTableInner::ctrl` here as we don't have
4536	// an actual `RawTableInner` reference to use.
4537	let index = self.probe_seq.pos;
4538	debug_assert!(index < self.bucket_mask + `1` + Group::WIDTH);
4539	let group_ctrl = self.ctrl.as_ptr().add(index);
4540
4541	self.group = Group::load(group_ctrl);
4542	self.bitmask = self.group.match_byte(self.h2_hash).into_iter();
4543	}
4544	}
4545	}
4546	}
4547
4548	pub(crate) struct RawExtractIf<'a, T, A: Allocator> {
4549	pub iter: RawIter<T>,
4550	pub table: &'a mut RawTable<T, A>,
4551	}
4552
4553	impl<T, A: Allocator> RawExtractIf<'_, T, A> {
4554	#[cfg_attr(feature = "inline-more", inline)]
4555	pub(crate) fn next<F>(&mut self, mut f: F) -> Option<T>
4556	where
4557	F: FnMut(&mut T) -> bool,
4558	{
4559	unsafe {
4560	for item: Bucket in &mut self.iter {
4561	if f(item.as_mut()) {
4562	return Some(self.table.remove(item).0);
4563	}
4564	}
4565	}
4566	None
4567	}
4568	}
4569
4570	#[cfg(test)]
4571	mod test_map {
4572	use super::*;
4573
4574	fn rehash_in_place<T>(table: &mut RawTable<T>, hasher: impl Fn(&T) -> u64) {
4575	unsafe {
4576	table.table.rehash_in_place(
4577	&\|table, index\| hasher(table.bucket::<T>(index).as_ref()),
4578	mem::size_of::<T>(),
4579	if mem::needs_drop::<T>() {
4580	Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
4581	} else {
4582	None
4583	},
4584	);
4585	}
4586	}
4587
4588	#[test]
4589	fn rehash() {
4590	let mut table = RawTable::new();
4591	let hasher = \|i: &u64\| *i;
4592	for i in `0`..`100` {
4593	table.insert(i, i, hasher);
4594	}
4595
4596	for i in `0`..`100` {
4597	unsafe {
4598	assert_eq!(table.find(i, \|x\| *x == i).map(\|b\| b.read()), Some(i));
4599	}
4600	assert!(table.find(i + `100`, \|x\| *x == i + `100`).is_none());
4601	}
4602
4603	rehash_in_place(&mut table, hasher);
4604
4605	for i in `0`..`100` {
4606	unsafe {
4607	assert_eq!(table.find(i, \|x\| *x == i).map(\|b\| b.read()), Some(i));
4608	}
4609	assert!(table.find(i + `100`, \|x\| *x == i + `100`).is_none());
4610	}
4611	}
4612
4613	/// CHECKING THAT WE ARE NOT TRYING TO READ THE MEMORY OF
4614	/// AN UNINITIALIZED TABLE DURING THE DROP
4615	#[test]
4616	fn test_drop_uninitialized() {
4617	use ::alloc::vec::Vec;
4618
4619	let table = unsafe {
4620	// SAFETY: The `buckets` is power of two and we're not
4621	// trying to actually use the returned RawTable.
4622	RawTable::<(u64, Vec<i32>)>::new_uninitialized(Global, `8`, Fallibility::Infallible)
4623	.unwrap()
4624	};
4625	drop(table);
4626	}
4627
4628	/// CHECKING THAT WE DON'T TRY TO DROP DATA IF THE `ITEMS`
4629	/// ARE ZERO, EVEN IF WE HAVE `FULL` CONTROL BYTES.
4630	#[test]
4631	fn test_drop_zero_items() {
4632	use ::alloc::vec::Vec;
4633	unsafe {
4634	// SAFETY: The `buckets` is power of two and we're not
4635	// trying to actually use the returned RawTable.
4636	let table =
4637	RawTable::<(u64, Vec<i32>)>::new_uninitialized(Global, `8`, Fallibility::Infallible)
4638	.unwrap();
4639
4640	// WE SIMULATE, AS IT WERE, A FULL TABLE.
4641
4642	// SAFETY: We checked that the table is allocated and therefore the table already has
4643	// `self.bucket_mask + 1 + Group::WIDTH` number of control bytes (see TableLayout::calculate_layout_for)
4644	// so writing `table.table.num_ctrl_bytes() == bucket_mask + 1 + Group::WIDTH` bytes is safe.
4645	table
4646	.table
4647	.ctrl(`0`)
4648	.write_bytes(EMPTY, table.table.num_ctrl_bytes());
4649
4650	// SAFETY: table.capacity() is guaranteed to be smaller than table.buckets()
4651	table.table.ctrl(`0`).write_bytes(`0`, table.capacity());
4652
4653	// Fix up the trailing control bytes. See the comments in set_ctrl
4654	// for the handling of tables smaller than the group width.
4655	if table.buckets() < Group::WIDTH {
4656	// SAFETY: We have `self.bucket_mask + 1 + Group::WIDTH` number of control bytes,
4657	// so copying `self.buckets() == self.bucket_mask + 1` bytes with offset equal to
4658	// `Group::WIDTH` is safe
4659	table
4660	.table
4661	.ctrl(`0`)
4662	.copy_to(table.table.ctrl(Group::WIDTH), table.table.buckets());
4663	} else {
4664	// SAFETY: We have `self.bucket_mask + 1 + Group::WIDTH` number of
4665	// control bytes,so copying `Group::WIDTH` bytes with offset equal
4666	// to `self.buckets() == self.bucket_mask + 1` is safe
4667	table
4668	.table
4669	.ctrl(`0`)
4670	.copy_to(table.table.ctrl(table.table.buckets()), Group::WIDTH);
4671	}
4672	drop(table);
4673	}
4674	}
4675
4676	/// CHECKING THAT WE DON'T TRY TO DROP DATA IF THE `ITEMS`
4677	/// ARE ZERO, EVEN IF WE HAVE `FULL` CONTROL BYTES.
4678	#[test]
4679	fn test_catch_panic_clone_from() {
4680	use ::alloc::sync::Arc;
4681	use ::alloc::vec::Vec;
4682	use allocator_api2::alloc::{AllocError, Allocator, Global};
4683	use core::sync::atomic::{AtomicI8, Ordering};
4684	use std::thread;
4685
4686	struct MyAllocInner {
4687	drop_count: Arc<AtomicI8>,
4688	}
4689
4690	#[derive(Clone)]
4691	struct MyAlloc {
4692	_inner: Arc<MyAllocInner>,
4693	}
4694
4695	impl Drop for MyAllocInner {
4696	fn drop(&mut self) {
4697	println!("MyAlloc freed.");
4698	self.drop_count.fetch_sub(`1`, Ordering::SeqCst);
4699	}
4700	}
4701
4702	unsafe impl Allocator for MyAlloc {
4703	fn allocate(&self, layout: Layout) -> std::result::Result<NonNull<[u8]>, AllocError> {
4704	let g = Global;
4705	g.allocate(layout)
4706	}
4707
4708	unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
4709	let g = Global;
4710	g.deallocate(ptr, layout)
4711	}
4712	}
4713
4714	const DISARMED: bool = `false`;
4715	const ARMED: bool = `true`;
4716
4717	struct CheckedCloneDrop {
4718	panic_in_clone: bool,
4719	dropped: bool,
4720	need_drop: Vec<u64>,
4721	}
4722
4723	impl Clone for CheckedCloneDrop {
4724	fn clone(&self) -> Self {
4725	if self.panic_in_clone {
4726	panic!("panic in clone")
4727	}
4728	Self {
4729	panic_in_clone: self.panic_in_clone,
4730	dropped: self.dropped,
4731	need_drop: self.need_drop.clone(),
4732	}
4733	}
4734	}
4735
4736	impl Drop for CheckedCloneDrop {
4737	fn drop(&mut self) {
4738	if self.dropped {
4739	panic!("double drop");
4740	}
4741	self.dropped = `true`;
4742	}
4743	}
4744
4745	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`2`));
4746
4747	let mut table = RawTable::new_in(MyAlloc {
4748	_inner: Arc::new(MyAllocInner {
4749	drop_count: dropped.clone(),
4750	}),
4751	});
4752
4753	for (idx, panic_in_clone) in core::iter::repeat(DISARMED).take(`7`).enumerate() {
4754	let idx = idx as u64;
4755	table.insert(
4756	idx,
4757	(
4758	idx,
4759	CheckedCloneDrop {
4760	panic_in_clone,
4761	dropped: `false`,
4762	need_drop: vec![idx],
4763	},
4764	),
4765	\|(k, _)\| *k,
4766	);
4767	}
4768
4769	assert_eq!(table.len(), `7`);
4770
4771	thread::scope(\|s\| {
4772	let result = s.spawn(\|\| {
4773	let armed_flags = [
4774	DISARMED, DISARMED, ARMED, DISARMED, DISARMED, DISARMED, DISARMED,
4775	];
4776	let mut scope_table = RawTable::new_in(MyAlloc {
4777	_inner: Arc::new(MyAllocInner {
4778	drop_count: dropped.clone(),
4779	}),
4780	});
4781	for (idx, &panic_in_clone) in armed_flags.iter().enumerate() {
4782	let idx = idx as u64;
4783	scope_table.insert(
4784	idx,
4785	(
4786	idx,
4787	CheckedCloneDrop {
4788	panic_in_clone,
4789	dropped: `false`,
4790	need_drop: vec![idx + `100`],
4791	},
4792	),
4793	\|(k, _)\| *k,
4794	);
4795	}
4796	table.clone_from(&scope_table);
4797	});
4798	assert!(result.join().is_err());
4799	});
4800
4801	// Let's check that all iterators work fine and do not return elements
4802	// (especially `RawIterRange`, which does not depend on the number of
4803	// elements in the table, but looks directly at the control bytes)
4804	//
4805	// SAFETY: We know for sure that `RawTable` will outlive
4806	// the returned `RawIter / RawIterRange` iterator.
4807	assert_eq!(table.len(), `0`);
4808	assert_eq!(unsafe { table.iter().count() }, `0`);
4809	assert_eq!(unsafe { table.iter().iter.count() }, `0`);
4810
4811	for idx in `0`..table.buckets() {
4812	let idx = idx as u64;
4813	assert!(
4814	table.find(idx, \|(k, _)\| *k == idx).is_none(),
4815	"Index: {idx}"
4816	);
4817	}
4818
4819	// All allocator clones should already be dropped.
4820	assert_eq!(dropped.load(Ordering::SeqCst), `1`);
4821	}
4822	}
4823