fyrox_core/
sparse.rs

1// Copyright (c) 2019-present Dmitry Stepanov and Fyrox Engine contributors.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19// SOFTWARE.
20
21use std::{
22    fmt::Debug,
23    sync::atomic::{AtomicUsize, Ordering},
24};
25
26#[derive(Debug)]
27pub struct AtomicIndex {
28    index: AtomicUsize,
29}
30
31impl Clone for AtomicIndex {
32    fn clone(&self) -> Self {
33        Self {
34            index: AtomicUsize::new(self.index.load(Ordering::SeqCst)),
35        }
36    }
37}
38
39impl Default for AtomicIndex {
40    fn default() -> Self {
41        Self::unassigned()
42    }
43}
44
45impl AtomicIndex {
46    pub const UNASSIGNED_INDEX: usize = usize::MAX;
47
48    pub fn unassigned() -> Self {
49        Self {
50            index: AtomicUsize::new(Self::UNASSIGNED_INDEX),
51        }
52    }
53
54    fn new(index: usize) -> Self {
55        Self {
56            index: AtomicUsize::new(index),
57        }
58    }
59
60    pub fn set(&self, index: usize) {
61        self.index.store(index, Ordering::SeqCst)
62    }
63
64    pub fn get(&self) -> usize {
65        self.index.load(Ordering::SeqCst)
66    }
67}
68
69pub struct SparseBuffer<T> {
70    vec: Vec<Option<T>>,
71    free: Vec<usize>,
72}
73
74impl<T> Default for SparseBuffer<T> {
75    fn default() -> Self {
76        Self {
77            vec: Default::default(),
78            free: Default::default(),
79        }
80    }
81}
82
83impl<T: Clone> Clone for SparseBuffer<T> {
84    fn clone(&self) -> Self {
85        Self {
86            vec: self.vec.clone(),
87            free: self.free.clone(),
88        }
89    }
90}
91
92impl<T> SparseBuffer<T> {
93    pub fn with_capacity(capacity: usize) -> Self {
94        Self {
95            vec: Vec::with_capacity(capacity),
96            free: vec![],
97        }
98    }
99
100    pub fn spawn(&mut self, payload: T) -> AtomicIndex {
101        match self.free.pop() {
102            Some(free) => {
103                let old = self.vec[free].replace(payload);
104                debug_assert!(old.is_none());
105                AtomicIndex::new(free)
106            }
107            None => {
108                let index = AtomicIndex::new(self.vec.len());
109                self.vec.push(Some(payload));
110                index
111            }
112        }
113    }
114
115    pub fn free(&mut self, index: &AtomicIndex) -> Option<T> {
116        self.free_raw(index.get())
117    }
118
119    pub fn free_raw(&mut self, index: usize) -> Option<T> {
120        match self.vec.get_mut(index) {
121            Some(entry) => match entry.take() {
122                Some(payload) => {
123                    self.free.push(index);
124                    Some(payload)
125                }
126                None => None,
127            },
128            None => None,
129        }
130    }
131
132    pub fn len(&self) -> usize {
133        self.vec.len()
134    }
135
136    pub fn is_empty(&self) -> bool {
137        self.filled() == 0
138    }
139
140    pub fn filled(&self) -> usize {
141        self.vec.len() - self.free.len()
142    }
143
144    pub fn is_index_valid(&self, index: &AtomicIndex) -> bool {
145        self.get(index).is_some()
146    }
147
148    pub fn get(&self, index: &AtomicIndex) -> Option<&T> {
149        self.get_raw(index.get())
150    }
151
152    pub fn get_mut(&mut self, index: &AtomicIndex) -> Option<&mut T> {
153        self.get_mut_raw(index.get())
154    }
155
156    pub fn get_raw(&self, index: usize) -> Option<&T> {
157        self.vec.get(index).and_then(|entry| entry.as_ref())
158    }
159
160    pub fn get_mut_raw(&mut self, index: usize) -> Option<&mut T> {
161        self.vec.get_mut(index).and_then(|entry| entry.as_mut())
162    }
163
164    pub fn iter(&self) -> impl Iterator<Item = &T> {
165        self.vec.iter().filter_map(|entry| entry.as_ref())
166    }
167
168    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
169        self.vec.iter_mut().filter_map(|entry| entry.as_mut())
170    }
171
172    pub fn clear(&mut self) {
173        self.vec.clear();
174        self.free.clear();
175    }
176}
177
178#[cfg(test)]
179mod test {
180
181    use super::*;
182
183    #[test]
184    fn atomic_index_get() {
185        let ai = AtomicIndex::new(42);
186        assert_eq!(ai.get(), 42);
187    }
188
189    #[test]
190    fn atomic_index_unassigned() {
191        let ai = AtomicIndex::unassigned();
192        assert_eq!(ai.get(), usize::MAX);
193    }
194
195    #[test]
196    fn atomic_index_new() {
197        let ai = AtomicIndex::new(42);
198        assert_eq!(ai.get(), 42);
199    }
200
201    #[test]
202    fn atomic_index_set() {
203        let ai = AtomicIndex::new(42);
204        assert_eq!(ai.get(), 42);
205
206        ai.set(1);
207        assert_eq!(ai.get(), 1);
208    }
209
210    #[test]
211    fn default_for_atomic_index() {
212        let mut ai = AtomicIndex::default();
213        assert_eq!(ai.index.get_mut(), &usize::MAX);
214    }
215
216    #[test]
217    fn clone_for_atomic_index() {
218        let ai = AtomicIndex::default();
219        let ai2 = ai.clone();
220        assert_eq!(ai2.get(), usize::MAX);
221    }
222
223    #[test]
224    fn default_for_sparse_buffer() {
225        let sb = SparseBuffer::<f32>::default();
226
227        assert_eq!(sb.vec, Vec::<Option<f32>>::default());
228        assert_eq!(sb.free, Vec::<usize>::default());
229    }
230
231    #[test]
232    fn clone_for_sparse_buffer() {
233        let sb = SparseBuffer::<f32>::default();
234        let sb2 = sb.clone();
235
236        assert_eq!(sb.vec, sb2.vec);
237        assert_eq!(sb.free, sb2.free);
238    }
239
240    #[test]
241    fn sparse_buffer_with_capacity() {
242        let sb = SparseBuffer::<f32>::with_capacity(10);
243
244        assert_eq!(sb.vec, Vec::with_capacity(10));
245        assert_eq!(sb.free, vec![]);
246    }
247
248    #[test]
249    fn sparse_buffer_len() {
250        let sb = SparseBuffer::<f32>::default();
251
252        assert_eq!(sb.len(), 0);
253    }
254
255    #[test]
256    fn sparse_buffer_filled() {
257        let sb = SparseBuffer {
258            vec: vec![None, Some(1)],
259            free: vec![],
260        };
261
262        assert_eq!(sb.filled(), 2);
263    }
264
265    #[test]
266    fn sparse_buffer_is_empty() {
267        let sb = SparseBuffer::<f32>::default();
268
269        assert!(sb.is_empty());
270
271        let sb = SparseBuffer {
272            vec: vec![None, Some(1)],
273            free: vec![],
274        };
275        assert!(!sb.is_empty());
276    }
277
278    #[test]
279    fn sparse_buffer_is_index_valid() {
280        let sb = SparseBuffer {
281            vec: vec![None, Some(1)],
282            free: vec![],
283        };
284
285        assert!(!sb.is_index_valid(&AtomicIndex::new(0)));
286        assert!(sb.is_index_valid(&AtomicIndex::new(1)));
287    }
288
289    #[test]
290    fn sparse_buffer_get_raw() {
291        let sb = SparseBuffer {
292            vec: vec![None, Some(1)],
293            free: vec![],
294        };
295
296        assert_eq!(sb.get_raw(0), None);
297        assert_eq!(sb.get_raw(1), Some(&1));
298    }
299
300    #[test]
301    fn sparse_buffer_get_mut_raw() {
302        let mut sb = SparseBuffer {
303            vec: vec![None, Some(1)],
304            free: vec![],
305        };
306
307        assert_eq!(sb.get_mut_raw(0), None);
308        assert_eq!(sb.get_mut_raw(1), Some(&mut 1));
309    }
310
311    #[test]
312    fn sparse_buffer_get() {
313        let sb = SparseBuffer {
314            vec: vec![None, Some(1)],
315            free: vec![],
316        };
317
318        assert_eq!(sb.get(&AtomicIndex::new(0)), None);
319        assert_eq!(sb.get(&AtomicIndex::new(1)), Some(&1));
320    }
321
322    #[test]
323    fn sparse_buffer_get_mut() {
324        let mut sb = SparseBuffer {
325            vec: vec![None, Some(1)],
326            free: vec![],
327        };
328
329        assert_eq!(sb.get_mut(&AtomicIndex::new(0)), None);
330        assert_eq!(sb.get_mut(&AtomicIndex::new(1)), Some(&mut 1));
331    }
332
333    #[test]
334    fn sparse_buffer_iter() {
335        let sb = SparseBuffer {
336            vec: vec![None, Some(1)],
337            free: vec![],
338        };
339
340        assert!(sb.iter().eq([&1]));
341    }
342
343    #[test]
344    fn sparse_buffer_iter_mut() {
345        let mut sb = SparseBuffer {
346            vec: vec![None, Some(1)],
347            free: vec![],
348        };
349
350        assert!(sb.iter_mut().eq([&mut 1]));
351    }
352
353    #[test]
354    fn sparse_buffer_clear() {
355        let mut sb = SparseBuffer {
356            vec: vec![None, Some(1)],
357            free: vec![1, 2],
358        };
359
360        sb.clear();
361        assert!(sb.vec.is_empty());
362        assert!(sb.free.is_empty());
363    }
364
365    #[test]
366    fn sparse_buffer_free_raw() {
367        let mut sb = SparseBuffer {
368            vec: vec![None, Some(1)],
369            free: vec![],
370        };
371
372        assert_eq!(sb.free_raw(42), None);
373        assert_eq!(sb.free_raw(0), None);
374        assert_eq!(sb.free_raw(1), Some(1));
375        assert_eq!(sb.vec, vec![None, None]);
376        assert_eq!(sb.free, vec![1]);
377    }
378
379    #[test]
380    fn sparse_buffer_free() {
381        let mut sb = SparseBuffer {
382            vec: vec![None, Some(1)],
383            free: vec![],
384        };
385
386        assert_eq!(sb.free(&AtomicIndex::new(0)), None);
387        assert_eq!(sb.free(&AtomicIndex::new(1)), Some(1));
388        assert_eq!(sb.vec, vec![None, None]);
389        assert_eq!(sb.free, vec![1]);
390    }
391
392    #[test]
393    fn sparse_buffer_spawn() {
394        let mut sb = SparseBuffer {
395            vec: vec![None, Some(1)],
396            free: vec![0],
397        };
398
399        assert_eq!(sb.spawn(42).get(), 0);
400        assert_eq!(sb.vec, vec![Some(42), Some(1)]);
401        assert_eq!(sb.free, vec![]);
402
403        assert_eq!(sb.spawn(5).get(), 2);
404        assert_eq!(sb.vec, vec![Some(42), Some(1), Some(5)]);
405        assert_eq!(sb.free, vec![]);
406    }
407}
fyrox_core/sparse.rs

fyrox_core/
sparse.rs
