Go to the first, previous, next, last section, table of contents.


3.2 Tables

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.