summaryrefslogtreecommitdiffstats
path: root/trie.c
diff options
context:
space:
mode:
Diffstat (limited to 'trie.c')
-rw-r--r--trie.c217
1 files changed, 83 insertions, 134 deletions
diff --git a/trie.c b/trie.c
index 75acd22..fffa4ac 100644
--- a/trie.c
+++ b/trie.c
@@ -96,7 +96,7 @@
#define OFFSET_MAX (((size_t)1 << OFFSET_BITS) - 1)
/**
- * A node in the trie.
+ * An internal node of the trie.
*/
struct trie_node {
/**
@@ -126,13 +126,13 @@ static bool trie_is_leaf(uintptr_t ptr) {
}
/** Decode a pointer to a leaf. */
-static void *trie_decode_leaf(uintptr_t ptr) {
+static struct trie_leaf *trie_decode_leaf(uintptr_t ptr) {
assert(trie_is_leaf(ptr));
- return (void *)(ptr ^ 1);
+ return (struct trie_leaf *)(ptr ^ 1);
}
/** Encode a pointer to a leaf. */
-static uintptr_t trie_encode_leaf(const void *leaf) {
+static uintptr_t trie_encode_leaf(const struct trie_leaf *leaf) {
uintptr_t ptr = (uintptr_t)leaf ^ 1;
assert(trie_is_leaf(ptr));
return ptr;
@@ -186,8 +186,14 @@ static unsigned char trie_key_nibble(const void *key, size_t offset) {
return (bytes[byte] >> shift) & 0xF;
}
-/** Find a leaf that might be the given key, if present. */
-static const void *trie_search(const struct trie *trie, const void *key, size_t size) {
+/**
+ * Finds a leaf in the trie that matches the key at every branch. If the key
+ * exists in the trie, the representative will match the searched key. But
+ * since only branch points are tested, it can be different from the key. In
+ * that case, the first mismatch between the key and the representative will be
+ * the depth at which to make a new branch to insert the key.
+ */
+static struct trie_leaf *trie_representative(const struct trie *trie, const void *key, size_t length) {
uintptr_t ptr = trie->root;
if (!ptr) {
return NULL;
@@ -197,45 +203,44 @@ static const void *trie_search(const struct trie *trie, const void *key, size_t
while (!trie_is_leaf(ptr)) {
struct trie_node *node = trie_decode_node(ptr);
offset += node->offset;
- if ((offset >> 1) >= size) {
- return NULL;
- }
- unsigned char nibble = trie_key_nibble(key, offset);
+ unsigned char nibble = 0;
+ if ((offset >> 1) < length) {
+ nibble = trie_key_nibble(key, offset);
+ }
unsigned int bit = 1U << nibble;
+ unsigned int index = 0;
if (node->bitmap & bit) {
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
- ptr = node->children[index];
- } else {
- return NULL;
+ index = trie_popcount(node->bitmap & (bit - 1));
}
+ ptr = node->children[index];
}
return trie_decode_leaf(ptr);
}
-bool trie_strsearch(const struct trie *trie, const char *key) {
- const char *rep = trie_search(trie, key, strlen(key) + 1);
- return rep && strcmp(key, rep) == 0;
+struct trie_leaf *trie_find_str(const struct trie *trie, const char *key) {
+ return trie_find_mem(trie, key, strlen(key) + 1);
}
-bool trie_strnsearch(const struct trie *trie, const char *key, size_t size) {
- const char *rep = trie_search(trie, key, size);
- return rep && strncmp(key, rep, size) == 0;
-}
-
-bool trie_memsearch(const struct trie *trie, const void *key, size_t size) {
- const void *rep = trie_search(trie, key, size);
- return rep && memcmp(key, rep, size) == 0;
+struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length) {
+ struct trie_leaf *rep = trie_representative(trie, key, length);
+ if (rep && rep->length == length && memcmp(rep->key, key, length) == 0) {
+ return rep;
+ } else {
+ return NULL;
+ }
}
/** Create a new leaf, holding a copy of the given key. */
-static uintptr_t new_trie_leaf(const void *key, size_t size) {
- void *leaf = malloc(size);
+static struct trie_leaf *new_trie_leaf(const void *key, size_t length) {
+ struct trie_leaf *leaf = malloc(sizeof(*leaf) + length);
if (leaf) {
- memcpy(leaf, key, size);
+ leaf->value = NULL;
+ leaf->length = length;
+ memcpy(leaf->key, key, length);
}
- return trie_encode_leaf(leaf);
+ return leaf;
}
/** Compute the size of a trie node with a certain number of children. */
@@ -248,50 +253,21 @@ static size_t trie_node_size(unsigned int size) {
return sizeof(struct trie_node) + size*sizeof(uintptr_t);
}
-/**
- * Finds a leaf in the trie that matches the key at every branch. If the key
- * exists in the trie, the representative will match the searched key. But
- * since only branch points are tested, it can be different from the key. In
- * that case, the first mismatch between the key and the representative will be
- * the depth at which to make a new branch to insert the key.
- */
-static const void *trie_representative(const struct trie *trie, const void *key, size_t size) {
- size_t offset = 0;
- uintptr_t ptr = trie->root;
- while (!trie_is_leaf(ptr)) {
- struct trie_node *node = trie_decode_node(ptr);
- offset += node->offset;
-
- unsigned char nibble = 0;
- if ((offset >> 1) < size) {
- nibble = trie_key_nibble(key, offset);
- }
- unsigned int bit = 1U << nibble;
- unsigned int index = 0;
- if (node->bitmap & bit) {
- index = trie_popcount(node->bitmap & (bit - 1));
- }
- ptr = node->children[index];
- }
-
- return trie_decode_leaf(ptr);
-}
-
/** Find the offset of the first nibble that differs between two keys. */
-static size_t trie_key_mismatch(const void *key1, const void *key2, size_t size) {
+static size_t trie_key_mismatch(const void *key1, const void *key2, size_t length) {
const unsigned char *bytes1 = key1;
const unsigned char *bytes2 = key2;
size_t i = 0;
size_t offset = 0;
const size_t chunk = sizeof(size_t);
- for (; i + chunk <= size; i += chunk) {
+ for (; i + chunk <= length; i += chunk) {
if (memcmp(bytes1 + i, bytes2 + i, chunk) != 0) {
break;
}
}
- for (; i < size; ++i) {
+ for (; i < length; ++i) {
unsigned char b1 = bytes1[i], b2 = bytes2[i];
if (b1 != b2) {
offset = (b1 & 0xF) == (b2 & 0xF);
@@ -325,7 +301,7 @@ static size_t trie_key_mismatch(const void *key1, const void *key2, size_t size)
* | Z
* +--->...
*/
-static int trie_node_insert(uintptr_t *ptr, const void *key, size_t key_size, size_t offset) {
+static struct trie_leaf *trie_node_insert(uintptr_t *ptr, const void *key, size_t length, size_t offset) {
struct trie_node *node = trie_decode_node(*ptr);
unsigned int size = trie_popcount(node->bitmap);
@@ -333,14 +309,14 @@ static int trie_node_insert(uintptr_t *ptr, const void *key, size_t key_size, si
if ((size & (size - 1)) == 0) {
node = realloc(node, trie_node_size(2*size));
if (!node) {
- return -1;
+ return NULL;
}
*ptr = trie_encode_node(node);
}
- uintptr_t leaf = new_trie_leaf(key, key_size);
+ struct trie_leaf *leaf = new_trie_leaf(key, length);
if (!leaf) {
- return -1;
+ return NULL;
}
unsigned char nibble = trie_key_nibble(key, offset);
@@ -355,8 +331,8 @@ static int trie_node_insert(uintptr_t *ptr, const void *key, size_t key_size, si
if (index < size) {
memmove(child + 1, child, (size - index)*sizeof(*child));
}
- *child = leaf;
- return 0;
+ *child = trie_encode_leaf(leaf);
+ return leaf;
}
/**
@@ -370,21 +346,21 @@ static int trie_node_insert(uintptr_t *ptr, const void *key, size_t key_size, si
*
* and changes it to:
*
- * ptr
- * |
- * v
- * *--->*--->rep
+ * ptr ret
+ * | |
+ * v v
+ * *--->*--->rep
*
* so that a new key can be inserted like:
*
- * ptr
- * |
- * v X
- * *--->*--->rep
- * | Y
- * +--->key
+ * ptr ret
+ * | |
+ * v v X
+ * *--->*--->rep
+ * | Y
+ * +--->key
*/
-static uintptr_t *trie_jump(uintptr_t *ptr, const char *key, size_t size, size_t *offset) {
+static uintptr_t *trie_jump(uintptr_t *ptr, const char *key, size_t *offset) {
// We only ever need to jump to leaf nodes, since internal nodes are
// guaranteed to be within OFFSET_MAX anyway
assert(trie_is_leaf(*ptr));
@@ -422,20 +398,20 @@ static uintptr_t *trie_jump(uintptr_t *ptr, const char *key, size_t size, size_t
* | Y
* +--->key
*/
-static int trie_split(uintptr_t *ptr, const void *key, size_t size, const void *rep, size_t offset, size_t mismatch) {
+static struct trie_leaf *trie_split(uintptr_t *ptr, const void *key, size_t length, struct trie_leaf *rep, size_t offset, size_t mismatch) {
unsigned char key_nibble = trie_key_nibble(key, mismatch);
- unsigned char rep_nibble = trie_key_nibble(rep, mismatch);
+ unsigned char rep_nibble = trie_key_nibble(rep->key, mismatch);
assert(key_nibble != rep_nibble);
struct trie_node *node = malloc(trie_node_size(2));
if (!node) {
- return -1;
+ return NULL;
}
- uintptr_t leaf = new_trie_leaf(key, size);
+ struct trie_leaf *leaf = new_trie_leaf(key, length);
if (!leaf) {
free(node);
- return -1;
+ return NULL;
}
node->bitmap = (1 << key_nibble) | (1 << rep_nibble);
@@ -448,32 +424,30 @@ static int trie_split(uintptr_t *ptr, const void *key, size_t size, const void *
node->offset = delta;
unsigned int key_index = key_nibble > rep_nibble;
- node->children[key_index] = leaf;
+ node->children[key_index] = trie_encode_leaf(leaf);
node->children[key_index ^ 1] = *ptr;
*ptr = trie_encode_node(node);
- return 0;
+ return leaf;
}
-/**
- * Insert a key into the trie.
- *
- * @param trie
- * The trie to modify.
- * @param key
- * The key to insert.
- * @param size
- * The size of the key in bytes.
- * @param rep
- * The representative for the key.
- * @param mismatch
- * The index of the first mismatched nibble between the key and the
- * representative.
- * @return
- * 0 on success, 1 if the key was already present, or -1 on error.
- */
-static int trie_insert(struct trie *trie, const void *key, size_t size, const void *rep, size_t mismatch) {
- if ((mismatch >> 1) >= size) {
- return 1;
+struct trie_leaf *trie_insert_str(struct trie *trie, const char *key) {
+ return trie_insert_mem(trie, key, strlen(key) + 1);
+}
+
+struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length) {
+ struct trie_leaf *rep = trie_representative(trie, key, length);
+ if (!rep) {
+ struct trie_leaf *leaf = new_trie_leaf(key, length);
+ if (leaf) {
+ trie->root = trie_encode_leaf(leaf);
+ }
+ return leaf;
+ }
+
+ size_t limit = length < rep->length ? length : rep->length;
+ size_t mismatch = trie_key_mismatch(key, rep->key, limit);
+ if ((mismatch >> 1) >= length) {
+ return rep;
}
size_t offset = 0;
@@ -493,43 +467,18 @@ static int trie_insert(struct trie *trie, const void *key, size_t size, const vo
ptr = node->children + index;
} else {
assert(offset == mismatch);
- return trie_node_insert(ptr, key, size, offset);
+ return trie_node_insert(ptr, key, length, offset);
}
}
while (mismatch - offset > OFFSET_MAX) {
- ptr = trie_jump(ptr, key, size, &offset);
+ ptr = trie_jump(ptr, key, &offset);
if (!ptr) {
- return -1;
+ return NULL;
}
}
- return trie_split(ptr, key, size, rep, offset, mismatch);
-}
-
-int trie_strinsert(struct trie *trie, const char *key) {
- size_t size = strlen(key) + 1;
-
- if (!trie->root) {
- trie->root = new_trie_leaf(key, size);
- return trie->root ? 0 : -1;
- }
-
- const char *rep = trie_representative(trie, key, size);
- size_t limit = strnlen(rep, size - 1) + 1;
- size_t mismatch = trie_key_mismatch(key, rep, limit);
- return trie_insert(trie, key, size, rep, mismatch);
-}
-
-int trie_meminsert(struct trie *trie, const void *key, size_t size) {
- if (!trie->root) {
- trie->root = new_trie_leaf(key, size);
- return trie->root ? 0 : -1;
- }
-
- const void *rep = trie_representative(trie, key, size);
- size_t mismatch = trie_key_mismatch(key, rep, size);
- return trie_insert(trie, key, size, rep, mismatch);
+ return trie_split(ptr, key, length, rep, offset, mismatch);
}
/** Free an encoded pointer to a node. */