src/libstd/collections/hash/table.rs

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