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
use crate::{index::GenerationalIndex, Error}; use std::collections::{HashMap, VecDeque}; /// Allocator for the LightVec /// /// Although not really an allocator, this entity guarantees that an action /// done to the vector will not violate the Generational scheme, or versioning /// scheme. For the time being, this *must* be passed as parameter to any /// LightVec function, such as insert or remove, in order to make those /// guarantees. The allocator can be instantiated with the lvec! macro, or with /// the ```new()``` function. /// /// Similar to the LightVec itself, the allocator can handle reallocations in /// case of insertion when the Vec is above capacity. In order to reduce /// overhead due to frequent reallocations, there is a setting in the /// allocator, called loan, which is used as way to assure how much memory is /// "loaned" when there is a reallocation. Default value for the loan is 1. pub struct LightVecAllocator { loan: usize, generations: HashMap<usize, usize>, free: VecDeque<usize>, } impl LightVecAllocator { /// Creates a new LightVecAllocator /// /// Creates a new LightVecAllocator, with the given capacity and with /// default values. fn with_capacity(capacity: usize) -> LightVecAllocator { let mut gens: HashMap<usize, usize> = HashMap::with_capacity(capacity); for i in 0..capacity { gens.insert(i, 0); } LightVecAllocator { loan: 1, generations: gens, free: VecDeque::with_capacity(capacity), } } /// Checks the generation /// /// Checks if the generation in the given GenerationalIndex does match what /// is allocated/store in the allocator fn match_generation(&self, index: &GenerationalIndex) -> bool { self.generations[&index.index()] == index.generation() } /// Allocates an index in the Generational mechanism fn allocate(&mut self, vec_len: usize) -> GenerationalIndex { if let Some(idx) = self.free.pop_front() { GenerationalIndex::new(idx, self.generations[&idx]) } else { self.generations.reserve(self.loan); self.generations.insert(vec_len, 0); self.free.reserve(self.loan); GenerationalIndex::new(vec_len, 0) } } /// Deallocates an index in the Generational mechanism fn deallocate(&mut self, index: GenerationalIndex) -> Result<(), Error> { if self.generations[&index.index()] == index.generation() { let x = self.generations.get_mut(&index.index()).unwrap(); self.free.push_back(index.index()); *x += 1; Ok(()) } else { Err(Error::WrongGeneration) } } /// Sets the loan /// /// Sets the loan strategy, or a simple value, to be used in reallocations /// during insertion. /// /// Default value on Allocator creation is set to 1. pub fn set_loan(&mut self, loan: usize) { self.loan = loan; } /// Returns the loan value /// /// Returns the loan value used in the loan strategy for reallocation pub fn loan(&self) -> usize { self.loan } } /// Light version of a Vec with Generational scheme /// /// LightVec is a lighter version of DenseVec, a Vec with a so-called /// Generational scheme, akin to the idea of versioning the indices to prevent /// use-after-free scenarions when using a given index. /// /// It is so called a lighter version due to the fact that the allocation of /// indices, i.e. the process that guarantees that indices are versioned, is /// placed outside the Vec itself. pub struct LightVec<T>(Vec<T>); impl<T> LightVec<T> { /// Creates a new Vec with the given capacity /// /// Creates a new Vec with the given capacity. It also creates an /// allocator, that is returned alongside the Vec itself. pub fn with_capacity(capacity: usize) -> (LightVec<T>, LightVecAllocator) { ( LightVec(Vec::with_capacity(capacity)), LightVecAllocator::with_capacity(capacity), ) } /// Returns a value with the given index /// /// # Examples /// /// ```{rust} /// use gvec::{lvec, LightVec, GenerationalIndex}; /// /// let (mut example, mut example_alloc, example_indices) = lvec![3; 1]; /// assert_eq!(example.get(&example_indices[0], &example_alloc), Some(&1)); /// ``` pub fn get(&self, index: &GenerationalIndex, allocator: &LightVecAllocator) -> Option<&T> { if allocator.match_generation(index) { self.0.get(index.index()) } else { None } } /// Inserts a value on the Vec /// /// If the Vec is full, it will reallocate itself (and the allocator) with /// the 'loan strategy' set on the allocator. If not altered, default loan /// strategy is set to 1. /// /// # Examples /// /// ```{rust} /// use gvec::LightVec; /// /// let (mut example, mut example_alloc) = LightVec::with_capacity(3); /// let idx = example.insert(1_f32, &mut example_alloc); /// assert_eq!(example.get(&idx, &example_alloc), Some(&1_f32)); /// ``` pub fn insert(&mut self, value: T, allocator: &mut LightVecAllocator) -> GenerationalIndex { let temp_idx = allocator.allocate(self.0.len()); self.0.insert(temp_idx.index(), value); temp_idx } /// Removes a value of the Vec /// /// Removes a value of the Vec with the given index. Index is checked /// before removal in order to guarantee that the index version is correct. /// Otherwise, returns an error. /// /// # Examples /// /// ```{rust} /// use gvec::LightVec; /// /// let (mut example, mut example_alloc) = LightVec::with_capacity(3); /// let idx = example.insert(1, &mut example_alloc); /// assert_eq!(example.remove(idx, &mut example_alloc), Ok(())); /// ``` pub fn remove( &mut self, index: GenerationalIndex, allocator: &mut LightVecAllocator, ) -> Result<(), Error> { if let Some(_val) = self.0.get(index.index()) { allocator.deallocate(index)?; self.0.remove(index.index()); Ok(()) } else { Err(Error::ElementNotFound) } } }