From f2a90174bb36b9ad528e863ab34c02ebce002b02 Mon Sep 17 00:00:00 2001 From: Valentin Date: Fri, 15 Jun 2018 18:57:24 +0200 Subject: Update for latest nightly 2018-06-09 (#70) * Update for latest nightly 2018-06-09 * We now have a proper horizon os and sys modules in libstd --- ctr-std/src/collections/hash/table.rs | 166 +++++++++++----------------------- 1 file changed, 53 insertions(+), 113 deletions(-) (limited to 'ctr-std/src/collections/hash/table.rs') diff --git a/ctr-std/src/collections/hash/table.rs b/ctr-std/src/collections/hash/table.rs index b50652e..d997fb2 100644 --- a/ctr-std/src/collections/hash/table.rs +++ b/ctr-std/src/collections/hash/table.rs @@ -8,14 +8,14 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use alloc::{Global, Alloc, Layout, CollectionAllocErr, oom}; -use cmp; +use alloc::{Global, Alloc, Layout, LayoutErr, CollectionAllocErr, oom}; use hash::{BuildHasher, Hash, Hasher}; use marker; -use mem::{align_of, size_of, needs_drop}; +use mem::{size_of, needs_drop}; use mem; use ops::{Deref, DerefMut}; use ptr::{self, Unique, NonNull}; +use hint; use self::BucketState::*; @@ -651,71 +651,39 @@ impl GapThenFull } } - -/// Rounds up to a multiple of a power of two. Returns the closest multiple -/// of `target_alignment` that is higher or equal to `unrounded`. -/// -/// # Panics -/// -/// Panics if `target_alignment` is not a power of two. -#[inline] -fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize { - assert!(target_alignment.is_power_of_two()); - (unrounded + target_alignment - 1) & !(target_alignment - 1) -} - -#[test] -fn test_rounding() { - assert_eq!(round_up_to_next(0, 4), 0); - assert_eq!(round_up_to_next(1, 4), 4); - assert_eq!(round_up_to_next(2, 4), 4); - assert_eq!(round_up_to_next(3, 4), 4); - assert_eq!(round_up_to_next(4, 4), 4); - assert_eq!(round_up_to_next(5, 4), 8); -} - -// Returns a tuple of (pairs_offset, end_of_pairs_offset), -// from the start of a mallocated array. -#[inline] -fn calculate_offsets(hashes_size: usize, - pairs_size: usize, - pairs_align: usize) - -> (usize, usize, bool) { - let pairs_offset = round_up_to_next(hashes_size, pairs_align); - let (end_of_pairs, oflo) = pairs_offset.overflowing_add(pairs_size); - - (pairs_offset, end_of_pairs, oflo) +// Returns a Layout which describes the allocation required for a hash table, +// and the offset of the array of (key, value) pairs in the allocation. +fn calculate_layout(capacity: usize) -> Result<(Layout, usize), LayoutErr> { + let hashes = Layout::array::(capacity)?; + let pairs = Layout::array::<(K, V)>(capacity)?; + hashes.extend(pairs).map(|(layout, _)| { + // LLVM seems to have trouble properly const-propagating pairs.align(), + // possibly due to the use of NonZeroUsize. This little hack allows it + // to generate optimal code. + // + // See https://github.com/rust-lang/rust/issues/51346 for more details. + ( + layout, + hashes.size() + hashes.padding_needed_for(mem::align_of::<(K, V)>()), + ) + }) } -// Returns a tuple of (minimum required malloc alignment, -// array_size), from the start of a mallocated array. -fn calculate_allocation(hash_size: usize, - hash_align: usize, - pairs_size: usize, - pairs_align: usize) - -> (usize, usize, bool) { - let (_, end_of_pairs, oflo) = calculate_offsets(hash_size, pairs_size, pairs_align); - - let align = cmp::max(hash_align, pairs_align); - - (align, end_of_pairs, oflo) +pub(crate) enum Fallibility { + Fallible, + Infallible, } -#[test] -fn test_offset_calculation() { - assert_eq!(calculate_allocation(128, 8, 16, 8), (8, 144, false)); - assert_eq!(calculate_allocation(3, 1, 2, 1), (1, 5, false)); - assert_eq!(calculate_allocation(6, 2, 12, 4), (4, 20, false)); - assert_eq!(calculate_offsets(128, 15, 4), (128, 143, false)); - assert_eq!(calculate_offsets(3, 2, 4), (4, 6, false)); - assert_eq!(calculate_offsets(6, 12, 4), (8, 20, false)); -} +use self::Fallibility::*; impl RawTable { /// Does not initialize the buckets. The caller should ensure they, /// at the very least, set every hash to EMPTY_BUCKET. /// Returns an error if it cannot allocate or capacity overflows. - unsafe fn try_new_uninitialized(capacity: usize) -> Result, CollectionAllocErr> { + unsafe fn new_uninitialized_internal( + capacity: usize, + fallibility: Fallibility, + ) -> Result, CollectionAllocErr> { if capacity == 0 { return Ok(RawTable { size: 0, @@ -725,37 +693,15 @@ impl RawTable { }); } - // No need for `checked_mul` before a more restrictive check performed - // later in this method. - let hashes_size = capacity.wrapping_mul(size_of::()); - let pairs_size = capacity.wrapping_mul(size_of::<(K, V)>()); - // Allocating hashmaps is a little tricky. We need to allocate two // arrays, but since we know their sizes and alignments up front, // we just allocate a single array, and then have the subarrays // point into it. - // - // This is great in theory, but in practice getting the alignment - // right is a little subtle. Therefore, calculating offsets has been - // factored out into a different function. - let (alignment, size, oflo) = calculate_allocation(hashes_size, - align_of::(), - pairs_size, - align_of::<(K, V)>()); - if oflo { - return Err(CollectionAllocErr::CapacityOverflow); - } - - // One check for overflow that covers calculation and rounding of size. - let size_of_bucket = size_of::().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 buffer = Global.alloc(Layout::from_size_align(size, alignment) - .map_err(|_| CollectionAllocErr::CapacityOverflow)?)?; + let (layout, _) = calculate_layout::(capacity)?; + let buffer = Global.alloc(layout).map_err(|e| match fallibility { + Infallible => oom(layout), + Fallible => e, + })?; Ok(RawTable { capacity_mask: capacity.wrapping_sub(1), @@ -768,48 +714,50 @@ impl RawTable { /// 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 { - match Self::try_new_uninitialized(capacity) { + match Self::new_uninitialized_internal(capacity, Infallible) { Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"), - Err(CollectionAllocErr::AllocErr) => oom(), + Err(CollectionAllocErr::AllocErr) => unreachable!(), Ok(table) => { table } } } fn raw_bucket_at(&self, index: usize) -> RawBucket { - let hashes_size = self.capacity() * size_of::(); - let pairs_size = self.capacity() * size_of::<(K, V)>(); - - let (pairs_offset, _, oflo) = - calculate_offsets(hashes_size, pairs_size, align_of::<(K, V)>()); - debug_assert!(!oflo, "capacity overflow"); - + let (_, pairs_offset) = calculate_layout::(self.capacity()) + .unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() }); let buffer = self.hashes.ptr() as *mut u8; unsafe { RawBucket { hash_start: buffer as *mut HashUint, - pair_start: buffer.offset(pairs_offset as isize) as *const (K, V), + pair_start: buffer.add(pairs_offset) as *const (K, V), idx: index, _marker: marker::PhantomData, } } } - /// 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, CollectionAllocErr> { + fn new_internal( + capacity: usize, + fallibility: Fallibility, + ) -> Result, CollectionAllocErr> { unsafe { - let ret = RawTable::try_new_uninitialized(capacity)?; + let ret = RawTable::new_uninitialized_internal(capacity, fallibility)?; ptr::write_bytes(ret.hashes.ptr(), 0, capacity); Ok(ret) } } + /// 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, CollectionAllocErr> { + Self::new_internal(capacity, Fallible) + } + /// Creates a new raw table from a given capacity. All buckets are /// initially empty. pub fn new(capacity: usize) -> RawTable { - match Self::try_new(capacity) { + match Self::new_internal(capacity, Infallible) { Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"), - Err(CollectionAllocErr::AllocErr) => oom(), + Err(CollectionAllocErr::AllocErr) => unreachable!(), Ok(table) => { table } } } @@ -1173,18 +1121,10 @@ unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for RawTable { } } - let hashes_size = self.capacity() * size_of::(); - let pairs_size = self.capacity() * size_of::<(K, V)>(); - let (align, size, oflo) = calculate_allocation(hashes_size, - align_of::(), - pairs_size, - align_of::<(K, V)>()); - - debug_assert!(!oflo, "should be impossible"); - + let (layout, _) = calculate_layout::(self.capacity()) + .unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() }); unsafe { - Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).as_opaque(), - Layout::from_size_align(size, align).unwrap()); + Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).as_opaque(), layout); // Remember how everything was allocated out of one buffer // during initialization? We only need one call to free here. } -- cgit v1.2.3