[−][src]Crate pour
pour
pour
is an implementation of an immutable IdMap
: it maps bitvector IDs to values using a radix trie.
Since these IdMap
s are immutable, they can share a lot of data between them, and hash-consing can be used to increase the
degree of sharing between IdMap
s. More interestingly, this data structure is designed to support asymptotically fast set operations
on hash-consed IdMaps
, including:
- Unions, intersections, (symmetric) differences, and complements
- Subset/superset checks
The best part is, the more memory shared, the faster these operations become in the general case (though the specialized ptr
variants of these operations may return incorrect values on non hash-consed, i.e. maximally shared, inputs!) To allow user
customized hash-consing strategies, the internal Arc
s behind this data structure can be exposed as opaque objects which the
user may manipulate using the ConsCtx
trait. Alternatively, ()
implements SetCtx
with no consing, and there are helpers
to perform set operations without consing.
There are also some nice implementation details (which may change), including:
IdMap<K, V>
and henceIdSet<K>
are the size of a pointer.NonEmptyIdMap<K, V>
and henceNonEmptyIdSet<K>
are the size of a pointer and null-pointer optimized, i.e.Option<NonEmptySet<T>>
is also the size of a pointer.
Right now, the feature-set is deliberately kept somewhat minimal, as pour
has a particular use case (the rain
intermediate
representation). But if I have time and/or anyone wants to contribute, all kinds of things can be added! Examples of potential
future features include
- Map not just from integer keys but from integer ranges, with similar efficiency
- Union maps of different types
pour
is currently implemented without any unsafe
, though that may change. We do, however use the non-standard elysees
Arc
implementation (a fork of Servo's triomphe
by the author) to avoid weak reference counts.
NOTE: "levels" are currently not yet supported! Returning a level number greater than 0 will cause a panic!
Contributions, questions, and issues are welcome! Please file issues at https://gitlab.com/tekne/pour, and contact the author at jad.ghalayini@gtc.ox.ac.uk for any other queries.
Modules
map_ctx | A simple cons context implemented using a |
mutation | Types and traits for functionally describing mutation of immutable maps |
Structs
IdMap | An immutable, optionally hash-consed pointer-sized map from small integer keys to arbitrary data |
IdMapIntoIter | An iterator over an |
IdMapIter | A borrowed iterator over an |
InnerMap | An |
Enums
BinaryResult | A binary result, which can be either the left value, the right value, or a new value |
UnaryResult | A unary result, which can be either a new value or the old value |
Traits
ConsCtx | A trait implemented by objects which can perform hash-consing on a map's internal data |
Pattern | An n-bit pattern |
RadixKey | A key which can be used in a radix trie |
Type Definitions
IdSet | An immutable, optionally hash-consed pointer-sized set of small integer keys |