two_sided_vec/
raw.rs

1use std::ptr::NonNull;
2use std::marker::PhantomData;
3use std::ops::Add;
4use std::mem;
5
6use std::alloc::{handle_alloc_error, Allocator, Global, Layout};
7
8pub struct RawTwoSidedVec<T> {
9    middle: NonNull<T>,
10    marker: PhantomData<T>,
11    capacity: Capacity
12}
13impl<T> RawTwoSidedVec<T> {
14    #[inline]
15    pub fn new() -> Self {
16        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
17        RawTwoSidedVec {
18            middle: NonNull::dangling(),
19            marker: PhantomData,
20            capacity: Capacity { back: 0, front: 0 }
21        }
22    }
23    pub fn with_capacity(capacity: Capacity) -> Self {
24        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
25        if capacity.is_empty() {
26            return RawTwoSidedVec::new()
27        }
28        let heap = Global::default();
29        let layout = capacity.layout::<T>();
30        unsafe {
31            let memory = heap.allocate(layout)
32                .unwrap_or_else(|_| handle_alloc_error(layout));
33            let middle = (memory.as_ptr() as *mut T).add(capacity.back);
34            RawTwoSidedVec::from_raw_parts(
35                middle,
36                capacity
37            )
38        }
39    }
40    /// Create a vector based on an existing pointer and capacity
41    ///
42    /// ## Safety
43    /// Undefined behavior if middle doesn't have enough space for `capacity`
44    /// elements (in either direction) or the memory was allocated incorrectly.
45    #[inline]
46    pub unsafe fn from_raw_parts(middle: *mut T, capacity: Capacity) -> Self {
47        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
48        debug_assert!(!middle.is_null());
49        RawTwoSidedVec { middle: NonNull::new_unchecked(middle), marker: PhantomData, capacity }
50    }
51    #[inline]
52    pub fn capacity(&self) -> &Capacity {
53        &self.capacity
54    }
55    #[inline]
56    pub fn middle(&self) -> *mut T {
57        self.middle.as_ptr()
58    }
59    /// A pointer to the start of the allocation
60    #[inline]
61    fn alloc_start(&self) -> *mut T {
62        unsafe { self.middle.as_ptr().sub(self.capacity.back) }
63    }
64    pub fn reserve(&mut self, request: CapacityRequest) {
65        assert!(self.capacity.can_fit(request.used));
66        let requested_capacity = request.used + request.needed;
67        unsafe {
68            // Reallocate
69            let result = Self::with_capacity(requested_capacity);
70            result.middle().sub(request.used.back).copy_from_nonoverlapping(
71                self.middle().sub(request.used.back),
72                request.used.back
73            );
74            result.middle().copy_from_nonoverlapping(
75                self.middle(),
76                request.used.front
77            );
78            *self = result; // Replace
79        }
80        debug_assert!(self.capacity.can_fit(requested_capacity));
81    }
82}
83unsafe impl<#[may_dangle] T> Drop for RawTwoSidedVec<T> {
84    #[inline]
85    fn drop(&mut self) {
86        if !self.capacity.is_empty() {
87            let heap = Global::default();
88            unsafe {
89                let layout = self.capacity.layout::<T>();
90                heap.deallocate(
91                    NonNull::new_unchecked(self.alloc_start() as *mut u8),
92                    layout
93                );
94            }
95        }
96    }
97}
98#[derive(Copy, Clone, Debug)]
99pub struct Capacity {
100    pub back: usize,
101    pub front: usize
102}
103impl Capacity {
104    #[inline]
105    pub fn empty() -> Self {
106        Capacity { back: 0, front: 0 }
107    }
108    #[inline]
109    pub fn checked_total(&self) -> usize {
110        self.back.checked_add(self.front).expect("Capacity overflow")
111    }
112    #[inline]
113    pub fn total(&self) -> usize {
114        self.back + self.front
115    }
116    #[inline]
117    pub fn can_fit(&self, other: Capacity) -> bool {
118        self.back >= other.back && self.front >= other.front
119    }
120    #[inline]
121    fn layout<T>(&self) -> Layout {
122        Layout::array::<T>(self.checked_total()).expect("Capacity overflow")
123    }
124    #[inline]
125    pub fn is_empty(&self) -> bool {
126        self.back == 0 && self.front == 0
127    }
128}
129impl Add for Capacity {
130    type Output = Capacity;
131
132    #[inline]
133    fn add(self, rhs: Capacity) -> Capacity {
134        match (self.front.checked_add(rhs.front), self.back.checked_add(rhs.back)) {
135            (Some(front), Some(back)) => Capacity { front, back },
136            _ => panic!("Capacity overflow")
137        }
138    }
139}
140#[derive(Copy, Clone, Debug)]
141pub struct CapacityRequest {
142    pub used: Capacity,
143    pub needed: Capacity
144}
two_sided_vec/raw.rs

two_sided_vec/
raw.rs
