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
use crate::{Error, GenerationalIndex};
use std::collections::{HashMap, VecDeque};
use std::ops::Index;

/// A Generational vector
///
/// A vector with a so-called Generational scheme, akin to a versioning scheme,
/// for its indices. This is done in order to prevent use-after-free scenarios,
/// where an attempt to access a specific position with a given index is denied
/// after the original item is removed and its position (or index) has been
/// freed. It also promotes memory reuse, since the memory allocated is not
/// released until the vector goes out of scope or the program ends, and it
/// _might_ lead to lower overall memory use.
///
/// ## Note
///
/// Due to the functionality of avoiding invalid access (use-after-free), this
/// type of vector consumes *much more* memory than a simple vector itself.
pub struct DenseVec<T> {
    vec: Vec<T>,
    free: VecDeque<usize>,
    generations: HashMap<usize, usize>,
}

impl<T> DenseVec<T> {
    /// Creates a GenVec with a specific capacity
    ///
    /// Creates a GenerationalVec with a pre-allocated memory in order to
    /// reduce the overhead of future reallocations.
    pub fn with_capacity(capacity: usize) -> DenseVec<T> {
        let mut temp_deque = VecDeque::with_capacity(capacity);
        let mut temp_map = HashMap::with_capacity(capacity);
        let temp_vec: Vec<T> = Vec::with_capacity(capacity);
        for i in 0..capacity {
            temp_deque.push_back(i);
            temp_map.insert(i, 0);
        }
        DenseVec {
            vec: temp_vec,
            free: temp_deque,
            generations: temp_map,
        }
    }

    /// Get a value by an index
    ///
    /// Returns the value if both the index and the generation do match.
    /// Otherwise returns None. A safe alternative to the index [] operator,
    /// which can panic if index out-of-bounds or generation does not match.
    pub fn get(&self, index: GenerationalIndex) -> Option<&T> {
        if self.generations[&index.index()] == index.generation() {
            self.vec.get(index.index())
        } else {
            None
        }
    }

    /// Insert a value on the vector
    ///
    /// Returns a GenerationalIndex with the index and the generation in which
    /// it was added.
    ///
    /// # Example
    ///
    /// ```
    /// use gvec::DenseVec as GenVec;
    ///
    /// let mut example = GenVec::with_capacity(2);
    /// let first = example.insert(2);
    /// assert_eq!(example[first], 2);
    /// ```
    pub fn insert(&mut self, value: T) -> GenerationalIndex {
        if let Some(idx) = self.free.pop_front() {
            self.vec.insert(idx, value);
            GenerationalIndex::new(idx, self.generations[&idx])
        } else {
            let vec_len = self.vec.len();
            self.generations.reserve(1);
            self.generations.insert(vec_len, 0);
            self.vec.push(value);
            self.free.reserve(1);
            GenerationalIndex::new(vec_len, 0)
        }
    }

    /// Remove a value of the vector by a given index
    ///
    /// Upon the removal of the value, the index is liberated for use, in order
    /// to reuse the space already allocated, and the generation is upped by
    /// one, in order to prevent use-after-free scenarios or "address
    /// violation" (access another value allocated in the same space (i.e. same
    /// index), but with a different generation)
    ///
    /// # Example
    ///
    /// ```,rust,should_panic
    /// use gvec::DenseVec as GenVec;
    ///
    /// let mut example = GenVec::with_capacity(2);
    /// let first = example.insert(1);
    /// assert_eq!(example[first], 1);
    /// example.remove(first);
    /// assert_eq!(example[first], 1); // produces a panic!
    /// ```
    pub fn remove(&mut self, index: GenerationalIndex) -> Result<(), Error> {
        if let Some(_val) = self.vec.get(index.index()) {
            if self.generations[&index.index()] == index.generation() {
                let x = self.generations.get_mut(&index.index()).unwrap();
                self.vec.remove(index.index());
                self.free.push_back(index.index());
                *x += 1;
                Ok(())
            } else {
                Err(Error::WrongGeneration)
            }
        } else {
            Err(Error::ElementNotFound)
        }
    }

    // Both these methods do need to be changed in order to avoid problems with
    // enumeration and Generation management, since the Enumerate struct
    // manages its own counter
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.vec.iter()
    }
}

impl<T> IntoIterator for DenseVec<T> {
    type Item = T;
    type IntoIter = ::std::vec::IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        self.vec.into_iter()
    }
}

impl<T> Index<GenerationalIndex> for DenseVec<T> {
    type Output = T;

    /// # Panics
    ///
    /// Indexing will panic! when the generation of the given index does not
    /// match the generation in the vector. Use ```GenVec::get()``` instead
    /// as a non-panic version that will return an Option.
    fn index(&self, index: GenerationalIndex) -> &Self::Output {
        if self.generations[&index.index()] == index.generation() {
            &self.vec[index.index()]
        } else {
            panic!(format!(
                "Generation does not match!
                Index generation: \u{1b}[38:5:1m{}
                Current generation: \u{1b}[38:5:4m{}\n",
                index.generation(),
                self.generations[&index.index()]
            ))
        }
    }
}