Module tree

The histogram is implemented as a trie.

Each node in the trie stores a count of a key/address sharing a prefix up to depth * LEVEL_STEP bits. The key/address is always 64 bits.

There are branch nodes, and two types of leaf nodes: dense, and sparse. Dense leaves are only found at the very bottom of the trie.

Modules

• large_and_fast 🔒
• small_and_slow 🔒

Structs

• BranchNode 🔒
• DenseLeaf 🔒
• Int64Histogram
  A histogram, mapping i64 key to a u64 count optimizing for very fast range-queries.
• Iter
  An iterator over an Int64Histogram.
• NodeIterator 🔒
• SparseLeaf 🔒
• TreeIterator 🔒

Enums

• Node 🔒

Constants

• ADDR_MASK 🔒
• MAX_SPARSE_LEAF_LEN 🔒
  When a SparseLeaf goes over this, it becomes a BranchNode.
• NUM_CHILDREN_IN_NODE 🔒
• NUM_NODE_STEPS 🔒
• NUM_STEPS_IN_DENSE_LEAF 🔒
• ROOT_LEVEL 🔒

Functions

• child_level_and_size 🔒
• range_u64_from_range_bounds 🔒

Type Aliases

• Level 🔒
  How high up in the tree we are (where root is highest). 1 << level is the size of the range the next child. So 1 << ROOT_LEVEL is the size of the range of each children of the root.