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