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