[][src]Crate pour

pour

crates.io Downloads Documentation Pipeline status codecov License: MIT

pour is an implementation of an immutable IdMap: it maps bitvector IDs to values using a radix trie.

Since these IdMaps are immutable, they can share a lot of data between them, and hash-consing can be used to increase the degree of sharing between IdMaps. 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 Arcs 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 hence IdSet<K> are the size of a pointer.
  • NonEmptyIdMap<K, V> and hence NonEmptyIdSet<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 hashbrown HashMap for efficient access to the raw entry API, which is very helpful for hash consing.

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 IdMap

IdMapIter

A borrowed iterator over an IdMap

InnerMap

An IdMap's internal data.

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