diff options
Diffstat (limited to 'components/util')
| -rw-r--r-- | components/util/Cargo.toml | 3 | ||||
| -rw-r--r-- | components/util/bloom.rs | 338 | ||||
| -rw-r--r-- | components/util/lib.rs | 6 | ||||
| -rw-r--r-- | components/util/smallvec.rs | 585 | ||||
| -rw-r--r-- | components/util/sort.rs | 104 |
5 files changed, 6 insertions, 1030 deletions
diff --git a/components/util/Cargo.toml b/components/util/Cargo.toml index 1ce8a396942..53893d88614 100644 --- a/components/util/Cargo.toml +++ b/components/util/Cargo.toml @@ -21,6 +21,9 @@ path = "../plugins" [dependencies.cssparser] git = "https://github.com/servo/rust-cssparser" +[dependencies.selectors] +git = "https://github.com/servo/rust-selectors" + [dependencies.geom] git = "https://github.com/servo/rust-geom" diff --git a/components/util/bloom.rs b/components/util/bloom.rs deleted file mode 100644 index 6fd5d17e775..00000000000 --- a/components/util/bloom.rs +++ /dev/null @@ -1,338 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -//! Simple counting bloom filters. - -use string_cache::{Atom, Namespace}; - -const KEY_SIZE: uint = 12; -const ARRAY_SIZE: uint = 1 << KEY_SIZE; -const KEY_MASK: u32 = (1 << KEY_SIZE) - 1; -const KEY_SHIFT: uint = 16; - -/// A counting Bloom filter with 8-bit counters. For now we assume -/// that having two hash functions is enough, but we may revisit that -/// decision later. -/// -/// The filter uses an array with 2**KeySize entries. -/// -/// Assuming a well-distributed hash function, a Bloom filter with -/// array size M containing N elements and -/// using k hash function has expected false positive rate exactly -/// -/// $ (1 - (1 - 1/M)^{kN})^k $ -/// -/// because each array slot has a -/// -/// $ (1 - 1/M)^{kN} $ -/// -/// chance of being 0, and the expected false positive rate is the -/// probability that all of the k hash functions will hit a nonzero -/// slot. -/// -/// For reasonable assumptions (M large, kN large, which should both -/// hold if we're worried about false positives) about M and kN this -/// becomes approximately -/// -/// $$ (1 - \exp(-kN/M))^k $$ -/// -/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$, -/// or in other words -/// -/// $$ N/M = -0.5 * \ln(1 - \sqrt(r)) $$ -/// -/// where r is the false positive rate. This can be used to compute -/// the desired KeySize for a given load N and false positive rate r. -/// -/// If N/M is assumed small, then the false positive rate can -/// further be approximated as 4*N^2/M^2. So increasing KeySize by -/// 1, which doubles M, reduces the false positive rate by about a -/// factor of 4, and a false positive rate of 1% corresponds to -/// about M/N == 20. -/// -/// What this means in practice is that for a few hundred keys using a -/// KeySize of 12 gives false positive rates on the order of 0.25-4%. -/// -/// Similarly, using a KeySize of 10 would lead to a 4% false -/// positive rate for N == 100 and to quite bad false positive -/// rates for larger N. -pub struct BloomFilter { - counters: [u8; ARRAY_SIZE], -} - -impl Clone for BloomFilter { - #[inline] - fn clone(&self) -> BloomFilter { - BloomFilter { - counters: self.counters, - } - } -} - -impl BloomFilter { - /// Creates a new bloom filter. - #[inline] - pub fn new() -> BloomFilter { - BloomFilter { - counters: [0; ARRAY_SIZE], - } - } - - #[inline] - fn first_slot(&self, hash: u32) -> &u8 { - &self.counters[hash1(hash) as uint] - } - - #[inline] - fn first_mut_slot(&mut self, hash: u32) -> &mut u8 { - &mut self.counters[hash1(hash) as uint] - } - - #[inline] - fn second_slot(&self, hash: u32) -> &u8 { - &self.counters[hash2(hash) as uint] - } - - #[inline] - fn second_mut_slot(&mut self, hash: u32) -> &mut u8 { - &mut self.counters[hash2(hash) as uint] - } - - #[inline] - pub fn clear(&mut self) { - self.counters = [0; ARRAY_SIZE] - } - - #[inline] - fn insert_hash(&mut self, hash: u32) { - { - let slot1 = self.first_mut_slot(hash); - if !full(slot1) { - *slot1 += 1 - } - } - { - let slot2 = self.second_mut_slot(hash); - if !full(slot2) { - *slot2 += 1 - } - } - } - - /// Inserts an item into the bloom filter. - #[inline] - pub fn insert<T:BloomHash>(&mut self, elem: &T) { - self.insert_hash(elem.bloom_hash()) - - } - - #[inline] - fn remove_hash(&mut self, hash: u32) { - { - let slot1 = self.first_mut_slot(hash); - if !full(slot1) { - *slot1 -= 1 - } - } - { - let slot2 = self.second_mut_slot(hash); - if !full(slot2) { - *slot2 -= 1 - } - } - } - - /// Removes an item from the bloom filter. - #[inline] - pub fn remove<T:BloomHash>(&mut self, elem: &T) { - self.remove_hash(elem.bloom_hash()) - } - - #[inline] - fn might_contain_hash(&self, hash: u32) -> bool { - *self.first_slot(hash) != 0 && *self.second_slot(hash) != 0 - } - - /// Check whether the filter might contain an item. This can - /// sometimes return true even if the item is not in the filter, - /// but will never return false for items that are actually in the - /// filter. - #[inline] - pub fn might_contain<T:BloomHash>(&self, elem: &T) -> bool { - self.might_contain_hash(elem.bloom_hash()) - } -} - -pub trait BloomHash { - fn bloom_hash(&self) -> u32; -} - -impl BloomHash for int { - #[allow(exceeding_bitshifts)] - #[inline] - fn bloom_hash(&self) -> u32 { - ((*self >> 32) ^ *self) as u32 - } -} - -impl BloomHash for uint { - #[allow(exceeding_bitshifts)] - #[inline] - fn bloom_hash(&self) -> u32 { - ((*self >> 32) ^ *self) as u32 - } -} - -impl BloomHash for Atom { - #[inline] - fn bloom_hash(&self) -> u32 { - ((self.data >> 32) ^ self.data) as u32 - } -} - -impl BloomHash for Namespace { - #[inline] - fn bloom_hash(&self) -> u32 { - let Namespace(ref atom) = *self; - atom.bloom_hash() - } -} - -#[inline] -fn full(slot: &u8) -> bool { - *slot == 0xff -} - -#[inline] -fn hash1(hash: u32) -> u32 { - hash & KEY_MASK -} - -#[inline] -fn hash2(hash: u32) -> u32 { - (hash >> KEY_SHIFT) & KEY_MASK -} - -#[test] -fn create_and_insert_some_stuff() { - use std::iter::range; - - let mut bf = BloomFilter::new(); - - for i in range(0u, 1000) { - bf.insert(&i); - } - - for i in range(0u, 1000) { - assert!(bf.might_contain(&i)); - } - - let false_positives = - range(1001u, 2000).filter(|i| bf.might_contain(i)).count(); - - assert!(false_positives < 10); // 1%. - - for i in range(0u, 100) { - bf.remove(&i); - } - - for i in range(100u, 1000) { - assert!(bf.might_contain(&i)); - } - - let false_positives = range(0u, 100).filter(|i| bf.might_contain(i)).count(); - - assert!(false_positives < 2); // 2%. - - bf.clear(); - - for i in range(0u, 2000) { - assert!(!bf.might_contain(&i)); - } -} - -#[cfg(test)] -mod bench { - extern crate test; - - use std::hash::{hash, SipHasher}; - use std::iter; - use super::BloomFilter; - - #[bench] - fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) { - b.iter(|| { - let mut bf = BloomFilter::new(); - for i in iter::range(0u, 1000) { - bf.insert(&i); - } - for i in iter::range(0u, 100) { - bf.remove(&i); - } - for i in iter::range(100u, 200) { - test::black_box(bf.might_contain(&i)); - } - }); - } - - #[bench] - fn might_contain(b: &mut test::Bencher) { - let mut bf = BloomFilter::new(); - - for i in iter::range(0u, 1000) { - bf.insert(&i); - } - - let mut i = 0u; - - b.bench_n(1000, |b| { - b.iter(|| { - test::black_box(bf.might_contain(&i)); - i += 1; - }); - }); - } - - #[bench] - fn insert(b: &mut test::Bencher) { - let mut bf = BloomFilter::new(); - - b.bench_n(1000, |b| { - let mut i = 0u; - - b.iter(|| { - test::black_box(bf.insert(&i)); - i += 1; - }); - }); - } - - #[bench] - fn remove(b: &mut test::Bencher) { - let mut bf = BloomFilter::new(); - for i in range(0u, 1000) { - bf.insert(&i); - } - - b.bench_n(1000, |b| { - let mut i = 0u; - - b.iter(|| { - bf.remove(&i); - i += 1; - }); - }); - - test::black_box(bf.might_contain(&0u)); - } - - #[bench] - fn hash_a_uint(b: &mut test::Bencher) { - let mut i = 0u; - b.iter(|| { - test::black_box(hash::<uint, SipHasher>(&i)); - i += 1; - }) - } -} diff --git a/components/util/lib.rs b/components/util/lib.rs index b6c1f938e66..c8df5466a68 100644 --- a/components/util/lib.rs +++ b/components/util/lib.rs @@ -37,6 +37,7 @@ extern crate "rustc-serialize" as rustc_serialize; extern crate task_info; extern crate "time" as std_time; extern crate text_writer; +extern crate selectors; extern crate string_cache; extern crate unicode; extern crate url; @@ -45,9 +46,10 @@ extern crate url; extern crate string_cache_macros; extern crate lazy_static; +pub use selectors::smallvec; + use std::sync::Arc; -pub mod bloom; pub mod cache; pub mod cursor; pub mod debug_utils; @@ -62,8 +64,6 @@ pub mod opts; pub mod persistent_list; pub mod range; pub mod resource_files; -pub mod smallvec; -pub mod sort; pub mod str; pub mod task; pub mod tid; diff --git a/components/util/smallvec.rs b/components/util/smallvec.rs deleted file mode 100644 index 14d983376e8..00000000000 --- a/components/util/smallvec.rs +++ /dev/null @@ -1,585 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -//! Small vectors in various sizes. These store a certain number of elements inline and fall back -//! to the heap for larger allocations. - -use std::mem::zeroed as i; -use std::cmp; -use std::fmt; -use std::intrinsics; -use std::iter::FromIterator; -use std::marker::ContravariantLifetime; -use std::mem; -use std::ptr; -use std::raw::Slice; -use alloc::heap; - -// Generic code for all small vectors - -pub trait VecLike<T> { - fn vec_len(&self) -> uint; - fn vec_push(&mut self, value: T); - - fn vec_slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T]; - - #[inline] - fn vec_slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T] { - let len = self.vec_len(); - self.vec_slice_mut(start, len) - } -} - -impl<T> VecLike<T> for Vec<T> { - #[inline] - fn vec_len(&self) -> uint { - self.len() - } - - #[inline] - fn vec_push(&mut self, value: T) { - self.push(value); - } - - #[inline] - fn vec_slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T] { - &mut self[start..end] - } -} - -pub trait SmallVecPrivate<T> { - unsafe fn set_len(&mut self, new_len: uint); - unsafe fn set_cap(&mut self, new_cap: uint); - fn data(&self, index: uint) -> *const T; - fn mut_data(&mut self, index: uint) -> *mut T; - unsafe fn ptr(&self) -> *const T; - unsafe fn mut_ptr(&mut self) -> *mut T; - unsafe fn set_ptr(&mut self, new_ptr: *mut T); -} - -pub trait SmallVec<T> : SmallVecPrivate<T> { - fn inline_size(&self) -> uint; - fn len(&self) -> uint; - fn is_empty(&self) -> bool; - fn cap(&self) -> uint; - - fn spilled(&self) -> bool { - self.cap() > self.inline_size() - } - - fn begin(&self) -> *const T { - unsafe { - if self.spilled() { - self.ptr() - } else { - self.data(0) - } - } - } - - fn end(&self) -> *const T { - unsafe { - self.begin().offset(self.len() as int) - } - } - - fn iter<'a>(&'a self) -> SmallVecIterator<'a,T> { - SmallVecIterator { - ptr: self.begin(), - end: self.end(), - lifetime: ContravariantLifetime::<'a>, - } - } - - fn mut_iter<'a>(&'a mut self) -> SmallVecMutIterator<'a,T> { - unsafe { - SmallVecMutIterator { - ptr: mem::transmute(self.begin()), - end: mem::transmute(self.end()), - lifetime: ContravariantLifetime::<'a>, - } - } - } - - /// NB: For efficiency reasons (avoiding making a second copy of the inline elements), this - /// actually clears out the original array instead of moving it. - fn into_iter<'a>(&'a mut self) -> SmallVecMoveIterator<'a,T> { - unsafe { - let iter = mem::transmute(self.iter()); - let ptr_opt = if self.spilled() { - Some(mem::transmute(self.ptr())) - } else { - None - }; - let cap = self.cap(); - let inline_size = self.inline_size(); - self.set_cap(inline_size); - self.set_len(0); - SmallVecMoveIterator { - allocation: ptr_opt, - cap: cap, - iter: iter, - lifetime: ContravariantLifetime::<'a>, - } - } - } - - fn push(&mut self, value: T) { - let cap = self.cap(); - if self.len() == cap { - self.grow(cmp::max(cap * 2, 1)) - } - unsafe { - let end: &mut T = mem::transmute(self.end()); - ptr::write(end, value); - let len = self.len(); - self.set_len(len + 1) - } - } - - fn push_all_move<V:SmallVec<T>>(&mut self, mut other: V) { - for value in other.into_iter() { - self.push(value) - } - } - - fn pop(&mut self) -> Option<T> { - if self.len() == 0 { - return None - } - - unsafe { - let mut value: T = mem::uninitialized(); - let last_index = self.len() - 1; - - if (last_index as int) < 0 { - panic!("overflow") - } - let end_ptr = self.begin().offset(last_index as int); - - mem::swap(&mut value, mem::transmute::<*const T,&mut T>(end_ptr)); - self.set_len(last_index); - Some(value) - } - } - - fn grow(&mut self, new_cap: uint) { - unsafe { - let new_alloc: *mut T = mem::transmute(heap::allocate(mem::size_of::<T>() * - new_cap, - mem::min_align_of::<T>())); - ptr::copy_nonoverlapping_memory(new_alloc, self.begin(), self.len()); - - if self.spilled() { - heap::deallocate(self.mut_ptr() as *mut u8, - mem::size_of::<T>() * self.cap(), - mem::min_align_of::<T>()) - } else { - let mut_begin: *mut T = mem::transmute(self.begin()); - intrinsics::set_memory(mut_begin, 0, self.len()) - } - - self.set_ptr(new_alloc); - self.set_cap(new_cap) - } - } - - fn get<'a>(&'a self, index: uint) -> &'a T { - if index >= self.len() { - self.fail_bounds_check(index) - } - unsafe { - mem::transmute(self.begin().offset(index as int)) - } - } - - fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T { - if index >= self.len() { - self.fail_bounds_check(index) - } - unsafe { - mem::transmute(self.begin().offset(index as int)) - } - } - - fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] { - assert!(start <= end); - assert!(end <= self.len()); - unsafe { - mem::transmute(Slice { - data: self.begin().offset(start as int), - len: (end - start) - }) - } - } - - fn as_slice<'a>(&'a self) -> &'a [T] { - self.slice(0, self.len()) - } - - fn as_slice_mut<'a>(&'a mut self) -> &'a mut [T] { - let len = self.len(); - self.slice_mut(0, len) - } - - fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T] { - assert!(start <= end); - assert!(end <= self.len()); - unsafe { - mem::transmute(Slice { - data: self.begin().offset(start as int), - len: (end - start) - }) - } - } - - fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T] { - let len = self.len(); - self.slice_mut(start, len) - } - - fn fail_bounds_check(&self, index: uint) { - panic!("index {} beyond length ({})", index, self.len()) - } -} - -pub struct SmallVecIterator<'a,T> { - ptr: *const T, - end: *const T, - lifetime: ContravariantLifetime<'a> -} - -impl<'a,T> Iterator for SmallVecIterator<'a,T> { - type Item = &'a T; - - #[inline] - fn next(&mut self) -> Option<&'a T> { - unsafe { - if self.ptr == self.end { - return None - } - let old = self.ptr; - self.ptr = if mem::size_of::<T>() == 0 { - mem::transmute(self.ptr as uint + 1) - } else { - self.ptr.offset(1) - }; - Some(mem::transmute(old)) - } - } -} - -pub struct SmallVecMutIterator<'a,T> { - ptr: *mut T, - end: *mut T, - lifetime: ContravariantLifetime<'a>, -} - -impl<'a,T> Iterator for SmallVecMutIterator<'a,T> { - type Item = &'a mut T; - - #[inline] - fn next(&mut self) -> Option<&'a mut T> { - unsafe { - if self.ptr == self.end { - return None - } - let old = self.ptr; - self.ptr = if mem::size_of::<T>() == 0 { - mem::transmute(self.ptr as uint + 1) - } else { - self.ptr.offset(1) - }; - Some(mem::transmute(old)) - } - } -} - -pub struct SmallVecMoveIterator<'a,T> { - allocation: Option<*mut u8>, - cap: uint, - iter: SmallVecIterator<'a,T>, - lifetime: ContravariantLifetime<'a>, -} - -impl<'a, T: 'a> Iterator for SmallVecMoveIterator<'a,T> { - type Item = T; - - #[inline] - fn next(&mut self) -> Option<T> { - unsafe { - match self.iter.next() { - None => None, - Some(reference) => { - // Zero out the values as we go so they don't get double-freed. - let reference: &mut T = mem::transmute(reference); - Some(mem::replace(reference, mem::zeroed())) - } - } - } - } -} - -#[unsafe_destructor] -impl<'a, T: 'a> Drop for SmallVecMoveIterator<'a,T> { - fn drop(&mut self) { - // Destroy the remaining elements. - for _ in self.by_ref() {} - - match self.allocation { - None => {} - Some(allocation) => { - unsafe { - heap::deallocate(allocation as *mut u8, - mem::size_of::<T>() * self.cap, - mem::min_align_of::<T>()) - } - } - } - } -} - -// Concrete implementations - -macro_rules! def_small_vector( - ($name:ident, $size:expr) => ( - pub struct $name<T> { - len: uint, - cap: uint, - ptr: *const T, - data: [T; $size], - } - - impl<T> SmallVecPrivate<T> for $name<T> { - unsafe fn set_len(&mut self, new_len: uint) { - self.len = new_len - } - unsafe fn set_cap(&mut self, new_cap: uint) { - self.cap = new_cap - } - fn data(&self, index: uint) -> *const T { - let ptr: *const T = &self.data[index]; - ptr - } - fn mut_data(&mut self, index: uint) -> *mut T { - let ptr: *mut T = &mut self.data[index]; - ptr - } - unsafe fn ptr(&self) -> *const T { - self.ptr - } - unsafe fn mut_ptr(&mut self) -> *mut T { - mem::transmute(self.ptr) - } - unsafe fn set_ptr(&mut self, new_ptr: *mut T) { - self.ptr = mem::transmute(new_ptr) - } - } - - impl<T> SmallVec<T> for $name<T> { - fn inline_size(&self) -> uint { - $size - } - fn len(&self) -> uint { - self.len - } - fn is_empty(&self) -> bool { - self.len == 0 - } - fn cap(&self) -> uint { - self.cap - } - } - - impl<T> VecLike<T> for $name<T> { - #[inline] - fn vec_len(&self) -> uint { - self.len() - } - - #[inline] - fn vec_push(&mut self, value: T) { - self.push(value); - } - - #[inline] - fn vec_slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T] { - self.slice_mut(start, end) - } - } - - impl<T> FromIterator<T> for $name<T> { - fn from_iter<I: Iterator<Item=T>>(iter: I) -> $name<T> { - let mut v = $name::new(); - - let (lower_size_bound, _) = iter.size_hint(); - - if lower_size_bound > v.cap() { - v.grow(lower_size_bound); - } - - for elem in iter { - v.push(elem); - } - - v - } - } - - impl<T> $name<T> { - pub fn extend<I: Iterator<Item=T>>(&mut self, iter: I) { - let (lower_size_bound, _) = iter.size_hint(); - - let target_len = self.len() + lower_size_bound; - - if target_len > self.cap() { - self.grow(target_len); - } - - for elem in iter { - self.push(elem); - } - } - } - - impl<T: fmt::Debug> fmt::Debug for $name<T> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - write!(f, "{:?}", self.as_slice()) - } - } - - impl<T> $name<T> { - #[inline] - pub fn new() -> $name<T> { - unsafe { - $name { - len: 0, - cap: $size, - ptr: ptr::null(), - data: mem::zeroed(), - } - } - } - } - ) -); - -def_small_vector!(SmallVec1, 1); -def_small_vector!(SmallVec2, 2); -def_small_vector!(SmallVec4, 4); -def_small_vector!(SmallVec8, 8); -def_small_vector!(SmallVec16, 16); -def_small_vector!(SmallVec24, 24); -def_small_vector!(SmallVec32, 32); - -macro_rules! def_small_vector_drop_impl( - ($name:ident, $size:expr) => ( - #[unsafe_destructor] - impl<T> Drop for $name<T> { - fn drop(&mut self) { - if !self.spilled() { - return - } - - unsafe { - let ptr = self.mut_ptr(); - for i in range(0, self.len()) { - *ptr.offset(i as int) = mem::uninitialized(); - } - - heap::deallocate(self.mut_ptr() as *mut u8, - mem::size_of::<T>() * self.cap(), - mem::min_align_of::<T>()) - } - } - } - ) -); - -def_small_vector_drop_impl!(SmallVec1, 1); -def_small_vector_drop_impl!(SmallVec2, 2); -def_small_vector_drop_impl!(SmallVec4, 4); -def_small_vector_drop_impl!(SmallVec8, 8); -def_small_vector_drop_impl!(SmallVec16, 16); -def_small_vector_drop_impl!(SmallVec24, 24); -def_small_vector_drop_impl!(SmallVec32, 32); - -macro_rules! def_small_vector_clone_impl( - ($name:ident) => ( - impl<T: Clone> Clone for $name<T> { - fn clone(&self) -> $name<T> { - let mut new_vector = $name::new(); - for element in self.iter() { - new_vector.push((*element).clone()) - } - new_vector - } - } - ) -); - -def_small_vector_clone_impl!(SmallVec1); -def_small_vector_clone_impl!(SmallVec2); -def_small_vector_clone_impl!(SmallVec4); -def_small_vector_clone_impl!(SmallVec8); -def_small_vector_clone_impl!(SmallVec16); -def_small_vector_clone_impl!(SmallVec24); -def_small_vector_clone_impl!(SmallVec32); - -#[cfg(test)] -pub mod tests { - use smallvec::{SmallVec, SmallVec2, SmallVec16}; - use std::borrow::ToOwned; - - // We heap allocate all these strings so that double frees will show up under valgrind. - - #[test] - pub fn test_inline() { - let mut v = SmallVec16::new(); - v.push("hello".to_owned()); - v.push("there".to_owned()); - assert_eq!(v.as_slice(), vec![ - "hello".to_owned(), - "there".to_owned(), - ].as_slice()); - } - - #[test] - pub fn test_spill() { - let mut v = SmallVec2::new(); - v.push("hello".to_owned()); - v.push("there".to_owned()); - v.push("burma".to_owned()); - v.push("shave".to_owned()); - assert_eq!(v.as_slice(), vec![ - "hello".to_owned(), - "there".to_owned(), - "burma".to_owned(), - "shave".to_owned(), - ].as_slice()); - } - - #[test] - pub fn test_double_spill() { - let mut v = SmallVec2::new(); - v.push("hello".to_owned()); - v.push("there".to_owned()); - v.push("burma".to_owned()); - v.push("shave".to_owned()); - v.push("hello".to_owned()); - v.push("there".to_owned()); - v.push("burma".to_owned()); - v.push("shave".to_owned()); - assert_eq!(v.as_slice(), vec![ - "hello".to_owned(), - "there".to_owned(), - "burma".to_owned(), - "shave".to_owned(), - "hello".to_owned(), - "there".to_owned(), - "burma".to_owned(), - "shave".to_owned(), - ].as_slice()); - } -} diff --git a/components/util/sort.rs b/components/util/sort.rs deleted file mode 100644 index ce7ab4d86c9..00000000000 --- a/components/util/sort.rs +++ /dev/null @@ -1,104 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -//! In-place sorting. - -use std::cmp::Ordering; - -fn quicksort_helper<T>(arr: &mut [T], left: int, right: int, compare: fn(&T, &T) -> Ordering) { - if right <= left { - return - } - - let mut i: int = left - 1; - let mut j: int = right; - let mut p: int = i; - let mut q: int = j; - unsafe { - let v: *mut T = &mut arr[right as uint]; - loop { - i += 1; - while compare(&arr[i as uint], &*v) == Ordering::Less { - i += 1 - } - j -= 1; - while compare(&*v, &arr[j as uint]) == Ordering::Less { - if j == left { - break - } - j -= 1; - } - if i >= j { - break - } - arr.swap(i as uint, j as uint); - if compare(&arr[i as uint], &*v) == Ordering::Equal { - p += 1; - arr.swap(p as uint, i as uint) - } - if compare(&*v, &arr[j as uint]) == Ordering::Equal { - q -= 1; - arr.swap(j as uint, q as uint) - } - } - } - - arr.swap(i as uint, right as uint); - j = i - 1; - i += 1; - let mut k: int = left; - while k < p { - arr.swap(k as uint, j as uint); - k += 1; - j -= 1; - assert!(k < arr.len() as int); - } - k = right - 1; - while k > q { - arr.swap(i as uint, k as uint); - k -= 1; - i += 1; - assert!(k != 0); - } - - quicksort_helper(arr, left, j, compare); - quicksort_helper(arr, i, right, compare); -} - -/// An in-place quicksort. -/// -/// The algorithm is from Sedgewick and Bentley, "Quicksort is Optimal": -/// http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf -pub fn quicksort_by<T>(arr: &mut [T], compare: fn(&T, &T) -> Ordering) { - if arr.len() <= 1 { - return - } - - let len = arr.len(); - quicksort_helper(arr, 0, (len - 1) as int, compare); -} - -#[cfg(test)] -pub mod test { - use std::cmp::Ordering; - use std::rand; - use std::rand::Rng; - - use sort; - - #[test] - pub fn random() { - let mut rng = rand::thread_rng(); - for _ in range(0u32, 50000u32) { - let len: uint = rng.gen(); - let mut v: Vec<int> = rng.gen_iter::<int>().take((len % 32) + 1).collect(); - fn compare_ints(a: &int, b: &int) -> Ordering { a.cmp(b) } - sort::quicksort_by(v.as_mut_slice(), compare_ints); - for i in range(0, v.len() - 1) { - assert!(v[i] <= v[i + 1]) - } - } - } -} - |