LIBPA provides three ways to store arbitrary information in tables:
table_t
, trie_t
, and hash_table_t
.
The table_t
module is a compact table for arbitrary
<symbol,datum> pairs. Lookups are performed in O(log n) using binary
search, while insertions and deletions are O(n) for a table containing n
entries. The table_t
module is typically used as a building
block for other modules, such as the trie_t
module, where memory
usage is the single most important performance desiderata.
The trie_t
module maps length-delimited strings over arbitrary
alphabets to consecutive unsigned integers. It also provides the
inverse map, from indices to length-delimited strings.
The hash_table_t
module supports the easy construction of compact
hash tables for arbitrary <key,datum> pairs with open addressing, double
hashing, and dynamic resizing. We used the hash_table_t
module
to implement two useful modules: the symbol_hash_t
for symbols of
arbitrary size and the string_hash_t
for NULL-terminated
character strings. Again, we strove to minimize the space requirements
of the implementation so that many hash_table_t
objects can
be used in even the most memory-intensive computations.
Go to the first, previous, next, last section, table of contents.