x_map/
maps.rs

1use std::alloc::Layout;
2use std::ptr;
3use crate::error::MapError;
4
5#[derive(Debug)]
6pub struct KeyValue<'a, K, V> {
7    key: &'a K,
8    value: &'a V,
9}
10
11impl<'a, K, V> KeyValue<'a, K, V> {
12    pub fn key(&self) -> &'a K {
13        &self.key
14    }
15
16    pub fn value(&self) -> &'a V {
17        &self.value
18    }
19}
20
21#[derive(Debug)]
22pub struct CIndexMap<K, V> {
23    key_layout: Layout,
24    val_layout: Layout,
25    keys: *mut K,
26    values: *mut V,
27
28    /// The total allocated memory for this map.
29    ///
30    /// Everything in the range `self.pos + 1..self.cap` is not uninitialized, but may be old
31    /// or unwanted.
32    cap: isize,
33
34    /// Position of the cursor where the **last valid value** was inserted. `keys[pos]` and
35    /// `values[pos]` will always be initialized with valid data.
36    ///
37    /// All elements 0 to `self.pos` are guaranteed to be initialized.
38    pos: isize,
39}
40
41impl<K, V> CIndexMap<K, V> {
42    /// Constructs a new `CIndexMap`.
43    ///
44    /// # Panics
45    /// When `size_of::<K>` or `size_of::<T>` is 0.
46    pub fn new() -> CIndexMap<K, V> {
47        if size_of::<K>() == 0 || size_of::<V>() == 0 {
48            panic!("Cannot initialize CIndexMap with ZSTs!");
49        }
50
51        let key_layout = unsafe {
52            Layout::from_size_align(size_of::<K>() * 1, align_of::<K>()).unwrap()
53        };
54        let val_layout = unsafe {
55            Layout::from_size_align(size_of::<V>() * 1, align_of::<V>()).unwrap()
56        };
57
58        // SAFETY:
59        // ZSTs are not supported, this point in the initializing cannot be reached
60        // if a ZST is provided.
61        let key_ptr = unsafe {
62            std::alloc::alloc(key_layout)
63        } as *mut K;
64
65        // SAFETY:
66        // ZSTs are not supported, this point in the initializing cannot be reached
67        // if a ZST is provided.
68        let val_ptr = unsafe {
69            std::alloc::alloc(val_layout)
70        } as *mut V;
71
72        CIndexMap {
73            key_layout,
74            val_layout,
75            keys: key_ptr,
76            values: val_ptr,
77            cap: 1,
78            pos: -1,
79        }
80    }
81
82    /// Inserts a new key/value pair into the map.
83    ///
84    /// This function returns `Ok(())` if the key/value pair was inserted successfully.
85    pub fn insert(&mut self, key: K, value: V) -> crate::result::Result<()> {
86        if (self.pos + 1) >= self.cap {
87            let new_cap = self.cap + 2;
88
89            let new_key_ptr = unsafe {
90                std::alloc::realloc(
91                    self.keys as *mut u8,
92                    self.key_layout,
93                    size_of::<K>() * (new_cap as usize)
94                ) as *mut K
95            };
96
97            let new_val_ptr = unsafe {
98                std::alloc::realloc(
99                    self.values as *mut u8,
100                    self.val_layout,
101                    size_of::<V>() * (new_cap as usize)
102                ) as *mut V
103            };
104
105            self.keys = new_key_ptr;
106            self.values = new_val_ptr;
107            self.cap = new_cap;
108        }
109
110        self.pos += 1;
111
112        // SAFETY:
113        // The data was properly aligned during initialization.
114        // The memory being pointed to was verified to be between 0 (the pointer starting position)
115        // and `self.cap`, which is the current amount of allocated space.
116        unsafe {
117            self.keys.offset(self.pos).write(key);
118            self.values.offset(self.pos).write(value);
119        }
120
121        Ok(())
122    }
123
124    /// Removes an element at the specified index.
125    pub fn remove(&mut self, index: usize) -> crate::result::Result<()> {
126        if index > (self.pos as usize) {
127            Err(MapError {})
128        } else {
129            // SAFETY:
130            // We've determined that the index requested fits within the range of valid data.
131            unsafe {
132                // Shift all elements between `index` and `self.pos` back by one by copying
133                // the pointer and overwriting it at the position specified by `index`.
134                ptr::copy(
135                    self.keys.offset((index as isize) + 1),
136                    self.keys.offset(index as isize),
137                    (self.pos as usize - index)
138                );
139
140                ptr::copy(
141                    self.values.offset((index as isize) + 1),
142                    self.values.offset(index as isize),
143                    self.pos as usize - index
144                );
145            }
146
147            // Decrement self.pos to ensure this is always set as the position of the
148            // last valid inserted value.
149            self.pos -= 1;
150            Ok(())
151        }
152    }
153
154    /// Returns the key/object pair based on insertion order.
155    pub fn index(&self, index: usize) -> Option<KeyValue<K, V>> {
156        if index > (self.pos as usize) {
157            None
158        } else {
159            // SAFETY:
160            // All elements `0..self.pos` should be already be initialized.
161            unsafe {
162                Some(
163                    KeyValue {
164                        key: &*self.keys.offset(index as isize),
165                        value: &*self.values.offset(index as isize)
166                    }
167                )
168            }
169        }
170    }
171}
x_map/maps.rs

x_map/
maps.rs
