Crate bbtree

Expand description

bbtree: the blessed B-tree.

Modules§

bbtree_map: BBTreeMap, an ordered map that threads share, and the types that go with it.
unsync: An ordered map and set for one thread at a time: BBTreeMap and BBTreeSet, drop-in replacements for std’s BTreeMap and BTreeSet (D1). They use the same nodes as crate::BBTreeMap, which threads share. They take &mut self to change, lend references into their nodes, and latch nothing.

AllocError: An allocator had no block to give.
AnnexedLeaf: A leaf of a BBTreeMap with strategy S, that an insert or a removal holds exclusively for 'a, while it runs its caller’s closure (BBTreeMap::update_or_insert_with_leaf, BBTreeMap::remove_with_leaf): the leaf’s annex (LeafAnnex), and its keys. No other thread reads or changes them meanwhile.
Auto: The default strategy: std byte-string keys and 64- and 128-bit integer keys have inline keys, other keys have none, at no cost.
BBTreeMap: An ordered map that threads share, through &self: a B+-tree whose internal nodes are read optimistically, and whose leaves are latched (design/09-concurrency.md).
Configured: The strategy whose inline keys are strategy S’s, and whose nodes are built as config C says: Configured<Auto, C> or Configured<WithInlineKey, C>.
Global: The global allocator, which #[global_allocator] picks: what a map uses unless given another.
WithInlineKey: The opt-in strategy: every key has the inline key its InlineKey impl gives, of which the nodes keep InlineKey::WIDTH bytes, and the hash tag it gives if InlineKey::HAS_HASH_TAG.
WithLeafAnnex: The strategy whose inline keys and node config are strategy S’s, and whose leaves keep an annex L: for a BBTreeMap.

InlineWidth: How many bytes of each inline key the nodes keep: the first 2, the first 4, or all 8 of the window that InlineKey::inline_key_at gives.

Allocator: An allocator of the pages a map keeps its nodes in, and that the code keeping a map’s keys and values beside it keeps them in (heap pages).
InlineKey: A key type whose keys have inline keys: windows of the key’s encoding, a byte string that orders like the key.
InlineKeyStrategy: Which keys of a map with keys K have inline keys: Auto or WithInlineKey, with the default NodeConfig, or either of them with another, Configured; and what its leaves keep besides, WithLeafAnnex. These are the only implementations.
LeafAnnex: Data a BBTreeMap keeps in each of its leaves, right after the leaf’s header, for the code that owns where its keys and values point: it reads and changes it while an insert or a removal holds the leaf (AnnexedLeaf). The map keeps it with its leaf:
NodeConfig: How a map builds its nodes: constants the map reads at compile time, so that a map with a config runs as one without would at the same sizes.

InlineWord: An inline key: bytes of a key’s encoding, big-endian, so that inline keys compare like the bytes they come from (see InlineKey).