]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
1a4d82fc | 10 | |
3157f602 | 11 | use alloc::heap::{EMPTY, allocate, deallocate}; |
1a4d82fc | 12 | |
1a4d82fc | 13 | use cmp; |
3157f602 | 14 | use hash::{BuildHasher, Hash, Hasher}; |
7453a54e | 15 | use intrinsics::needs_drop; |
e9174d1e | 16 | use marker; |
62682a34 | 17 | use mem::{align_of, size_of}; |
1a4d82fc | 18 | use mem; |
e9174d1e | 19 | use ops::{Deref, DerefMut}; |
c34b1796 | 20 | use ptr::{self, Unique}; |
1a4d82fc | 21 | |
e9174d1e SL |
22 | use self::BucketState::*; |
23 | ||
c34b1796 | 24 | const EMPTY_BUCKET: u64 = 0; |
1a4d82fc JJ |
25 | |
26 | /// The raw hashtable, providing safe-ish access to the unzipped and highly | |
27 | /// optimized arrays of hashes, keys, and values. | |
28 | /// | |
29 | /// This design uses less memory and is a lot faster than the naive | |
30 | /// `Vec<Option<u64, K, V>>`, because we don't pay for the overhead of an | |
31 | /// option on every element, and we get a generally more cache-aware design. | |
32 | /// | |
33 | /// Essential invariants of this structure: | |
34 | /// | |
35 | /// - if t.hashes[i] == EMPTY_BUCKET, then `Bucket::at_index(&t, i).raw` | |
36 | /// points to 'undefined' contents. Don't read from it. This invariant is | |
37 | /// enforced outside this module with the `EmptyBucket`, `FullBucket`, | |
38 | /// and `SafeHash` types. | |
39 | /// | |
40 | /// - An `EmptyBucket` is only constructed at an index with | |
41 | /// a hash of EMPTY_BUCKET. | |
42 | /// | |
43 | /// - A `FullBucket` is only constructed at an index with a | |
44 | /// non-EMPTY_BUCKET hash. | |
45 | /// | |
46 | /// - A `SafeHash` is only constructed for non-`EMPTY_BUCKET` hash. We get | |
47 | /// around hashes of zero by changing them to 0x8000_0000_0000_0000, | |
48 | /// which will likely map to the same bucket, while not being confused | |
49 | /// with "empty". | |
50 | /// | |
51 | /// - All three "arrays represented by pointers" are the same length: | |
52 | /// `capacity`. This is set at creation and never changes. The arrays | |
53 | /// are unzipped to save space (we don't have to pay for the padding | |
54 | /// between odd sized elements, such as in a map from u64 to u8), and | |
55 | /// be more cache aware (scanning through 8 hashes brings in at most | |
56 | /// 2 cache lines, since they're all right beside each other). | |
57 | /// | |
58 | /// You can kind of think of this module/data structure as a safe wrapper | |
59 | /// around just the "table" part of the hashtable. It enforces some | |
60 | /// invariants at the type level and employs some performance trickery, | |
61 | /// but in general is just a tricked out `Vec<Option<u64, K, V>>`. | |
62 | #[unsafe_no_drop_flag] | |
63 | pub struct RawTable<K, V> { | |
85aaf69f | 64 | capacity: usize, |
3157f602 XL |
65 | size: usize, |
66 | hashes: Unique<u64>, | |
85aaf69f | 67 | |
1a4d82fc JJ |
68 | // Because K/V do not appear directly in any of the types in the struct, |
69 | // inform rustc that in fact instances of K and V are reachable from here. | |
3157f602 | 70 | marker: marker::PhantomData<(K, V)>, |
1a4d82fc JJ |
71 | } |
72 | ||
85aaf69f SL |
73 | unsafe impl<K: Send, V: Send> Send for RawTable<K, V> {} |
74 | unsafe impl<K: Sync, V: Sync> Sync for RawTable<K, V> {} | |
75 | ||
1a4d82fc JJ |
76 | struct RawBucket<K, V> { |
77 | hash: *mut u64, | |
54a0048b SL |
78 | |
79 | // We use *const to ensure covariance with respect to K and V | |
3157f602 XL |
80 | key: *const K, |
81 | val: *const V, | |
82 | _marker: marker::PhantomData<(K, V)>, | |
1a4d82fc JJ |
83 | } |
84 | ||
3157f602 XL |
85 | impl<K, V> Copy for RawBucket<K, V> {} |
86 | impl<K, V> Clone for RawBucket<K, V> { | |
87 | fn clone(&self) -> RawBucket<K, V> { | |
88 | *self | |
89 | } | |
c34b1796 | 90 | } |
1a4d82fc JJ |
91 | |
92 | pub struct Bucket<K, V, M> { | |
3157f602 XL |
93 | raw: RawBucket<K, V>, |
94 | idx: usize, | |
95 | table: M, | |
1a4d82fc JJ |
96 | } |
97 | ||
3157f602 XL |
98 | impl<K, V, M: Copy> Copy for Bucket<K, V, M> {} |
99 | impl<K, V, M: Copy> Clone for Bucket<K, V, M> { | |
100 | fn clone(&self) -> Bucket<K, V, M> { | |
101 | *self | |
102 | } | |
c34b1796 | 103 | } |
1a4d82fc JJ |
104 | |
105 | pub struct EmptyBucket<K, V, M> { | |
3157f602 XL |
106 | raw: RawBucket<K, V>, |
107 | idx: usize, | |
108 | table: M, | |
1a4d82fc JJ |
109 | } |
110 | ||
111 | pub struct FullBucket<K, V, M> { | |
3157f602 XL |
112 | raw: RawBucket<K, V>, |
113 | idx: usize, | |
114 | table: M, | |
1a4d82fc JJ |
115 | } |
116 | ||
117 | pub type EmptyBucketImm<'table, K, V> = EmptyBucket<K, V, &'table RawTable<K, V>>; | |
3157f602 | 118 | pub type FullBucketImm<'table, K, V> = FullBucket<K, V, &'table RawTable<K, V>>; |
1a4d82fc JJ |
119 | |
120 | pub type EmptyBucketMut<'table, K, V> = EmptyBucket<K, V, &'table mut RawTable<K, V>>; | |
3157f602 | 121 | pub type FullBucketMut<'table, K, V> = FullBucket<K, V, &'table mut RawTable<K, V>>; |
1a4d82fc JJ |
122 | |
123 | pub enum BucketState<K, V, M> { | |
124 | Empty(EmptyBucket<K, V, M>), | |
125 | Full(FullBucket<K, V, M>), | |
126 | } | |
127 | ||
128 | // A GapThenFull encapsulates the state of two consecutive buckets at once. | |
129 | // The first bucket, called the gap, is known to be empty. | |
130 | // The second bucket is full. | |
9cc50fc6 | 131 | pub struct GapThenFull<K, V, M> { |
1a4d82fc JJ |
132 | gap: EmptyBucket<K, V, ()>, |
133 | full: FullBucket<K, V, M>, | |
134 | } | |
135 | ||
136 | /// A hash that is not zero, since we use a hash of zero to represent empty | |
137 | /// buckets. | |
c34b1796 | 138 | #[derive(PartialEq, Copy, Clone)] |
1a4d82fc JJ |
139 | pub struct SafeHash { |
140 | hash: u64, | |
141 | } | |
142 | ||
143 | impl SafeHash { | |
144 | /// Peek at the hash value, which is guaranteed to be non-zero. | |
145 | #[inline(always)] | |
3157f602 XL |
146 | pub fn inspect(&self) -> u64 { |
147 | self.hash | |
148 | } | |
1a4d82fc JJ |
149 | } |
150 | ||
151 | /// We need to remove hashes of 0. That's reserved for empty buckets. | |
152 | /// This function wraps up `hash_keyed` to be the only way outside this | |
153 | /// module to generate a SafeHash. | |
85aaf69f | 154 | pub fn make_hash<T: ?Sized, S>(hash_state: &S, t: &T) -> SafeHash |
3157f602 XL |
155 | where T: Hash, |
156 | S: BuildHasher | |
85aaf69f | 157 | { |
9cc50fc6 | 158 | let mut state = hash_state.build_hasher(); |
85aaf69f | 159 | t.hash(&mut state); |
c34b1796 | 160 | // We need to avoid 0 in order to prevent collisions with |
85aaf69f SL |
161 | // EMPTY_HASH. We can maintain our precious uniform distribution |
162 | // of initial indexes by unconditionally setting the MSB, | |
163 | // effectively reducing 64-bits hashes to 63 bits. | |
164 | SafeHash { hash: 0x8000_0000_0000_0000 | state.finish() } | |
165 | } | |
166 | ||
1a4d82fc JJ |
167 | // `replace` casts a `*u64` to a `*SafeHash`. Since we statically |
168 | // ensure that a `FullBucket` points to an index with a non-zero hash, | |
169 | // and a `SafeHash` is just a `u64` with a different name, this is | |
170 | // safe. | |
171 | // | |
172 | // This test ensures that a `SafeHash` really IS the same size as a | |
173 | // `u64`. If you need to change the size of `SafeHash` (and | |
174 | // consequently made this test fail), `replace` needs to be | |
175 | // modified to no longer assume this. | |
176 | #[test] | |
177 | fn can_alias_safehash_as_u64() { | |
178 | assert_eq!(size_of::<SafeHash>(), size_of::<u64>()) | |
179 | } | |
180 | ||
181 | impl<K, V> RawBucket<K, V> { | |
85aaf69f | 182 | unsafe fn offset(self, count: isize) -> RawBucket<K, V> { |
1a4d82fc JJ |
183 | RawBucket { |
184 | hash: self.hash.offset(count), | |
3157f602 XL |
185 | key: self.key.offset(count), |
186 | val: self.val.offset(count), | |
85aaf69f | 187 | _marker: marker::PhantomData, |
1a4d82fc JJ |
188 | } |
189 | } | |
190 | } | |
191 | ||
192 | // Buckets hold references to the table. | |
193 | impl<K, V, M> FullBucket<K, V, M> { | |
194 | /// Borrow a reference to the table. | |
195 | pub fn table(&self) -> &M { | |
196 | &self.table | |
197 | } | |
198 | /// Move out the reference to the table. | |
199 | pub fn into_table(self) -> M { | |
200 | self.table | |
201 | } | |
202 | /// Get the raw index. | |
85aaf69f | 203 | pub fn index(&self) -> usize { |
1a4d82fc JJ |
204 | self.idx |
205 | } | |
206 | } | |
207 | ||
208 | impl<K, V, M> EmptyBucket<K, V, M> { | |
209 | /// Borrow a reference to the table. | |
210 | pub fn table(&self) -> &M { | |
211 | &self.table | |
212 | } | |
1a4d82fc JJ |
213 | } |
214 | ||
215 | impl<K, V, M> Bucket<K, V, M> { | |
1a4d82fc | 216 | /// Get the raw index. |
85aaf69f | 217 | pub fn index(&self) -> usize { |
1a4d82fc JJ |
218 | self.idx |
219 | } | |
220 | } | |
221 | ||
3157f602 XL |
222 | impl<K, V, M> Deref for FullBucket<K, V, M> |
223 | where M: Deref<Target = RawTable<K, V>> | |
224 | { | |
54a0048b SL |
225 | type Target = RawTable<K, V>; |
226 | fn deref(&self) -> &RawTable<K, V> { | |
227 | &self.table | |
228 | } | |
229 | } | |
230 | ||
231 | /// `Put` is implemented for types which provide access to a table and cannot be invalidated | |
232 | /// by filling a bucket. A similar implementation for `Take` is possible. | |
233 | pub trait Put<K, V> { | |
234 | unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V>; | |
235 | } | |
236 | ||
237 | ||
238 | impl<'t, K, V> Put<K, V> for &'t mut RawTable<K, V> { | |
239 | unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> { | |
240 | *self | |
241 | } | |
242 | } | |
243 | ||
3157f602 XL |
244 | impl<K, V, M> Put<K, V> for Bucket<K, V, M> |
245 | where M: Put<K, V> | |
246 | { | |
54a0048b SL |
247 | unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> { |
248 | self.table.borrow_table_mut() | |
249 | } | |
250 | } | |
251 | ||
3157f602 XL |
252 | impl<K, V, M> Put<K, V> for FullBucket<K, V, M> |
253 | where M: Put<K, V> | |
254 | { | |
54a0048b SL |
255 | unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> { |
256 | self.table.borrow_table_mut() | |
257 | } | |
258 | } | |
259 | ||
3157f602 | 260 | impl<K, V, M: Deref<Target = RawTable<K, V>>> Bucket<K, V, M> { |
1a4d82fc | 261 | pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> { |
85aaf69f | 262 | Bucket::at_index(table, hash.inspect() as usize) |
1a4d82fc JJ |
263 | } |
264 | ||
85aaf69f | 265 | pub fn at_index(table: M, ib_index: usize) -> Bucket<K, V, M> { |
c34b1796 AL |
266 | // if capacity is 0, then the RawBucket will be populated with bogus pointers. |
267 | // This is an uncommon case though, so avoid it in release builds. | |
3157f602 XL |
268 | debug_assert!(table.capacity() > 0, |
269 | "Table should have capacity at this point"); | |
1a4d82fc JJ |
270 | let ib_index = ib_index & (table.capacity() - 1); |
271 | Bucket { | |
3157f602 | 272 | raw: unsafe { table.first_bucket_raw().offset(ib_index as isize) }, |
1a4d82fc | 273 | idx: ib_index, |
3157f602 | 274 | table: table, |
1a4d82fc JJ |
275 | } |
276 | } | |
277 | ||
278 | pub fn first(table: M) -> Bucket<K, V, M> { | |
279 | Bucket { | |
280 | raw: table.first_bucket_raw(), | |
281 | idx: 0, | |
3157f602 | 282 | table: table, |
1a4d82fc JJ |
283 | } |
284 | } | |
285 | ||
286 | /// Reads a bucket at a given index, returning an enum indicating whether | |
287 | /// it's initialized or not. You need to match on this enum to get | |
288 | /// the appropriate types to call most of the other functions in | |
289 | /// this module. | |
290 | pub fn peek(self) -> BucketState<K, V, M> { | |
291 | match unsafe { *self.raw.hash } { | |
3157f602 | 292 | EMPTY_BUCKET => { |
1a4d82fc JJ |
293 | Empty(EmptyBucket { |
294 | raw: self.raw, | |
295 | idx: self.idx, | |
3157f602 XL |
296 | table: self.table, |
297 | }) | |
298 | } | |
299 | _ => { | |
1a4d82fc JJ |
300 | Full(FullBucket { |
301 | raw: self.raw, | |
302 | idx: self.idx, | |
3157f602 | 303 | table: self.table, |
1a4d82fc | 304 | }) |
3157f602 | 305 | } |
1a4d82fc JJ |
306 | } |
307 | } | |
308 | ||
309 | /// Modifies the bucket pointer in place to make it point to the next slot. | |
310 | pub fn next(&mut self) { | |
1a4d82fc | 311 | self.idx += 1; |
54a0048b SL |
312 | let range = self.table.capacity(); |
313 | // This code is branchless thanks to a conditional move. | |
314 | let dist = if self.idx & (range - 1) == 0 { | |
315 | 1 - range as isize | |
316 | } else { | |
317 | 1 | |
318 | }; | |
1a4d82fc JJ |
319 | unsafe { |
320 | self.raw = self.raw.offset(dist); | |
321 | } | |
322 | } | |
323 | } | |
324 | ||
3157f602 | 325 | impl<K, V, M: Deref<Target = RawTable<K, V>>> EmptyBucket<K, V, M> { |
1a4d82fc JJ |
326 | #[inline] |
327 | pub fn next(self) -> Bucket<K, V, M> { | |
328 | let mut bucket = self.into_bucket(); | |
329 | bucket.next(); | |
330 | bucket | |
331 | } | |
332 | ||
333 | #[inline] | |
334 | pub fn into_bucket(self) -> Bucket<K, V, M> { | |
335 | Bucket { | |
336 | raw: self.raw, | |
337 | idx: self.idx, | |
3157f602 | 338 | table: self.table, |
1a4d82fc JJ |
339 | } |
340 | } | |
341 | ||
342 | pub fn gap_peek(self) -> Option<GapThenFull<K, V, M>> { | |
343 | let gap = EmptyBucket { | |
344 | raw: self.raw, | |
345 | idx: self.idx, | |
3157f602 | 346 | table: (), |
1a4d82fc JJ |
347 | }; |
348 | ||
349 | match self.next().peek() { | |
350 | Full(bucket) => { | |
351 | Some(GapThenFull { | |
352 | gap: gap, | |
3157f602 | 353 | full: bucket, |
1a4d82fc JJ |
354 | }) |
355 | } | |
3157f602 | 356 | Empty(..) => None, |
1a4d82fc JJ |
357 | } |
358 | } | |
359 | } | |
360 | ||
3157f602 XL |
361 | impl<K, V, M> EmptyBucket<K, V, M> |
362 | where M: Put<K, V> | |
363 | { | |
1a4d82fc JJ |
364 | /// Puts given key and value pair, along with the key's hash, |
365 | /// into this bucket in the hashtable. Note how `self` is 'moved' into | |
366 | /// this function, because this slot will no longer be empty when | |
367 | /// we return! A `FullBucket` is returned for later use, pointing to | |
368 | /// the newly-filled slot in the hashtable. | |
369 | /// | |
370 | /// Use `make_hash` to construct a `SafeHash` to pass to this function. | |
3157f602 | 371 | pub fn put(mut self, hash: SafeHash, key: K, value: V) -> FullBucket<K, V, M> { |
1a4d82fc JJ |
372 | unsafe { |
373 | *self.raw.hash = hash.inspect(); | |
54a0048b SL |
374 | ptr::write(self.raw.key as *mut K, key); |
375 | ptr::write(self.raw.val as *mut V, value); | |
1a4d82fc | 376 | |
54a0048b SL |
377 | self.table.borrow_table_mut().size += 1; |
378 | } | |
1a4d82fc | 379 | |
3157f602 XL |
380 | FullBucket { |
381 | raw: self.raw, | |
382 | idx: self.idx, | |
383 | table: self.table, | |
384 | } | |
1a4d82fc JJ |
385 | } |
386 | } | |
387 | ||
3157f602 | 388 | impl<K, V, M: Deref<Target = RawTable<K, V>>> FullBucket<K, V, M> { |
1a4d82fc JJ |
389 | #[inline] |
390 | pub fn next(self) -> Bucket<K, V, M> { | |
391 | let mut bucket = self.into_bucket(); | |
392 | bucket.next(); | |
393 | bucket | |
394 | } | |
395 | ||
396 | #[inline] | |
397 | pub fn into_bucket(self) -> Bucket<K, V, M> { | |
398 | Bucket { | |
399 | raw: self.raw, | |
400 | idx: self.idx, | |
3157f602 | 401 | table: self.table, |
1a4d82fc JJ |
402 | } |
403 | } | |
404 | ||
54a0048b SL |
405 | /// Duplicates the current position. This can be useful for operations |
406 | /// on two or more buckets. | |
407 | pub fn stash(self) -> FullBucket<K, V, Self> { | |
408 | FullBucket { | |
409 | raw: self.raw, | |
410 | idx: self.idx, | |
411 | table: self, | |
412 | } | |
413 | } | |
414 | ||
1a4d82fc JJ |
415 | /// Get the distance between this bucket and the 'ideal' location |
416 | /// as determined by the key's hash stored in it. | |
417 | /// | |
418 | /// In the cited blog posts above, this is called the "distance to | |
419 | /// initial bucket", or DIB. Also known as "probe count". | |
54a0048b | 420 | pub fn displacement(&self) -> usize { |
1a4d82fc JJ |
421 | // Calculates the distance one has to travel when going from |
422 | // `hash mod capacity` onwards to `idx mod capacity`, wrapping around | |
423 | // if the destination is not reached before the end of the table. | |
c34b1796 | 424 | (self.idx.wrapping_sub(self.hash().inspect() as usize)) & (self.table.capacity() - 1) |
1a4d82fc JJ |
425 | } |
426 | ||
427 | #[inline] | |
428 | pub fn hash(&self) -> SafeHash { | |
3157f602 | 429 | unsafe { SafeHash { hash: *self.raw.hash } } |
1a4d82fc JJ |
430 | } |
431 | ||
432 | /// Gets references to the key and value at a given index. | |
433 | pub fn read(&self) -> (&K, &V) { | |
3157f602 | 434 | unsafe { (&*self.raw.key, &*self.raw.val) } |
1a4d82fc JJ |
435 | } |
436 | } | |
437 | ||
54a0048b SL |
438 | // We take a mutable reference to the table instead of accepting anything that |
439 | // implements `DerefMut` to prevent fn `take` from being called on `stash`ed | |
440 | // buckets. | |
441 | impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> { | |
1a4d82fc JJ |
442 | /// Removes this bucket's key and value from the hashtable. |
443 | /// | |
444 | /// This works similarly to `put`, building an `EmptyBucket` out of the | |
445 | /// taken bucket. | |
54a0048b | 446 | pub fn take(mut self) -> (EmptyBucket<K, V, &'t mut RawTable<K, V>>, K, V) { |
1a4d82fc JJ |
447 | self.table.size -= 1; |
448 | ||
449 | unsafe { | |
450 | *self.raw.hash = EMPTY_BUCKET; | |
3157f602 XL |
451 | (EmptyBucket { |
452 | raw: self.raw, | |
453 | idx: self.idx, | |
454 | table: self.table, | |
455 | }, | |
456 | ptr::read(self.raw.key), | |
457 | ptr::read(self.raw.val)) | |
1a4d82fc JJ |
458 | } |
459 | } | |
54a0048b | 460 | } |
1a4d82fc | 461 | |
54a0048b SL |
462 | // This use of `Put` is misleading and restrictive, but safe and sufficient for our use cases |
463 | // where `M` is a full bucket or table reference type with mutable access to the table. | |
3157f602 XL |
464 | impl<K, V, M> FullBucket<K, V, M> |
465 | where M: Put<K, V> | |
466 | { | |
1a4d82fc JJ |
467 | pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) { |
468 | unsafe { | |
469 | let old_hash = ptr::replace(self.raw.hash as *mut SafeHash, h); | |
3157f602 XL |
470 | let old_key = ptr::replace(self.raw.key as *mut K, k); |
471 | let old_val = ptr::replace(self.raw.val as *mut V, v); | |
1a4d82fc JJ |
472 | |
473 | (old_hash, old_key, old_val) | |
474 | } | |
475 | } | |
54a0048b | 476 | } |
1a4d82fc | 477 | |
3157f602 XL |
478 | impl<K, V, M> FullBucket<K, V, M> |
479 | where M: Deref<Target = RawTable<K, V>> + DerefMut | |
480 | { | |
1a4d82fc JJ |
481 | /// Gets mutable references to the key and value at a given index. |
482 | pub fn read_mut(&mut self) -> (&mut K, &mut V) { | |
3157f602 | 483 | unsafe { (&mut *(self.raw.key as *mut K), &mut *(self.raw.val as *mut V)) } |
1a4d82fc JJ |
484 | } |
485 | } | |
486 | ||
3157f602 XL |
487 | impl<'t, K, V, M> FullBucket<K, V, M> |
488 | where M: Deref<Target = RawTable<K, V>> + 't | |
489 | { | |
1a4d82fc JJ |
490 | /// Exchange a bucket state for immutable references into the table. |
491 | /// Because the underlying reference to the table is also consumed, | |
492 | /// no further changes to the structure of the table are possible; | |
493 | /// in exchange for this, the returned references have a longer lifetime | |
494 | /// than the references returned by `read()`. | |
495 | pub fn into_refs(self) -> (&'t K, &'t V) { | |
3157f602 | 496 | unsafe { (&*self.raw.key, &*self.raw.val) } |
1a4d82fc JJ |
497 | } |
498 | } | |
499 | ||
3157f602 XL |
500 | impl<'t, K, V, M> FullBucket<K, V, M> |
501 | where M: Deref<Target = RawTable<K, V>> + DerefMut + 't | |
502 | { | |
1a4d82fc JJ |
503 | /// This works similarly to `into_refs`, exchanging a bucket state |
504 | /// for mutable references into the table. | |
505 | pub fn into_mut_refs(self) -> (&'t mut K, &'t mut V) { | |
3157f602 | 506 | unsafe { (&mut *(self.raw.key as *mut K), &mut *(self.raw.val as *mut V)) } |
1a4d82fc JJ |
507 | } |
508 | } | |
509 | ||
3157f602 XL |
510 | impl<K, V, M> GapThenFull<K, V, M> |
511 | where M: Deref<Target = RawTable<K, V>> | |
512 | { | |
1a4d82fc JJ |
513 | #[inline] |
514 | pub fn full(&self) -> &FullBucket<K, V, M> { | |
515 | &self.full | |
516 | } | |
517 | ||
518 | pub fn shift(mut self) -> Option<GapThenFull<K, V, M>> { | |
519 | unsafe { | |
520 | *self.gap.raw.hash = mem::replace(&mut *self.full.raw.hash, EMPTY_BUCKET); | |
54a0048b SL |
521 | ptr::copy_nonoverlapping(self.full.raw.key, self.gap.raw.key as *mut K, 1); |
522 | ptr::copy_nonoverlapping(self.full.raw.val, self.gap.raw.val as *mut V, 1); | |
1a4d82fc JJ |
523 | } |
524 | ||
525 | let FullBucket { raw: prev_raw, idx: prev_idx, .. } = self.full; | |
526 | ||
527 | match self.full.next().peek() { | |
528 | Full(bucket) => { | |
529 | self.gap.raw = prev_raw; | |
530 | self.gap.idx = prev_idx; | |
531 | ||
532 | self.full = bucket; | |
533 | ||
534 | Some(self) | |
535 | } | |
3157f602 | 536 | Empty(..) => None, |
1a4d82fc JJ |
537 | } |
538 | } | |
539 | } | |
540 | ||
541 | ||
542 | /// Rounds up to a multiple of a power of two. Returns the closest multiple | |
543 | /// of `target_alignment` that is higher or equal to `unrounded`. | |
544 | /// | |
545 | /// # Panics | |
546 | /// | |
547 | /// Panics if `target_alignment` is not a power of two. | |
e9174d1e | 548 | #[inline] |
85aaf69f | 549 | fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize { |
1a4d82fc JJ |
550 | assert!(target_alignment.is_power_of_two()); |
551 | (unrounded + target_alignment - 1) & !(target_alignment - 1) | |
552 | } | |
553 | ||
554 | #[test] | |
555 | fn test_rounding() { | |
556 | assert_eq!(round_up_to_next(0, 4), 0); | |
557 | assert_eq!(round_up_to_next(1, 4), 4); | |
558 | assert_eq!(round_up_to_next(2, 4), 4); | |
559 | assert_eq!(round_up_to_next(3, 4), 4); | |
560 | assert_eq!(round_up_to_next(4, 4), 4); | |
561 | assert_eq!(round_up_to_next(5, 4), 8); | |
562 | } | |
563 | ||
564 | // Returns a tuple of (key_offset, val_offset), | |
565 | // from the start of a mallocated array. | |
62682a34 | 566 | #[inline] |
85aaf69f | 567 | fn calculate_offsets(hashes_size: usize, |
3157f602 XL |
568 | keys_size: usize, |
569 | keys_align: usize, | |
85aaf69f | 570 | vals_align: usize) |
c34b1796 | 571 | -> (usize, usize, bool) { |
1a4d82fc | 572 | let keys_offset = round_up_to_next(hashes_size, keys_align); |
c34b1796 | 573 | let (end_of_keys, oflo) = keys_offset.overflowing_add(keys_size); |
1a4d82fc JJ |
574 | |
575 | let vals_offset = round_up_to_next(end_of_keys, vals_align); | |
576 | ||
c34b1796 | 577 | (keys_offset, vals_offset, oflo) |
1a4d82fc JJ |
578 | } |
579 | ||
580 | // Returns a tuple of (minimum required malloc alignment, hash_offset, | |
581 | // array_size), from the start of a mallocated array. | |
3157f602 XL |
582 | fn calculate_allocation(hash_size: usize, |
583 | hash_align: usize, | |
584 | keys_size: usize, | |
585 | keys_align: usize, | |
586 | vals_size: usize, | |
587 | vals_align: usize) | |
c34b1796 | 588 | -> (usize, usize, usize, bool) { |
1a4d82fc | 589 | let hash_offset = 0; |
3157f602 | 590 | let (_, vals_offset, oflo) = calculate_offsets(hash_size, keys_size, keys_align, vals_align); |
c34b1796 | 591 | let (end_of_vals, oflo2) = vals_offset.overflowing_add(vals_size); |
1a4d82fc | 592 | |
62682a34 | 593 | let align = cmp::max(hash_align, cmp::max(keys_align, vals_align)); |
1a4d82fc | 594 | |
62682a34 | 595 | (align, hash_offset, end_of_vals, oflo || oflo2) |
1a4d82fc JJ |
596 | } |
597 | ||
598 | #[test] | |
599 | fn test_offset_calculation() { | |
3157f602 XL |
600 | assert_eq!(calculate_allocation(128, 8, 15, 1, 4, 4), |
601 | (8, 0, 148, false)); | |
602 | assert_eq!(calculate_allocation(3, 1, 2, 1, 1, 1), (1, 0, 6, false)); | |
603 | assert_eq!(calculate_allocation(6, 2, 12, 4, 24, 8), (8, 0, 48, false)); | |
c34b1796 | 604 | assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144, false)); |
3157f602 XL |
605 | assert_eq!(calculate_offsets(3, 2, 1, 1), (3, 5, false)); |
606 | assert_eq!(calculate_offsets(6, 12, 4, 8), (8, 24, false)); | |
1a4d82fc JJ |
607 | } |
608 | ||
609 | impl<K, V> RawTable<K, V> { | |
610 | /// Does not initialize the buckets. The caller should ensure they, | |
611 | /// at the very least, set every hash to EMPTY_BUCKET. | |
85aaf69f | 612 | unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> { |
1a4d82fc JJ |
613 | if capacity == 0 { |
614 | return RawTable { | |
615 | size: 0, | |
616 | capacity: 0, | |
85aaf69f SL |
617 | hashes: Unique::new(EMPTY as *mut u64), |
618 | marker: marker::PhantomData, | |
1a4d82fc JJ |
619 | }; |
620 | } | |
85aaf69f | 621 | |
1a4d82fc JJ |
622 | // No need for `checked_mul` before a more restrictive check performed |
623 | // later in this method. | |
624 | let hashes_size = capacity * size_of::<u64>(); | |
3157f602 XL |
625 | let keys_size = capacity * size_of::<K>(); |
626 | let vals_size = capacity * size_of::<V>(); | |
1a4d82fc JJ |
627 | |
628 | // Allocating hashmaps is a little tricky. We need to allocate three | |
629 | // arrays, but since we know their sizes and alignments up front, | |
630 | // we just allocate a single array, and then have the subarrays | |
631 | // point into it. | |
632 | // | |
633 | // This is great in theory, but in practice getting the alignment | |
634 | // right is a little subtle. Therefore, calculating offsets has been | |
635 | // factored out into a different function. | |
3157f602 XL |
636 | let (malloc_alignment, hash_offset, size, oflo) = calculate_allocation(hashes_size, |
637 | align_of::<u64>(), | |
638 | keys_size, | |
639 | align_of::<K>(), | |
640 | vals_size, | |
641 | align_of::<V>()); | |
1a4d82fc | 642 | |
c34b1796 AL |
643 | assert!(!oflo, "capacity overflow"); |
644 | ||
1a4d82fc | 645 | // One check for overflow that covers calculation and rounding of size. |
3157f602 XL |
646 | let size_of_bucket = size_of::<u64>() |
647 | .checked_add(size_of::<K>()) | |
648 | .unwrap() | |
649 | .checked_add(size_of::<V>()) | |
650 | .unwrap(); | |
651 | assert!(size >= | |
652 | capacity.checked_mul(size_of_bucket) | |
653 | .expect("capacity overflow"), | |
1a4d82fc JJ |
654 | "capacity overflow"); |
655 | ||
656 | let buffer = allocate(size, malloc_alignment); | |
3157f602 XL |
657 | if buffer.is_null() { |
658 | ::alloc::oom() | |
659 | } | |
1a4d82fc | 660 | |
85aaf69f | 661 | let hashes = buffer.offset(hash_offset as isize) as *mut u64; |
1a4d82fc JJ |
662 | |
663 | RawTable { | |
664 | capacity: capacity, | |
3157f602 XL |
665 | size: 0, |
666 | hashes: Unique::new(hashes), | |
667 | marker: marker::PhantomData, | |
1a4d82fc JJ |
668 | } |
669 | } | |
670 | ||
671 | fn first_bucket_raw(&self) -> RawBucket<K, V> { | |
672 | let hashes_size = self.capacity * size_of::<u64>(); | |
673 | let keys_size = self.capacity * size_of::<K>(); | |
674 | ||
54a0048b | 675 | let buffer = *self.hashes as *const u8; |
3157f602 XL |
676 | let (keys_offset, vals_offset, oflo) = calculate_offsets(hashes_size, |
677 | keys_size, | |
678 | align_of::<K>(), | |
679 | align_of::<V>()); | |
c34b1796 | 680 | debug_assert!(!oflo, "capacity overflow"); |
1a4d82fc JJ |
681 | unsafe { |
682 | RawBucket { | |
85aaf69f | 683 | hash: *self.hashes, |
3157f602 XL |
684 | key: buffer.offset(keys_offset as isize) as *const K, |
685 | val: buffer.offset(vals_offset as isize) as *const V, | |
85aaf69f | 686 | _marker: marker::PhantomData, |
1a4d82fc JJ |
687 | } |
688 | } | |
689 | } | |
690 | ||
691 | /// Creates a new raw table from a given capacity. All buckets are | |
692 | /// initially empty. | |
85aaf69f | 693 | pub fn new(capacity: usize) -> RawTable<K, V> { |
1a4d82fc JJ |
694 | unsafe { |
695 | let ret = RawTable::new_uninitialized(capacity); | |
c34b1796 | 696 | ptr::write_bytes(*ret.hashes, 0, capacity); |
1a4d82fc JJ |
697 | ret |
698 | } | |
699 | } | |
700 | ||
701 | /// The hashtable's capacity, similar to a vector's. | |
85aaf69f | 702 | pub fn capacity(&self) -> usize { |
1a4d82fc JJ |
703 | self.capacity |
704 | } | |
705 | ||
706 | /// The number of elements ever `put` in the hashtable, minus the number | |
707 | /// of elements ever `take`n. | |
85aaf69f | 708 | pub fn size(&self) -> usize { |
1a4d82fc JJ |
709 | self.size |
710 | } | |
711 | ||
712 | fn raw_buckets(&self) -> RawBuckets<K, V> { | |
713 | RawBuckets { | |
714 | raw: self.first_bucket_raw(), | |
3157f602 | 715 | hashes_end: unsafe { self.hashes.offset(self.capacity as isize) }, |
85aaf69f | 716 | marker: marker::PhantomData, |
1a4d82fc JJ |
717 | } |
718 | } | |
719 | ||
720 | pub fn iter(&self) -> Iter<K, V> { | |
721 | Iter { | |
722 | iter: self.raw_buckets(), | |
723 | elems_left: self.size(), | |
724 | } | |
725 | } | |
726 | ||
727 | pub fn iter_mut(&mut self) -> IterMut<K, V> { | |
728 | IterMut { | |
729 | iter: self.raw_buckets(), | |
730 | elems_left: self.size(), | |
54a0048b | 731 | _marker: marker::PhantomData, |
1a4d82fc JJ |
732 | } |
733 | } | |
734 | ||
735 | pub fn into_iter(self) -> IntoIter<K, V> { | |
736 | let RawBuckets { raw, hashes_end, .. } = self.raw_buckets(); | |
737 | // Replace the marker regardless of lifetime bounds on parameters. | |
738 | IntoIter { | |
739 | iter: RawBuckets { | |
740 | raw: raw, | |
741 | hashes_end: hashes_end, | |
85aaf69f | 742 | marker: marker::PhantomData, |
1a4d82fc JJ |
743 | }, |
744 | table: self, | |
745 | } | |
746 | } | |
747 | ||
748 | pub fn drain(&mut self) -> Drain<K, V> { | |
749 | let RawBuckets { raw, hashes_end, .. } = self.raw_buckets(); | |
750 | // Replace the marker regardless of lifetime bounds on parameters. | |
751 | Drain { | |
752 | iter: RawBuckets { | |
753 | raw: raw, | |
754 | hashes_end: hashes_end, | |
85aaf69f | 755 | marker: marker::PhantomData, |
1a4d82fc JJ |
756 | }, |
757 | table: self, | |
758 | } | |
759 | } | |
760 | ||
761 | /// Returns an iterator that copies out each entry. Used while the table | |
762 | /// is being dropped. | |
763 | unsafe fn rev_move_buckets(&mut self) -> RevMoveBuckets<K, V> { | |
764 | let raw_bucket = self.first_bucket_raw(); | |
765 | RevMoveBuckets { | |
85aaf69f | 766 | raw: raw_bucket.offset(self.capacity as isize), |
1a4d82fc JJ |
767 | hashes_end: raw_bucket.hash, |
768 | elems_left: self.size, | |
3157f602 | 769 | marker: marker::PhantomData, |
1a4d82fc JJ |
770 | } |
771 | } | |
772 | } | |
773 | ||
774 | /// A raw iterator. The basis for some other iterators in this module. Although | |
775 | /// this interface is safe, it's not used outside this module. | |
776 | struct RawBuckets<'a, K, V> { | |
777 | raw: RawBucket<K, V>, | |
778 | hashes_end: *mut u64, | |
85aaf69f SL |
779 | |
780 | // Strictly speaking, this should be &'a (K,V), but that would | |
781 | // require that K:'a, and we often use RawBuckets<'static...> for | |
782 | // move iterations, so that messes up a lot of other things. So | |
783 | // just use `&'a (K,V)` as this is not a publicly exposed type | |
784 | // anyway. | |
785 | marker: marker::PhantomData<&'a ()>, | |
1a4d82fc JJ |
786 | } |
787 | ||
788 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
789 | impl<'a, K, V> Clone for RawBuckets<'a, K, V> { | |
790 | fn clone(&self) -> RawBuckets<'a, K, V> { | |
791 | RawBuckets { | |
792 | raw: self.raw, | |
793 | hashes_end: self.hashes_end, | |
85aaf69f | 794 | marker: marker::PhantomData, |
1a4d82fc JJ |
795 | } |
796 | } | |
797 | } | |
798 | ||
799 | ||
800 | impl<'a, K, V> Iterator for RawBuckets<'a, K, V> { | |
801 | type Item = RawBucket<K, V>; | |
802 | ||
803 | fn next(&mut self) -> Option<RawBucket<K, V>> { | |
804 | while self.raw.hash != self.hashes_end { | |
805 | unsafe { | |
806 | // We are swapping out the pointer to a bucket and replacing | |
807 | // it with the pointer to the next one. | |
808 | let prev = ptr::replace(&mut self.raw, self.raw.offset(1)); | |
809 | if *prev.hash != EMPTY_BUCKET { | |
810 | return Some(prev); | |
811 | } | |
812 | } | |
813 | } | |
814 | ||
815 | None | |
816 | } | |
817 | } | |
818 | ||
819 | /// An iterator that moves out buckets in reverse order. It leaves the table | |
820 | /// in an inconsistent state and should only be used for dropping | |
821 | /// the table's remaining entries. It's used in the implementation of Drop. | |
822 | struct RevMoveBuckets<'a, K, V> { | |
823 | raw: RawBucket<K, V>, | |
824 | hashes_end: *mut u64, | |
85aaf69f SL |
825 | elems_left: usize, |
826 | ||
827 | // As above, `&'a (K,V)` would seem better, but we often use | |
828 | // 'static for the lifetime, and this is not a publicly exposed | |
829 | // type. | |
830 | marker: marker::PhantomData<&'a ()>, | |
1a4d82fc JJ |
831 | } |
832 | ||
833 | impl<'a, K, V> Iterator for RevMoveBuckets<'a, K, V> { | |
834 | type Item = (K, V); | |
835 | ||
836 | fn next(&mut self) -> Option<(K, V)> { | |
837 | if self.elems_left == 0 { | |
838 | return None; | |
839 | } | |
840 | ||
841 | loop { | |
842 | debug_assert!(self.raw.hash != self.hashes_end); | |
843 | ||
844 | unsafe { | |
845 | self.raw = self.raw.offset(-1); | |
846 | ||
847 | if *self.raw.hash != EMPTY_BUCKET { | |
848 | self.elems_left -= 1; | |
3157f602 | 849 | return Some((ptr::read(self.raw.key), ptr::read(self.raw.val))); |
1a4d82fc JJ |
850 | } |
851 | } | |
852 | } | |
853 | } | |
854 | } | |
855 | ||
856 | /// Iterator over shared references to entries in a table. | |
857 | pub struct Iter<'a, K: 'a, V: 'a> { | |
858 | iter: RawBuckets<'a, K, V>, | |
85aaf69f | 859 | elems_left: usize, |
1a4d82fc JJ |
860 | } |
861 | ||
e9174d1e SL |
862 | unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {} |
863 | unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {} | |
864 | ||
1a4d82fc JJ |
865 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` |
866 | impl<'a, K, V> Clone for Iter<'a, K, V> { | |
867 | fn clone(&self) -> Iter<'a, K, V> { | |
868 | Iter { | |
869 | iter: self.iter.clone(), | |
3157f602 | 870 | elems_left: self.elems_left, |
1a4d82fc JJ |
871 | } |
872 | } | |
873 | } | |
874 | ||
875 | ||
876 | /// Iterator over mutable references to entries in a table. | |
877 | pub struct IterMut<'a, K: 'a, V: 'a> { | |
878 | iter: RawBuckets<'a, K, V>, | |
85aaf69f | 879 | elems_left: usize, |
54a0048b SL |
880 | // To ensure invariance with respect to V |
881 | _marker: marker::PhantomData<&'a mut V>, | |
1a4d82fc JJ |
882 | } |
883 | ||
e9174d1e SL |
884 | unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {} |
885 | // Both K: Sync and K: Send are correct for IterMut's Send impl, | |
886 | // but Send is the more useful bound | |
887 | unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {} | |
888 | ||
1a4d82fc JJ |
889 | /// Iterator over the entries in a table, consuming the table. |
890 | pub struct IntoIter<K, V> { | |
891 | table: RawTable<K, V>, | |
3157f602 | 892 | iter: RawBuckets<'static, K, V>, |
1a4d82fc JJ |
893 | } |
894 | ||
e9174d1e SL |
895 | unsafe impl<K: Sync, V: Sync> Sync for IntoIter<K, V> {} |
896 | unsafe impl<K: Send, V: Send> Send for IntoIter<K, V> {} | |
897 | ||
1a4d82fc JJ |
898 | /// Iterator over the entries in a table, clearing the table. |
899 | pub struct Drain<'a, K: 'a, V: 'a> { | |
900 | table: &'a mut RawTable<K, V>, | |
901 | iter: RawBuckets<'static, K, V>, | |
902 | } | |
903 | ||
e9174d1e SL |
904 | unsafe impl<'a, K: Sync, V: Sync> Sync for Drain<'a, K, V> {} |
905 | unsafe impl<'a, K: Send, V: Send> Send for Drain<'a, K, V> {} | |
906 | ||
1a4d82fc JJ |
907 | impl<'a, K, V> Iterator for Iter<'a, K, V> { |
908 | type Item = (&'a K, &'a V); | |
909 | ||
910 | fn next(&mut self) -> Option<(&'a K, &'a V)> { | |
911 | self.iter.next().map(|bucket| { | |
912 | self.elems_left -= 1; | |
3157f602 | 913 | unsafe { (&*bucket.key, &*bucket.val) } |
1a4d82fc JJ |
914 | }) |
915 | } | |
916 | ||
85aaf69f | 917 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
918 | (self.elems_left, Some(self.elems_left)) |
919 | } | |
920 | } | |
85aaf69f | 921 | impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { |
3157f602 XL |
922 | fn len(&self) -> usize { |
923 | self.elems_left | |
924 | } | |
85aaf69f | 925 | } |
1a4d82fc JJ |
926 | |
927 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { | |
928 | type Item = (&'a K, &'a mut V); | |
929 | ||
930 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { | |
931 | self.iter.next().map(|bucket| { | |
932 | self.elems_left -= 1; | |
3157f602 | 933 | unsafe { (&*bucket.key, &mut *(bucket.val as *mut V)) } |
1a4d82fc JJ |
934 | }) |
935 | } | |
936 | ||
85aaf69f | 937 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
938 | (self.elems_left, Some(self.elems_left)) |
939 | } | |
940 | } | |
85aaf69f | 941 | impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { |
3157f602 XL |
942 | fn len(&self) -> usize { |
943 | self.elems_left | |
944 | } | |
85aaf69f | 945 | } |
1a4d82fc JJ |
946 | |
947 | impl<K, V> Iterator for IntoIter<K, V> { | |
948 | type Item = (SafeHash, K, V); | |
949 | ||
950 | fn next(&mut self) -> Option<(SafeHash, K, V)> { | |
951 | self.iter.next().map(|bucket| { | |
952 | self.table.size -= 1; | |
953 | unsafe { | |
3157f602 | 954 | (SafeHash { hash: *bucket.hash }, ptr::read(bucket.key), ptr::read(bucket.val)) |
1a4d82fc JJ |
955 | } |
956 | }) | |
957 | } | |
958 | ||
85aaf69f | 959 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
960 | let size = self.table.size(); |
961 | (size, Some(size)) | |
962 | } | |
963 | } | |
85aaf69f | 964 | impl<K, V> ExactSizeIterator for IntoIter<K, V> { |
3157f602 XL |
965 | fn len(&self) -> usize { |
966 | self.table.size() | |
967 | } | |
85aaf69f | 968 | } |
1a4d82fc | 969 | |
85aaf69f | 970 | impl<'a, K, V> Iterator for Drain<'a, K, V> { |
1a4d82fc JJ |
971 | type Item = (SafeHash, K, V); |
972 | ||
973 | #[inline] | |
974 | fn next(&mut self) -> Option<(SafeHash, K, V)> { | |
975 | self.iter.next().map(|bucket| { | |
976 | self.table.size -= 1; | |
977 | unsafe { | |
3157f602 XL |
978 | (SafeHash { hash: ptr::replace(bucket.hash, EMPTY_BUCKET) }, |
979 | ptr::read(bucket.key), | |
980 | ptr::read(bucket.val)) | |
1a4d82fc JJ |
981 | } |
982 | }) | |
983 | } | |
984 | ||
85aaf69f | 985 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
986 | let size = self.table.size(); |
987 | (size, Some(size)) | |
988 | } | |
989 | } | |
85aaf69f | 990 | impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { |
3157f602 XL |
991 | fn len(&self) -> usize { |
992 | self.table.size() | |
993 | } | |
85aaf69f | 994 | } |
1a4d82fc | 995 | |
1a4d82fc JJ |
996 | impl<'a, K: 'a, V: 'a> Drop for Drain<'a, K, V> { |
997 | fn drop(&mut self) { | |
b039eaaf | 998 | for _ in self {} |
1a4d82fc JJ |
999 | } |
1000 | } | |
1001 | ||
1002 | impl<K: Clone, V: Clone> Clone for RawTable<K, V> { | |
1003 | fn clone(&self) -> RawTable<K, V> { | |
1004 | unsafe { | |
1005 | let mut new_ht = RawTable::new_uninitialized(self.capacity()); | |
1006 | ||
1007 | { | |
1008 | let cap = self.capacity(); | |
1009 | let mut new_buckets = Bucket::first(&mut new_ht); | |
1010 | let mut buckets = Bucket::first(self); | |
1011 | while buckets.index() != cap { | |
1012 | match buckets.peek() { | |
1013 | Full(full) => { | |
1014 | let (h, k, v) = { | |
1015 | let (k, v) = full.read(); | |
1016 | (full.hash(), k.clone(), v.clone()) | |
1017 | }; | |
1018 | *new_buckets.raw.hash = h.inspect(); | |
54a0048b SL |
1019 | ptr::write(new_buckets.raw.key as *mut K, k); |
1020 | ptr::write(new_buckets.raw.val as *mut V, v); | |
1a4d82fc JJ |
1021 | } |
1022 | Empty(..) => { | |
1023 | *new_buckets.raw.hash = EMPTY_BUCKET; | |
1024 | } | |
1025 | } | |
1026 | new_buckets.next(); | |
1027 | buckets.next(); | |
1028 | } | |
1029 | }; | |
1030 | ||
1031 | new_ht.size = self.size(); | |
1032 | ||
1033 | new_ht | |
1034 | } | |
1035 | } | |
1036 | } | |
1037 | ||
1a4d82fc | 1038 | impl<K, V> Drop for RawTable<K, V> { |
b039eaaf | 1039 | #[unsafe_destructor_blind_to_params] |
1a4d82fc | 1040 | fn drop(&mut self) { |
c34b1796 | 1041 | if self.capacity == 0 || self.capacity == mem::POST_DROP_USIZE { |
1a4d82fc JJ |
1042 | return; |
1043 | } | |
85aaf69f | 1044 | |
1a4d82fc JJ |
1045 | // This is done in reverse because we've likely partially taken |
1046 | // some elements out with `.into_iter()` from the front. | |
1047 | // Check if the size is 0, so we don't do a useless scan when | |
1048 | // dropping empty tables such as on resize. | |
1049 | // Also avoid double drop of elements that have been already moved out. | |
1050 | unsafe { | |
3157f602 XL |
1051 | if needs_drop::<(K, V)>() { |
1052 | // avoid linear runtime for types that don't need drop | |
7453a54e SL |
1053 | for _ in self.rev_move_buckets() {} |
1054 | } | |
1a4d82fc JJ |
1055 | } |
1056 | ||
1057 | let hashes_size = self.capacity * size_of::<u64>(); | |
1058 | let keys_size = self.capacity * size_of::<K>(); | |
1059 | let vals_size = self.capacity * size_of::<V>(); | |
3157f602 XL |
1060 | let (align, _, size, oflo) = calculate_allocation(hashes_size, |
1061 | align_of::<u64>(), | |
1062 | keys_size, | |
1063 | align_of::<K>(), | |
1064 | vals_size, | |
1065 | align_of::<V>()); | |
c34b1796 AL |
1066 | |
1067 | debug_assert!(!oflo, "should be impossible"); | |
1a4d82fc JJ |
1068 | |
1069 | unsafe { | |
85aaf69f | 1070 | deallocate(*self.hashes as *mut u8, size, align); |
1a4d82fc JJ |
1071 | // Remember how everything was allocated out of one buffer |
1072 | // during initialization? We only need one call to free here. | |
1073 | } | |
1074 | } | |
1075 | } |