diff --git a/src/collections/raw_array.rs b/src/collections/raw_array.rs new file mode 100644 index 0000000000000000000000000000000000000000..93fa6d7b25f5a2bcae741b1716e6087deb2e2982 --- /dev/null +++ b/src/collections/raw_array.rs @@ -0,0 +1,184 @@ +use std::{mem, ptr}; +use std::alloc::{Layout, alloc, dealloc}; + +/// Very simple resizable array. Doesn't call destructors or anything. Just +/// makes sure that the array is cleaned up when dropped, and allows the user +/// to ergonomically resize. Assumes that `size_of::() != 0` (and checks this +/// in debug mode). +pub struct RawArray { + data: *mut T, + count: usize, +} + +impl RawArray { + const SIZE: usize = mem::size_of::(); + const ALIGNMENT: usize = mem::align_of::(); + + /// Constructs a new and empty (not allocated) array. + pub fn new() -> Self { + return Self{ + data: ptr::null_mut(), + count: 0, + } + } + + /// Resizes the array. All existing elements are preserved (whether the + /// contained bytes are bogus or not). + pub fn resize(&mut self, new_count: usize) { + if new_count > self.count { + let new_data = Self::allocate(new_count); + if !self.data.is_null() { + unsafe { + ptr::copy_nonoverlapping(self.data, new_data, self.count); + Self::deallocate(self.data, self.count); + } + } + + self.data = new_data; + self.count = new_count; + } else if new_count < self.count { + // `new_count < count` and `new_count >= 0`, so `data != null`. + if new_count == 0 { + Self::deallocate(self.data, self.count); + self.data = ptr::null_mut(); + self.count = 0; + } else { + let new_data = Self::allocate(new_count); + unsafe { + ptr::copy_nonoverlapping(self.data, new_data, new_count); + Self::deallocate(self.data, self.count); + } + self.data = new_data; + self.count = new_count; + } + } // otherwise: equal + } + + /// Retrieves mutable pointer to the value at the specified index. The + /// returned `*mut T` may point to bogus uninitialized memory. + pub fn get(&self, index: usize) -> *mut T { + debug_assert!(index < self.count); // at least some safety, amirite? + return unsafe{ self.data.add(index) }; + } + + /// Retrieves the base pointer of the array. Hence may be null, or may point + /// to bogus uninitialized memory. + pub fn data(&self) -> *mut T { + return self.data; + } + + /// Returns the length of the array. + pub fn len(&self) -> usize { + return self.count; + } + + fn allocate(count: usize) -> *mut T { + debug_assert_ne!(Self::SIZE, 0); + let size = count * Self::SIZE; + unsafe { + let layout = Layout::from_size_align_unchecked(size, Self::ALIGNMENT); + let data = alloc(layout); + return mem::transmute(data); + } + } + + fn deallocate(data: *mut T, count: usize) { + let size = count * Self::SIZE; + unsafe { + let layout = Layout::from_size_align_unchecked(size, Self::ALIGNMENT); + dealloc(mem::transmute(data), layout); + } + } +} + +impl Drop for RawArray { + fn drop(&mut self) { + if !self.data.is_null() { + Self::deallocate(self.data, self.count); + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn fill(array: &mut RawArray, count: usize) { + for idx in 0..count { + unsafe{ *array.get(idx) = idx } + } + } + + fn check(array: &RawArray, count: usize) { + for idx in 0..count { + assert_eq!(unsafe{ *array.get(idx) }, idx); + } + } + + #[test] + fn drop_empty_array() { + let array = RawArray::::new(); + assert_eq!(array.len(), 0); + assert_eq!(array.data(), ptr::null_mut()); + } + + #[test] + fn increase_size() { + const INIT_SIZE: usize = 16; + const NUM_RESIZES: usize = 4; + let mut array = RawArray::new(); + array.resize(INIT_SIZE); + fill(&mut array, INIT_SIZE); + + for grow_idx in 0..NUM_RESIZES { + let new_size = INIT_SIZE + grow_idx * 4; + array.resize(new_size); + assert_eq!(array.len(), new_size); + } + + check(&array, INIT_SIZE); + } + + #[test] + fn maintain_size() { + const INIT_SIZE: usize = 16; + const NUM_RESIZES :usize = 4; + + let mut array = RawArray::new(); + array.resize(INIT_SIZE); + fill(&mut array, INIT_SIZE); + for _idx in 0..NUM_RESIZES { + array.resize(INIT_SIZE); + assert_eq!(array.len(), INIT_SIZE); + } + check(&array, INIT_SIZE); + } + + #[test] + fn decrease_size() { + const INIT_SIZE: usize = 16; + const FINAL_SIZE: usize = 8; + + let mut array = RawArray::new(); + array.resize(INIT_SIZE); + fill(&mut array, INIT_SIZE); + array.resize(FINAL_SIZE); + check(&array, FINAL_SIZE); + } + + #[test] + fn increase_and_decrease_size() { + let sizes = [12, 8, 6, 150, 128, 32, 16, 90, 4, 18, 27]; + let min_size = *sizes.iter().min().unwrap(); + let max_size = *sizes.iter().max().unwrap(); + + let mut array = RawArray::new(); + array.resize(max_size); + fill(&mut array, max_size); + for size in sizes { + array.resize(size); + assert_eq!(array.len(), size); + } + check(&array, min_size); + } +} \ No newline at end of file