auto merge of #13440 : huonw/rust/strbuf, r=alexcrichton

libstd: Implement `StrBuf`, a new string buffer type like `Vec`, and port all code over to use it.

Rebased & tests-fixed version of https://github.com/mozilla/rust/pull/13269

2 files changed, 123 insertions, 73 deletions

diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
index cdcc05bf729..9d33ce6fe65 100644
--- a/src/libcollections/bitv.rs
+++ b/src/libcollections/bitv.rs
@@ -15,8 +15,9 @@ use std::cmp;
 use std::iter::RandomAccessIterator;
 use std::iter::{Rev, Enumerate, Repeat, Map, Zip};
 use std::ops;
-use std::uint;
 use std::slice;
+use std::strbuf::StrBuf;
+use std::uint;
 
 #[deriving(Clone)]
 struct SmallBitv {
@@ -499,7 +500,7 @@ impl Bitv {
      * character is either '0' or '1'.
      */
      pub fn to_str(&self) -> ~str {
-        let mut rs = ~"";
+        let mut rs = StrBuf::new();
         for i in self.iter() {
             if i {
                 rs.push_char('1');
@@ -507,7 +508,7 @@ impl Bitv {
                 rs.push_char('0');
             }
         };
-        rs
+        rs.into_owned()
      }
 
 
diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs
index dadf92a58e0..9982a0c4822 100644
--- a/src/libcollections/hashmap.rs
+++ b/src/libcollections/hashmap.rs
@@ -795,6 +795,97 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     fn search(&self, k: &K) -> Option<table::FullIndex> {
         self.search_hashed(&self.make_hash(k), k)
     }
+
+    fn pop_internal(&mut self, starting_index: table::FullIndex) -> Option<V> {
+        let starting_probe = starting_index.raw_index();
+
+        let ending_probe = {
+            let mut probe = self.probe_next(starting_probe);
+            for _ in range(0u, self.table.size()) {
+                match self.table.peek(probe) {
+                    table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
+                    table::Full(idx) => {
+                        // Bucket that isn't us, which has a non-zero probe distance.
+                        // This isn't the ending index, so keep searching.
+                        if self.bucket_distance(&idx) != 0 {
+                            probe = self.probe_next(probe);
+                            continue;
+                        }
+
+                        // if we do have a bucket_distance of zero, we're at the end
+                        // of what we need to shift.
+                    }
+                }
+                break;
+            }
+
+            probe
+        };
+
+        let (_, _, retval) = self.table.take(starting_index);
+
+        let mut      probe = starting_probe;
+        let mut next_probe = self.probe_next(probe);
+
+        // backwards-shift all the elements after our newly-deleted one.
+        while next_probe != ending_probe {
+            match self.table.peek(next_probe) {
+                table::Empty(_) => {
+                    // nothing to shift in. just empty it out.
+                    match self.table.peek(probe) {
+                        table::Empty(_) => {},
+                        table::Full(idx) => { self.table.take(idx); }
+                    }
+                },
+                table::Full(next_idx) => {
+                    // something to shift. move it over!
+                    let next_hash = next_idx.hash();
+                    let (_, next_key, next_val) = self.table.take(next_idx);
+                    match self.table.peek(probe) {
+                        table::Empty(idx) => {
+                            self.table.put(idx, next_hash, next_key, next_val);
+                        },
+                        table::Full(idx) => {
+                            let (emptyidx, _, _) = self.table.take(idx);
+                            self.table.put(emptyidx, next_hash, next_key, next_val);
+                        }
+                    }
+                }
+            }
+
+            probe = next_probe;
+            next_probe = self.probe_next(next_probe);
+        }
+
+        // Done the backwards shift, but there's still an element left!
+        // Empty it out.
+        match self.table.peek(probe) {
+            table::Empty(_) => {},
+            table::Full(idx) => { self.table.take(idx); }
+        }
+
+        // Now we're done all our shifting. Return the value we grabbed
+        // earlier.
+        return Some(retval);
+    }
+
+    /// Like `pop`, but can operate on any type that is equivalent to a key.
+    #[experimental]
+    pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
+        if self.table.size() == 0 {
+            return None
+        }
+
+        let potential_new_size = self.table.size() - 1;
+        self.make_some_room(potential_new_size);
+
+        let starting_index = match self.search_equiv(k) {
+            Some(idx) => idx,
+            None      => return None,
+        };
+
+        self.pop_internal(starting_index)
+    }
 }
 
 impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H> {
@@ -894,77 +985,9 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V
             None      => return None,
         };
 
-        let starting_probe = starting_index.raw_index();
-
-        let ending_probe = {
-            let mut probe = self.probe_next(starting_probe);
-            for _ in range(0u, self.table.size()) {
-                match self.table.peek(probe) {
-                    table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
-                    table::Full(idx) => {
-                        // Bucket that isn't us, which has a non-zero probe distance.
-                        // This isn't the ending index, so keep searching.
-                        if self.bucket_distance(&idx) != 0 {
-                            probe = self.probe_next(probe);
-                            continue;
-                        }
-
-                        // if we do have a bucket_distance of zero, we're at the end
-                        // of what we need to shift.
-                    }
-                }
-                break;
-            }
-
-            probe
-        };
-
-        let (_, _, retval) = self.table.take(starting_index);
-
-        let mut      probe = starting_probe;
-        let mut next_probe = self.probe_next(probe);
-
-        // backwards-shift all the elements after our newly-deleted one.
-        while next_probe != ending_probe {
-            match self.table.peek(next_probe) {
-                table::Empty(_) => {
-                    // nothing to shift in. just empty it out.
-                    match self.table.peek(probe) {
-                        table::Empty(_) => {},
-                        table::Full(idx) => { self.table.take(idx); }
-                    }
-                },
-                table::Full(next_idx) => {
-                    // something to shift. move it over!
-                    let next_hash = next_idx.hash();
-                    let (_, next_key, next_val) = self.table.take(next_idx);
-                    match self.table.peek(probe) {
-                        table::Empty(idx) => {
-                            self.table.put(idx, next_hash, next_key, next_val);
-                        },
-                        table::Full(idx) => {
-                            let (emptyidx, _, _) = self.table.take(idx);
-                            self.table.put(emptyidx, next_hash, next_key, next_val);
-                        }
-                    }
-                }
-            }
-
-            probe = next_probe;
-            next_probe = self.probe_next(next_probe);
-        }
-
-        // Done the backwards shift, but there's still an element left!
-        // Empty it out.
-        match self.table.peek(probe) {
-            table::Empty(_) => {},
-            table::Full(idx) => { self.table.take(idx); }
-        }
-
-        // Now we're done all our shifting. Return the value we grabbed
-        // earlier.
-        return Some(retval);
+        self.pop_internal(starting_index)
     }
+
 }
 
 impl<K: Hash + TotalEq, V> HashMap<K, V, sip::SipHasher> {
@@ -1571,10 +1594,27 @@ pub type SetAlgebraItems<'a, T, H> =
 #[cfg(test)]
 mod test_map {
     use super::HashMap;
+    use std::cmp::Equiv;
+    use std::hash::Hash;
     use std::iter::{Iterator,range_inclusive,range_step_inclusive};
     use std::local_data;
     use std::vec;
 
+    struct KindaIntLike(int);
+
+    impl Equiv<int> for KindaIntLike {
+        fn equiv(&self, other: &int) -> bool {
+            let KindaIntLike(this) = *self;
+            this == *other
+        }
+    }
+    impl<S: Writer> Hash<S> for KindaIntLike {
+        fn hash(&self, state: &mut S) {
+            let KindaIntLike(this) = *self;
+            this.hash(state)
+        }
+    }
+
     #[test]
     fn test_create_capacity_zero() {
         let mut m = HashMap::with_capacity(0);
@@ -1815,6 +1855,15 @@ mod test_map {
     }
 
     #[test]
+    #[allow(experimental)]
+    fn test_pop_equiv() {
+        let mut m = HashMap::new();
+        m.insert(1, 2);
+        assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
+        assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
+    }
+
+    #[test]
     fn test_swap() {
         let mut m = HashMap::new();
         assert_eq!(m.swap(1, 2), None);