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