From d8e45ea7c054b4ad6fb82ec3a9fcf1736b4d7260 Mon Sep 17 00:00:00 2001 From: Patrick Walton Date: Wed, 2 Apr 2014 16:54:22 -0700 Subject: libstd: Implement `StrBuf`, a new string buffer type like `Vec`, and port all code over to use it. --- src/libcollections/bitv.rs | 7 +- src/libcollections/hashmap.rs | 181 ++++++++++++++++++++++++++---------------- 2 files changed, 115 insertions(+), 73 deletions(-) (limited to 'src/libcollections') diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs index 510e8908427..49865cf5272 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 8090b2cea8c..bd0e2ebec6f 100644 --- a/src/libcollections/hashmap.rs +++ b/src/libcollections/hashmap.rs @@ -795,6 +795,97 @@ impl, V, S, H: Hasher> HashMap { fn search(&self, k: &K) -> Option { self.search_hashed(&self.make_hash(k), k) } + + fn pop_internal(&mut self, starting_index: table::FullIndex) -> Option { + 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 + Equiv>(&mut self, k: &Q) -> Option { + 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, V, S, H: Hasher> Container for HashMap { @@ -894,77 +985,9 @@ impl, V, S, H: Hasher> MutableMap for HashMap 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 HashMap { @@ -1571,10 +1594,20 @@ pub type SetAlgebraItems<'a, T, H> = #[cfg(test)] mod test_map { use super::HashMap; + use std::cmp::Equiv; use std::iter::{Iterator,range_inclusive,range_step_inclusive}; use std::local_data; use std::vec; + struct KindaIntLike(int); + + impl Equiv for KindaIntLike { + fn equiv(&self, other: &int) -> bool { + let KindaIntLike(this) = *self; + this == *other + } + } + #[test] fn test_create_capacity_zero() { let mut m = HashMap::with_capacity(0); @@ -1814,6 +1847,14 @@ mod test_map { assert_eq!(m.pop(&1), None); } + #[test] + 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(); -- cgit 1.4.1-3-g733a5 From def90f43e2df9968cda730a2a30cb7ccb9513002 Mon Sep 17 00:00:00 2001 From: Huon Wilson Date: Thu, 10 Apr 2014 20:55:34 +1000 Subject: Fix tests. Add Vec conversion to StrBuf. --- src/libcollections/hashmap.rs | 12 +++++- src/libglob/lib.rs | 8 ++-- src/libnative/io/process.rs | 2 +- src/libstd/hash/sip.rs | 2 +- src/libstd/strbuf.rs | 21 +++++++++- src/test/bench/shootout-chameneos-redux.rs | 57 ++++++++++++++++----------- src/test/bench/shootout-k-nucleotide-pipes.rs | 20 +++------- src/test/bench/shootout-k-nucleotide.rs | 26 ++++++------ 8 files changed, 88 insertions(+), 60 deletions(-) (limited to 'src/libcollections') diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs index bd0e2ebec6f..9d08bf17668 100644 --- a/src/libcollections/hashmap.rs +++ b/src/libcollections/hashmap.rs @@ -1595,6 +1595,7 @@ pub type SetAlgebraItems<'a, T, H> = 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; @@ -1607,6 +1608,12 @@ mod test_map { this == *other } } + impl Hash for KindaIntLike { + fn hash(&self, state: &mut S) { + let KindaIntLike(this) = *self; + this.hash(state) + } + } #[test] fn test_create_capacity_zero() { @@ -1848,11 +1855,12 @@ 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)); + assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2)); + assert_eq!(m.pop_equiv(&KindaIntLike(1)), None); } #[test] diff --git a/src/libglob/lib.rs b/src/libglob/lib.rs index e7661b26b76..3cad5bf8175 100644 --- a/src/libglob/lib.rs +++ b/src/libglob/lib.rs @@ -462,8 +462,8 @@ impl Pattern { fn fill_todo(todo: &mut Vec<(Path, uint)>, patterns: &[Pattern], idx: uint, path: &Path, options: MatchOptions) { // convert a pattern that's just many Char(_) to a string - fn pattern_as_str(pattern: &Pattern) -> Option<~str> { - let mut s = ~""; + fn pattern_as_str(pattern: &Pattern) -> Option { + let mut s = StrBuf::new(); for token in pattern.tokens.iter() { match *token { Char(c) => s.push_char(c), @@ -493,8 +493,8 @@ fn fill_todo(todo: &mut Vec<(Path, uint)>, patterns: &[Pattern], idx: uint, path // continue. So instead of passing control back to the iterator, // we can just check for that one entry and potentially recurse // right away. - let special = "." == s || ".." == s; - let next_path = path.join(s); + let special = "." == s.as_slice() || ".." == s.as_slice(); + let next_path = path.join(s.as_slice()); if (special && path.is_dir()) || (!special && next_path.exists()) { add(todo, next_path); } diff --git a/src/libnative/io/process.rs b/src/libnative/io/process.rs index 8ef46239e61..e3bb938995b 100644 --- a/src/libnative/io/process.rs +++ b/src/libnative/io/process.rs @@ -402,7 +402,7 @@ fn make_command_line(prog: &str, args: &[~str]) -> ~str { cmd.push_char(' '); append_arg(&mut cmd, *arg); } - return cmd.to_owned_str(); + return cmd.into_owned(); fn append_arg(cmd: &mut StrBuf, arg: &str) { let quote = arg.chars().any(|c| c == ' ' || c == '\t'); diff --git a/src/libstd/hash/sip.rs b/src/libstd/hash/sip.rs index 69b35df50e4..4a523e3d09e 100644 --- a/src/libstd/hash/sip.rs +++ b/src/libstd/hash/sip.rs @@ -291,7 +291,7 @@ mod tests { use iter::Iterator; use num::ToStrRadix; use option::{Some, None}; - use str::{Str, OwnedStr}; + use str::Str; use strbuf::StrBuf; use slice::{Vector, ImmutableVector, OwnedVector}; use self::test::BenchHarness; diff --git a/src/libstd/strbuf.rs b/src/libstd/strbuf.rs index e9e50f0a07a..1fcc9c6465a 100644 --- a/src/libstd/strbuf.rs +++ b/src/libstd/strbuf.rs @@ -20,9 +20,11 @@ use iter::{Extendable, FromIterator, Iterator, range}; use option::{None, Option, Some}; use ptr::RawPtr; use slice::{OwnedVector, Vector}; +use str; use str::{OwnedStr, Str, StrSlice}; use vec::Vec; +/// A growable string stored as a UTF-8 encoded buffer. #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd)] pub struct StrBuf { vec: Vec, @@ -69,6 +71,23 @@ impl StrBuf { } } + /// Tries to create a new string buffer from the given byte + /// vector, validating that the vector is UTF-8 encoded. + #[inline] + pub fn from_utf8(vec: Vec) -> Option { + if str::is_utf8(vec.as_slice()) { + Some(StrBuf { vec: vec }) + } else { + None + } + } + + /// Return the underlying byte buffer, encoded as UTF-8. + #[inline] + pub fn into_bytes(self) -> Vec { + self.vec + } + /// Pushes the given string onto this buffer; then, returns `self` so that it can be used /// again. #[inline] @@ -100,6 +119,7 @@ impl StrBuf { self.vec.push_all(string.as_bytes()) } + /// Push `ch` onto the given string `count` times. #[inline] pub fn grow(&mut self, count: uint, ch: char) { for _ in range(0, count) { @@ -352,4 +372,3 @@ mod tests { s.truncate(1); } } - diff --git a/src/test/bench/shootout-chameneos-redux.rs b/src/test/bench/shootout-chameneos-redux.rs index 18900abace6..5ea84feffde 100644 --- a/src/test/bench/shootout-chameneos-redux.rs +++ b/src/test/bench/shootout-chameneos-redux.rs @@ -32,53 +32,62 @@ struct CreatureInfo { color: color } -fn show_color(cc: color) -> ~str { +fn show_color(cc: color) -> &'static str { match cc { - Red => {~"red"} - Yellow => {~"yellow"} - Blue => {~"blue"} + Red => "red", + Yellow => "yellow", + Blue => "blue" } } -fn show_color_list(set: Vec) -> ~str { +fn show_color_list(set: Vec) -> StrBuf { let mut out = StrBuf::new(); for col in set.iter() { out.push_char(' '); out.push_str(show_color(*col)); } - return out.to_owned_str(); + out } -fn show_digit(nn: uint) -> ~str { +fn show_digit(nn: uint) -> &'static str { match nn { - 0 => {~"zero"} - 1 => {~"one"} - 2 => {~"two"} - 3 => {~"three"} - 4 => {~"four"} - 5 => {~"five"} - 6 => {~"six"} - 7 => {~"seven"} - 8 => {~"eight"} - 9 => {~"nine"} + 0 => {"zero"} + 1 => {"one"} + 2 => {"two"} + 3 => {"three"} + 4 => {"four"} + 5 => {"five"} + 6 => {"six"} + 7 => {"seven"} + 8 => {"eight"} + 9 => {"nine"} _ => {fail!("expected digits from 0 to 9...")} } } -fn show_number(nn: uint) -> ~str { - let mut out = ~""; +fn show_number(nn: uint) -> StrBuf { + let mut out = vec![]; let mut num = nn; let mut dig; - - if num == 0 { out = show_digit(0) }; + let mut len = 0; + if num == 0 { out.push(show_digit(0)) }; while num != 0 { dig = num % 10; num = num / 10; - out = show_digit(dig) + " " + out; + out.push(" "); + let s = show_digit(dig); + out.push(s); + len += 1 + s.len(); } + len += 1; + out.push(" "); - return ~" " + out; + let mut ret = StrBuf::with_capacity(len); + for s in out.iter().rev() { + ret.push_str(*s); + } + ret } fn transform(aa: color, bb: color) -> color { @@ -125,7 +134,7 @@ fn creature( option::None => { // log creatures met and evil clones of self let report = format!("{} {}", - creatures_met, show_number(evil_clones_met)); + creatures_met, show_number(evil_clones_met).as_slice()); to_rendezvous_log.send(report); break; } diff --git a/src/test/bench/shootout-k-nucleotide-pipes.rs b/src/test/bench/shootout-k-nucleotide-pipes.rs index ca88f107336..9dd76f5e475 100644 --- a/src/test/bench/shootout-k-nucleotide-pipes.rs +++ b/src/test/bench/shootout-k-nucleotide-pipes.rs @@ -15,17 +15,11 @@ extern crate collections; -use std::cmp::Ord; -use std::comm; use collections::HashMap; use std::mem::replace; use std::option; use std::os; -use std::io; -use std::str; use std::strbuf::StrBuf; -use std::task; -use std::vec; fn f64_cmp(x: f64, y: f64) -> Ordering { // arbitrarily decide that NaNs are larger than everything. @@ -66,16 +60,14 @@ fn sort_and_fmt(mm: &HashMap , uint>, total: uint) -> ~str { let mut buffer = StrBuf::new(); for &(ref k, v) in pairs_sorted.iter() { - unsafe { - buffer.push_str(format!("{} {:0.3f}\n", - k.as_slice() - .to_ascii() - .to_upper() - .into_str(), v)); - } + buffer.push_str(format!("{} {:0.3f}\n", + k.as_slice() + .to_ascii() + .to_upper() + .into_str(), v)); } - return buffer.to_owned_str(); + return buffer.into_owned(); } // given a map, search for the frequency of a pattern diff --git a/src/test/bench/shootout-k-nucleotide.rs b/src/test/bench/shootout-k-nucleotide.rs index c9794d54829..a1daf45cea9 100644 --- a/src/test/bench/shootout-k-nucleotide.rs +++ b/src/test/bench/shootout-k-nucleotide.rs @@ -11,8 +11,6 @@ // ignore-android see #10393 #13206 // ignore-pretty -use std::ascii::OwnedStrAsciiExt; -use std::str; use std::strbuf::StrBuf; use std::slice; @@ -50,8 +48,7 @@ impl Code { string.bytes().fold(Code(0u64), |a, b| a.push_char(b)) } - // FIXME: Inefficient. - fn unpack(&self, frame: uint) -> ~str { + fn unpack(&self, frame: uint) -> StrBuf { let mut key = self.hash(); let mut result = Vec::new(); for _ in range(0, frame) { @@ -60,7 +57,7 @@ impl Code { } result.reverse(); - str::from_utf8_owned(result.move_iter().collect()).unwrap() + StrBuf::from_utf8(result).unwrap() } } @@ -239,7 +236,7 @@ fn print_frequencies(frequencies: &Table, frame: uint) { for &(count, key) in vector.iter().rev() { println!("{} {:.3f}", - key.unpack(frame), + key.unpack(frame).as_slice(), (count as f32 * 100.0) / (total_count as f32)); } println!(""); @@ -249,14 +246,17 @@ fn print_occurrences(frequencies: &mut Table, occurrence: &'static str) { frequencies.lookup(Code::pack(occurrence), PrintCallback(occurrence)) } -fn get_sequence(r: &mut R, key: &str) -> ~[u8] { - let mut res = StrBuf::new(); +fn get_sequence(r: &mut R, key: &str) -> Vec { + let mut res = Vec::new(); for l in r.lines().map(|l| l.ok().unwrap()) .skip_while(|l| key != l.slice_to(key.len())).skip(1) { - res.push_str(l.trim()); + res.push_all(l.trim().as_bytes()); } - res.to_owned_str().into_ascii_upper().into_bytes() + for b in res.mut_iter() { + *b = b.to_ascii().to_upper().to_byte(); + } + res } fn main() { @@ -268,17 +268,17 @@ fn main() { }; let mut frequencies = Table::new(); - generate_frequencies(&mut frequencies, input, 1); + generate_frequencies(&mut frequencies, input.as_slice(), 1); print_frequencies(&frequencies, 1); frequencies = Table::new(); - generate_frequencies(&mut frequencies, input, 2); + generate_frequencies(&mut frequencies, input.as_slice(), 2); print_frequencies(&frequencies, 2); for occurrence in OCCURRENCES.iter() { frequencies = Table::new(); generate_frequencies(&mut frequencies, - input, + input.as_slice(), occurrence.len()); print_occurrences(&mut frequencies, *occurrence); } -- cgit 1.4.1-3-g733a5