diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/c_str.rs | 4 | ||||
| -rw-r--r-- | src/libstd/hashmap.rs | 50 | ||||
| -rw-r--r-- | src/libstd/lib.rs | 1 | ||||
| -rw-r--r-- | src/libstd/libc.rs | 2 | ||||
| -rw-r--r-- | src/libstd/rt/global_heap.rs | 4 | ||||
| -rw-r--r-- | src/libstd/sync/deque.rs | 2 | ||||
| -rw-r--r-- | src/libstd/unstable/mutex.rs | 40 | ||||
| -rw-r--r-- | src/libstd/vec.rs | 12 | ||||
| -rw-r--r-- | src/libstd/vec_ng.rs | 231 |
9 files changed, 289 insertions, 57 deletions
diff --git a/src/libstd/c_str.rs b/src/libstd/c_str.rs index c735e325068..22e93e58194 100644 --- a/src/libstd/c_str.rs +++ b/src/libstd/c_str.rs @@ -183,7 +183,7 @@ impl Drop for CString { fn drop(&mut self) { if self.owns_buffer_ { unsafe { - libc::free(self.buf as *libc::c_void) + libc::free(self.buf as *mut libc::c_void) } } } @@ -459,7 +459,7 @@ mod tests { #[test] fn test_unwrap() { let c_str = "hello".to_c_str(); - unsafe { libc::free(c_str.unwrap() as *libc::c_void) } + unsafe { libc::free(c_str.unwrap() as *mut libc::c_void) } } #[test] diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs index 7f19105cdc8..13a03d32525 100644 --- a/src/libstd/hashmap.rs +++ b/src/libstd/hashmap.rs @@ -66,8 +66,9 @@ use rand::Rng; use rand; use uint; use util::replace; -use vec::{ImmutableVector, MutableVector, OwnedVector}; -use vec; +use vec::{ImmutableVector, MutableVector, OwnedVector, Items, MutItems}; +use vec_ng; +use vec_ng::Vec; static INITIAL_CAPACITY: uint = 32u; // 2^5 @@ -90,7 +91,7 @@ pub struct HashMap<K,V> { priv k1: u64, priv resize_at: uint, priv size: uint, - priv buckets: ~[Option<Bucket<K, V>>], + priv buckets: Vec<Option<Bucket<K, V>>> } // We could rewrite FoundEntry to have type Option<&Bucket<K, V>> @@ -151,7 +152,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { -> SearchResult { let mut ret = TableFull; self.bucket_sequence(hash, |i| { - match self.buckets[i] { + match self.buckets.as_slice()[i] { Some(ref bkt) if bkt.hash == hash && *k == bkt.key => { ret = FoundEntry(i); false }, @@ -169,7 +170,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { -> SearchResult { let mut ret = TableFull; self.bucket_sequence(hash, |i| { - match self.buckets[i] { + match self.buckets.as_slice()[i] { Some(ref bkt) if bkt.hash == hash && k.equiv(&bkt.key) => { ret = FoundEntry(i); false }, @@ -194,7 +195,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { self.resize_at = resize_at(new_capacity); let old_buckets = replace(&mut self.buckets, - vec::from_fn(new_capacity, |_| None)); + Vec::from_fn(new_capacity, |_| None)); self.size = 0; for bucket in old_buckets.move_iter() { @@ -213,7 +214,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { #[inline] fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V { - match self.buckets[idx] { + match self.buckets.as_slice()[idx] { Some(ref bkt) => &bkt.value, None => fail!("HashMap::find: internal logic error"), } @@ -221,7 +222,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { #[inline] fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V { - match self.buckets[idx] { + match self.buckets.as_mut_slice()[idx] { Some(ref mut bkt) => &mut bkt.value, None => unreachable!() } @@ -234,13 +235,12 @@ impl<K:Hash + Eq,V> HashMap<K, V> { match self.bucket_for_key_with_hash(hash, &k) { TableFull => { fail!("Internal logic error"); } FoundHole(idx) => { - self.buckets[idx] = Some(Bucket{hash: hash, key: k, - value: v}); + self.buckets.as_mut_slice()[idx] = Some(Bucket{hash: hash, key: k, value: v}); self.size += 1; None } FoundEntry(idx) => { - match self.buckets[idx] { + match self.buckets.as_mut_slice()[idx] { None => { fail!("insert_internal: Internal logic error") } Some(ref mut b) => { b.hash = hash; @@ -273,7 +273,7 @@ impl<K:Hash + Eq,V> HashMap<K, V> { }; let len_buckets = self.buckets.len(); - let bucket = self.buckets[idx].take(); + let bucket = self.buckets.as_mut_slice()[idx].take(); let value = bucket.map(|bucket| bucket.value); @@ -281,8 +281,8 @@ impl<K:Hash + Eq,V> HashMap<K, V> { what our new size is ahead of time before we start insertions */ let size = self.size - 1; idx = self.next_bucket(idx, len_buckets); - while self.buckets[idx].is_some() { - let bucket = self.buckets[idx].take(); + while self.buckets.as_slice()[idx].is_some() { + let bucket = self.buckets.as_mut_slice()[idx].take(); self.insert_opt_bucket(bucket); idx = self.next_bucket(idx, len_buckets); } @@ -300,7 +300,7 @@ impl<K:Hash + Eq,V> Container for HashMap<K, V> { impl<K:Hash + Eq,V> Mutable for HashMap<K, V> { /// Clear the map, removing all key-value pairs. fn clear(&mut self) { - for bkt in self.buckets.mut_iter() { + for bkt in self.buckets.as_mut_slice().mut_iter() { *bkt = None; } self.size = 0; @@ -380,7 +380,7 @@ impl<K: Hash + Eq, V> HashMap<K, V> { k0: k0, k1: k1, resize_at: resize_at(cap), size: 0, - buckets: vec::from_fn(cap, |_| None) + buckets: Vec::from_fn(cap, |_| None) } } @@ -455,7 +455,7 @@ impl<K: Hash + Eq, V> HashMap<K, V> { FoundEntry(idx) => { found(&k, self.mut_value_for_bucket(idx), a); idx } FoundHole(idx) => { let v = not_found(&k, a); - self.buckets[idx] = Some(Bucket{hash: hash, key: k, value: v}); + self.buckets.as_mut_slice()[idx] = Some(Bucket{hash: hash, key: k, value: v}); self.size += 1; idx } @@ -541,14 +541,14 @@ impl<K: Hash + Eq, V> HashMap<K, V> { /// An iterator visiting all key-value pairs in arbitrary order. /// Iterator element type is (&'a K, &'a V). pub fn iter<'a>(&'a self) -> Entries<'a, K, V> { - Entries { iter: self.buckets.iter() } + Entries { iter: self.buckets.as_slice().iter() } } /// An iterator visiting all key-value pairs in arbitrary order, /// with mutable references to the values. /// Iterator element type is (&'a K, &'a mut V). pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> { - MutEntries { iter: self.buckets.mut_iter() } + MutEntries { iter: self.buckets.as_mut_slice().mut_iter() } } /// Creates a consuming iterator, that is, one that moves each key-value @@ -599,17 +599,17 @@ impl<K:Hash + Eq + Clone,V:Clone> Clone for HashMap<K,V> { /// HashMap iterator #[deriving(Clone)] pub struct Entries<'a, K, V> { - priv iter: vec::Items<'a, Option<Bucket<K, V>>>, + priv iter: Items<'a, Option<Bucket<K, V>>>, } /// HashMap mutable values iterator pub struct MutEntries<'a, K, V> { - priv iter: vec::MutItems<'a, Option<Bucket<K, V>>>, + priv iter: MutItems<'a, Option<Bucket<K, V>>>, } /// HashMap move iterator pub struct MoveEntries<K, V> { - priv iter: vec::MoveItems<Option<Bucket<K, V>>>, + priv iter: vec_ng::MoveItems<Option<Bucket<K, V>>>, } /// HashMap keys iterator @@ -623,12 +623,12 @@ pub type Values<'a, K, V> = /// HashSet iterator #[deriving(Clone)] pub struct SetItems<'a, K> { - priv iter: vec::Items<'a, Option<Bucket<K, ()>>>, + priv iter: Items<'a, Option<Bucket<K, ()>>>, } /// HashSet move iterator pub struct SetMoveItems<K> { - priv iter: vec::MoveItems<Option<Bucket<K, ()>>>, + priv iter: vec_ng::MoveItems<Option<Bucket<K, ()>>>, } impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> { @@ -807,7 +807,7 @@ impl<T:Hash + Eq> HashSet<T> { /// An iterator visiting all elements in arbitrary order. /// Iterator element type is &'a T. pub fn iter<'a>(&'a self) -> SetItems<'a, T> { - SetItems { iter: self.map.buckets.iter() } + SetItems { iter: self.map.buckets.as_slice().iter() } } /// Creates a consuming iterator, that is, one that moves each value out diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs index f4f83892a9c..7e53a0071bd 100644 --- a/src/libstd/lib.rs +++ b/src/libstd/lib.rs @@ -110,6 +110,7 @@ pub mod char; pub mod tuple; pub mod vec; +pub mod vec_ng; pub mod at_vec; pub mod str; diff --git a/src/libstd/libc.rs b/src/libstd/libc.rs index 8975c2a7955..6f2d64ff668 100644 --- a/src/libstd/libc.rs +++ b/src/libstd/libc.rs @@ -3225,7 +3225,7 @@ pub mod funcs { pub fn calloc(nobj: size_t, size: size_t) -> *c_void; pub fn malloc(size: size_t) -> *mut c_void; pub fn realloc(p: *mut c_void, size: size_t) -> *mut c_void; - pub fn free(p: *c_void); + pub fn free(p: *mut c_void); pub fn exit(status: c_int) -> !; // Omitted: atexit. pub fn system(s: *c_char) -> c_int; diff --git a/src/libstd/rt/global_heap.rs b/src/libstd/rt/global_heap.rs index 54442cedb68..6bee8cb70f5 100644 --- a/src/libstd/rt/global_heap.rs +++ b/src/libstd/rt/global_heap.rs @@ -52,7 +52,7 @@ pub unsafe fn realloc_raw(ptr: *mut u8, size: uint) -> *mut u8 { // `realloc(ptr, 0)` may allocate, but it may also return a null pointer // http://pubs.opengroup.org/onlinepubs/9699919799/functions/realloc.html if size == 0 { - free(ptr as *c_void); + free(ptr as *mut c_void); mut_null() } else { let p = realloc(ptr as *mut c_void, size as size_t); @@ -107,7 +107,7 @@ pub unsafe fn exchange_free_(ptr: *u8) { #[inline] pub unsafe fn exchange_free(ptr: *u8) { - free(ptr as *c_void); + free(ptr as *mut c_void); } #[cfg(test)] diff --git a/src/libstd/sync/deque.rs b/src/libstd/sync/deque.rs index e99e9ef0940..e740862fddf 100644 --- a/src/libstd/sync/deque.rs +++ b/src/libstd/sync/deque.rs @@ -389,7 +389,7 @@ impl<T: Send> Buffer<T> { impl<T: Send> Drop for Buffer<T> { fn drop(&mut self) { // It is assumed that all buffers are empty on drop. - unsafe { libc::free(self.storage as *libc::c_void) } + unsafe { libc::free(self.storage as *mut libc::c_void) } } } diff --git a/src/libstd/unstable/mutex.rs b/src/libstd/unstable/mutex.rs index ff38a8c0199..69c6204cc32 100644 --- a/src/libstd/unstable/mutex.rs +++ b/src/libstd/unstable/mutex.rs @@ -173,49 +173,49 @@ mod imp { type pthread_condattr_t = libc::c_void; pub unsafe fn init_lock() -> uint { - let block = malloc_raw(rust_pthread_mutex_t_size() as uint) as *pthread_mutex_t; + let block = malloc_raw(rust_pthread_mutex_t_size() as uint) as *mut pthread_mutex_t; let n = pthread_mutex_init(block, ptr::null()); assert_eq!(n, 0); return block as uint; } pub unsafe fn init_cond() -> uint { - let block = malloc_raw(rust_pthread_cond_t_size() as uint) as *pthread_cond_t; + let block = malloc_raw(rust_pthread_cond_t_size() as uint) as *mut pthread_cond_t; let n = pthread_cond_init(block, ptr::null()); assert_eq!(n, 0); return block as uint; } pub unsafe fn free_lock(h: uint) { - let block = h as *libc::c_void; + let block = h as *mut libc::c_void; assert_eq!(pthread_mutex_destroy(block), 0); libc::free(block); } pub unsafe fn free_cond(h: uint) { - let block = h as *pthread_cond_t; + let block = h as *mut pthread_cond_t; assert_eq!(pthread_cond_destroy(block), 0); libc::free(block); } pub unsafe fn lock(l: uint) { - assert_eq!(pthread_mutex_lock(l as *pthread_mutex_t), 0); + assert_eq!(pthread_mutex_lock(l as *mut pthread_mutex_t), 0); } pub unsafe fn trylock(l: uint) -> bool { - pthread_mutex_trylock(l as *pthread_mutex_t) == 0 + pthread_mutex_trylock(l as *mut pthread_mutex_t) == 0 } pub unsafe fn unlock(l: uint) { - assert_eq!(pthread_mutex_unlock(l as *pthread_mutex_t), 0); + assert_eq!(pthread_mutex_unlock(l as *mut pthread_mutex_t), 0); } pub unsafe fn wait(cond: uint, m: uint) { - assert_eq!(pthread_cond_wait(cond as *pthread_cond_t, m as *pthread_mutex_t), 0); + assert_eq!(pthread_cond_wait(cond as *mut pthread_cond_t, m as *mut pthread_mutex_t), 0); } pub unsafe fn signal(cond: uint) { - assert_eq!(pthread_cond_signal(cond as *pthread_cond_t), 0); + assert_eq!(pthread_cond_signal(cond as *mut pthread_cond_t), 0); } extern { @@ -224,19 +224,19 @@ mod imp { } extern { - fn pthread_mutex_init(lock: *pthread_mutex_t, + fn pthread_mutex_init(lock: *mut pthread_mutex_t, attr: *pthread_mutexattr_t) -> libc::c_int; - fn pthread_mutex_destroy(lock: *pthread_mutex_t) -> libc::c_int; - fn pthread_cond_init(cond: *pthread_cond_t, + fn pthread_mutex_destroy(lock: *mut pthread_mutex_t) -> libc::c_int; + fn pthread_cond_init(cond: *mut pthread_cond_t, attr: *pthread_condattr_t) -> libc::c_int; - fn pthread_cond_destroy(cond: *pthread_cond_t) -> libc::c_int; - fn pthread_mutex_lock(lock: *pthread_mutex_t) -> libc::c_int; - fn pthread_mutex_trylock(lock: *pthread_mutex_t) -> libc::c_int; - fn pthread_mutex_unlock(lock: *pthread_mutex_t) -> libc::c_int; + fn pthread_cond_destroy(cond: *mut pthread_cond_t) -> libc::c_int; + fn pthread_mutex_lock(lock: *mut pthread_mutex_t) -> libc::c_int; + fn pthread_mutex_trylock(lock: *mut pthread_mutex_t) -> libc::c_int; + fn pthread_mutex_unlock(lock: *mut pthread_mutex_t) -> libc::c_int; - fn pthread_cond_wait(cond: *pthread_cond_t, - lock: *pthread_mutex_t) -> libc::c_int; - fn pthread_cond_signal(cond: *pthread_cond_t) -> libc::c_int; + fn pthread_cond_wait(cond: *mut pthread_cond_t, + lock: *mut pthread_mutex_t) -> libc::c_int; + fn pthread_cond_signal(cond: *mut pthread_cond_t) -> libc::c_int; } } @@ -263,7 +263,7 @@ mod imp { pub unsafe fn free_lock(h: uint) { DeleteCriticalSection(h as LPCRITICAL_SECTION); - libc::free(h as *c_void); + libc::free(h as *mut c_void); } pub unsafe fn free_cond(h: uint) { diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 885c669ecb4..8e8e5f6e62c 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -960,7 +960,7 @@ pub trait ImmutableVector<'a, T> { fn flat_map<U>(&self, f: |t: &T| -> ~[U]) -> ~[U]; /// Returns a pointer to the element at the given index, without doing /// bounds checking. - unsafe fn unsafe_ref(&self, index: uint) -> *T; + unsafe fn unsafe_ref(self, index: uint) -> &'a T; /** * Returns an unsafe pointer to the vector's buffer @@ -1149,8 +1149,8 @@ impl<'a,T> ImmutableVector<'a, T> for &'a [T] { } #[inline] - unsafe fn unsafe_ref(&self, index: uint) -> *T { - self.repr().data.offset(index as int) + unsafe fn unsafe_ref(self, index: uint) -> &'a T { + cast::transmute(self.repr().data.offset(index as int)) } #[inline] @@ -2183,7 +2183,7 @@ pub trait MutableVector<'a, T> { fn move_from(self, src: ~[T], start: uint, end: uint) -> uint; /// Returns an unsafe mutable pointer to the element in index - unsafe fn unsafe_mut_ref(self, index: uint) -> *mut T; + unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T; /// Return an unsafe mutable pointer to the vector's buffer. /// @@ -2361,8 +2361,8 @@ impl<'a,T> MutableVector<'a, T> for &'a mut [T] { } #[inline] - unsafe fn unsafe_mut_ref(self, index: uint) -> *mut T { - ptr::mut_offset(self.repr().data as *mut T, index as int) + unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T { + cast::transmute(ptr::mut_offset(self.repr().data as *mut T, index as int)) } #[inline] diff --git a/src/libstd/vec_ng.rs b/src/libstd/vec_ng.rs new file mode 100644 index 00000000000..e503497d95d --- /dev/null +++ b/src/libstd/vec_ng.rs @@ -0,0 +1,231 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Migrate documentation over from `std::vec` when it is removed. +#[doc(hidden)]; + +use prelude::*; +use container::Container; +use mem::size_of; +use cast::{forget, transmute}; +use rt::global_heap::{malloc_raw, realloc_raw}; +use vec::Items; +use unstable::raw::Slice; +use ptr::{offset, read_ptr}; +use libc::{free, c_void}; +use unstable::intrinsics::move_val_init; + +pub struct Vec<T> { + priv len: uint, + priv cap: uint, + priv ptr: *mut T +} + +impl<T> Vec<T> { + #[inline] + pub fn new() -> Vec<T> { + Vec { len: 0, cap: 0, ptr: 0 as *mut T } + } + + pub fn with_capacity(capacity: uint) -> Vec<T> { + if capacity == 0 { + Vec::new() + } else { + let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow"); + let ptr = unsafe { malloc_raw(size) }; + Vec { len: 0, cap: capacity, ptr: ptr as *mut T } + } + } + + pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> { + unsafe { + let mut xs = Vec::with_capacity(length); + while xs.len < length { + move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), op(xs.len)); + xs.len += 1; + } + xs + } + } +} + +impl<T: Clone> Vec<T> { + pub fn from_elem(length: uint, value: T) -> Vec<T> { + unsafe { + let mut xs = Vec::with_capacity(length); + while xs.len < length { + move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), value.clone()); + xs.len += 1; + } + xs + } + } +} + +impl<T> Container for Vec<T> { + #[inline] + fn len(&self) -> uint { + self.len + } +} + +impl<T> Vec<T> { + #[inline] + pub fn capacity(&self) -> uint { + self.cap + } + + pub fn reserve_exact(&mut self, capacity: uint) { + if capacity >= self.len { + let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow"); + self.cap = capacity; + unsafe { + self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T; + } + } + } + + pub fn shrink_to_fit(&mut self) { + if self.len == 0 { + unsafe { free(self.ptr as *mut c_void) }; + self.cap = 0; + self.ptr = 0 as *mut T; + } else { + unsafe { + // Overflow check is unnecessary as the vector is already at least this large. + self.ptr = realloc_raw(self.ptr as *mut u8, self.len * size_of::<T>()) as *mut T; + } + self.cap = self.len; + } + } + + #[inline] + pub fn pop(&mut self) -> Option<T> { + if self.len == 0 { + None + } else { + unsafe { + self.len -= 1; + Some(read_ptr(self.as_slice().unsafe_ref(self.len()))) + } + } + } + + #[inline] + pub fn push(&mut self, value: T) { + if self.len == self.cap { + if self.cap == 0 { self.cap += 2 } + let old_size = self.cap * size_of::<T>(); + self.cap = self.cap * 2; + let size = old_size * 2; + if old_size > size { fail!("capacity overflow") } + unsafe { + self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T; + } + } + + unsafe { + let end = offset(self.ptr as *T, self.len as int) as *mut T; + move_val_init(&mut *end, value); + self.len += 1; + } + } + + pub fn truncate(&mut self, len: uint) { + unsafe { + let mut i = len; + // drop any extra elements + while i < self.len { + read_ptr(self.as_slice().unsafe_ref(i)); + i += 1; + } + } + self.len = len; + } + + #[inline] + pub fn as_slice<'a>(&'a self) -> &'a [T] { + let slice = Slice { data: self.ptr as *T, len: self.len }; + unsafe { transmute(slice) } + } + + #[inline] + pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] { + let slice = Slice { data: self.ptr as *T, len: self.len }; + unsafe { transmute(slice) } + } + + #[inline] + pub fn move_iter(self) -> MoveItems<T> { + unsafe { + let iter = transmute(self.as_slice().iter()); + let ptr = self.ptr as *mut c_void; + forget(self); + MoveItems { allocation: ptr, iter: iter } + } + } + + #[inline] + pub unsafe fn set_len(&mut self, len: uint) { + self.len = len; + } +} + + +#[unsafe_destructor] +impl<T> Drop for Vec<T> { + fn drop(&mut self) { + unsafe { + for x in self.as_mut_slice().iter() { + read_ptr(x); + } + free(self.ptr as *mut c_void) + } + } +} + +pub struct MoveItems<T> { + priv allocation: *mut c_void, // the block of memory allocated for the vector + priv iter: Items<'static, T> +} + +impl<T> Iterator<T> for MoveItems<T> { + #[inline] + fn next(&mut self) -> Option<T> { + unsafe { + self.iter.next().map(|x| read_ptr(x)) + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option<uint>) { + self.iter.size_hint() + } +} + +impl<T> DoubleEndedIterator<T> for MoveItems<T> { + #[inline] + fn next_back(&mut self) -> Option<T> { + unsafe { + self.iter.next_back().map(|x| read_ptr(x)) + } + } +} + +#[unsafe_destructor] +impl<T> Drop for MoveItems<T> { + fn drop(&mut self) { + // destroy the remaining elements + for _x in *self {} + unsafe { + free(self.allocation) + } + } +} |