id_arena/lib.rs
1//! [](https://crates.io/crates/id-arena)
2//! [](https://crates.io/crates/id-arena)
3//! [](https://travis-ci.org/fitzgen/id-arena)
4//!
5//! A simple, id-based arena.
6//!
7//! ## Id-based
8//!
9//! Allocate objects and get an identifier for that object back, *not* a
10//! reference to the allocated object. Given an id, you can get a shared or
11//! exclusive reference to the allocated object from the arena. This id-based
12//! approach is useful for constructing mutable graph data structures.
13//!
14//! If you want allocation to return a reference, consider [the `typed-arena`
15//! crate](https://github.com/SimonSapin/rust-typed-arena/) instead.
16//!
17//! ## No Deletion
18//!
19//! This arena does not support deletion, which makes its implementation simple
20//! and allocation fast. If you want deletion, you need a way to solve the ABA
21//! problem. Consider using [the `generational-arena`
22//! crate](https://github.com/fitzgen/generational-arena) instead.
23//!
24//! ## Homogeneous
25//!
26//! This crate's arenas can only contain objects of a single type `T`. If you
27//! need an arena of objects with heterogeneous types, consider another crate.
28//!
29//! ## `#![no_std]` Support
30//!
31//! Requires the `alloc` nightly feature. Disable the on-by-default `"std"` feature:
32//!
33//! ```toml
34//! [dependencies.id-arena]
35//! version = "2"
36//! default-features = false
37//! ```
38//!
39//! ## `rayon` Support
40//!
41//! If the `rayon` feature of this crate is activated:
42//!
43//! ```toml
44//! [dependencies]
45//! id-arena = { version = "2", features = ["rayon"] }
46//! ```
47//!
48//! then you can use [`rayon`](https://crates.io/crates/rayon)'s support for
49//! parallel iteration. The `Arena` type will have a `par_iter` family of
50//! methods where appropriate.
51//!
52//! ## Example
53//!
54//! ```rust
55//! use id_arena::{Arena, Id};
56//!
57//! type AstNodeId = Id<AstNode>;
58//!
59//! #[derive(Debug, Eq, PartialEq)]
60//! pub enum AstNode {
61//! Const(i64),
62//! Var(String),
63//! Add {
64//! lhs: AstNodeId,
65//! rhs: AstNodeId,
66//! },
67//! Sub {
68//! lhs: AstNodeId,
69//! rhs: AstNodeId,
70//! },
71//! Mul {
72//! lhs: AstNodeId,
73//! rhs: AstNodeId,
74//! },
75//! Div {
76//! lhs: AstNodeId,
77//! rhs: AstNodeId,
78//! },
79//! }
80//!
81//! let mut ast_nodes = Arena::<AstNode>::new();
82//!
83//! // Create the AST for `a * (b + 3)`.
84//! let three = ast_nodes.alloc(AstNode::Const(3));
85//! let b = ast_nodes.alloc(AstNode::Var("b".into()));
86//! let b_plus_three = ast_nodes.alloc(AstNode::Add {
87//! lhs: b,
88//! rhs: three,
89//! });
90//! let a = ast_nodes.alloc(AstNode::Var("a".into()));
91//! let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul {
92//! lhs: a,
93//! rhs: b_plus_three,
94//! });
95//!
96//! // Can use indexing to access allocated nodes.
97//! assert_eq!(ast_nodes[three], AstNode::Const(3));
98//! ```
99
100#![forbid(unsafe_code)]
101#![deny(missing_debug_implementations)]
102#![deny(missing_docs)]
103// In no-std mode, use the alloc crate to get `Vec`.
104#![no_std]
105#![cfg_attr(not(feature = "std"), feature(alloc))]
106
107use core::cmp::Ordering;
108use core::fmt;
109use core::hash::{Hash, Hasher};
110use core::iter;
111use core::marker::PhantomData;
112use core::ops;
113use core::slice;
114use core::sync::atomic::{self, AtomicUsize, ATOMIC_USIZE_INIT};
115
116#[cfg(not(feature = "std"))]
117extern crate alloc;
118#[cfg(not(feature = "std"))]
119use alloc::vec::{self, Vec};
120
121#[cfg(feature = "std")]
122extern crate std;
123#[cfg(feature = "std")]
124use std::vec::{self, Vec};
125
126#[cfg(feature = "rayon")]
127mod rayon;
128#[cfg(feature = "rayon")]
129pub use rayon::*;
130
131/// A trait representing the implementation behavior of an arena and how
132/// identifiers are represented.
133///
134/// ## When should I implement `ArenaBehavior` myself?
135///
136/// Usually, you should just use `DefaultArenaBehavior`, which is simple and
137/// correct. However, there are some scenarios where you might want to implement
138/// `ArenaBehavior` yourself:
139///
140/// * **Space optimizations:** The default identifier is two words in size,
141/// which is larger than is usually necessary. For example, if you know that an
142/// arena *cannot* contain more than 256 items, you could make your own
143/// identifier type that stores the index as a `u8` and then you can save some
144/// space.
145///
146/// * **Trait Coherence:** If you need to implement an upstream crate's traits
147/// for identifiers, then defining your own identifier type allows you to work
148/// with trait coherence rules.
149///
150/// * **Share identifiers across arenas:** You can coordinate and share
151/// identifiers across different arenas to enable a "struct of arrays" style
152/// data representation.
153pub trait ArenaBehavior {
154 /// The identifier type.
155 type Id: Copy;
156
157 /// Construct a new object identifier from the given index and arena
158 /// identifier.
159 ///
160 /// ## Panics
161 ///
162 /// Implementations are allowed to panic if the given index is larger than
163 /// the underlying storage (e.g. the implementation uses a `u8` for storing
164 /// indices and the given index value is larger than 255).
165 fn new_id(arena_id: u32, index: usize) -> Self::Id;
166
167 /// Get the given identifier's index.
168 fn index(Self::Id) -> usize;
169
170 /// Get the given identifier's arena id.
171 fn arena_id(Self::Id) -> u32;
172
173 /// Construct a new arena identifier.
174 ///
175 /// This is used to disambiguate `Id`s across different arenas. To make
176 /// identifiers with the same index from different arenas compare false for
177 /// equality, return a unique `u32` on every invocation. This is the
178 /// default, provided implementation's behavior.
179 ///
180 /// To make identifiers with the same index from different arenas compare
181 /// true for equality, return the same `u32` on every invocation.
182 fn new_arena_id() -> u32 {
183 static ARENA_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
184 ARENA_COUNTER.fetch_add(1, atomic::Ordering::SeqCst) as u32
185 }
186}
187
188/// An identifier for an object allocated within an arena.
189pub struct Id<T> {
190 idx: usize,
191 arena_id: u32,
192 _ty: PhantomData<fn() -> T>,
193}
194
195impl<T> fmt::Debug for Id<T> {
196 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
197 f.debug_struct("Id").field("idx", &self.idx).finish()
198 }
199}
200
201impl<T> Copy for Id<T> {}
202
203impl<T> Clone for Id<T> {
204 #[inline]
205 fn clone(&self) -> Id<T> {
206 *self
207 }
208}
209
210impl<T> PartialEq for Id<T> {
211 #[inline]
212 fn eq(&self, rhs: &Self) -> bool {
213 self.arena_id == rhs.arena_id && self.idx == rhs.idx
214 }
215}
216
217impl<T> Eq for Id<T> {}
218
219impl<T> Hash for Id<T> {
220 #[inline]
221 fn hash<H: Hasher>(&self, h: &mut H) {
222 self.arena_id.hash(h);
223 self.idx.hash(h);
224 }
225}
226
227impl<T> PartialOrd for Id<T> {
228 fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
229 Some(self.cmp(rhs))
230 }
231}
232
233impl<T> Ord for Id<T> {
234 fn cmp(&self, rhs: &Self) -> Ordering {
235 self.arena_id
236 .cmp(&rhs.arena_id)
237 .then(self.idx.cmp(&rhs.idx))
238 }
239}
240
241impl<T> Id<T> {
242 /// Get the index within the arena that this id refers to.
243 #[inline]
244 pub fn index(&self) -> usize {
245 self.idx
246 }
247}
248
249/// The default `ArenaBehavior` implementation.
250#[derive(Clone, Debug, PartialEq, Eq)]
251pub struct DefaultArenaBehavior<T> {
252 _phantom: PhantomData<fn() -> T>,
253}
254
255impl<T> ArenaBehavior for DefaultArenaBehavior<T> {
256 type Id = Id<T>;
257
258 #[inline]
259 fn new_id(arena_id: u32, idx: usize) -> Self::Id {
260 Id {
261 idx,
262 arena_id,
263 _ty: PhantomData,
264 }
265 }
266
267 #[inline]
268 fn index(id: Self::Id) -> usize {
269 id.idx
270 }
271
272 #[inline]
273 fn arena_id(id: Self::Id) -> u32 {
274 id.arena_id
275 }
276}
277
278/// An arena of objects of type `T`.
279///
280/// ```
281/// use id_arena::Arena;
282///
283/// let mut arena = Arena::<&str>::new();
284///
285/// let a = arena.alloc("Albert");
286/// assert_eq!(arena[a], "Albert");
287///
288/// arena[a] = "Alice";
289/// assert_eq!(arena[a], "Alice");
290/// ```
291#[derive(Clone, Debug, PartialEq, Eq)]
292pub struct Arena<T, A = DefaultArenaBehavior<T>> {
293 arena_id: u32,
294 items: Vec<T>,
295 _phantom: PhantomData<fn() -> A>,
296}
297
298impl<T, A> Default for Arena<T, A>
299where
300 A: ArenaBehavior,
301{
302 #[inline]
303 fn default() -> Arena<T, A> {
304 Arena {
305 arena_id: A::new_arena_id(),
306 items: Vec::new(),
307 _phantom: PhantomData,
308 }
309 }
310}
311
312impl<T, A> Arena<T, A>
313where
314 A: ArenaBehavior,
315{
316 /// Construct a new, empty `Arena`.
317 ///
318 /// ```
319 /// use id_arena::Arena;
320 ///
321 /// let mut arena = Arena::<usize>::new();
322 /// arena.alloc(42);
323 /// ```
324 #[inline]
325 pub fn new() -> Arena<T, A> {
326 Default::default()
327 }
328
329 /// Construct a new, empty `Arena` with capacity for the given number of
330 /// elements.
331 ///
332 /// ```
333 /// use id_arena::Arena;
334 ///
335 /// let mut arena = Arena::<usize>::with_capacity(100);
336 /// for x in 0..100 {
337 /// arena.alloc(x * x);
338 /// }
339 /// ```
340 #[inline]
341 pub fn with_capacity(capacity: usize) -> Arena<T, A> {
342 Arena {
343 arena_id: A::new_arena_id(),
344 items: Vec::with_capacity(capacity),
345 _phantom: PhantomData,
346 }
347 }
348
349 /// Allocate `item` within this arena and return its id.
350 ///
351 /// ```
352 /// use id_arena::Arena;
353 ///
354 /// let mut arena = Arena::<usize>::new();
355 /// let _id = arena.alloc(42);
356 /// ```
357 ///
358 /// ## Panics
359 ///
360 /// Panics if the number of elements in the arena overflows a `usize` or
361 /// `Id`'s index storage representation.
362 #[inline]
363 pub fn alloc(&mut self, item: T) -> A::Id {
364 let id = self.next_id();
365 self.items.push(item);
366 id
367 }
368
369 /// Allocate an item with the id that it will be assigned.
370 ///
371 /// This is useful for structures that want to store their id as their own
372 /// member.
373 ///
374 /// ```
375 /// use id_arena::{Arena, Id};
376 ///
377 /// struct Cat {
378 /// id: Id<Cat>,
379 /// }
380 ///
381 /// let mut arena = Arena::<Cat>::new();
382 ///
383 /// let kitty = arena.alloc_with_id(|id| Cat { id });
384 /// assert_eq!(arena[kitty].id, kitty);
385 /// ```
386 #[inline]
387 pub fn alloc_with_id(&mut self, f: impl FnOnce(A::Id) -> T) -> A::Id {
388 let id = self.next_id();
389 let val = f(id);
390 self.alloc(val)
391 }
392
393 /// Get the id that will be used for the next item allocated into this
394 /// arena.
395 ///
396 /// If you are allocating a `struct` that wants to have its id as a member
397 /// of itself, prefer the less error-prone `Arena::alloc_with_id` method.
398 #[inline]
399 pub fn next_id(&self) -> A::Id {
400 let arena_id = self.arena_id;
401 let idx = self.items.len();
402 A::new_id(arena_id, idx)
403 }
404
405 /// Get a shared reference to the object associated with the given `id` if
406 /// it exists.
407 ///
408 /// If there is no object associated with `id` (for example, it might
409 /// reference an object allocated within a different arena) then return
410 /// `None`.
411 ///
412 /// ```
413 /// use id_arena::Arena;
414 ///
415 /// let mut arena = Arena::<usize>::new();
416 /// let id = arena.alloc(42);
417 /// assert!(arena.get(id).is_some());
418 ///
419 /// let other_arena = Arena::<usize>::new();
420 /// assert!(other_arena.get(id).is_none());
421 /// ```
422 #[inline]
423 pub fn get(&self, id: A::Id) -> Option<&T> {
424 if A::arena_id(id) != self.arena_id {
425 None
426 } else {
427 self.items.get(A::index(id))
428 }
429 }
430
431 /// Get an exclusive reference to the object associated with the given `id`
432 /// if it exists.
433 ///
434 /// If there is no object associated with `id` (for example, it might
435 /// reference an object allocated within a different arena) then return
436 /// `None`.
437 ///
438 /// ```
439 /// use id_arena::Arena;
440 ///
441 /// let mut arena = Arena::<usize>::new();
442 /// let id = arena.alloc(42);
443 /// assert!(arena.get_mut(id).is_some());
444 ///
445 /// let mut other_arena = Arena::<usize>::new();
446 /// assert!(other_arena.get_mut(id).is_none());
447 /// ```
448 #[inline]
449 pub fn get_mut(&mut self, id: A::Id) -> Option<&mut T> {
450 if A::arena_id(id) != self.arena_id {
451 None
452 } else {
453 self.items.get_mut(A::index(id))
454 }
455 }
456
457 /// Iterate over this arena's items and their ids.
458 ///
459 /// ```
460 /// use id_arena::Arena;
461 ///
462 /// let mut arena = Arena::<&str>::new();
463 ///
464 /// arena.alloc("hello");
465 /// arena.alloc("hi");
466 /// arena.alloc("yo");
467 ///
468 /// for (id, s) in arena.iter() {
469 /// assert_eq!(arena.get(id).unwrap(), s);
470 /// println!("{:?} -> {}", id, s);
471 /// }
472 /// ```
473 #[inline]
474 pub fn iter(&self) -> Iter<T, A> {
475 IntoIterator::into_iter(self)
476 }
477
478 /// Iterate over this arena's items and their ids, allowing mutation of each
479 /// item.
480 #[inline]
481 pub fn iter_mut(&mut self) -> IterMut<T, A> {
482 IntoIterator::into_iter(self)
483 }
484
485 /// Get the number of objects allocated in this arena.
486 ///
487 /// ```
488 /// use id_arena::Arena;
489 ///
490 /// let mut arena = Arena::<&str>::new();
491 ///
492 /// arena.alloc("hello");
493 /// arena.alloc("hi");
494 ///
495 /// assert_eq!(arena.len(), 2);
496 /// ```
497 #[inline]
498 pub fn len(&self) -> usize {
499 self.items.len()
500 }
501}
502
503impl<T, A> ops::Index<A::Id> for Arena<T, A>
504where
505 A: ArenaBehavior,
506{
507 type Output = T;
508
509 #[inline]
510 fn index(&self, id: A::Id) -> &T {
511 assert_eq!(self.arena_id, A::arena_id(id));
512 &self.items[A::index(id)]
513 }
514}
515
516impl<T, A> ops::IndexMut<A::Id> for Arena<T, A>
517where
518 A: ArenaBehavior,
519{
520 #[inline]
521 fn index_mut(&mut self, id: A::Id) -> &mut T {
522 assert_eq!(self.arena_id, A::arena_id(id));
523 &mut self.items[A::index(id)]
524 }
525}
526
527fn add_id<A, T>(item: Option<(usize, T)>, arena_id: u32) -> Option<(A::Id, T)>
528where
529 A: ArenaBehavior,
530{
531 item.map(|(idx, item)| (A::new_id(arena_id, idx), item))
532}
533
534/// An iterator over `(Id, &T)` pairs in an arena.
535///
536/// See [the `Arena::iter()` method](./struct.Arena.html#method.iter) for details.
537#[derive(Debug)]
538pub struct Iter<'a, T: 'a, A: 'a> {
539 arena_id: u32,
540 iter: iter::Enumerate<slice::Iter<'a, T>>,
541 _phantom: PhantomData<fn() -> A>,
542}
543
544impl<'a, T: 'a, A: 'a> Iterator for Iter<'a, T, A>
545where
546 A: ArenaBehavior,
547{
548 type Item = (A::Id, &'a T);
549
550 #[inline]
551 fn next(&mut self) -> Option<Self::Item> {
552 add_id::<A, _>(self.iter.next(), self.arena_id)
553 }
554
555 fn size_hint(&self) -> (usize, Option<usize>) {
556 self.iter.size_hint()
557 }
558}
559
560impl<'a, T: 'a, A: 'a> DoubleEndedIterator for Iter<'a, T, A>
561where
562 A: ArenaBehavior,
563{
564 fn next_back(&mut self) -> Option<Self::Item> {
565 add_id::<A, _>(self.iter.next_back(), self.arena_id)
566 }
567}
568
569impl<'a, T: 'a, A: 'a> ExactSizeIterator for Iter<'a, T, A>
570where
571 A: ArenaBehavior,
572{
573 fn len(&self) -> usize {
574 self.iter.len()
575 }
576}
577
578impl<'a, T, A> IntoIterator for &'a Arena<T, A>
579where
580 A: ArenaBehavior,
581{
582 type Item = (A::Id, &'a T);
583 type IntoIter = Iter<'a, T, A>;
584
585 #[inline]
586 fn into_iter(self) -> Iter<'a, T, A> {
587 Iter {
588 arena_id: self.arena_id,
589 iter: self.items.iter().enumerate(),
590 _phantom: PhantomData,
591 }
592 }
593}
594
595/// An iterator over `(Id, &mut T)` pairs in an arena.
596///
597/// See [the `Arena::iter_mut()` method](./struct.Arena.html#method.iter_mut)
598/// for details.
599#[derive(Debug)]
600pub struct IterMut<'a, T: 'a, A: 'a> {
601 arena_id: u32,
602 iter: iter::Enumerate<slice::IterMut<'a, T>>,
603 _phantom: PhantomData<fn() -> A>,
604}
605
606impl<'a, T: 'a, A: 'a> Iterator for IterMut<'a, T, A>
607where
608 A: ArenaBehavior,
609{
610 type Item = (A::Id, &'a mut T);
611
612 #[inline]
613 fn next(&mut self) -> Option<Self::Item> {
614 add_id::<A, _>(self.iter.next(), self.arena_id)
615 }
616
617 fn size_hint(&self) -> (usize, Option<usize>) {
618 self.iter.size_hint()
619 }
620}
621
622impl<'a, T: 'a, A: 'a> DoubleEndedIterator for IterMut<'a, T, A>
623where
624 A: ArenaBehavior,
625{
626 fn next_back(&mut self) -> Option<Self::Item> {
627 add_id::<A, _>(self.iter.next_back(), self.arena_id)
628 }
629}
630
631impl<'a, T: 'a, A: 'a> ExactSizeIterator for IterMut<'a, T, A>
632where
633 A: ArenaBehavior,
634{
635 fn len(&self) -> usize {
636 self.iter.len()
637 }
638}
639
640impl<'a, T, A> IntoIterator for &'a mut Arena<T, A>
641where
642 A: ArenaBehavior,
643{
644 type Item = (A::Id, &'a mut T);
645 type IntoIter = IterMut<'a, T, A>;
646
647 #[inline]
648 fn into_iter(self) -> IterMut<'a, T, A> {
649 IterMut {
650 arena_id: self.arena_id,
651 iter: self.items.iter_mut().enumerate(),
652 _phantom: PhantomData,
653 }
654 }
655}
656
657/// An iterator over `(Id, T)` pairs in an arena.
658#[derive(Debug)]
659pub struct IntoIter<T, A> {
660 arena_id: u32,
661 iter: iter::Enumerate<vec::IntoIter<T>>,
662 _phantom: PhantomData<fn() -> A>,
663}
664
665impl<T, A> Iterator for IntoIter<T, A>
666where
667 A: ArenaBehavior,
668{
669 type Item = (A::Id, T);
670
671 #[inline]
672 fn next(&mut self) -> Option<Self::Item> {
673 add_id::<A, _>(self.iter.next(), self.arena_id)
674 }
675
676 fn size_hint(&self) -> (usize, Option<usize>) {
677 self.iter.size_hint()
678 }
679}
680
681impl<T, A> DoubleEndedIterator for IntoIter<T, A>
682where
683 A: ArenaBehavior,
684{
685 fn next_back(&mut self) -> Option<Self::Item> {
686 add_id::<A, _>(self.iter.next_back(), self.arena_id)
687 }
688}
689
690impl<T, A> ExactSizeIterator for IntoIter<T, A>
691where
692 A: ArenaBehavior,
693{
694 fn len(&self) -> usize {
695 self.iter.len()
696 }
697}
698
699impl<T, A> IntoIterator for Arena<T, A>
700where
701 A: ArenaBehavior,
702{
703 type Item = (A::Id, T);
704 type IntoIter = IntoIter<T, A>;
705
706 #[inline]
707 fn into_iter(self) -> IntoIter<T, A> {
708 IntoIter {
709 arena_id: self.arena_id,
710 iter: self.items.into_iter().enumerate(),
711 _phantom: PhantomData,
712 }
713 }
714}
715
716#[cfg(test)]
717mod tests {
718 use super::*;
719
720 #[test]
721 fn ids_are_send_sync() {
722 fn assert_send_sync<T: Send + Sync>() {}
723 struct Foo;
724 assert_send_sync::<Id<Foo>>();
725 }
726}