pubgrub/internal/
arena.rs

1use std::fmt;
2use std::hash::{Hash, Hasher};
3use std::marker::PhantomData;
4use std::ops::{Index, Range};
5
6type FnvIndexSet<V> = indexmap::IndexSet<V, rustc_hash::FxBuildHasher>;
7
8/// The index of a value allocated in an arena that holds `T`s.
9///
10/// The Clone, Copy and other traits are defined manually because
11/// deriving them adds some additional constraints on the `T` generic type
12/// that we actually don't need since it is phantom.
13///
14/// <https://github.com/rust-lang/rust/issues/26925>
15pub struct Id<T> {
16    raw: u32,
17    _ty: PhantomData<fn() -> T>,
18}
19
20impl<T> Clone for Id<T> {
21    fn clone(&self) -> Self {
22        *self
23    }
24}
25
26impl<T> Copy for Id<T> {}
27
28impl<T> PartialEq for Id<T> {
29    fn eq(&self, other: &Id<T>) -> bool {
30        self.raw == other.raw
31    }
32}
33
34impl<T> Eq for Id<T> {}
35
36impl<T> Hash for Id<T> {
37    fn hash<H: Hasher>(&self, state: &mut H) {
38        self.raw.hash(state)
39    }
40}
41
42impl<T> fmt::Debug for Id<T> {
43    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44        let mut type_name = std::any::type_name::<T>();
45        if let Some(id) = type_name.rfind(':') {
46            type_name = &type_name[id + 1..]
47        }
48        write!(f, "Id::<{}>({})", type_name, self.raw)
49    }
50}
51
52impl<T> Id<T> {
53    pub(crate) fn into_raw(self) -> usize {
54        self.raw as usize
55    }
56    fn from(n: u32) -> Self {
57        Self {
58            raw: n,
59            _ty: PhantomData,
60        }
61    }
62    pub(crate) fn range_to_iter(range: Range<Self>) -> impl Iterator<Item = Self> {
63        let start = range.start.raw;
64        let end = range.end.raw;
65        (start..end).map(Self::from)
66    }
67}
68
69/// Yet another index-based arena.
70///
71/// An arena is a kind of simple grow-only allocator, backed by a `Vec`
72/// where all items have the same lifetime, making it easier
73/// to have references between those items.
74/// They are all dropped at once when the arena is dropped.
75#[derive(Clone, PartialEq, Eq)]
76pub struct Arena<T> {
77    data: Vec<T>,
78}
79
80impl<T: fmt::Debug> fmt::Debug for Arena<T> {
81    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
82        fmt.debug_struct("Arena")
83            .field("len", &self.data.len())
84            .field("data", &self.data)
85            .finish()
86    }
87}
88
89impl<T> Default for Arena<T> {
90    fn default() -> Self {
91        Self::new()
92    }
93}
94
95impl<T> Arena<T> {
96    pub(crate) fn new() -> Self {
97        Self { data: Vec::new() }
98    }
99
100    pub(crate) fn alloc(&mut self, value: T) -> Id<T> {
101        let raw = self.data.len();
102        self.data.push(value);
103        Id::from(raw as u32)
104    }
105
106    pub(crate) fn alloc_iter<I: Iterator<Item = T>>(&mut self, values: I) -> Range<Id<T>> {
107        let start = Id::from(self.data.len() as u32);
108        values.for_each(|v| {
109            self.alloc(v);
110        });
111        let end = Id::from(self.data.len() as u32);
112        Range { start, end }
113    }
114}
115
116impl<T> Index<Id<T>> for Arena<T> {
117    type Output = T;
118    fn index(&self, id: Id<T>) -> &T {
119        &self.data[id.raw as usize]
120    }
121}
122
123impl<T> Index<Range<Id<T>>> for Arena<T> {
124    type Output = [T];
125    fn index(&self, id: Range<Id<T>>) -> &[T] {
126        &self.data[(id.start.raw as usize)..(id.end.raw as usize)]
127    }
128}
129
130/// Yet another index-based arena. This one de-duplicates entries by hashing.
131///
132/// An arena is a kind of simple grow-only allocator, backed by a `Vec`
133/// where all items have the same lifetime, making it easier
134/// to have references between those items.
135/// In this case the `Vec` is inside a `IndexSet` allowing fast lookup by value not just index.
136/// They are all dropped at once when the arena is dropped.
137#[derive(Clone, PartialEq, Eq)]
138pub struct HashArena<T: Hash + Eq> {
139    data: FnvIndexSet<T>,
140}
141
142impl<T: Hash + Eq + fmt::Debug> fmt::Debug for HashArena<T> {
143    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
144        fmt.debug_struct("Arena")
145            .field("len", &self.data.len())
146            .field("data", &self.data)
147            .finish()
148    }
149}
150
151impl<T: Hash + Eq> HashArena<T> {
152    pub fn new() -> Self {
153        Self::default()
154    }
155
156    pub fn alloc(&mut self, value: T) -> Id<T> {
157        let (raw, _) = self.data.insert_full(value);
158        Id::from(raw as u32)
159    }
160}
161
162impl<T: Hash + Eq> Default for HashArena<T> {
163    fn default() -> Self {
164        Self {
165            data: FnvIndexSet::default(),
166        }
167    }
168}
169
170impl<T: Hash + Eq> Index<Id<T>> for HashArena<T> {
171    type Output = T;
172    fn index(&self, id: Id<T>) -> &T {
173        &self.data[id.raw as usize]
174    }
175}
pubgrub/internal/arena.rs

pubgrub/internal/
arena.rs
