summaryrefslogtreecommitdiffstats
path: root/trie.c
diff options
context:
space:
mode:
Diffstat (limited to 'trie.c')
-rw-r--r--trie.c693
1 files changed, 0 insertions, 693 deletions
diff --git a/trie.c b/trie.c
deleted file mode 100644
index bae9acb..0000000
--- a/trie.c
+++ /dev/null
@@ -1,693 +0,0 @@
-/****************************************************************************
- * bfs *
- * Copyright (C) 2019 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. *
- ****************************************************************************/
-
-/**
- * This is an implementation of a "qp trie," as documented at
- * https://dotat.at/prog/qp/README.html
- *
- * An uncompressed trie over the dataset {AAAA, AADD, ABCD, DDAA, DDDD} would
- * look like
- *
- * A A A A
- * *--->*--->*--->*--->$
- * | | | D D
- * | | +--->*--->$
- * | | B C D
- * | +--->*--->*--->$
- * | D D A A
- * +--->*--->*--->*--->$
- * | D D
- * +--->*--->$
- *
- * A compressed (PATRICIA) trie collapses internal nodes that have only a single
- * child, like this:
- *
- * A A AA
- * *--->*--->*---->$
- * | | | DD
- * | | +---->$
- * | | BCD
- * | +----->$
- * | DD AA
- * +---->*---->$
- * | DD
- * +---->$
- *
- * The nodes can be compressed further by dropping the actual compressed
- * sequences from the nodes, storing it only in the leaves. This is the
- * technique applied in QP tries, and the crit-bit trees that inspired them
- * (https://cr.yp.to/critbit.html). Only the index to test, and the values to
- * branch on, need to be stored in each node.
- *
- * A A A
- * 0--->1--->2--->AAAA
- * | | | D
- * | | +--->AADD
- * | | B
- * | +--->ABCD
- * | D A
- * +--->2--->DDAA
- * | D
- * +--->DDDD
- *
- * Nodes are represented very compactly. Rather than a dense array of children,
- * a sparse array of only the non-NULL children directly follows the node in
- * memory. A bitmap is used to track which children exist; the index of a child
- * i is found by counting the number of bits below bit i that are set. A tag
- * bit is used to tell pointers to internal nodes apart from pointers to leaves.
- *
- * This implementation tests a whole nibble (half byte/hex digit) at every
- * branch, so the bitmap takes up 16 bits. The remainder of a machine word is
- * used to hold the offset, which severely constrains its range on 32-bit
- * platforms. As a workaround, we store relative instead of absolute offsets,
- * and insert intermediate singleton "jump" nodes when necessary.
- */
-
-#include "trie.h"
-#include "util.h"
-#include <assert.h>
-#include <limits.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-#if CHAR_BIT != 8
-# error "This trie implementation assumes 8-bit bytes."
-#endif
-
-/** Number of bits for the sparse array bitmap, aka the range of a nibble. */
-#define BITMAP_BITS 16
-/** The number of remaining bits in a word, to hold the offset. */
-#define OFFSET_BITS (sizeof(size_t)*CHAR_BIT - BITMAP_BITS)
-/** The highest representable offset (only 64k on a 32-bit architecture). */
-#define OFFSET_MAX (((size_t)1 << OFFSET_BITS) - 1)
-
-/**
- * An internal node of the trie.
- */
-struct trie_node {
- /**
- * A bitmap that hold which indices exist in the sparse children array.
- * Bit i will be set if a child exists at logical index i, and its index
- * into the array will be popcount(bitmap & ((1 << i) - 1)).
- */
- size_t bitmap : BITMAP_BITS;
-
- /**
- * The offset into the key in nibbles. This is relative to the parent
- * node, to support offsets larger than OFFSET_MAX.
- */
- size_t offset : OFFSET_BITS;
-
- /**
- * Flexible array of children. Each pointer uses the lowest bit as a
- * tag to distinguish internal nodes from leaves. This is safe as long
- * as all dynamic allocations are aligned to more than a single byte.
- */
- uintptr_t children[];
-};
-
-/** Check if an encoded pointer is to a leaf. */
-static bool trie_is_leaf(uintptr_t ptr) {
- return ptr & 1;
-}
-
-/** Decode a pointer to a leaf. */
-static struct trie_leaf *trie_decode_leaf(uintptr_t ptr) {
- assert(trie_is_leaf(ptr));
- return (struct trie_leaf *)(ptr ^ 1);
-}
-
-/** Encode a pointer to a 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;
-}
-
-/** Decode a pointer to an internal node. */
-static struct trie_node *trie_decode_node(uintptr_t ptr) {
- assert(!trie_is_leaf(ptr));
- return (struct trie_node *)ptr;
-}
-
-/** Encode a pointer to an internal node. */
-static uintptr_t trie_encode_node(const struct trie_node *node) {
- uintptr_t ptr = (uintptr_t)node;
- assert(!trie_is_leaf(ptr));
- return ptr;
-}
-
-void trie_init(struct trie *trie) {
- trie->root = 0;
-}
-
-/** Compute the popcount (Hamming weight) of a bitmap. */
-static unsigned int trie_popcount(unsigned int n) {
-#if __POPCNT__
- // Use the x86 instruction if we have it. Otherwise, GCC generates a
- // library call, so use the below implementation instead.
- return __builtin_popcount(n);
-#else
- // See https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
- n -= (n >> 1) & 0x5555;
- n = (n & 0x3333) + ((n >> 2) & 0x3333);
- n = (n + (n >> 4)) & 0x0F0F;
- n = (n + (n >> 8)) & 0xFF;
- return n;
-#endif
-}
-
-/** Extract the nibble at a certain offset from a byte sequence. */
-static unsigned char trie_key_nibble(const void *key, size_t offset) {
- const unsigned char *bytes = key;
- size_t byte = offset >> 1;
-
- // A branchless version of
- // if (offset & 1) {
- // return bytes[byte] >> 4;
- // } else {
- // return bytes[byte] & 0xF;
- // }
- unsigned int shift = (offset & 1) << 2;
- return (bytes[byte] >> shift) & 0xF;
-}
-
-/**
- * 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;
- }
-
- size_t offset = 0;
- while (!trie_is_leaf(ptr)) {
- struct trie_node *node = trie_decode_node(ptr);
- offset += node->offset;
-
- unsigned int index = 0;
- if ((offset >> 1) < length) {
- unsigned char nibble = trie_key_nibble(key, offset);
- unsigned int bit = 1U << nibble;
- if (node->bitmap & bit) {
- index = trie_popcount(node->bitmap & (bit - 1));
- }
- }
- ptr = node->children[index];
- }
-
- return trie_decode_leaf(ptr);
-}
-
-struct trie_leaf *trie_first_leaf(const struct trie *trie) {
- return trie_representative(trie, NULL, 0);
-}
-
-struct trie_leaf *trie_find_str(const struct trie *trie, const char *key) {
- return trie_find_mem(trie, key, strlen(key) + 1);
-}
-
-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;
- }
-}
-
-struct trie_leaf *trie_find_postfix(const struct trie *trie, const char *key) {
- size_t length = strlen(key);
- struct trie_leaf *rep = trie_representative(trie, key, length + 1);
- if (rep && rep->length >= length && memcmp(rep->key, key, length) == 0) {
- return rep;
- } else {
- return NULL;
- }
-}
-
-/**
- * Find a leaf that may end at the current node.
- */
-static struct trie_leaf *trie_terminal_leaf(const struct trie_node *node) {
- // Finding a terminating NUL byte may take two nibbles
- for (int i = 0; i < 2; ++i) {
- if (!(node->bitmap & 1)) {
- break;
- }
-
- uintptr_t ptr = node->children[0];
- if (trie_is_leaf(ptr)) {
- return trie_decode_leaf(ptr);
- } else {
- node = trie_decode_node(ptr);
- }
- }
-
- return NULL;
-}
-
-/** Check if a leaf is a prefix of a search key. */
-static bool trie_check_prefix(struct trie_leaf *leaf, size_t skip, const char *key, size_t length) {
- if (leaf && leaf->length <= length) {
- return memcmp(key + skip, leaf->key + skip, leaf->length - skip - 1) == 0;
- } else {
- return false;
- }
-}
-
-struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
- uintptr_t ptr = trie->root;
- if (!ptr) {
- return NULL;
- }
-
- struct trie_leaf *best = NULL;
- size_t skip = 0;
- size_t length = strlen(key) + 1;
-
- size_t offset = 0;
- while (!trie_is_leaf(ptr)) {
- struct trie_node *node = trie_decode_node(ptr);
- offset += node->offset;
- if ((offset >> 1) >= length) {
- return best;
- }
-
- struct trie_leaf *leaf = trie_terminal_leaf(node);
- if (trie_check_prefix(leaf, skip, key, length)) {
- best = leaf;
- skip = offset >> 1;
- }
-
- unsigned char nibble = trie_key_nibble(key, offset);
- unsigned int bit = 1U << nibble;
- if (node->bitmap & bit) {
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
- ptr = node->children[index];
- } else {
- return best;
- }
- }
-
- struct trie_leaf *leaf = trie_decode_leaf(ptr);
- if (trie_check_prefix(leaf, skip, key, length)) {
- best = leaf;
- }
-
- return best;
-}
-
-/** Create a new leaf, holding a copy of the given key. */
-static struct trie_leaf *new_trie_leaf(const void *key, size_t length) {
- struct trie_leaf *leaf = malloc(BFS_FLEX_SIZEOF(struct trie_leaf, key, length));
- if (leaf) {
- leaf->value = NULL;
- leaf->length = length;
- memcpy(leaf->key, key, length);
- }
- return leaf;
-}
-
-/** Compute the size of a trie node with a certain number of children. */
-static size_t trie_node_size(unsigned int size) {
- // Empty nodes aren't supported
- assert(size > 0);
- // Node size must be a power of two
- assert((size & (size - 1)) == 0);
-
- return BFS_FLEX_SIZEOF(struct trie_node, children, size);
-}
-
-/** 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 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 <= length; i += chunk) {
- if (memcmp(bytes1 + i, bytes2 + i, chunk) != 0) {
- break;
- }
- }
-
- for (; i < length; ++i) {
- unsigned char b1 = bytes1[i], b2 = bytes2[i];
- if (b1 != b2) {
- offset = (b1 & 0xF) == (b2 & 0xF);
- break;
- }
- }
-
- offset |= i << 1;
- return offset;
-}
-
-/**
- * Insert a key into a node. The node must not have a child in that position
- * already. Effectively takes a subtrie like this:
- *
- * ptr
- * |
- * v X
- * *--->...
- * | Z
- * +--->...
- *
- * and transforms it to:
- *
- * ptr
- * |
- * v X
- * *--->...
- * | Y
- * +--->key
- * | Z
- * +--->...
- */
-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);
-
- // Double the capacity every power of two
- if ((size & (size - 1)) == 0) {
- node = realloc(node, trie_node_size(2*size));
- if (!node) {
- return NULL;
- }
- *ptr = trie_encode_node(node);
- }
-
- struct trie_leaf *leaf = new_trie_leaf(key, length);
- if (!leaf) {
- return NULL;
- }
-
- unsigned char nibble = trie_key_nibble(key, offset);
- unsigned int bit = 1U << nibble;
-
- // The child must not already be present
- assert(!(node->bitmap & bit));
- node->bitmap |= bit;
-
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
- uintptr_t *child = &node->children[index];
- if (index < size) {
- memmove(child + 1, child, (size - index)*sizeof(*child));
- }
- *child = trie_encode_leaf(leaf);
- return leaf;
-}
-
-/**
- * When the current offset exceeds OFFSET_MAX, insert "jump" nodes that bridge
- * the gap. This function takes a subtrie like this:
- *
- * ptr
- * |
- * v
- * *--->rep
- *
- * and changes it to:
- *
- * ptr ret
- * | |
- * v v
- * *--->*--->rep
- *
- * so that a new key can be inserted like:
- *
- * ptr ret
- * | |
- * v v X
- * *--->*--->rep
- * | Y
- * +--->key
- */
-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));
-
- struct trie_node *node = malloc(trie_node_size(1));
- if (!node) {
- return NULL;
- }
-
- *offset += OFFSET_MAX;
- node->offset = OFFSET_MAX;
-
- unsigned char nibble = trie_key_nibble(key, *offset);
- node->bitmap = 1 << nibble;
-
- node->children[0] = *ptr;
- *ptr = trie_encode_node(node);
- return node->children;
-}
-
-/**
- * Split a node in the trie. Changes a subtrie like this:
- *
- * ptr
- * |
- * v
- * *...>--->rep
- *
- * into this:
- *
- * ptr
- * |
- * v X
- * *--->*...>--->rep
- * | Y
- * +--->key
- */
-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->key, mismatch);
- assert(key_nibble != rep_nibble);
-
- struct trie_node *node = malloc(trie_node_size(2));
- if (!node) {
- return NULL;
- }
-
- struct trie_leaf *leaf = new_trie_leaf(key, length);
- if (!leaf) {
- free(node);
- return NULL;
- }
-
- node->bitmap = (1 << key_nibble) | (1 << rep_nibble);
-
- size_t delta = mismatch - offset;
- if (!trie_is_leaf(*ptr)) {
- struct trie_node *child = trie_decode_node(*ptr);
- child->offset -= delta;
- }
- node->offset = delta;
-
- unsigned int key_index = key_nibble > rep_nibble;
- node->children[key_index] = trie_encode_leaf(leaf);
- node->children[key_index ^ 1] = *ptr;
- *ptr = trie_encode_node(node);
- return leaf;
-}
-
-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;
- uintptr_t *ptr = &trie->root;
- while (!trie_is_leaf(*ptr)) {
- struct trie_node *node = trie_decode_node(*ptr);
- if (offset + node->offset > mismatch) {
- break;
- }
- offset += node->offset;
-
- unsigned char nibble = trie_key_nibble(key, offset);
- unsigned int bit = 1U << nibble;
- if (node->bitmap & bit) {
- assert(offset < mismatch);
- unsigned int index = trie_popcount(node->bitmap & (bit - 1));
- ptr = &node->children[index];
- } else {
- assert(offset == mismatch);
- return trie_node_insert(ptr, key, length, offset);
- }
- }
-
- while (mismatch - offset > OFFSET_MAX) {
- ptr = trie_jump(ptr, key, &offset);
- if (!ptr) {
- return NULL;
- }
- }
-
- return trie_split(ptr, key, length, rep, offset, mismatch);
-}
-
-/** Free a chain of singleton nodes. */
-static void trie_free_singletons(uintptr_t ptr) {
- while (!trie_is_leaf(ptr)) {
- struct trie_node *node = trie_decode_node(ptr);
-
- // Make sure the bitmap is a power of two, i.e. it has just one child
- assert((node->bitmap & (node->bitmap - 1)) == 0);
-
- ptr = node->children[0];
- free(node);
- }
-
- free(trie_decode_leaf(ptr));
-}
-
-/**
- * Try to collapse a two-child node like:
- *
- * parent child
- * | |
- * v v
- * *----->*----->*----->leaf
- * |
- * +----->other
- *
- * into
- *
- * parent
- * |
- * v
- * other
- */
-static int trie_collapse_node(uintptr_t *parent, struct trie_node *parent_node, unsigned int child_index) {
- uintptr_t other = parent_node->children[child_index ^ 1];
- if (!trie_is_leaf(other)) {
- struct trie_node *other_node = trie_decode_node(other);
- if (other_node->offset + parent_node->offset <= OFFSET_MAX) {
- other_node->offset += parent_node->offset;
- } else {
- return -1;
- }
- }
-
- *parent = other;
- free(parent_node);
- return 0;
-}
-
-void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
- uintptr_t *child = &trie->root;
- uintptr_t *parent = NULL;
- unsigned int child_bit = 0, child_index = 0;
- size_t offset = 0;
- while (!trie_is_leaf(*child)) {
- struct trie_node *node = trie_decode_node(*child);
- offset += node->offset;
- assert((offset >> 1) < leaf->length);
-
- unsigned char nibble = trie_key_nibble(leaf->key, offset);
- unsigned int bit = 1U << nibble;
- unsigned int bitmap = node->bitmap;
- assert(bitmap & bit);
- unsigned int index = trie_popcount(bitmap & (bit - 1));
-
- // Advance the parent pointer, unless this node had only one child
- if (bitmap & (bitmap - 1)) {
- parent = child;
- child_bit = bit;
- child_index = index;
- }
-
- child = &node->children[index];
- }
-
- assert(trie_decode_leaf(*child) == leaf);
-
- if (!parent) {
- trie_free_singletons(trie->root);
- trie->root = 0;
- return;
- }
-
- struct trie_node *node = trie_decode_node(*parent);
- child = node->children + child_index;
- trie_free_singletons(*child);
-
- node->bitmap ^= child_bit;
- unsigned int parent_size = trie_popcount(node->bitmap);
- assert(parent_size > 0);
- if (parent_size == 1 && trie_collapse_node(parent, node, child_index) == 0) {
- return;
- }
-
- if (child_index < parent_size) {
- memmove(child, child + 1, (parent_size - child_index)*sizeof(*child));
- }
-
- if ((parent_size & (parent_size - 1)) == 0) {
- node = realloc(node, trie_node_size(parent_size));
- if (node) {
- *parent = trie_encode_node(node);
- }
- }
-}
-
-/** Free an encoded pointer to a node. */
-static void free_trie_ptr(uintptr_t ptr) {
- if (trie_is_leaf(ptr)) {
- free(trie_decode_leaf(ptr));
- } else {
- struct trie_node *node = trie_decode_node(ptr);
- size_t size = trie_popcount(node->bitmap);
- for (size_t i = 0; i < size; ++i) {
- free_trie_ptr(node->children[i]);
- }
- free(node);
- }
-}
-
-void trie_destroy(struct trie *trie) {
- if (trie->root) {
- free_trie_ptr(trie->root);
- }
-}