[][src]Crate cranelift_bforest

A forest of B+-trees.

This crate provides a data structures representing a set of small ordered sets or maps. It is implemented as a forest of B+-trees all allocating nodes out of the same pool.

These are not general purpose data structures that are somehow magically faster that the standard library's BTreeSet and BTreeMap types.

The tradeoffs are different:

  • Keys and values are expected to be small and copyable. We optimize for 32-bit types.
  • A comparator object is used to compare keys, allowing smaller "context free" keys.
  • Empty trees have a very small 32-bit footprint.
  • All the trees in a forest can be cleared in constant time.

Structs

Map

B-tree mapping from K to V.

MapCursor

A position in a Map used to navigate and modify the ordered map.

MapForest

Memory pool for a forest of Map instances.

MapIter

An iterator visiting the key-value pairs of a Map.

Set

B-tree representing an ordered set of Ks using C for comparing elements.

SetCursor

A position in a Set used to navigate and modify the ordered set.

SetForest

Memory pool for a forest of Set instances.

SetIter

An iterator visiting the elements of a Set.

Traits

Comparator

Key comparator.