Source / Include Folder (#88)

Moved Source Files Into `src` Folder

1 files changed, 693 insertions, 0 deletions

diff --git a/src/trie.c b/src/trie.c
new file mode 100644
index 0000000..bae9acb
--- /dev/null
+++ b/src/trie.c
@@ -0,0 +1,693 @@
+/****************************************************************************
+ * 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);
+	}
+}