about summary refs log tree commit diff
path: root/src/libcore/hashmap.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/libcore/hashmap.rs')
-rw-r--r--src/libcore/hashmap.rs173
1 files changed, 171 insertions, 2 deletions
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index d4af0ffe7fe..2869c198ca2 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -186,6 +186,7 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage0)]
     #[inline(always)]
     fn value_for_bucket(&self, idx: uint) -> &'self V {
         match self.buckets[idx] {
@@ -194,6 +195,18 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V {
+        match self.buckets[idx] {
+            Some(ref bkt) => &bkt.value,
+            None => fail!(~"HashMap::find: internal logic error"),
+        }
+    }
+
+    #[cfg(stage0)]
     #[inline(always)]
     fn mut_value_for_bucket(&mut self, idx: uint) -> &'self mut V {
         match self.buckets[idx] {
@@ -202,6 +215,17 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V {
+        match self.buckets[idx] {
+            Some(ref mut bkt) => &mut bkt.value,
+            None => unreachable()
+        }
+    }
+
     /// Inserts the key value pair into the buckets.
     /// Assumes that there will be a bucket.
     /// True if there was no previous entry with that key
@@ -307,6 +331,7 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
     }
 
     /// Visit all key-value pairs
+    #[cfg(stage0)]
     fn each(&self, blk: &fn(&'self K, &'self V) -> bool) {
         for uint::range(0, self.buckets.len()) |i| {
             for self.buckets[i].each |bucket| {
@@ -317,19 +342,41 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Visit all key-value pairs
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, blk: &fn(&'a K, &'a V) -> bool) {
+        for uint::range(0, self.buckets.len()) |i| {
+            for self.buckets[i].each |bucket| {
+                if !blk(&bucket.key, &bucket.value) {
+                    return;
+                }
+            }
+        }
+    }
+
     /// Visit all keys
     fn each_key(&self, blk: &fn(k: &K) -> bool) {
         self.each(|k, _| blk(k))
     }
 
     /// Visit all values
+    #[cfg(stage0)]
     fn each_value(&self, blk: &fn(v: &V) -> bool) {
         self.each(|_, v| blk(v))
     }
 
+    /// Visit all values
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_value<'a>(&'a self, blk: &fn(v: &'a V) -> bool) {
+        self.each(|_, v| blk(v))
+    }
+
     /// Iterate over the map and mutate the contained values
-    fn mutate_values(&mut self, blk: &fn(&'self K,
-                          &'self mut V) -> bool) {
+    fn mutate_values(&mut self, blk: &fn(&K, &mut V) -> bool) {
         for uint::range(0, self.buckets.len()) |i| {
             match self.buckets[i] {
               Some(Bucket{key: ref key, value: ref mut value, _}) => {
@@ -341,6 +388,7 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
     }
 
     /// Return a reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find(&self, k: &K) -> Option<&'self V> {
         match self.bucket_for_key(k) {
             FoundEntry(idx) => Some(self.value_for_bucket(idx)),
@@ -348,7 +396,19 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Return a reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
+        match self.bucket_for_key(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
+        }
+    }
+
     /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find_mut(&mut self, k: &K) -> Option<&'self mut V> {
         let idx = match self.bucket_for_key(k) {
             FoundEntry(idx) => idx,
@@ -359,6 +419,20 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
+        let idx = match self.bucket_for_key(k) {
+            FoundEntry(idx) => idx,
+            TableFull | FoundHole(_) => return None
+        };
+        unsafe {  // FIXME(#4903)---requires flow-sensitive borrow checker
+            Some(::cast::transmute_mut_region(self.mut_value_for_bucket(idx)))
+        }
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -431,6 +505,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
 
     /// Return the value corresponding to the key in the map, or insert
     /// and return the value if it doesn't exist.
+    #[cfg(stage0)]
     fn find_or_insert(&mut self, k: K, v: V) -> &'self V {
         if self.size >= self.resize_at {
             // n.b.: We could also do this after searching, so
@@ -459,8 +534,42 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    /// Return the value corresponding to the key in the map, or insert
+    /// and return the value if it doesn't exist.
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
+        }
+    }
+
     /// Return the value corresponding to the key in the map, or create,
     /// insert, and return a new value if it doesn't exist.
+    #[cfg(stage0)]
     fn find_or_insert_with(&mut self, k: K, f: &fn(&K) -> V) -> &'self V {
         if self.size >= self.resize_at {
             // n.b.: We could also do this after searching, so
@@ -490,6 +599,40 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    /// Return the value corresponding to the key in the map, or create,
+    /// insert, and return a new value if it doesn't exist.
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_or_insert_with<'a>(&'a mut self, k: K, f: &fn(&K) -> V) -> &'a V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                let v = f(&k);
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
+        }
+    }
+
     fn consume(&mut self, f: &fn(K, V)) {
         let mut buckets = ~[];
         self.buckets <-> buckets;
@@ -506,6 +649,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage0)]
     fn get(&self, k: &K) -> &'self V {
         match self.find(k) {
             Some(v) => v,
@@ -513,6 +657,16 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get<'a>(&'a self, k: &K) -> &'a V {
+        match self.find(k) {
+            Some(v) => v,
+            None => fail!(fmt!("No entry found for key: %?", k)),
+        }
+    }
+
     /// Return true if the map contains a value for the specified key,
     /// using equivalence
     fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, key: &Q)
@@ -525,6 +679,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
 
     /// Return the value corresponding to the key in the map, using
     /// equivalence
+    #[cfg(stage0)]
     fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
                                               -> Option<&'self V> {
         match self.bucket_for_key_equiv(k) {
@@ -532,6 +687,20 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
             TableFull | FoundHole(_) => None,
         }
     }
+
+    /// Return the value corresponding to the key in the map, using
+    /// equivalence
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_equiv<'a, Q:Hash + IterBytes + Equiv<K>>(
+        &'a self, k: &Q) -> Option<&'a V>
+    {
+        match self.bucket_for_key_equiv(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
+        }
+    }
 }
 
 impl<K:Hash + IterBytes + Eq,V:Eq> Eq for HashMap<K, V> {
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2025-10-30 01:05:24 +0000