packed_array/
lib.rs

1#![allow(dead_code)]
2use std::ptr::NonNull;
3use std::marker::PhantomData;
4use std::alloc::{self, Layout};
5use std::ptr;
6use array_init::array_init;
7
8/// Densly packed data structure for fast iteration
9pub struct PackedArray<T, const N : usize> {
10    size : usize,
11    index_to_entry : [usize; N],
12    entry_to_index : [usize; N],
13    ptr : NonNull<T>,
14    _marker : PhantomData<T>
15}
16
17impl<T, const N : usize> PackedArray<T, N> {
18
19    /// Return new PackedArray with allocated storage
20    pub fn new() -> Self {
21        let layout = Layout::array::<T>(N).unwrap();
22        let ptr = match NonNull::new(unsafe { alloc::alloc(layout) } as *mut T) {
23            Some(p) => p,
24            None => alloc::handle_alloc_error( layout ),
25        };
26
27        PackedArray { 
28            size : 0,
29            index_to_entry : array_init(|i| i),
30            entry_to_index : array_init(|i| i),
31            ptr, 
32            _marker : PhantomData
33        }
34    }
35
36    /// Returns current number of elements stored
37    pub fn len(&self) -> usize {
38        self.size
39    }
40
41    /// Returns true if there is a valid entry under index
42    pub fn has(&self, index : usize) -> bool {
43        self.index_to_entry[index] < self.size
44    }
45
46    /// Returns true if allocated memory is exhausted
47    /// True also means that no more entries can be added
48    pub fn full(&self) -> bool {
49        self.size == N
50    }
51
52    /// Returns reference to an element at index
53    /// Panics if there is no valid element with such index 
54    pub fn get(&self, index : usize) -> & T {
55        assert!(self.has(index));
56
57        unsafe {
58            &*self.get_ptr(self.index_to_entry[index])
59        }
60    }
61
62    /// Return mutable reference to an element at index
63    /// Panics if there is no valid element with such index 
64    pub fn get_mut(&mut self, index : usize) -> &mut T {
65        assert!(self.has(index));
66
67        unsafe {
68            &mut *self.get_ptr(self.index_to_entry[index])
69        }
70    }
71
72    /// Adds element to the end of array.
73    /// Return index of newly-added element for future access
74    /// Panics if structure is full
75    pub fn append(&mut self, value : T) -> usize {
76        assert!(!self.full());
77
78        unsafe {
79            ptr::write(self.ptr.as_ptr().add(self.size), value);
80        }
81
82        self.size += 1;
83        self.entry_to_index[self.size-1]
84    }
85
86    /// Sets value of passed index
87    /// If there is no valid element with such index, element is added
88    pub fn set(&mut self, index : usize, value : T) {
89        if !self.has(index) {
90            self.swap_with_back(index);
91            self.size += 1;
92        }
93        self[index] = value;
94    }
95
96    /// Removes element by given index
97    /// Panics if there is no valid element with such index 
98    pub fn remove(&mut self, index : usize) {
99        assert!(self.has(index));
100
101        self.size -= 1;
102        if self.index_to_entry[index] != self.size {
103            let entry_to_delete = self.index_to_entry[index];
104
105            unsafe {
106                ptr::copy_nonoverlapping(self.get_ptr(self.size), self.get_ptr(entry_to_delete), 1);
107            }
108            self.swap_with_back(index);
109        }
110    }
111
112    /// Returns an underlying storage as slice
113    pub fn as_slice(&self) -> &[T] {
114        unsafe {
115            std::slice::from_raw_parts(self.ptr.as_ptr(), self.size)
116        }
117    }
118
119    /// Returns an underlying storage as mutable slice
120    pub fn as_slice_mut(&mut self) -> &mut [T] {
121        unsafe {
122            std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.size)
123        }
124    }
125
126    /// Returns an iterator to underlying storage
127    pub fn iter(&self) -> std::slice::Iter<'_, T> {
128       self.as_slice().iter() 
129    }
130
131    /// Return a mutable iterator to underlying storage
132    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, T> {
133        self.as_slice_mut().iter_mut()
134    }
135
136    fn swap_with_back(&mut self, index : usize) {
137        let entry = self.index_to_entry[index];
138        let last_index = self.entry_to_index[self.size];
139
140        self.index_to_entry.swap(index, last_index);
141        self.entry_to_index.swap(entry, self.size);
142    }
143
144    fn get_ptr(&self, entry : usize) -> *mut T {
145        unsafe {
146            self.ptr.as_ptr().add(entry)
147        }
148    }
149}
150
151impl<T, const N : usize> std::ops::Index<usize> for PackedArray<T, N> {
152    type Output = T;
153
154    fn index(&self, index : usize) -> &Self::Output {
155        self.get(index)
156    }
157}
158
159impl<T, const N : usize> std::ops::IndexMut<usize> for PackedArray<T, N> {
160    fn index_mut(&mut self, index : usize) -> &mut Self::Output {
161        self.get_mut(index)
162    }
163}
packed_array/lib.rs

packed_array/
lib.rs
