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

use crate::{
    id::{Id, Marker},
    lock::{rank, Mutex},
    Epoch, Index,
};
use std::{fmt::Debug, marker::PhantomData};

#[derive(Copy, Clone, Debug, PartialEq)]
enum IdSource {
    External,
    Allocated,
    None,
}

/// A simple structure to allocate [`Id`] identifiers.
///
/// Calling [`alloc`] returns a fresh, never-before-seen id. Calling [`release`]
/// marks an id as dead; it will never be returned again by `alloc`.
///
/// `IdentityValues` returns `Id`s whose index values are suitable for use as
/// indices into a `Vec<T>` that holds those ids' referents:
///
/// - Every live id has a distinct index value. Every live id's index
///   selects a distinct element in the vector.
///
/// - `IdentityValues` prefers low index numbers. If you size your vector to
///   accommodate the indices produced here, the vector's length will reflect
///   the highwater mark of actual occupancy.
///
/// - `IdentityValues` reuses the index values of freed ids before returning
///   ids with new index values. Freed vector entries get reused.
///
/// [`Id`]: crate::id::Id
/// [`Backend`]: wgt::Backend;
/// [`alloc`]: IdentityValues::alloc
/// [`release`]: IdentityValues::release
#[derive(Debug)]
pub(super) struct IdentityValues {
    free: Vec<(Index, Epoch)>,
    next_index: Index,
    count: usize,
    // Sanity check: The allocation logic works under the assumption that we don't
    // do a mix of allocating ids from here and providing ids manually for the same
    // storage container.
    id_source: IdSource,
}

impl IdentityValues {
    /// Allocate a fresh, never-before-seen id with the given `backend`.
    ///
    /// The backend is incorporated into the id, so that ids allocated with
    /// different `backend` values are always distinct.
    pub fn alloc<T: Marker>(&mut self) -> Id<T> {
        assert!(
            self.id_source != IdSource::External,
            "Mix of internally allocated and externally provided IDs"
        );
        self.id_source = IdSource::Allocated;

        self.count += 1;
        match self.free.pop() {
            Some((index, epoch)) => Id::zip(index, epoch + 1),
            None => {
                let index = self.next_index;
                self.next_index += 1;
                let epoch = 1;
                Id::zip(index, epoch)
            }
        }
    }

    pub fn mark_as_used<T: Marker>(&mut self, id: Id<T>) -> Id<T> {
        assert!(
            self.id_source != IdSource::Allocated,
            "Mix of internally allocated and externally provided IDs"
        );
        self.id_source = IdSource::External;

        self.count += 1;
        id
    }

    /// Free `id`. It will never be returned from `alloc` again.
    pub fn release<T: Marker>(&mut self, id: Id<T>) {
        if let IdSource::Allocated = self.id_source {
            let (index, epoch) = id.unzip();
            self.free.push((index, epoch));
        }
        self.count -= 1;
    }

    pub fn count(&self) -> usize {
        self.count
    }
}

#[derive(Debug)]
pub struct IdentityManager<T: Marker> {
    pub(super) values: Mutex<IdentityValues>,
    _phantom: PhantomData<T>,
}

impl<T: Marker> IdentityManager<T> {
    pub fn process(&self) -> Id<T> {
        self.values.lock().alloc()
    }
    pub fn mark_as_used(&self, id: Id<T>) -> Id<T> {
        self.values.lock().mark_as_used(id)
    }
    pub fn free(&self, id: Id<T>) {
        self.values.lock().release(id)
    }
}

impl<T: Marker> IdentityManager<T> {
    pub fn new() -> Self {
        Self {
            values: Mutex::new(
                rank::IDENTITY_MANAGER_VALUES,
                IdentityValues {
                    free: Vec::new(),
                    next_index: 0,
                    count: 0,
                    id_source: IdSource::None,
                },
            ),
            _phantom: PhantomData,
        }
    }
}

#[test]
fn test_epoch_end_of_life() {
    use crate::id;
    let man = IdentityManager::<id::markers::Buffer>::new();
    let id1 = man.process();
    assert_eq!(id1.unzip(), (0, 1));
    man.free(id1);
    let id2 = man.process();
    // confirm that the epoch 1 is no longer re-used
    assert_eq!(id2.unzip(), (0, 2));
}