prefix-trie

What's new

rkyv zero-copy (de)serialization

This release adds a new rkyv feature flag, bringing zero-copy serialization support to PrefixMap, PrefixSet, and JointPrefixMap/JointPrefixSet. The archived types implement the same TrieView interface as their live counterparts, so you can look up, iterate, and compute covering/LPM/SPM queries directly on the archived (mmap'ed) representation without deserializing.

• get, get_key_value, contains, get_lpm, get_spm, is_covered, is_covered_in_aggregate, address_count, children, iter/iter_from, and cover iterators are all available on the archived variants.
• ArchivedTrieRef type that implements TrieView, enabling integration with concrete (non-archive) types. The new functions on TrieView simplify this process.
• See the new module-level examples for how to serialize, mmap, and query an archived trie.

Others

• New FilterView to filter a view by a predicate closure.
• New ClonedView and CopiedView adapters.
• New MapView combinator for TrieView.
• is_covered and is_covered_in_aggregate added to the core map/set API.

Fixes

• Fixed a repositioning bug in TrieView that could cause UB.
• Fixed Default implementations on Joint iterators (were previously inconsistent/incorrect).
• Removed step and navigate_to from the public TrieView interface (internal-only).

Other

• Raised rust minimal supported version to 1.81.0

Full Changelog: v0.9.4...v0.10.0

What's Changed

• Feature: Add address_count to PrefixMap, PrefixSet, and JointPrefixMap by @digizeph in #31
• Example: add streaming export/import example by @digizeph in #32
• Fix: remove_children now properly cleans up the tree.

New Contributors

• @digizeph made their first contribution in #31 and #32

Full Changelog: v0.9.3...v0.9.4

New Aggregation Algorithms

• PrefixMap::aggregate_consistent and PrefixSet::aggregate_consistent remove covering prefixes (that are covered with the same value). Any get_lpm call (for any prefix) will still return the same value (with a potential different result).
• PrefixSet::aggregate removes covering prefixes and merges adjacent ones. In contrast to aggregate_consistent, calling get_lpm on addresses (e.g., /32 on IPv4) still yields the same value. However, for prefixes, that is not the case.
• PrefixMap::aggregate, PrefixMap::aggregate_fill, and PrefixMap::aggregate_fill_default are implementation of the ORTC algorithm by R. P. Draves, C. King, S. Venkatachary, and B. D. Zill. The fill variants are allowed to add new prefixes (e.g., 0.0.0.0/0) with the provided default value, while the non-fill variant does ensures that uncovered prefixes remain uncovered.

Bug Fixes

• Add missing joint::map::OccupiedEntry::into_mut function

Full Changelog: v0.9.1...v0.9.3

What's Changed

• Add iter_from function to enable paginated output.
• Implement equality on views (eq_keys and eq_by)
• Add Eq implementation for PrefixMap
• Slightly reduce memory footprint (increment number of tiers in allocator from 6 to 7; [1, 2, 4, 8, 16, 24, 32])
• Benchmark using mutations from RIPE RIS by @ties in #28
• Add IPv6 test cases and data by @ties in #30

Bug Fixes

• Drop values only when needed.
• Fix memory corruption bug when calling remove_children in deep trees.
• Fix overflow for obtaining sub-views of maximum prefix length views.
• Fix mask computation on 32-bit targets.
• Fix undefined behavior when drop panics in remove_children.

New Contributors

• @ties made their first contribution in #28

Full Changelog: v0.9.0...v0.9.1

What's Changed

• Migrate to the TreeBitMap implementation by W. Eatherton, Z. Dittia, G. Varghes.
• ~4x less memory consumption and ~8x performance improvement over v0.8.4, measured on all IPv4 prefixes advertised at AMS-IX.
• Flexible simultaneous tree traversal algorithms that can be combined arbitrarily.

Migration Notes

• Prefixes are reconstructed from the tree location and no longer stored.
  Consequently, information in the host part of an address is no longer maintained.
  Additionally, the function yields prefixes by value instead of by reference.
  If you wish to store the host-bits as well, consider constructing a type PrefixMap<P, (P, T)>.
• Mutable views of the tree can no longer modify the tree structure (to maintain memory safety).
  This is because one can construct two mutable views pointing to branches within the same multi-bit node.
• Thanks to bitmaps, set operations can now be chained (as we can define a common interface for them to return their bitmaps).J

Full Changelog: v0.8.4...v0.9.0

What's Changed

• Raise minimum dependency versions by @divergentdave in #25

New Contributors

• @divergentdave made their first contribution in #25

Full Changelog: v0.8.3...v0.8.4

What's Changed

• Fix memory leak during parent node collapse (Closes #23) by @nawed2010 in #24

New Contributors

• @nawed2010 made their first contribution in #24

Full Changelog: v0.8.2...v0.8.3

• Reduced memory usage by applying niche optimization (thanks to #22)