src/libstd/collections/hash/table.rs

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