twizzler/collections/
vec.rs

1use std::{
2    alloc::{AllocError, Layout},
3    mem::MaybeUninit,
4    ops::RangeBounds,
5};
6
7use twizzler_rt_abi::{
8    error::{ArgumentError, ResourceError},
9    object::{MAX_SIZE, NULLPAGE_SIZE},
10};
11
12use crate::{
13    alloc::{Allocator, SingleObjectAllocator},
14    marker::{Invariant, StoreCopy},
15    ptr::{GlobalPtr, InvPtr, Ref, RefMut, RefSlice, RefSliceMut, TxRef, TxRefSlice},
16    util::same_object,
17    Result,
18};
19
20mod vec_object;
21pub use vec_object::{VecIter, VecObject};
22
23#[cfg(test)]
24mod tests;
25
26pub struct VecInner<T: Invariant> {
27    len: usize,
28    cap: usize,
29    start: InvPtr<T>,
30}
31
32impl<T: Invariant> VecInner<T> {
33    fn resolve_start(&self) -> Ref<'_, T> {
34        tracing::trace!("found start as {:x}", self.start.raw());
35        unsafe { self.start.resolve() }
36    }
37
38    fn resolve_start_tx(&self) -> Result<TxRef<T>> {
39        tracing::trace!("found start as {:x}", self.start.raw());
40        let mut tx = unsafe { self.start.resolve().into_tx() }?;
41        if same_object(tx.raw(), self) {
42            tx.nosync();
43        }
44        Ok(tx)
45    }
46
47    fn do_realloc<Alloc: Allocator>(
48        &mut self,
49        newcap: usize,
50        newlen: usize,
51        alloc: &Alloc,
52    ) -> Result<()> {
53        let place = unsafe { Ref::from_ptr(self) };
54        if newcap <= self.cap {
55            // TODO: shrinking.
56            return Ok(());
57        }
58
59        let new_layout = Layout::array::<T>(newcap).map_err(|_| AllocError)?;
60        let old_layout = Layout::array::<T>(self.cap).map_err(|_| AllocError)?;
61
62        let old_global = self.start.global().cast();
63        let new_alloc = unsafe { alloc.realloc(old_global, old_layout, new_layout.size()) }?;
64        let new_start = InvPtr::new(place, new_alloc.cast())?;
65        self.start = new_start;
66        self.cap = newcap;
67        self.len = newlen;
68        tracing::trace!(
69            "set start: {:x} len {}, cap {}",
70            self.start.raw(),
71            self.len,
72            self.cap
73        );
74
75        Ok(())
76    }
77
78    fn do_remove(&mut self, idx: usize) -> Result<()> {
79        let mut rslice = unsafe {
80            TxRefSlice::from_ref(
81                self.start.resolve().into_tx()?.cast::<u8>(),
82                self.cap * size_of::<T>(),
83            )
84        };
85        let slice = rslice.as_slice_mut();
86        let byte_idx_start = (idx + 1) * size_of::<T>();
87        let byte_idx = idx * size_of::<T>();
88        let byte_end = self.len * size_of::<T>();
89        tracing::trace!(
90            "slice byte copy: {} {} {}",
91            byte_idx,
92            byte_idx_start,
93            byte_end
94        );
95        slice.copy_within(byte_idx_start..byte_end, byte_idx);
96        if byte_idx_start == byte_end {
97            slice[byte_idx..byte_idx_start].fill(0);
98        }
99        self.len -= 1;
100        Ok(())
101    }
102
103    pub fn as_slice(&self) -> RefSlice<'_, T> {
104        let r = self.resolve_start();
105        let slice = unsafe { RefSlice::from_ref(r, self.len) };
106        slice
107    }
108
109    fn with_slice<R>(&self, f: impl FnOnce(&[T]) -> R) -> R {
110        let r = self.resolve_start();
111        let slice = unsafe { RefSlice::from_ref(r, self.len) };
112        f(slice.as_slice())
113    }
114
115    fn with_mut_slice<R>(
116        &mut self,
117        range: impl RangeBounds<usize>,
118        f: impl FnOnce(&mut [T]) -> Result<R>,
119    ) -> Result<R> {
120        let r = self.resolve_start_tx()?;
121        let slice = unsafe { TxRefSlice::from_ref(r, self.len) };
122        f(slice.slice(range).as_slice_mut())
123    }
124
125    fn with_mut<R>(&mut self, idx: usize, f: impl FnOnce(&mut T) -> Result<R>) -> Result<R> {
126        let r = self.resolve_start_tx()?;
127        let mut slice = unsafe { TxRefSlice::from_ref(r, self.len) };
128        let mut item = slice.get_mut(idx).unwrap();
129        f(&mut *item)
130    }
131}
132
133#[derive(twizzler_derive::BaseType)]
134pub struct Vec<T: Invariant, Alloc: Allocator> {
135    inner: VecInner<T>,
136    alloc: Alloc,
137}
138
139#[derive(Clone)]
140pub struct VecObjectAlloc;
141
142impl Allocator for VecObjectAlloc {
143    fn alloc(
144        &self,
145        layout: Layout,
146    ) -> std::result::Result<crate::ptr::GlobalPtr<u8>, std::alloc::AllocError> {
147        // 1 for null page, 2 for metadata pages, 1 for base
148        if layout.size() > MAX_SIZE - NULLPAGE_SIZE * 4 {
149            return Err(std::alloc::AllocError);
150        }
151        let obj = twizzler_rt_abi::object::twz_rt_get_object_handle((self as *const Self).cast())
152            .unwrap();
153        Ok(GlobalPtr::new(obj.id(), (NULLPAGE_SIZE * 2) as u64))
154    }
155
156    unsafe fn dealloc(&self, _ptr: crate::ptr::GlobalPtr<u8>, _layout: Layout) {}
157
158    unsafe fn realloc(
159        &self,
160        _ptr: GlobalPtr<u8>,
161        _layout: Layout,
162        newsize: usize,
163    ) -> std::result::Result<GlobalPtr<u8>, AllocError> {
164        // 1 for null page, 2 for metadata pages, 1 for base
165        if newsize > MAX_SIZE - NULLPAGE_SIZE * 4 {
166            return Err(std::alloc::AllocError);
167        }
168        let obj = twizzler_rt_abi::object::twz_rt_get_object_handle((self as *const Self).cast())
169            .unwrap();
170        Ok(GlobalPtr::new(obj.id(), (NULLPAGE_SIZE * 2) as u64))
171    }
172}
173
174impl SingleObjectAllocator for VecObjectAlloc {}
175
176//impl<T: Invariant, A: Allocator> BaseType for Vec<T, A> {}
177
178impl<T: Invariant, Alloc: Allocator> Vec<T, Alloc> {
179    fn maybe_uninit_slice<'a>(r: TxRef<T>, cap: usize) -> TxRefSlice<MaybeUninit<T>> {
180        unsafe { TxRefSlice::from_ref(r.cast(), cap) }
181    }
182
183    #[inline]
184    pub fn get_ref(&self, idx: usize) -> Option<Ref<'_, T>> {
185        let slice = self.as_slice();
186        slice.get_ref(idx)
187    }
188
189    #[inline]
190    pub unsafe fn get_mut(&mut self, idx: usize) -> Option<RefMut<'_, T>> {
191        let mut slice = self.as_mut_slice();
192        slice.get_mut(idx)
193    }
194
195    #[inline]
196    pub unsafe fn get_tx(&self, idx: usize) -> Result<Option<TxRef<T>>> {
197        let slice = self.as_slice();
198        slice.get_ref(idx).map(|f| f.owned().into_tx()).transpose()
199    }
200
201    pub fn new_in(alloc: Alloc) -> Self {
202        Self {
203            inner: VecInner {
204                cap: 0,
205                len: 0,
206                start: InvPtr::null(),
207            },
208            alloc,
209        }
210    }
211
212    fn get_slice_grow(&mut self) -> Result<TxRef<MaybeUninit<T>>> {
213        let oldlen = self.inner.len;
214        tracing::trace!("len: {}, cap: {}", self.inner.len, self.inner.cap);
215        if self.inner.len == self.inner.cap {
216            if self.inner.start.raw() as usize + size_of::<T>() * self.inner.cap
217                >= MAX_SIZE - NULLPAGE_SIZE
218            {
219                return Err(ResourceError::OutOfMemory.into());
220            }
221            let newcap = std::cmp::max(self.inner.cap, 1) * 2;
222            self.inner.do_realloc(newcap, oldlen + 1, &self.alloc)?;
223            let r = self.inner.resolve_start_tx()?;
224            tracing::trace!("grow {:p}", r.raw());
225            Ok(Self::maybe_uninit_slice(r, newcap)
226                .get_into(oldlen)
227                .unwrap())
228        } else {
229            self.inner.len += 1;
230            let r = self.inner.resolve_start_tx()?;
231            tracing::trace!(
232                "no grow {:p} {}, {} {}",
233                r.raw(),
234                r.is_nosync(),
235                self.inner.len,
236                self.inner.cap
237            );
238            Ok(Self::maybe_uninit_slice(r, self.inner.cap)
239                .get_into(oldlen)
240                .unwrap())
241        }
242    }
243
244    fn do_push(&mut self, item: T) -> Result<()> {
245        let r = self.get_slice_grow()?;
246        tracing::trace!("store value: {:p}", r.raw());
247        let r = r.write(item)?;
248        drop(r);
249        Ok(())
250    }
251
252    pub fn len(&self) -> usize {
253        self.inner.len
254    }
255
256    pub fn capacity(&self) -> usize {
257        self.inner.cap
258    }
259
260    pub fn reserve(&mut self, additional: usize) -> Result<()> {
261        self.inner
262            .do_realloc(self.inner.cap + additional, self.inner.len, &self.alloc)?;
263        Ok(())
264    }
265
266    #[inline]
267    pub fn as_slice(&self) -> RefSlice<'_, T> {
268        let r = self.inner.resolve_start();
269        let slice = unsafe { RefSlice::from_ref(r, self.inner.len) };
270        slice
271    }
272
273    #[inline]
274    pub fn as_tx_slice(&self) -> Result<TxRefSlice<T>> {
275        let r = self.inner.resolve_start_tx()?;
276        let slice = unsafe { TxRefSlice::from_ref(r, self.inner.len) };
277        Ok(slice)
278    }
279
280    #[inline]
281    pub unsafe fn as_mut_slice(&mut self) -> RefSliceMut<'_, T> {
282        let r = unsafe { self.inner.start.resolve_mut() };
283        let slice = unsafe { RefSliceMut::from_ref(r, self.inner.len) };
284        slice
285    }
286
287    pub fn remove_inplace(&mut self, idx: usize) -> Result<()> {
288        if idx >= self.inner.len {
289            return Err(ArgumentError::InvalidArgument.into());
290        }
291        self.inner.with_mut(idx, |item| {
292            unsafe { core::ptr::drop_in_place(item) };
293            Ok(())
294        })?;
295        self.inner.do_remove(idx)?;
296        Ok(())
297    }
298
299    pub fn truncate(&mut self, newlen: usize) -> Result<()> {
300        let oldlen = self.inner.len;
301        if newlen >= oldlen {
302            return Ok(());
303        }
304        self.inner.with_mut_slice(newlen..oldlen, |slice| {
305            for item in slice {
306                unsafe { core::ptr::drop_in_place(item) };
307            }
308            Ok(())
309        })?;
310        self.inner.len = newlen;
311        Ok(())
312    }
313
314    pub fn shrink_to_fit(&mut self) -> Result<()> {
315        self.inner.cap = self.inner.len;
316        // TODO: release memory
317        Ok(())
318    }
319
320    pub fn with_slice<R>(&self, f: impl FnOnce(&[T]) -> R) -> R {
321        self.inner.with_slice(f)
322    }
323
324    pub fn with_mut_slice<R>(
325        &mut self,
326        range: impl RangeBounds<usize>,
327        f: impl FnOnce(&mut [T]) -> Result<R>,
328    ) -> Result<R> {
329        self.inner.with_mut_slice(range, f)
330    }
331
332    pub fn is_empty(&self) -> bool {
333        self.len() == 0
334    }
335
336    pub fn clear(&mut self) -> Result<()> {
337        self.truncate(0)
338    }
339
340    pub fn swap(&mut self, a: usize, b: usize) {
341        if a == b {
342            return;
343        }
344        unsafe {
345            let mut slice = self.as_mut_slice();
346            let slice_mut = slice.as_slice_mut();
347            slice_mut.swap(a, b);
348        }
349    }
350
351    pub fn first_ref(&self) -> Option<Ref<'_, T>> {
352        self.get_ref(0)
353    }
354
355    pub fn last_ref(&self) -> Option<Ref<'_, T>> {
356        if self.inner.len == 0 {
357            None
358        } else {
359            self.get_ref(self.inner.len - 1)
360        }
361    }
362
363    pub fn contains(&self, item: &T) -> bool
364    where
365        T: PartialEq,
366    {
367        self.with_slice(|slice| slice.contains(item))
368    }
369
370    pub fn starts_with(&self, needle: &[T]) -> bool
371    where
372        T: PartialEq,
373    {
374        self.with_slice(|slice| slice.starts_with(needle))
375    }
376
377    pub fn ends_with(&self, needle: &[T]) -> bool
378    where
379        T: PartialEq,
380    {
381        self.with_slice(|slice| slice.ends_with(needle))
382    }
383
384    pub fn binary_search(&self, x: &T) -> std::result::Result<usize, usize>
385    where
386        T: Ord,
387    {
388        self.with_slice(|slice| slice.binary_search(x))
389    }
390
391    pub fn binary_search_by<F>(&self, f: F) -> std::result::Result<usize, usize>
392    where
393        F: FnMut(&T) -> std::cmp::Ordering,
394    {
395        self.with_slice(|slice| slice.binary_search_by(f))
396    }
397
398    pub fn reverse(&mut self) -> Result<()> {
399        self.with_mut_slice(.., |slice| {
400            slice.reverse();
401            Ok(())
402        })
403    }
404
405    pub fn sort(&mut self) -> Result<()>
406    where
407        T: Ord,
408    {
409        self.with_mut_slice(.., |slice| {
410            slice.sort();
411            Ok(())
412        })
413    }
414
415    pub fn sort_by<F>(&mut self, compare: F) -> Result<()>
416    where
417        F: FnMut(&T, &T) -> std::cmp::Ordering,
418    {
419        self.with_mut_slice(.., |slice| {
420            slice.sort_by(compare);
421            Ok(())
422        })
423    }
424
425    pub fn sort_unstable(&mut self) -> Result<()>
426    where
427        T: Ord,
428    {
429        self.with_mut_slice(.., |slice| {
430            slice.sort_unstable();
431            Ok(())
432        })
433    }
434
435    pub fn sort_unstable_by<F>(&mut self, compare: F) -> Result<()>
436    where
437        F: FnMut(&T, &T) -> std::cmp::Ordering,
438    {
439        self.with_mut_slice(.., |slice| {
440            slice.sort_unstable_by(compare);
441            Ok(())
442        })
443    }
444
445    pub fn retain<F>(&mut self, mut f: F) -> Result<()>
446    where
447        F: FnMut(&T) -> bool,
448    {
449        let mut del = 0;
450        let len = self.len();
451
452        for i in 0..len {
453            let should_retain = self.with_slice(|slice| f(&slice[i - del]));
454            if !should_retain {
455                self.remove_inplace(i - del)?;
456                del += 1;
457            }
458        }
459
460        Ok(())
461    }
462}
463
464impl<T: Invariant + StoreCopy, Alloc: Allocator> Vec<T, Alloc> {
465    pub fn push(&mut self, item: T) -> Result<()> {
466        self.do_push(item)
467    }
468
469    pub fn pop(&mut self) -> Result<Option<T>> {
470        if self.inner.len == 0 {
471            return Ok(None);
472        }
473        let new_len = self.inner.len - 1;
474        let val = self
475            .inner
476            .with_slice(|slice| unsafe { ((&slice[new_len]) as *const T).read() });
477        self.inner.do_remove(new_len)?;
478        Ok(Some(val))
479    }
480
481    pub fn remove(&mut self, idx: usize) -> Result<T> {
482        //let mut inner = self.inner.get()?;
483        if idx >= self.inner.len {
484            return Err(ArgumentError::InvalidArgument.into());
485        }
486        let val = self
487            .inner
488            .with_slice(|slice| unsafe { ((&slice[idx]) as *const T).read() });
489        self.inner.do_remove(idx)?;
490        Ok(val)
491    }
492}
493
494impl<T: Invariant, Alloc: Allocator + SingleObjectAllocator> Vec<T, Alloc> {
495    pub fn push_inplace(&mut self, item: T) -> Result<()> {
496        self.do_push(item)
497    }
498
499    pub fn push_ctor<F>(&mut self, ctor: F) -> Result<()>
500    where
501        F: FnOnce(RefMut<MaybeUninit<T>>) -> Result<RefMut<T>>,
502    {
503        let mut r = self.get_slice_grow()?;
504        let _val = ctor(r.as_mut())?;
505        Ok(())
506    }
507}
508
509impl<T: Invariant, A: Allocator, U> PartialEq<&[U]> for Vec<T, A>
510where
511    T: PartialEq<U>,
512{
513    fn eq(&self, other: &&[U]) -> bool {
514        self.with_slice(|s| s.eq(*other))
515    }
516}
517
518impl<T: Invariant, A: Allocator, U: Invariant, A2: Allocator> PartialEq<Vec<U, A2>> for Vec<T, A>
519where
520    T: PartialEq<U>,
521{
522    fn eq(&self, other: &Vec<U, A2>) -> bool {
523        self.with_slice(|s| other.with_slice(|o| s.eq(o)))
524    }
525}
526
527impl<T: Invariant, A: Allocator, U> PartialOrd<&[U]> for Vec<T, A>
528where
529    T: PartialOrd<U>,
530{
531    fn partial_cmp(&self, other: &&[U]) -> Option<std::cmp::Ordering> {
532        self.with_slice(|s| s.iter().partial_cmp(*other))
533    }
534}
535
536impl<T: Invariant, A: Allocator, U: Invariant, A2: Allocator> PartialOrd<Vec<U, A2>> for Vec<T, A>
537where
538    T: PartialOrd<U>,
539{
540    fn partial_cmp(&self, other: &Vec<U, A2>) -> Option<std::cmp::Ordering> {
541        self.with_slice(|s| other.with_slice(|o| s.iter().partial_cmp(o)))
542    }
543}
544
545impl<T: Invariant + Eq, A: Allocator> Eq for Vec<T, A> {}
546
547impl<T: Invariant + Ord, A: Allocator> Ord for Vec<T, A> {
548    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
549        self.partial_cmp(other).unwrap()
550    }
551}
552
553use std::fmt::Debug;
554impl<T: Debug + Invariant, A: Allocator> Debug for Vec<T, A> {
555    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
556        self.with_slice(|s| f.debug_list().entries(s.iter()).finish())
557    }
558}
twizzler/collections/vec.rs

twizzler/collections/
vec.rs
