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(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(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&RawTable |
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: &{unknown})) = 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, layout, ref alloc)) = 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, 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 = 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<{unknown}> = 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: <&mut RawIter as IntoIterator>::Item 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 | |