diff options
Diffstat (limited to 'trie.h')
| -rw-r--r-- | trie.h | 66 |
1 files changed, 36 insertions, 30 deletions
@@ -22,82 +22,88 @@ #include <stdint.h> /** - * A trie that holds a set of fixed- or dynamic-length strings. + * A trie that holds a set of fixed- or variable-length strings. */ struct trie { uintptr_t root; }; /** - * Initialize an empty trie. + * A leaf of a trie. */ -void trie_init(struct trie *trie); +struct trie_leaf { + /** + * An arbitrary value associated with this leaf. + */ + const void *value; + + /** + * The length of the key in bytes. + */ + size_t length; + + /** + * The key itself, stored inline. + */ + char key[]; +}; /** - * Check if a NUL-terminated string key exists in a trie. - * - * @param trie - * The trie to search. - * @param key - * The key to search for. - * @return - * Whether the key was found. + * Initialize an empty trie. */ -bool trie_strsearch(const struct trie *trie, const char *key); +void trie_init(struct trie *trie); /** - * Check if a prefix of a NUL-terminated string key exists in a trie. + * Find the leaf for a string key. * * @param trie * The trie to search. * @param key - * The key to search for. - * @param size - * The length of the prefix to consider, in bytes. + * The key to look up. * @return - * Whether the key was found. + * The found leaf, or NULL if the key is not present. */ -bool trie_strnsearch(const struct trie *trie, const char *key, size_t size); +struct trie_leaf *trie_find_str(const struct trie *trie, const char *key); /** - * Check if a fixed-length key exists in a trie. + * Find the leaf for a fixed-size key. * * @param trie * The trie to search. * @param key - * The key to search for. - * @param size + * The key to look up. + * @param length * The length of the key in bytes. * @return - * Whether the key was found. + * The found leaf, or NULL if the key is not present. */ -bool trie_memsearch(const struct trie *trie, const void *key, size_t size); +struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length); /** - * Insert a NUL-terminated string key in the trie. + * Insert a string key into the trie. * * @param trie * The trie to modify. * @param key * The key to insert. * @return - * 0 on success, 1 if the key was already present, or -1 on error. + * The inserted leaf, or NULL on failure. */ -int trie_strinsert(struct trie *trie, const char *key); +struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); /** - * Insert a fixed-length key in the trie. + * Insert a fixed-size key into the trie. * * @param trie * The trie to modify. * @param key * The key to insert. - * @param size + * @param length * The length of the key in bytes. * @return - * 0 on success, 1 if the key was already present, or -1 on error. + * The inserted leaf, or NULL on failure. */ -int trie_meminsert(struct trie *trie, const void *key, size_t size); +struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length); /** * Destroy a trie and its contents. |