veloren_common/
depot.rs

1use serde::{Deserialize, Serialize};
2use std::{
3    cmp::{Eq, Ord, PartialEq, PartialOrd},
4    fmt,
5    marker::PhantomData,
6};
7
8/// Type safe index into Depot
9#[derive(Deserialize, Serialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub struct Id<T> {
11    idx: u32,
12    gen: u32,
13    phantom: PhantomData<T>,
14}
15
16impl<T> Id<T> {
17    pub fn id(&self) -> u64 { self.idx as u64 | ((self.gen as u64) << 32) }
18}
19
20impl<T> fmt::Debug for Id<T> {
21    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
22        write!(
23            f,
24            "Id<{}>({}, {})",
25            std::any::type_name::<T>(),
26            self.idx,
27            self.gen
28        )
29    }
30}
31
32struct Entry<T> {
33    gen: u32,
34    item: Option<T>,
35}
36
37/// A general-purpose high performance allocator, basically Vec with type safe
38/// indices (Id)
39pub struct Depot<T> {
40    entries: Vec<Entry<T>>,
41    len: usize,
42}
43
44impl<T> Default for Depot<T> {
45    fn default() -> Self {
46        Self {
47            entries: Vec::new(),
48            len: 0,
49        }
50    }
51}
52
53impl<T> Depot<T> {
54    pub fn is_empty(&self) -> bool { self.len == 0 }
55
56    pub fn len(&self) -> usize { self.len }
57
58    pub fn contains(&self, id: Id<T>) -> bool {
59        self.entries
60            .get(id.idx as usize)
61            .map(|e| e.gen == id.gen && e.item.is_some())
62            .unwrap_or(false)
63    }
64
65    pub fn get(&self, id: Id<T>) -> Option<&T> {
66        if let Some(entry) = self.entries.get(id.idx as usize) {
67            if entry.gen == id.gen {
68                entry.item.as_ref()
69            } else {
70                None
71            }
72        } else {
73            None
74        }
75    }
76
77    pub fn get_mut(&mut self, id: Id<T>) -> Option<&mut T> {
78        if let Some(entry) = self.entries.get_mut(id.idx as usize) {
79            if entry.gen == id.gen {
80                entry.item.as_mut()
81            } else {
82                None
83            }
84        } else {
85            None
86        }
87    }
88
89    pub fn ids(&self) -> impl Iterator<Item = Id<T>> + '_ { self.iter().map(|(id, _)| id) }
90
91    pub fn values(&self) -> impl Iterator<Item = &T> + '_ { self.iter().map(|(_, item)| item) }
92
93    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> + '_ {
94        self.iter_mut().map(|(_, item)| item)
95    }
96
97    pub fn iter(&self) -> impl Iterator<Item = (Id<T>, &T)> + '_ {
98        self.entries
99            .iter()
100            .enumerate()
101            .filter_map(move |(idx, entry)| {
102                Some(Id {
103                    idx: idx as u32,
104                    gen: entry.gen,
105                    phantom: PhantomData,
106                })
107                .zip(entry.item.as_ref())
108            })
109    }
110
111    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Id<T>, &mut T)> + '_ {
112        self.entries
113            .iter_mut()
114            .enumerate()
115            .filter_map(move |(idx, entry)| {
116                Some(Id {
117                    idx: idx as u32,
118                    gen: entry.gen,
119                    phantom: PhantomData,
120                })
121                .zip(entry.item.as_mut())
122            })
123    }
124
125    pub fn insert(&mut self, item: T) -> Id<T> {
126        if self.len < self.entries.len() {
127            // TODO: Make this more efficient with a lookahead system
128            let (idx, entry) = self
129                .entries
130                .iter_mut()
131                .enumerate()
132                .find(|(_, e)| e.item.is_none())
133                .unwrap();
134            entry.item = Some(item);
135            assert!(entry.gen < u32::MAX);
136            entry.gen += 1;
137            self.len += 1;
138            Id {
139                idx: idx as u32,
140                gen: entry.gen,
141                phantom: PhantomData,
142            }
143        } else {
144            assert!(self.entries.len() < (u32::MAX - 1) as usize);
145            let id = Id {
146                idx: self.entries.len() as u32,
147                gen: 0,
148                phantom: PhantomData,
149            };
150            self.entries.push(Entry {
151                gen: 0,
152                item: Some(item),
153            });
154            self.len += 1;
155            id
156        }
157    }
158
159    pub fn remove(&mut self, id: Id<T>) -> Option<T> {
160        if let Some(item) = self
161            .entries
162            .get_mut(id.idx as usize)
163            .and_then(|e| if e.gen == id.gen { e.item.take() } else { None })
164        {
165            self.len -= 1;
166            Some(item)
167        } else {
168            None
169        }
170    }
171
172    pub fn recreate_id(&self, i: u64) -> Option<Id<T>> {
173        if i as usize >= self.entries.len() {
174            None
175        } else {
176            Some(Id {
177                idx: i as u32,
178                gen: self
179                    .entries
180                    .get(i as usize)
181                    .map(|e| e.gen)
182                    .unwrap_or_default(),
183                phantom: PhantomData,
184            })
185        }
186    }
187}
veloren_common/depot.rs

veloren_common/
depot.rs
