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 (key_offset, val_offset),
 530 // from the start of a mallocated array.
 531 fn calculate_offsets(hashes_size: uint,
 532                      keys_size: uint, keys_align: uint,
 533                      vals_align: uint)
 534                      -> (uint, uint) {
 535     let keys_offset = round_up_to_next(hashes_size, keys_align);
 536     let end_of_keys = keys_offset + keys_size;
 537
 538     let vals_offset = round_up_to_next(end_of_keys, vals_align);
 539
 540     (keys_offset, vals_offset)
 541 }
 542
 543 // Returns a tuple of (minimum required malloc alignment, hash_offset,
 544 // array_size), from the start of a mallocated array.
 545 fn calculate_allocation(hash_size: uint, hash_align: uint,
 546                         keys_size: uint, keys_align: uint,
 547                         vals_size: uint, vals_align: uint)
 548                         -> (uint, uint, uint) {
 549     let hash_offset = 0;
 550     let (_, vals_offset) = calculate_offsets(hash_size,
 551                                              keys_size, keys_align,
 552                                                         vals_align);
 553     let end_of_vals = vals_offset + vals_size;
 554
 555     let min_align = cmp::max(hash_align, cmp::max(keys_align, vals_align));
 556
 557     (min_align, hash_offset, end_of_vals)
 558 }
 559
 560 #[test]
 561 fn test_offset_calculation() {
 562     assert_eq!(calculate_allocation(128, 8, 15, 1, 4,  4), (8, 0, 148));
 563     assert_eq!(calculate_allocation(3,   1, 2,  1, 1,  1), (1, 0, 6));
 564     assert_eq!(calculate_allocation(6,   2, 12, 4, 24, 8), (8, 0, 48));
 565     assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144));
 566     assert_eq!(calculate_offsets(3,   2,  1, 1), (3,   5));
 567     assert_eq!(calculate_offsets(6,   12, 4, 8), (8,   24));
 568 }
 569
 570 impl<K, V> RawTable<K, V> {
 571     /// Does not initialize the buckets. The caller should ensure they,
 572     /// at the very least, set every hash to EMPTY_BUCKET.
 573     unsafe fn new_uninitialized(capacity: uint) -> RawTable<K, V> {
 574         if capacity == 0 {
 575             return RawTable {
 576                 size: 0,
 577                 capacity: 0,
 578                 hashes: 0 as *mut u64,
 579                 marker: marker::CovariantType,
 580             };
 581         }
 582         // No need for `checked_mul` before a more restrictive check performed
 583         // later in this method.
 584         let hashes_size = capacity * size_of::<u64>();
 585         let keys_size   = capacity * size_of::< K >();
 586         let vals_size   = capacity * size_of::< V >();
 587
 588         // Allocating hashmaps is a little tricky. We need to allocate three
 589         // arrays, but since we know their sizes and alignments up front,
 590         // we just allocate a single array, and then have the subarrays
 591         // point into it.
 592         //
 593         // This is great in theory, but in practice getting the alignment
 594         // right is a little subtle. Therefore, calculating offsets has been
 595         // factored out into a different function.
 596         let (malloc_alignment, hash_offset, size) =
 597             calculate_allocation(
 598                 hashes_size, min_align_of::<u64>(),
 599                 keys_size,   min_align_of::< K >(),
 600                 vals_size,   min_align_of::< V >());
 601
 602         // One check for overflow that covers calculation and rounding of size.
 603         let size_of_bucket = size_of::<u64>().checked_add(&size_of::<K>()).unwrap()
 604                                              .checked_add(&size_of::<V>()).unwrap();
 605         assert!(size >= capacity.checked_mul(&size_of_bucket)
 606                                 .expect("capacity overflow"),
 607                 "capacity overflow");
 608
 609         let buffer = allocate(size, malloc_alignment);
 610
 611         let hashes = buffer.offset(hash_offset as int) as *mut u64;
 612
 613         RawTable {
 614             capacity: capacity,
 615             size:     0,
 616             hashes:   hashes,
 617             marker:   marker::CovariantType,
 618         }
 619     }
 620
 621     fn first_bucket_raw(&self) -> RawBucket<K, V> {
 622         let hashes_size = self.capacity * size_of::<u64>();
 623         let keys_size = self.capacity * size_of::<K>();
 624
 625         let buffer = self.hashes as *mut u8;
 626         let (keys_offset, vals_offset) = calculate_offsets(hashes_size,
 627                                                            keys_size, min_align_of::<K>(),
 628                                                            min_align_of::<V>());
 629
 630         unsafe {
 631             RawBucket {
 632                 hash: self.hashes,
 633                 key:  buffer.offset(keys_offset as int) as *mut K,
 634                 val:  buffer.offset(vals_offset as int) as *mut V
 635             }
 636         }
 637     }
 638
 639     /// Creates a new raw table from a given capacity. All buckets are
 640     /// initially empty.
 641     #[allow(experimental)]
 642     pub fn new(capacity: uint) -> RawTable<K, V> {
 643         unsafe {
 644             let ret = RawTable::new_uninitialized(capacity);
 645             zero_memory(ret.hashes, capacity);
 646             ret
 647         }
 648     }
 649
 650     /// The hashtable's capacity, similar to a vector's.
 651     pub fn capacity(&self) -> uint {
 652         self.capacity
 653     }
 654
 655     /// The number of elements ever `put` in the hashtable, minus the number
 656     /// of elements ever `take`n.
 657     pub fn size(&self) -> uint {
 658         self.size
 659     }
 660
 661     fn raw_buckets(&self) -> RawBuckets<K, V> {
 662         RawBuckets {
 663             raw: self.first_bucket_raw(),
 664             hashes_end: unsafe {
 665                 self.hashes.offset(self.capacity as int)
 666             }
 667         }
 668     }
 669
 670     pub fn iter(&self) -> Entries<K, V> {
 671         Entries {
 672             iter: self.raw_buckets(),
 673             elems_left: self.size(),
 674         }
 675     }
 676
 677     pub fn iter_mut(&mut self) -> MutEntries<K, V> {
 678         MutEntries {
 679             iter: self.raw_buckets(),
 680             elems_left: self.size(),
 681         }
 682     }
 683
 684     pub fn into_iter(self) -> MoveEntries<K, V> {
 685         MoveEntries {
 686             iter: self.raw_buckets(),
 687             table: self,
 688         }
 689     }
 690
 691     /// Returns an iterator that copies out each entry. Used while the table
 692     /// is being dropped.
 693     unsafe fn rev_move_buckets(&mut self) -> RevMoveBuckets<K, V> {
 694         let raw_bucket = self.first_bucket_raw();
 695         RevMoveBuckets {
 696             raw: raw_bucket.offset(self.capacity as int),
 697             hashes_end: raw_bucket.hash,
 698             elems_left: self.size
 699         }
 700     }
 701 }
 702
 703 /// A raw iterator. The basis for some other iterators in this module. Although
 704 /// this interface is safe, it's not used outside this module.
 705 struct RawBuckets<'a, K, V> {
 706     raw: RawBucket<K, V>,
 707     hashes_end: *mut u64
 708 }
 709
 710 impl<'a, K, V> Iterator<RawBucket<K, V>> for RawBuckets<'a, K, V> {
 711     fn next(&mut self) -> Option<RawBucket<K, V>> {
 712         while self.raw.hash != self.hashes_end {
 713             unsafe {
 714                 // We are swapping out the pointer to a bucket and replacing
 715                 // it with the pointer to the next one.
 716                 let prev = ptr::replace(&mut self.raw, self.raw.offset(1));
 717                 if *prev.hash != EMPTY_BUCKET {
 718                     return Some(prev);
 719                 }
 720             }
 721         }
 722
 723         None
 724     }
 725 }
 726
 727 /// An iterator that moves out buckets in reverse order. It leaves the table
 728 /// in an an inconsistent state and should only be used for dropping
 729 /// the table's remaining entries. It's used in the implementation of Drop.
 730 struct RevMoveBuckets<'a, K, V> {
 731     raw: RawBucket<K, V>,
 732     hashes_end: *mut u64,
 733     elems_left: uint
 734 }
 735
 736 impl<'a, K, V> Iterator<(K, V)> for RevMoveBuckets<'a, K, V> {
 737     fn next(&mut self) -> Option<(K, V)> {
 738         if self.elems_left == 0 {
 739             return None;
 740         }
 741
 742         loop {
 743             debug_assert!(self.raw.hash != self.hashes_end);
 744
 745             unsafe {
 746                 self.raw = self.raw.offset(-1);
 747
 748                 if *self.raw.hash != EMPTY_BUCKET {
 749                     self.elems_left -= 1;
 750                     return Some((
 751                         ptr::read(self.raw.key as *const K),
 752                         ptr::read(self.raw.val as *const V)
 753                     ));
 754                 }
 755             }
 756         }
 757     }
 758 }
 759
 760 /// Iterator over shared references to entries in a table.
 761 pub struct Entries<'a, K: 'a, V: 'a> {
 762     iter: RawBuckets<'a, K, V>,
 763     elems_left: uint,
 764 }
 765
 766 /// Iterator over mutable references to entries in a table.
 767 pub struct MutEntries<'a, K: 'a, V: 'a> {
 768     iter: RawBuckets<'a, K, V>,
 769     elems_left: uint,
 770 }
 771
 772 /// Iterator over the entries in a table, consuming the table.
 773 pub struct MoveEntries<K, V> {
 774     table: RawTable<K, V>,
 775     iter: RawBuckets<'static, K, V>
 776 }
 777
 778 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
 779     fn next(&mut self) -> Option<(&'a K, &'a V)> {
 780         self.iter.next().map(|bucket| {
 781             self.elems_left -= 1;
 782             unsafe {
 783                 (&*bucket.key,
 784                  &*bucket.val)
 785             }
 786         })
 787     }
 788
 789     fn size_hint(&self) -> (uint, Option<uint>) {
 790         (self.elems_left, Some(self.elems_left))
 791     }
 792 }
 793
 794 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
 795     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
 796         self.iter.next().map(|bucket| {
 797             self.elems_left -= 1;
 798             unsafe {
 799                 (&*bucket.key,
 800                  &mut *bucket.val)
 801             }
 802         })
 803     }
 804
 805     fn size_hint(&self) -> (uint, Option<uint>) {
 806         (self.elems_left, Some(self.elems_left))
 807     }
 808 }
 809
 810 impl<K, V> Iterator<(SafeHash, K, V)> for MoveEntries<K, V> {
 811     fn next(&mut self) -> Option<(SafeHash, K, V)> {
 812         self.iter.next().map(|bucket| {
 813             self.table.size -= 1;
 814             unsafe {
 815                 (
 816                     SafeHash {
 817                         hash: *bucket.hash,
 818                     },
 819                     ptr::read(bucket.key as *const K),
 820                     ptr::read(bucket.val as *const V)
 821                 )
 822             }
 823         })
 824     }
 825
 826     fn size_hint(&self) -> (uint, Option<uint>) {
 827         let size = self.table.size();
 828         (size, Some(size))
 829     }
 830 }
 831
 832 impl<K: Clone, V: Clone> Clone for RawTable<K, V> {
 833     fn clone(&self) -> RawTable<K, V> {
 834         unsafe {
 835             let mut new_ht = RawTable::new_uninitialized(self.capacity());
 836
 837             {
 838                 let cap = self.capacity();
 839                 let mut new_buckets = Bucket::first(&mut new_ht);
 840                 let mut buckets = Bucket::first(self);
 841                 while buckets.index() != cap {
 842                     match buckets.peek() {
 843                         Full(full) => {
 844                             let (h, k, v) = {
 845                                 let (k, v) = full.read();
 846                                 (full.hash(), k.clone(), v.clone())
 847                             };
 848                             *new_buckets.raw.hash = h.inspect();
 849                             mem::overwrite(new_buckets.raw.key, k);
 850                             mem::overwrite(new_buckets.raw.val, v);
 851                         }
 852                         Empty(..) => {
 853                             *new_buckets.raw.hash = EMPTY_BUCKET;
 854                         }
 855                     }
 856                     new_buckets.next();
 857                     buckets.next();
 858                 }
 859             };
 860
 861             new_ht.size = self.size();
 862
 863             new_ht
 864         }
 865     }
 866 }
 867
 868 #[unsafe_destructor]
 869 impl<K, V> Drop for RawTable<K, V> {
 870     fn drop(&mut self) {
 871         if self.hashes.is_null() {
 872             return;
 873         }
 874         // This is done in reverse because we've likely partially taken
 875         // some elements out with `.into_iter()` from the front.
 876         // Check if the size is 0, so we don't do a useless scan when
 877         // dropping empty tables such as on resize.
 878         // Also avoid double drop of elements that have been already moved out.
 879         unsafe {
 880             for _ in self.rev_move_buckets() {}
 881         }
 882
 883         let hashes_size = self.capacity * size_of::<u64>();
 884         let keys_size = self.capacity * size_of::<K>();
 885         let vals_size = self.capacity * size_of::<V>();
 886         let (align, _, size) = calculate_allocation(hashes_size, min_align_of::<u64>(),
 887                                                     keys_size, min_align_of::<K>(),
 888                                                     vals_size, min_align_of::<V>());
 889
 890         unsafe {
 891             deallocate(self.hashes as *mut u8, size, align);
 892             // Remember how everything was allocated out of one buffer
 893             // during initialization? We only need one call to free here.
 894         }
 895     }
 896 }