diff options
Diffstat (limited to 'ctr-std/src/collections/hash/table.rs')
| -rw-r--r-- | ctr-std/src/collections/hash/table.rs | 93 |
1 files changed, 44 insertions, 49 deletions
diff --git a/ctr-std/src/collections/hash/table.rs b/ctr-std/src/collections/hash/table.rs index 73bd574..93f0590 100644 --- a/ctr-std/src/collections/hash/table.rs +++ b/ctr-std/src/collections/hash/table.rs @@ -8,8 +8,7 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use alloc::heap::{Heap, Alloc, Layout}; - +use alloc::{Global, Alloc, Layout, CollectionAllocErr}; use cmp; use hash::{BuildHasher, Hash, Hasher}; use marker; @@ -484,21 +483,6 @@ impl<K, V, M> EmptyBucket<K, V, M> table: self.table, } } - - /// Puts given key, remain value uninitialized. - /// It is only used for inplacement insertion. - pub unsafe fn put_key(mut self, hash: SafeHash, key: K) -> FullBucket<K, V, M> { - *self.raw.hash() = hash.inspect(); - let pair_ptr = self.raw.pair(); - ptr::write(&mut (*pair_ptr).0, key); - - self.table.borrow_table_mut().size += 1; - - FullBucket { - raw: self.raw, - table: self.table, - } - } } impl<K, V, M: Deref<Target = RawTable<K, V>>> FullBucket<K, V, M> { @@ -574,17 +558,6 @@ impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> { v) } } - - /// Remove this bucket's `key` from the hashtable. - /// Only used for inplacement insertion. - /// NOTE: `Value` is uninitialized when this function is called, don't try to drop the `Value`. - pub unsafe fn remove_key(&mut self) { - self.table.size -= 1; - - *self.raw.hash() = EMPTY_BUCKET; - let pair_ptr = self.raw.pair(); - ptr::drop_in_place(&mut (*pair_ptr).0); // only drop key - } } // This use of `Put` is misleading and restrictive, but safe and sufficient for our use cases @@ -741,14 +714,15 @@ fn test_offset_calculation() { impl<K, V> RawTable<K, V> { /// Does not initialize the buckets. The caller should ensure they, /// at the very least, set every hash to EMPTY_BUCKET. - unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> { + /// Returns an error if it cannot allocate or capacity overflows. + unsafe fn try_new_uninitialized(capacity: usize) -> Result<RawTable<K, V>, CollectionAllocErr> { if capacity == 0 { - return RawTable { + return Ok(RawTable { size: 0, capacity_mask: capacity.wrapping_sub(1), hashes: TaggedHashUintPtr::new(EMPTY as *mut HashUint), marker: marker::PhantomData, - }; + }); } // No need for `checked_mul` before a more restrictive check performed @@ -768,25 +742,36 @@ impl<K, V> RawTable<K, V> { align_of::<HashUint>(), pairs_size, align_of::<(K, V)>()); - assert!(!oflo, "capacity overflow"); + if oflo { + return Err(CollectionAllocErr::CapacityOverflow); + } // One check for overflow that covers calculation and rounding of size. - let size_of_bucket = size_of::<HashUint>().checked_add(size_of::<(K, V)>()).unwrap(); - assert!(size >= - capacity.checked_mul(size_of_bucket) - .expect("capacity overflow"), - "capacity overflow"); - - let buffer = Heap.alloc(Layout::from_size_align(size, alignment).unwrap()) - .unwrap_or_else(|e| Heap.oom(e)); + let size_of_bucket = size_of::<HashUint>().checked_add(size_of::<(K, V)>()) + .ok_or(CollectionAllocErr::CapacityOverflow)?; + let capacity_mul_size_of_bucket = capacity.checked_mul(size_of_bucket); + if capacity_mul_size_of_bucket.is_none() || size < capacity_mul_size_of_bucket.unwrap() { + return Err(CollectionAllocErr::CapacityOverflow); + } - let hashes = buffer as *mut HashUint; + let buffer = Global.alloc(Layout::from_size_align(size, alignment) + .map_err(|_| CollectionAllocErr::CapacityOverflow)?)?; - RawTable { + Ok(RawTable { capacity_mask: capacity.wrapping_sub(1), size: 0, - hashes: TaggedHashUintPtr::new(hashes), + hashes: TaggedHashUintPtr::new(buffer.cast().as_ptr()), marker: marker::PhantomData, + }) + } + + /// Does not initialize the buckets. The caller should ensure they, + /// at the very least, set every hash to EMPTY_BUCKET. + unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> { + match Self::try_new_uninitialized(capacity) { + Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"), + Err(CollectionAllocErr::AllocErr) => Global.oom(), + Ok(table) => { table } } } @@ -809,13 +794,23 @@ impl<K, V> RawTable<K, V> { } } + /// Tries to create a new raw table from a given capacity. If it cannot allocate, + /// it returns with AllocErr. + pub fn try_new(capacity: usize) -> Result<RawTable<K, V>, CollectionAllocErr> { + unsafe { + let ret = RawTable::try_new_uninitialized(capacity)?; + ptr::write_bytes(ret.hashes.ptr(), 0, capacity); + Ok(ret) + } + } + /// Creates a new raw table from a given capacity. All buckets are /// initially empty. pub fn new(capacity: usize) -> RawTable<K, V> { - unsafe { - let ret = RawTable::new_uninitialized(capacity); - ptr::write_bytes(ret.hashes.ptr(), 0, capacity); - ret + match Self::try_new(capacity) { + Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"), + Err(CollectionAllocErr::AllocErr) => Global.oom(), + Ok(table) => { table } } } @@ -1188,8 +1183,8 @@ unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for RawTable<K, V> { debug_assert!(!oflo, "should be impossible"); unsafe { - Heap.dealloc(self.hashes.ptr() as *mut u8, - Layout::from_size_align(size, align).unwrap()); + Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).as_opaque(), + Layout::from_size_align(size, align).unwrap()); // Remember how everything was allocated out of one buffer // during initialization? We only need one call to free here. } |