stable_id/
eids.rs

1use std::mem;
2
3use stable_id_traits::{Maximum, Predecessor, Successor};
4
5use crate::Eids;
6
7impl<IndexT> Eids<IndexT>
8where
9    IndexT: Successor + Predecessor + Clone + Copy + Ord + Maximum,
10{
11    pub fn claim(&mut self) -> IndexT {
12        assert!(
13            self.next < IndexT::max_value(),
14            "storing more items than you can address"
15        );
16
17        self.freed
18            .iter()
19            .next()
20            .cloned()
21            .map(|id| {
22                // found an id in the free list, return it
23                let is_removed = self.freed.remove(&id);
24                debug_assert!(is_removed, "freeing something not in the database");
25                id
26            })
27            .unwrap_or_else(|| {
28                // otherwise increment the id and return it
29                let next = self.next.next_value();
30                mem::replace(&mut self.next, next)
31            })
32    }
33
34    pub fn unclaim(&mut self, val: IndexT) {
35        assert!(val < self.next, "not a valid entity");
36
37        let is_double_inserted = self.freed.insert(val);
38        debug_assert!(is_double_inserted, "double-freeing entity")
39    }
40
41    /**
42        Pack up recycled ids from the freed list while you deal with the change through `f(old_id, new_id)`.
43
44        ```
45        use stable_id::Eids;
46
47        let mut entities: Eids<u8> = Default::default();
48        (0..255).for_each(|i| {
49            assert_eq!(entities.claim(), i);
50        });
51
52        entities.unclaim(27);
53        entities.unclaim(15);
54
55        // free up 254 to 251, so that coalescing would be 15 & 27 to takeover 249, 250
56        entities.unclaim(254);
57        entities.unclaim(252);
58        entities.unclaim(251);
59        entities.unclaim(253);
60
61        let mut records_old = Vec::new();
62        let mut records_new = Vec::new();
63
64        entities.coalesce(|old_id, new_id| {
65            records_old.push(old_id);
66            records_new.push(new_id);
67
68            // update all data that reference the old_id and replace them with new_id
69        });
70
71        assert_eq!(records_old, [250,249]); // reclaiming from the last-issued
72        assert_eq!(records_new, [27,15]); // note: larger ids come first
73        ```
74    */
75    pub fn coalesce<F>(&mut self, mut f: F)
76    where
77        F: FnMut(IndexT, IndexT),
78    {
79        if self.freed.is_empty() {
80            return;
81        }
82
83        while let Some(freed) = self.freed.pop_last() {
84            let target = self.next.prev_value();
85            self.next = target;
86
87            if target != freed {
88                f(target, freed);
89            }
90        }
91    }
92}
93
94#[cfg(test)]
95mod eid_tests {
96    use super::Eids;
97
98    #[test]
99    fn claim_ids() {
100        let mut entities: Eids<u8> = Default::default();
101        for i in 0..100 {
102            let id = entities.claim();
103            assert_eq!(id, i);
104        }
105
106        fn is_multiple_of_3(i: &u8) -> bool {
107            i % 3 == 0
108        }
109
110        (0..60u8)
111            .filter(is_multiple_of_3)
112            .for_each(|i| entities.unclaim(i));
113
114        (0..60u8)
115            .filter(is_multiple_of_3)
116            .all(|i| entities.claim() == i);
117    }
118
119    #[test]
120    #[should_panic]
121    fn unclaim_invalid() {
122        let mut entities: Eids<u8> = Default::default();
123        entities.unclaim(123u8)
124    }
125
126    #[test]
127    #[should_panic]
128    fn double_free() {
129        let mut entities: Eids<u8> = Default::default();
130        let id = entities.claim();
131        entities.unclaim(id);
132        entities.unclaim(id);
133    }
134
135    #[test]
136    #[should_panic]
137    fn claim_over_max() {
138        let mut entities: Eids<u8> = Default::default();
139        (0..257).for_each(|_| {
140            entities.claim();
141        });
142    }
143}
stable_id/eids.rs

stable_id/
eids.rs
