summaryrefslogtreecommitdiffstats
path: root/src/trie.h
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2024-05-07 15:42:46 -0400
committerTavian Barnes <tavianator@tavianator.com>2024-05-07 15:42:46 -0400
commit452d6697e0f92326ab139eed4eadd9c2fd8b55ca (patch)
tree0feeb3722dcf6debb6c33c5175342bf1d70a1dba /src/trie.h
parenta4299f9bc1d3e60a7e628561e8d650c2a241e1c2 (diff)
parentc5cf2cf90834f2f56b2940d2a499a1a614ebfd21 (diff)
downloadbfs-452d6697e0f92326ab139eed4eadd9c2fd8b55ca.tar.xz
Merge branch 'main' into find2fdfind2fd
Diffstat (limited to 'src/trie.h')
-rw-r--r--src/trie.h54
1 files changed, 19 insertions, 35 deletions
diff --git a/src/trie.h b/src/trie.h
index 2ede6ea..4288d76 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -1,23 +1,11 @@
-/****************************************************************************
- * bfs *
- * Copyright (C) 2019-2022 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * Permission to use, copy, modify, and/or distribute this software for any *
- * purpose with or without fee is hereby granted. *
- * *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
- ****************************************************************************/
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
#ifndef BFS_TRIE_H
#define BFS_TRIE_H
-#include <stdbool.h>
+#include "alloc.h"
+#include "list.h"
#include <stddef.h>
#include <stdint.h>
@@ -25,24 +13,13 @@
* A leaf of a trie.
*/
struct trie_leaf {
- /**
- * Linked list of leaves, in insertion order.
- */
+ /** Linked list of leaves, in insertion order. */
struct trie_leaf *prev, *next;
-
- /**
- * An arbitrary value associated with this leaf.
- */
+ /** An arbitrary value associated with this leaf. */
void *value;
-
- /**
- * The length of the key in bytes.
- */
+ /** The length of the key in bytes. */
size_t length;
-
- /**
- * The key itself, stored inline.
- */
+ /** The key itself, stored inline. */
char key[];
};
@@ -54,6 +31,10 @@ struct trie {
uintptr_t root;
/** Linked list of leaves. */
struct trie_leaf *head, *tail;
+ /** Node allocator. */
+ struct varena nodes;
+ /** Leaf allocator. */
+ struct varena leaves;
};
/**
@@ -148,6 +129,11 @@ struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t len
void trie_remove(struct trie *trie, struct trie_leaf *leaf);
/**
+ * Remove all leaves from a trie.
+ */
+void trie_clear(struct trie *trie);
+
+/**
* Destroy a trie and its contents.
*/
void trie_destroy(struct trie *trie);
@@ -155,9 +141,7 @@ void trie_destroy(struct trie *trie);
/**
* Iterate over the leaves of a trie.
*/
-#define TRIE_FOR_EACH(trie, leaf) \
- for (struct trie_leaf *leaf = (trie)->head, *_next; \
- leaf && (_next = leaf->next, true); \
- leaf = _next)
+#define for_trie(leaf, trie) \
+ for_list (struct trie_leaf, leaf, trie)
#endif // BFS_TRIE_H