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