[−][src]Module pui_arena::base::hop
Hop Arenas - Fast Access, Fast Iteration, Slow Mutation, Small memory footprint
A hop arena has a minimal footprint, it stores a doubly-linked-list of empty
slots embeded in the same location as the values, so as long as the size
of you values is greater than or equal to [usize; 3]
, then there is no memory
overhead. This doubly-linked-list of empty slots means that insertion and deletion
are O(1)
operations.
This doubly-linked-list also encodes just enough inforation to about vacant slots that you can skip over all contiguous vacant slots in one go while iterating. This means if there are large blocks of vacant slots, a hop arena will efficiently jump over the entire block in one go.
While this method of iteration is faster than sparse arenas, it still can't compare to dense arenas. However, hop arenas are more memory efficient than dense arenas.
Each slot is versioned by using Version
trait. See Version
for docs
on version exhaustion. Once a slot's version exhausts, it will not be pushed
onto the doubly-linked list. This prevents it from ever being used again.
Structs
Arena | A hop arena |
Drain | Returned by |
DrainFilter | Returned by |
Entries | Returned by |
EntriesMut | Returned by |
IntoEntries | Returned by |
IntoIter | Returned by |
Iter | Returned by |
IterMut | Returned by |
Keys | Returned by |
VacantEntry | An empty slot in a hop arena |