1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
//! Slots object that provides an unrestricted access control for the stored data. //! //! Data type that stores values and returns an index that can be used to manipulate //! the stored values. //! //! Unlike [`Slots`], it's not guaranteed that the accessed slot has valid data. //! For this reason, the data access methods are always fallible, meaning they return //! None when a free slot is addressed. //! //! This structure is also susceptible to the [ABA problem](https://en.wikipedia.org/wiki/ABA_problem). //! //! # Store data //! //! When a piece of data is stored in the collection, a handle is returned. This handle //! identifies the slot and can be used to access the data. Unlike with [`Slots`], this //! handle is a `usize` which can be freely copied and shared. //! //! There should be no assumptions made on the value of the handle, except that it is `0 <= handle < N` //! where N is the capacity. //! //! ```rust //! use slots::unrestricted::UnrestrictedSlots; //! use slots::consts::U2; //! //! let mut slots: UnrestrictedSlots<_, U2> = UnrestrictedSlots::new(); // Capacity of 2 elements //! //! // Store elements //! let k1 = slots.store(2).unwrap(); //! let k2 = slots.store(4).unwrap(); //! //! // Now that the collection is full, the next store will fail and //! // return an Err object that holds the original value we wanted to store. //! let k3 = slots.store(8); //! assert_eq!(k3.err(), Some(8)); //! //! // Storage statistics //! assert_eq!(2, slots.capacity()); // this instance can hold at most 2 elements //! assert_eq!(2, slots.count()); // there are currently 2 elements stored //! ``` //! //! [`Slots`]: ../slots/index.html use core::mem::replace; use generic_array::{sequence::GenericSequence, ArrayLength, GenericArray}; use crate::iterator::*; use crate::private::Entry; /// Alias of [`ArrayLength`](../generic_array/trait.ArrayLength.html) pub trait Size<I>: ArrayLength<Entry<I>> {} impl<T, I> Size<I> for T where T: ArrayLength<Entry<I>> {} /// Slots object that provides an unrestricted access control for the stored data. /// /// The struct has two type parameters: /// - `IT` is the type of the stored data /// - `N` is the number of slots, which is a type-level constant provided by the `typenum` crate. /// /// For more information, see the [module level documentation](./index.html) #[derive(Default)] pub struct UnrestrictedSlots<IT, N> where N: Size<IT>, { items: GenericArray<Entry<IT>, N>, next_free: usize, count: usize, } impl<IT, N> UnrestrictedSlots<IT, N> where N: Size<IT>, { /// Creates a new, empty UnrestrictedSlots object. pub fn new() -> Self { Self { items: GenericArray::generate(|i| { i.checked_sub(1) .map(Entry::EmptyNext) .unwrap_or(Entry::EmptyLast) }), next_free: N::USIZE.saturating_sub(1), // edge case: N == 0 count: 0, } } /// Returns a read-only iterator. /// The iterator can be used to read data from all occupied slots. /// /// **Note:** Do not rely on the order in which the elements are returned. /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// # let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// slots.store(2).unwrap(); /// slots.store(4).unwrap(); /// slots.store(6).unwrap(); /// /// assert_eq!(true, slots.iter().any(|&x| x < 3)); /// ``` pub fn iter(&self) -> Iter<IT> { Iter::from_entry_slice(self.items.as_slice()) } /// Returns a read-write iterator. /// The iterator can be used to read and modify data from all occupied slots, but it can't remove data. /// /// **Note:** Do not rely on the order in which the elements are returned. /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// # let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// let k = slots.store(2).unwrap(); /// slots.store(4).unwrap(); /// slots.store(6).unwrap(); /// /// for mut x in slots.iter_mut() { /// *x *= 2; /// } /// /// assert_eq!(4, slots.take(k).unwrap()); /// ``` pub fn iter_mut(&mut self) -> IterMut<IT> { IterMut::from_entry_slice(self.items.as_mut_slice()) } /// Returns the number of slots /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// let slots: UnrestrictedSlots<f32, U4> = UnrestrictedSlots::new(); /// /// assert_eq!(4, slots.capacity()); /// ``` pub fn capacity(&self) -> usize { N::USIZE } /// Returns the number of occupied slots /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// /// assert_eq!(0, slots.count()); /// /// slots.store(3).unwrap(); /// slots.store(6).unwrap(); /// /// assert_eq!(2, slots.count()); /// ``` pub fn count(&self) -> usize { self.count } /// Returns whether all the slots are occupied and the next [`store()`](#method.store) will fail. /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// /// slots.store(3).unwrap(); /// slots.store(4).unwrap(); /// slots.store(5).unwrap(); /// /// assert_eq!(false, slots.is_full()); /// /// slots.store(6).unwrap(); /// /// assert_eq!(true, slots.is_full()); /// ``` pub fn is_full(&self) -> bool { self.count == self.capacity() } fn free(&mut self, idx: usize) { debug_assert!(self.count != 0, "Free called on an empty collection"); self.items[idx] = if self.is_full() { Entry::EmptyLast } else { Entry::EmptyNext(self.next_free) }; self.next_free = idx; // the freed element will always be the top of the free stack self.count -= 1; } fn alloc(&mut self) -> Option<usize> { if self.is_full() { // no free slot None } else { // next_free points to the top of the free stack let index = self.next_free; self.next_free = match self.items[index] { Entry::EmptyNext(n) => n, // pop the stack Entry::EmptyLast => 0, // replace last element with anything _ => unreachable!("Non-empty item in entry behind free chain"), }; self.count += 1; Some(index) } } /// Store an element in a free slot and return the key to access it. /// /// Storing a variable takes ownership over it. If the storage is full, /// the inserted data is returned in the return value. pub fn store(&mut self, item: IT) -> Result<usize, IT> { match self.alloc() { Some(i) => { self.items[i] = Entry::Used(item); Ok(i) } None => Err(item), } } /// Remove and return the element that belongs to the key. /// /// This operation is fallible. If `key` addresses a free slot, `None` is returned. pub fn take(&mut self, key: usize) -> Option<IT> { if let Entry::Used(item) = replace(&mut self.items[key], Entry::EmptyLast) { self.free(key); Some(item) } else { None } } /// Read the element that belongs to a particular index. Since the index may point to /// a free slot or outside the collection, this operation may return None without invoking the callback. /// /// This operation does not move ownership so the `function` callback must be used /// to access the stored element. The callback may return arbitrary derivative of the element. /// /// This operation is fallible. If `key` addresses a free slot, `None` is returned. /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// # let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// /// let k = slots.store(3).unwrap(); /// /// assert_eq!(Some(4), slots.read(k, |elem| { /// elem + 1 /// })); /// /// slots.take(k); /// /// assert_eq!(None, slots.read(k, |elem| { /// elem + 1 /// })); /// ``` pub fn read<T>(&self, key: usize, function: impl FnOnce(&IT) -> T) -> Option<T> { if key >= self.capacity() { None } else { match &self.items[key] { Entry::Used(item) => Some(function(&item)), _ => None, } } } /// Access the element that belongs to the key for modification. /// /// This operation does not move ownership so the `function` callback must be used /// to access the stored element. The callback may return arbitrary derivative of the element. /// /// This operation is fallible. If `key` addresses a free slot, `None` is returned. /// /// ``` /// # use slots::unrestricted::UnrestrictedSlots; /// # use slots::consts::U4; /// # let mut slots: UnrestrictedSlots<_, U4> = UnrestrictedSlots::new(); /// /// let k = slots.store(3).unwrap(); /// /// assert_eq!(Some("found"), slots.modify(k, |elem| { /// *elem = *elem + 1; /// /// "found" /// })); /// /// // Assert that the stored data was modified /// assert_eq!(Some(4), slots.take(k)); /// /// assert_eq!(None, slots.modify(k, |elem| { /// *elem = *elem + 1; /// /// "found" /// })); /// ``` pub fn modify<T>(&mut self, key: usize, function: impl FnOnce(&mut IT) -> T) -> Option<T> { match self.items[key] { Entry::Used(ref mut item) => Some(function(item)), _ => None, } } }