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