Menu

Released v4.0.0

Added: general purpose Trie container.

The trie implementation is based on:
- reduced alphabet size (4 bit),
- direct node indexing.
- stacked nodes (2 different stacks are used for sub-tree and string nodes),
- offset-linked lists of deleted nodes,
- single-bit terminal nodes.

Storing trie nodes on stacks has huge impact on the trie properties:
- dynamic heap allocations are almost completely eliminated;
- sub-tree node size is reduced, by using node offsets instead of pointers;
- allocation and deletion of nodes is very fast, especially when the
operations are interleaved;
- saving, loading and archiving operations are trivial, cause nodes are
stored in a continuous memory block;

Posted by Tomasz Pawlak 2024-06-16

Log in to post a comment.

Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.