summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/parserutils/utils/dict.h28
-rw-r--r--src/utils/Makefile2
-rw-r--r--src/utils/dict.c275
-rw-r--r--src/utils/rbtree.c732
-rw-r--r--src/utils/rbtree.h40
-rw-r--r--test/INDEX2
-rw-r--r--test/Makefile3
-rw-r--r--test/dict.c54
-rw-r--r--test/rbtree.c87
9 files changed, 1221 insertions, 2 deletions
diff --git a/include/parserutils/utils/dict.h b/include/parserutils/utils/dict.h
new file mode 100644
index 0000000..43c96cb
--- /dev/null
+++ b/include/parserutils/utils/dict.h
@@ -0,0 +1,28 @@
+/*
+ * This file is part of LibParserUtils.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#ifndef parserutils_utils_dict_h_
+#define parserutils_utils_dict_h_
+
+#include <parserutils/errors.h>
+#include <parserutils/functypes.h>
+
+struct parserutils_dict_entry;
+typedef struct parserutils_dict_entry parserutils_dict_entry;
+
+struct parserutils_dict;
+typedef struct parserutils_dict parserutils_dict;
+
+parserutils_dict *parserutils_dict_create(parserutils_alloc alloc, void *pw);
+void parserutils_dict_destroy(parserutils_dict *dict);
+
+parserutils_error parserutils_dict_insert(parserutils_dict *dict,
+ const uint8_t *data, size_t len,
+ const parserutils_dict_entry **result);
+
+#endif
+
diff --git a/src/utils/Makefile b/src/utils/Makefile
index e053673..2ea94f2 100644
--- a/src/utils/Makefile
+++ b/src/utils/Makefile
@@ -35,7 +35,7 @@ d := $(DIR)
override CFLAGS := $(CFLAGS) -I$(d)
# Sources
-SRCS_$(d) := buffer.c errors.c
+SRCS_$(d) := buffer.c dict.c errors.c rbtree.c
# Append to sources for component
SOURCES += $(addprefix $(d), $(SRCS_$(d)))
diff --git a/src/utils/dict.c b/src/utils/dict.c
new file mode 100644
index 0000000..a9d5dd8
--- /dev/null
+++ b/src/utils/dict.c
@@ -0,0 +1,275 @@
+/*
+ * This file is part of LibParserUtils.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#include <assert.h>
+#include <string.h>
+
+#include <parserutils/utils/dict.h>
+
+#include "utils/rbtree.h"
+#include "utils/utils.h"
+
+/**
+ * A dictionary entry
+ */
+struct parserutils_dict_entry
+{
+ size_t len; /**< Length of data, in bytes */
+ uint8_t *data; /**< Entry data */
+};
+
+/**
+ * Dictionary object
+ */
+struct parserutils_dict
+{
+#define TABLE_SIZE (79)
+ parserutils_rbtree *table[TABLE_SIZE]; /**< Hashtable of entries */
+
+ parserutils_alloc alloc; /**< Memory (de)allocation function */
+ void *pw; /**< Client-specific data */
+};
+
+static inline uint32_t dict_hash(const uint8_t *data, size_t len);
+static int dict_cmp(const void *a, const void *b);
+static void dict_del(void *key, void *value, void *pw);
+
+/**
+ * Create a dictionary
+ *
+ * \param alloc Memory (de)allocation function
+ * \param pw Pointer to client-specific private data
+ * \return Pointer to dictionary instance, or NULL on memory exhaustion
+ */
+parserutils_dict *parserutils_dict_create(parserutils_alloc alloc, void *pw)
+{
+ parserutils_dict *dict;
+
+ if (alloc == NULL)
+ return NULL;
+
+ dict = alloc(NULL, sizeof(parserutils_dict), pw);
+ if (dict == NULL)
+ return NULL;
+
+ memset(dict->table, 0, TABLE_SIZE * sizeof(parserutils_rbtree *));
+
+ dict->alloc = alloc;
+ dict->pw = pw;
+
+ return dict;
+}
+
+/**
+ * Destroy a dictionary
+ *
+ * \param dict The dictionary instance to destroy
+ */
+void parserutils_dict_destroy(parserutils_dict *dict)
+{
+ for (int i = 0; i < TABLE_SIZE; i++) {
+ parserutils_rbtree_destroy(dict->table[i], dict_del, dict);
+ }
+
+ dict->alloc(dict, 0, dict->pw);
+}
+
+/**
+ * Insert an item into a dictionary
+ *
+ * \param dict The dictionary to insert into
+ * \param data Pointer to data
+ * \param len Length, in bytes, of data
+ * \param result Pointer to location to receive pointer to data in dictionary
+ */
+parserutils_error parserutils_dict_insert(parserutils_dict *dict,
+ const uint8_t *data, size_t len,
+ const parserutils_dict_entry **result)
+{
+ parserutils_error error;
+ parserutils_dict_entry *entry = NULL;
+ void *old_value;
+ uint32_t index;
+
+ if (dict == NULL || data == NULL || len == 0)
+ return PARSERUTILS_BADPARM;
+
+ index = dict_hash(data, len) % TABLE_SIZE;
+
+ if (dict->table[index] != NULL) {
+ parserutils_dict_entry search = { len, (uint8_t *) data };
+
+ error = parserutils_rbtree_find(dict->table[index],
+ (void *) &search, (void *) &entry);
+ if (error != PARSERUTILS_OK)
+ return error;
+
+ if (entry != NULL) {
+ *result = entry;
+ return PARSERUTILS_OK;
+ }
+ } else {
+ dict->table[index] = parserutils_rbtree_create(dict_cmp,
+ dict->alloc, dict->pw);
+ if (dict->table[index] == NULL)
+ return PARSERUTILS_NOMEM;
+ }
+
+ entry = dict->alloc(NULL, sizeof(parserutils_dict_entry) + len,
+ dict->pw);
+ if (entry == NULL)
+ return PARSERUTILS_NOMEM;
+
+ /* Do-it-yourself variable-sized data member (simplifies the
+ * manufacture of an entry to search for, above) */
+ memcpy(((uint8_t *) entry) + sizeof(parserutils_dict_entry), data, len);
+ entry->data = ((uint8_t *) entry) + sizeof(parserutils_dict_entry);
+ entry->len = len;
+
+ error = parserutils_rbtree_insert(dict->table[index], (void *) entry,
+ (void *) entry, &old_value);
+ if (error != PARSERUTILS_OK) {
+ dict->alloc(entry, 0, dict->pw);
+ return error;
+ }
+ assert(old_value == NULL);
+
+ *result = entry;
+
+ return PARSERUTILS_OK;
+}
+
+/**
+ * Hsieh hash function
+ *
+ * \param data Pointer to data to hash
+ * \param len Length, in bytes, of data
+ * \return hash value
+ */
+uint32_t dict_hash(const uint8_t *data, size_t len)
+{
+ uint32_t hash = len, tmp;
+ int rem = len & 3;
+
+#define read16(d) ((((uint32_t)((d)[1])) << 8) | ((uint32_t)((d)[0])))
+
+ for (len = len / 4; len > 0; len--) {
+ hash += read16(data);
+ tmp = (read16(data + 2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 4;
+ hash += hash >> 11;
+ }
+
+ switch (rem) {
+ case 3:
+ hash += read16(data);
+ hash ^= hash << 16;
+ hash ^= data[2] << 18;
+ hash += hash >> 11;
+ break;
+ case 2:
+ hash += read16(data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1:
+ hash += data[0];
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+#undef read16
+
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
+/**
+ * Comparison function for dictionary entries
+ *
+ * \param a First entry to consider
+ * \param b Second entry to consider
+ * \return <0 iff a<b, ==0 iff a=b, >0 iff a>b
+ */
+int dict_cmp(const void *a, const void *b)
+{
+ const parserutils_dict_entry *aa = (const parserutils_dict_entry *) a;
+ const parserutils_dict_entry *bb = (const parserutils_dict_entry *) b;
+ size_t min_len = min(aa->len, bb->len);
+ int result = 0;
+
+ if ((result = memcmp(aa->data, bb->data, min_len)) == 0) {
+ result = aa->len - bb->len;
+ }
+
+ return result;
+}
+
+/**
+ * Destructor for dictionary entries
+ *
+ * \param key Key
+ * \param value Value
+ * \param pw Dictionary instance
+ */
+void dict_del(void *key, void *value, void *pw)
+{
+ parserutils_dict *dict = (parserutils_dict *) pw;
+
+ UNUSED(value);
+
+ dict->alloc(key, 0, dict->pw);
+}
+
+#ifndef NDEBUG
+#include <stdio.h>
+
+extern void parserutils_dict_dump(parserutils_dict *dict);
+
+/**
+ * Print out a dictionary entry
+ *
+ * \param key The key
+ * \param value The value
+ * \param depth Depth in tree
+ */
+static void dict_print(const void *key, const void *value, int depth)
+{
+ const parserutils_dict_entry *e = (const parserutils_dict_entry *) key;
+
+ UNUSED(value);
+
+ while (depth-- > 0)
+ putchar(' ');
+
+ printf("'%.*s'\n", e->len, e->data);
+}
+
+/**
+ * Print out a dictionary
+ *
+ * \param dict The dictionary to print
+ */
+void parserutils_dict_dump(parserutils_dict *dict)
+{
+ if (dict == NULL)
+ return;
+
+ for (int i = 0; i < TABLE_SIZE; i++) {
+ printf("%d:\n", i);
+ parserutils_rbtree_dump(dict->table[i], dict_print);
+ }
+}
+#endif
+
diff --git a/src/utils/rbtree.c b/src/utils/rbtree.c
new file mode 100644
index 0000000..9bf1087
--- /dev/null
+++ b/src/utils/rbtree.c
@@ -0,0 +1,732 @@
+/*
+ * This file is part of LibParserUtils.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#include <assert.h>
+#ifndef NDEBUG
+#include <stdio.h>
+#endif
+
+#include <parserutils/errors.h>
+#include <parserutils/functypes.h>
+
+#include "utils/rbtree.h"
+
+/* Compile-time configuration */
+
+/* Define this to validate the tree structure after every insertion/deletion
+ * Note: this performs a complete tree traversal, so has a large performance
+ * impact */
+#undef RBTREE_VALIDATE
+
+/* Define this to use deleteMax() to destroy a tree.
+ * Uses deleteMin() if undefined. */
+#undef USE_DELETEMAX
+
+/**
+ * Node in an RB tree
+ */
+typedef struct rbnode
+{
+ struct rbnode *left; /**< Left subtree */
+ struct rbnode *right; /**< Right subtree */
+ enum { RED = true, BLACK = false } colour; /**< Colour of node */
+
+ void *key; /**< Node key */
+ void *value; /**< Node value */
+} rbnode;
+
+/**
+ * RB tree object
+ */
+struct parserutils_rbtree
+{
+ rbnode *root; /**< Root node of tree */
+
+ parserutils_rbtree_cmp cmp; /**< Key comparator */
+
+ parserutils_alloc alloc; /**< Memory (de)allocation function */
+ void *pw; /**< Pointer to client data */
+};
+
+static rbnode *rbtree_insert_internal(parserutils_rbtree *tree,
+ rbnode *current, void *key, void *value, void **oldvalue);
+static rbnode *rbtree_delete_internal(parserutils_rbtree *tree,
+ rbnode *current, const void *key, void **intkey, void **value);
+static inline rbnode *rbnode_create(parserutils_alloc alloc, void *pw,
+ void *key, void *value);
+static inline void rbnode_destroy(parserutils_alloc alloc, void *pw,
+ rbnode *node);
+static inline bool isRed(rbnode *node);
+static inline void colourFlip(rbnode *node);
+static inline rbnode *rotateLeft(rbnode *node);
+static inline rbnode *rotateRight(rbnode *node);
+static inline rbnode *moveRedLeft(rbnode *node);
+static inline rbnode *moveRedRight(rbnode *node);
+static inline rbnode *fixUp(rbnode *node);
+#ifdef USE_DELETEMAX
+static inline rbnode *deleteMax(parserutils_rbtree *tree, rbnode *node,
+ parserutils_rbtree_del destructor, void *pw);
+#else
+static inline rbnode *deleteMin(parserutils_rbtree *tree, rbnode *node,
+ parserutils_rbtree_del destructor, void *pw);
+#endif
+static inline rbnode *findMin(rbnode *node);
+
+#ifndef NDEBUG
+#ifdef RBTREE_VALIDATE
+static inline void verify_tree(rbnode *node);
+static inline rbnode *verify_tree_internal(rbnode *node);
+static inline void dump_tree_raw(rbnode *node, uint32_t depth);
+#endif
+static inline void dump_tree(rbnode *node, parserutils_rbtree_print print,
+ uint32_t depth);
+#endif
+
+/**
+ * Create a RB tree
+ *
+ * \param cmp Comparator routine for keys
+ * \param alloc Memory (de)allocation function
+ * \param pw Pointer to client-specific private data
+ * \return Pointer to tree instance, or NULL on memory exhaustion
+ */
+parserutils_rbtree *parserutils_rbtree_create(parserutils_rbtree_cmp cmp,
+ parserutils_alloc alloc, void *pw)
+{
+ parserutils_rbtree *tree;
+
+ if (cmp == NULL || alloc == NULL)
+ return NULL;
+
+ tree = alloc(NULL, sizeof(parserutils_rbtree), pw);
+ if (tree == NULL)
+ return NULL;
+
+ tree->root = NULL;
+ tree->cmp = cmp;
+ tree->alloc = alloc;
+ tree->pw = pw;
+
+ return tree;
+}
+
+/**
+ * Destroy an RB tree
+ *
+ * \param tree The tree to destroy
+ * \param destructor Routine to be called with key/value pairs to destroy
+ * \param pw Pointer to client-specific private data
+ */
+void parserutils_rbtree_destroy(parserutils_rbtree *tree,
+ parserutils_rbtree_del destructor, void *pw)
+{
+ if (tree == NULL)
+ return;
+
+ while (tree->root != NULL) {
+#ifndef USE_DELETEMAX
+ tree->root = deleteMin(tree, tree->root, destructor, pw);
+#else
+ tree->root = deleteMax(tree, tree->root, destructor, pw);
+#endif
+ if (tree->root != NULL)
+ tree->root->colour = BLACK;
+
+#if !defined(NDEBUG) && defined(RBTREE_VALIDATE)
+ verify_tree(tree->root);
+#endif
+ }
+
+ tree->alloc(tree, 0, tree->pw);
+}
+
+/**
+ * Insert into a RB tree
+ *
+ * \param tree The tree to insert into
+ * \param key The key to insert (not copied)
+ * \param value The value to insert (not copied)
+ * \param oldvalue Pointer to location to receive previous value for key
+ * \return PARSERUTILS_OK on success, appropriate error otherwise.
+ */
+parserutils_error parserutils_rbtree_insert(parserutils_rbtree *tree,
+ void *key, void *value, void **oldvalue)
+{
+ rbnode *temp;
+
+ if (tree == NULL || key == NULL || oldvalue == NULL)
+ return PARSERUTILS_BADPARM;
+
+ temp = rbtree_insert_internal(tree, tree->root, key,
+ value, oldvalue);
+ if (temp == NULL)
+ return PARSERUTILS_NOMEM;
+
+ temp->colour = BLACK;
+ tree->root = temp;
+
+#if !defined(NDEBUG) && defined(RBTREE_VALIDATE)
+ verify_tree(tree->root);
+#endif
+
+ return PARSERUTILS_OK;
+}
+
+/**
+ * Find an entry in a RB tree
+ *
+ * \param tree The tree to search in
+ * \param key The key to search for
+ * \param value Pointer to location to receive value for key
+ * \return PARSERUTILS_OK on success, appropriate error otherwise
+ */
+parserutils_error parserutils_rbtree_find(parserutils_rbtree *tree,
+ const void *key, void **value)
+{
+ rbnode *node;
+
+ if (tree == NULL || key == NULL || value == NULL)
+ return PARSERUTILS_BADPARM;
+
+ node = tree->root;
+ *value = NULL;
+
+ while (node != NULL) {
+ int cmp = tree->cmp(key, node->key);
+
+ if (cmp == 0) {
+ *value = node->value;
+ break;
+ } else if (cmp < 0) {
+ node = node->left;
+ } else {
+ node = node->right;
+ }
+ }
+
+ return PARSERUTILS_OK;
+}
+
+/**
+ * Delete an entry from a RB tree
+ *
+ * \param tree The tree to delete from
+ * \param key The key to delete
+ * \param intkey Pointer to location to receive key
+ * \param value Pointer to location to receive value
+ * \return PARSERUTILS_OK on success, appropriate error otherwise
+ */
+parserutils_error parserutils_rbtree_delete(parserutils_rbtree *tree,
+ const void *key, void **intkey, void **value)
+{
+ rbnode *temp;
+
+ if (tree == NULL || key == NULL || intkey == NULL || value == NULL)
+ return PARSERUTILS_BADPARM;
+
+ if (tree->root == NULL) {
+ *intkey = NULL;
+ *value = NULL;
+ return PARSERUTILS_OK;
+ }
+
+ temp = rbtree_delete_internal(tree, tree->root, key, intkey, value);
+ if (temp != NULL)
+ temp->colour = BLACK;
+ tree->root = temp;
+
+#if !defined(NDEBUG) && defined(RBTREE_VALIDATE)
+ verify_tree(tree->root);
+#endif
+
+ return PARSERUTILS_OK;
+}
+
+/**
+ * Helper function for tree insertion
+ *
+ * \param tree Tree to insert into
+ * \param current The root of the current subtree
+ * \param key Key to insert (not copied)
+ * \param value Value to insert (not copied)
+ * \param oldvalue Pointer to location to receive old value for key
+ * \return Pointer to new root of current subtree
+ */
+rbnode *rbtree_insert_internal(parserutils_rbtree *tree, rbnode *current,
+ void *key, void *value, void **oldvalue)
+{
+ if (current == NULL) {
+ rbnode *node = rbnode_create(tree->alloc, tree->pw, key, value);
+ if (node == NULL)
+ return NULL;
+
+ *oldvalue = NULL;
+
+ return node;
+ }
+
+ /* Split 4-nodes */
+ if (isRed(current->left) && isRed(current->right))
+ colourFlip(current);
+
+ int cmp = tree->cmp(key, current->key);
+
+ if (cmp == 0) {
+ *oldvalue = current->value;
+ current->value = value;
+ } else if (cmp < 0) {
+ rbnode *temp = rbtree_insert_internal(tree, current->left,
+ key, value, oldvalue);
+ if (temp == NULL)
+ return NULL;
+ current->left = temp;
+ } else {
+ rbnode *temp = rbtree_insert_internal(tree, current->right,
+ key, value, oldvalue);
+ if (temp == NULL)
+ return NULL;
+ current->right = temp;
+ }
+
+ /* Eliminate right-leaning 3-nodes by rotating left */
+ if (isRed(current->right))
+ current = rotateLeft(current);
+
+ /* Balance 4-nodes by rotating right */
+ if (isRed(current->left) && isRed(current->left->left))
+ current = rotateRight(current);
+
+ return current;
+}
+
+/**
+ * Helper function for tree deletion
+ *
+ * \param tree Tree to delete from
+ * \param current Root node of current subtree
+ * \param key Key to delete
+ * \param intkey Pointer to location to receive key
+ * \param value Pointer to location to receive value
+ * \return Pointer to new root node for current subtree
+ */
+rbnode *rbtree_delete_internal(parserutils_rbtree *tree, rbnode *current,
+ const void *key, void **intkey, void **value)
+{
+ int cmp;
+
+ if (current == NULL)
+ return NULL;
+
+ cmp = tree->cmp(key, current->key);
+
+ if (cmp < 0) {
+ if (current->left != NULL && !isRed(current->left) &&
+ !isRed(current->left->left))
+ current = moveRedLeft(current);
+ current->left = rbtree_delete_internal(tree, current->left,
+ key, intkey, value);
+ } else {
+ if (isRed(current->left))
+ current = rotateRight(current);
+
+ if (cmp == 0 && current->right == NULL) {
+ *intkey = current->key;
+ *value = current->value;
+
+ rbnode_destroy(tree->alloc, tree->pw, current);
+ return NULL;
+ }
+
+ if (current->right != NULL && !isRed(current->right) &&
+ !isRed(current->right->left))
+ current = moveRedRight(current);
+
+ /* Must recalculate here, as current may have changed */
+ if (tree->cmp(key, current->key) == 0) {
+ *intkey = current->key;
+ *value = current->value;
+
+ rbnode *successor = findMin(current->right);
+
+ current->value = successor->value;
+ current->key = successor->key;
+
+ current->right = deleteMin(tree, current->right,
+ NULL, NULL);
+ } else {
+ current->right = rbtree_delete_internal(tree,
+ current->right, key, intkey, value);
+ }
+ }
+
+ return fixUp(current);
+}
+
+/**
+ * Create a RB node
+ *
+ * \param alloc Memory (de)allocation function
+ * \param pw Pointer to client-specific private data
+ * \param key Key for node (not copied)
+ * \param value Value for node (not copied)
+ * \return Pointer to node, or NULL on memory exhaustion
+ */
+rbnode *rbnode_create(parserutils_alloc alloc, void *pw, void *key, void *value)
+{
+ rbnode *node = alloc(NULL, sizeof(rbnode), pw);
+ if (node == NULL)
+ return NULL;
+
+ node->left = NULL;
+ node->right = NULL;
+ node->colour = RED;
+ node->key = key;
+ node->value = value;
+
+ return node;
+}
+
+/**
+ * Destroy a RB node
+ *
+ * \param alloc Memory (de)allocation function
+ * \param pw Pointer to client-specific private data
+ * \param node The node to destroy
+ */
+void rbnode_destroy(parserutils_alloc alloc, void *pw, rbnode *node)
+{
+ alloc(node, 0, pw);
+}
+
+/**
+ * Determine if a given node is red
+ *
+ * \param node The node to consider
+ * \return True if node is red, false otherwise
+ */
+bool isRed(rbnode *node)
+{
+ if (node == NULL)
+ return false;
+
+ return node->colour == RED;
+}
+
+/**
+ * Flip the colours for a node
+ *
+ * \param node The node to consider
+ */
+void colourFlip(rbnode *node)
+{
+ node->colour = !node->colour;
+ if (node->left != NULL)
+ node->left->colour = !node->left->colour;
+ if (node->right != NULL)
+ node->right->colour = !node->right->colour;
+}
+
+/**
+ * Rotate a node left
+ *
+ * \param node The node to rotate
+ * \return The new root of the subtree
+ */
+rbnode *rotateLeft(rbnode *node)
+{
+ rbnode *r = node->right;
+
+ node->right = r->left;
+ r->left = node;
+ r->colour = node->colour;
+ node->colour = RED;
+
+ return r;
+}
+
+/**
+ * Rotate a node right
+ *
+ * \param node The node to rotate
+ * \return The new root of the subtree
+ */
+rbnode *rotateRight(rbnode *node)
+{
+ rbnode *l = node->left;
+
+ node->left = l->right;
+ l->right = node;
+ l->colour = node->colour;
+ node->colour = RED;
+
+ return l;
+}
+
+/**
+ * Move a red node left
+ *
+ * \param node Root of subtree to manipulate
+ * \return New root of subtree
+ */
+rbnode *moveRedLeft(rbnode *node)
+{
+ colourFlip(node);
+
+ if (node->right != NULL && isRed(node->right->left)) {
+ node->right = rotateRight(node->right);
+ node = rotateLeft(node);
+ colourFlip(node);
+
+ /* Maintain left-leaning requirement for 3-nodes after
+ * we've just split a 4-node */
+ if (node->right != NULL && isRed(node->right->right)) {
+ node->right = rotateLeft(node->right);
+ }
+ }
+
+ return node;
+}
+
+/**
+ * Move a red node right
+ *
+ * \param node Root of subtree to manipulate
+ * \return New root of subtree
+ */
+rbnode *moveRedRight(rbnode *node)
+{
+ colourFlip(node);
+
+ if (node->left != NULL && isRed(node->left->left)) {
+ node = rotateRight(node);
+ colourFlip(node);
+ }
+
+ return node;
+}
+
+/**
+ * Fix right-leaning red links
+ *
+ * \param node Root of subtree to manipulate
+ * \return New root of subtree
+ */
+rbnode *fixUp(rbnode *node)
+{
+ if (node->right != NULL && isRed(node->right))
+ node = rotateLeft(node);
+
+ if (node->left != NULL && isRed(node->left)) {
+ /* Two red links in a row aren't permitted */
+ if (node->left->left != NULL && isRed(node->left->left)) {
+ node = rotateRight(node);
+ } else if (node->left->right != NULL &&
+ isRed(node->left->right)) {
+ node->left = rotateLeft(node->left);
+ /* Force left child colour to black (it can only have
+ * been red before). We can't use colourFlip() here, as
+ * it will potentially break the right-hand subtree. */
+ node->left->colour = BLACK;
+ }
+ }
+
+ if (isRed(node->left) && isRed(node->right))
+ colourFlip(node);
+
+ return node;
+}
+
+#ifdef USE_DELETEMAX
+/**
+ * Delete the right-most node in a tree
+ *
+ * \param tree The tree instance
+ * \param node Root of subtree to manipulate
+ * \param destructor Destructor routine, or NULL
+ * \param pw Pointer to client-specific private data
+ * \return New root of subtree
+ */
+rbnode *deleteMax(parserutils_rbtree *tree, rbnode *node,
+ parserutils_rbtree_del destructor, void *pw)
+{
+ if (isRed(node->left))
+ node = rotateRight(node);
+
+ if (node->right == NULL) {
+ if (destructor != NULL)
+ destructor(node->key, node->value, pw);
+ rbnode_destroy(tree->alloc, tree->pw, node);
+ return NULL;
+ }
+
+ if (!isRed(node->right) && !isRed(node->right->left))
+ node = moveRedRight(node);
+
+ assert(isRed(node->right) || isRed(node->right->left) ||
+ isRed(node->right->right));
+
+ node->right = deleteMax(tree, node->right, destructor, pw);
+
+ return fixUp(node);
+}
+#else
+/**
+ * Delete the left-most node in a tree
+ *
+ * \param tree The tree instance
+ * \param node Root of subtree to manipulate
+ * \param destructor Destructor routine, or NULL
+ * \param pw Pointer to client-specific private data
+ * \return New root of subtree
+ */
+rbnode *deleteMin(parserutils_rbtree *tree, rbnode *node,
+ parserutils_rbtree_del destructor, void *pw)
+{
+ if (node->left == NULL) {
+ if (destructor != NULL)
+ destructor(node->key, node->value, pw);
+ rbnode_destroy(tree->alloc, tree->pw, node);
+ return NULL;
+ }
+
+ if (!isRed(node->left) && !isRed(node->left->left))
+ node = moveRedLeft(node);
+
+ assert(isRed(node->left) || isRed(node->left->left));
+
+ node->left = deleteMin(tree, node->left, destructor, pw);
+
+ return fixUp(node);
+}
+#endif
+
+/**
+ * Find the left-most node in a tree
+ *
+ * \param node Root of the subtree to consider
+ * \return Left-most node
+ */
+rbnode *findMin(rbnode *node)
+{
+ while (node->left != NULL)
+ node = node->left;
+
+ return node;
+}
+
+#ifndef NDEBUG
+#ifdef RBTREE_VALIDATE
+/**
+ * Verify the correctness of a tree
+ *
+ * \param node Root of tree to verify
+ */
+void verify_tree(rbnode *node)
+{
+ rbnode *invalid;
+
+ if ((invalid = verify_tree_internal(node)) != NULL) {
+ dump_tree_raw(node, 0);
+ printf("Invalid node: %p\n", (void *) invalid);
+ assert(0 && "RB invariant violated");
+ }
+}
+
+/**
+ * Verify the structure of an RB tree
+ *
+ * \param node Root node of tree to validate
+ * \return Pointer to invalid node, or NULL
+ */
+rbnode *verify_tree_internal(rbnode *node)
+{
+ rbnode *invalid;
+
+ if (node == NULL)
+ return NULL;
+
+ if (isRed(node) && (isRed(node->left) || isRed(node->right))) {
+ return node;
+ }
+
+ if (isRed(node->right) && !isRed(node->left)) {
+ return node;
+ }
+
+ if (isRed(node->left) && isRed(node->left->left)) {
+ return node;
+ }
+
+ if (isRed(node->right) && isRed(node->right->right)) {
+ return node;
+ }
+
+ if ((invalid = verify_tree_internal(node->left)) != NULL)
+ return invalid;
+
+ if ((invalid = verify_tree_internal(node->right)) != NULL)
+ return invalid;
+
+ return NULL;
+}
+
+/**
+ * Dump a tree to stdout in raw format
+ *
+ * \param node Root of tree to dump
+ * \param depth Current node depth
+ */
+void dump_tree_raw(rbnode *node, uint32_t depth)
+{
+ if (node->right)
+ dump_tree_raw(node->right, depth + 1);
+
+ for (uint32_t i = 0; i < depth; i++)
+ putchar(' ');
+
+ printf("%p %p %p [%c]\n", (void *) node, node->key, node->value,
+ isRed(node) ? 'r' : 'b');
+
+ if (node->left)
+ dump_tree_raw(node->left, depth + 1);
+}
+#endif
+
+/**
+ * Recursively print out a pre-order traversal of a RB tree
+ *
+ * \param node Root node of subtree
+ * \param print Print routine
+ * \param depth Current depth in tree
+ */
+void dump_tree(rbnode *node, parserutils_rbtree_print print, uint32_t depth)
+{
+ if (node->right)
+ dump_tree(node->right, print, depth + 1);
+
+ print(node->key, node->value, depth);
+
+ if (node->left)
+ dump_tree(node->left, print, depth + 1);
+}
+
+/**
+ * Print out a RB tree
+ *
+ * \param tree The tree to print
+ * \param print Print routine
+ */
+void parserutils_rbtree_dump(parserutils_rbtree *tree,
+ parserutils_rbtree_print print)
+{
+ if (tree == NULL || tree->root == NULL)
+ return;
+
+ dump_tree(tree->root, print, 0);
+}
+#endif
+
diff --git a/src/utils/rbtree.h b/src/utils/rbtree.h
new file mode 100644
index 0000000..0225c92
--- /dev/null
+++ b/src/utils/rbtree.h
@@ -0,0 +1,40 @@
+/*
+ * This file is part of LibParserUtils.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org>
+ */
+
+#ifndef parserutils_utils_rbtree_h_
+#define parserutils_utils_rbtree_h_
+
+#include <parserutils/errors.h>
+#include <parserutils/functypes.h>
+
+struct parserutils_rbtree;
+typedef struct parserutils_rbtree parserutils_rbtree;
+
+typedef int (*parserutils_rbtree_cmp)(const void *a, const void *b);
+typedef void (*parserutils_rbtree_del)(void *key, void *value, void *pw);
+typedef void (*parserutils_rbtree_print)(const void *key, const void *value,
+ int depth);
+
+parserutils_rbtree *parserutils_rbtree_create(parserutils_rbtree_cmp cmp,
+ parserutils_alloc alloc, void *pw);
+void parserutils_rbtree_destroy(parserutils_rbtree *tree,
+ parserutils_rbtree_del destructor, void *pw);
+
+parserutils_error parserutils_rbtree_insert(parserutils_rbtree *tree,
+ void *key, void *value, void **oldvalue);
+parserutils_error parserutils_rbtree_find(parserutils_rbtree *tree,
+ const void *key, void **value);
+parserutils_error parserutils_rbtree_delete(parserutils_rbtree *tree,
+ const void *key, void **intkey, void **value);
+
+#ifndef NDEBUG
+void parserutils_rbtree_dump(parserutils_rbtree *tree,
+ parserutils_rbtree_print print);
+#endif
+
+#endif
+
diff --git a/test/INDEX b/test/INDEX
index 772c82f..0042c36 100644
--- a/test/INDEX
+++ b/test/INDEX
@@ -6,6 +6,8 @@ charset Charset initialisation/finalisation
parserutils Library initialisation/finalisation
aliases Encoding alias handling
cscodec Charset codec implementation cscodec
+dict Dictionary handling
+rbtree Red-black tree implementation
filter Input stream filtering
inputstream Inputstream handling input
diff --git a/test/Makefile b/test/Makefile
index 2ed0b44..4c5caac 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -35,7 +35,8 @@ d := $(DIR)
override CFLAGS := $(CFLAGS) -I$(TOP)/src/ -I$(d)
# Tests
-TESTS_$(d) := aliases cscodec charset filter inputstream parserutils
+TESTS_$(d) := aliases cscodec charset dict filter inputstream parserutils \
+ rbtree
TESTS_$(d) := $(TESTS_$(d)) regression/cscodec-segv regression/filter-segv \
regression/stream-nomem
diff --git a/test/dict.c b/test/dict.c
new file mode 100644
index 0000000..ee8c597
--- /dev/null
+++ b/test/dict.c
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <parserutils/utils/dict.h>
+
+#include "testutils.h"
+
+extern void parserutils_dict_dump(parserutils_dict *dict);
+
+static void *myrealloc(void *ptr, size_t len, void *pw)
+{
+ UNUSED(pw);
+
+ return realloc(ptr, len);
+}
+
+int main(int argc, char **argv)
+{
+ parserutils_dict *dict;
+ uint8_t buf[256];
+
+ UNUSED(argc);
+ UNUSED(argv);
+
+ /* Seed buffer with printable ascii */
+ for (int i = 0; i < (int) sizeof(buf); i++) {
+ buf[i] = 97 + (int) (26.0 * (rand() / (RAND_MAX + 1.0)));
+ }
+ buf[sizeof(buf) - 1] = '\0';
+
+ dict = parserutils_dict_create(myrealloc, NULL);
+ assert(dict != NULL);
+
+ for (int i = 0; i < (int) sizeof(buf); i++) {
+ uint8_t *s = buf;
+
+ while (s - buf <= i) {
+ const parserutils_dict_entry *e;
+
+ parserutils_dict_insert(dict,
+ s, (size_t) (sizeof(buf) - i), &e);
+
+ s++;
+ }
+ }
+
+ parserutils_dict_destroy(dict);
+
+ printf("PASS\n");
+
+ return 0;
+}
+
diff --git a/test/rbtree.c b/test/rbtree.c
new file mode 100644
index 0000000..4179561
--- /dev/null
+++ b/test/rbtree.c
@@ -0,0 +1,87 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "utils/rbtree.h"
+
+#include "testutils.h"
+
+static void *myrealloc(void *ptr, size_t len, void *pw)
+{
+ UNUSED(pw);
+
+ return realloc(ptr, len);
+}
+
+static int mycmp(const void *a, const void *b)
+{
+ return ((const uint32_t) a) - ((const uint32_t) b);
+}
+
+int main(int argc, char **argv)
+{
+ parserutils_rbtree *tree;
+
+ UNUSED(argc);
+ UNUSED(argv);
+
+ tree = parserutils_rbtree_create(mycmp, myrealloc, NULL);
+ assert(tree != NULL);
+
+#define N 40000
+#define G 307
+//#define N 400
+//#define G 7
+
+ printf("Inserting %d items\n", N);
+
+ for (int i = G, count = 1; i != 0; i = (i + G) % N, count++) {
+ void *old;
+ assert(parserutils_rbtree_insert(tree, (void *) i, (void *) i,
+ &old) == PARSERUTILS_OK);
+
+ if ((count % 10000) == 0)
+ printf("%d\n", count);
+ }
+
+ printf("Removing %d items\n", N/2);
+
+ for (int i = 1, count = 1; i < N; i += 2, count++) {
+ void *key, *value;
+ assert(parserutils_rbtree_delete(tree, (void *) i, &key,
+ &value) == PARSERUTILS_OK);
+ if ((count % 10000) == 0)
+ printf("%d\n", count);
+ }
+
+ printf("Finding %d items\n", N/2);
+
+ for (int i = 2, count = 1; i < N; i += 2, count++) {
+ void *value = NULL;
+ assert(parserutils_rbtree_find(tree, (void *) i, &value) ==
+ PARSERUTILS_OK);
+ assert(value != NULL && ((int) value) == i);
+ if ((count % 10000) == 0)
+ printf("%d\n", count);
+ }
+
+ printf("Verifying & removing %d items\n", N/2);
+
+ for (int i = 1, count = 1; i < N; i += 2, count++) {
+ void *key, *value = NULL;
+ assert(parserutils_rbtree_find(tree, (void *) i, &value) ==
+ PARSERUTILS_OK);
+ assert(value == NULL);
+ assert(parserutils_rbtree_delete(tree, (void *) i,
+ &key, &value) == PARSERUTILS_OK);
+ if ((count % 10000) == 0)
+ printf("%d\n", count);
+ }
+
+ parserutils_rbtree_destroy(tree, NULL, NULL);
+
+ printf("PASS\n");
+
+ return 0;
+}
+