#btree #forest #set #map

no-std cranelift-bforest

A forest of B+-trees

26 breaking releases

✓ Uses Rust 2018 edition

new 0.45.0 Oct 9, 2019
0.43.1 Sep 20, 2019
0.37.0 Jul 27, 2019
0.30.0 Mar 26, 2019
0.25.0 Nov 27, 2018

#11 in No standard library

Download history 1054/week @ 2019-06-26 923/week @ 2019-07-03 798/week @ 2019-07-10 792/week @ 2019-07-17 812/week @ 2019-07-24 2683/week @ 2019-07-31 1701/week @ 2019-08-07 1460/week @ 2019-08-14 1793/week @ 2019-08-21 1554/week @ 2019-08-28 1861/week @ 2019-09-04 2145/week @ 2019-09-11 2656/week @ 2019-09-18 3205/week @ 2019-09-25 1719/week @ 2019-10-02

7,649 downloads per month
Used in 44 crates (1 directly)

Apache-2.0 WITH LLVM-exception

210KB
4.5K SLoC

This crate contains array-based data structures used by the core Cranelift code generator which represent a set of small ordered sets or maps.

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.

lib.rs:

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.

Dependencies