From 419e9a6766e9676fc1905291eeccaf655c8d5b09 Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Sat, 10 May 2008 00:16:42 +0000 Subject: Have some generic dictionary implementation. Even comes with testcases, which is nice. svn path=/trunk/libparserutils/; revision=4138 --- include/parserutils/utils/dict.h | 28 ++ src/utils/Makefile | 2 +- src/utils/dict.c | 275 +++++++++++++++ src/utils/rbtree.c | 732 +++++++++++++++++++++++++++++++++++++++ src/utils/rbtree.h | 40 +++ test/INDEX | 2 + test/Makefile | 3 +- test/dict.c | 54 +++ test/rbtree.c | 87 +++++ 9 files changed, 1221 insertions(+), 2 deletions(-) create mode 100644 include/parserutils/utils/dict.h create mode 100644 src/utils/dict.c create mode 100644 src/utils/rbtree.c create mode 100644 src/utils/rbtree.h create mode 100644 test/dict.c create mode 100644 test/rbtree.c 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 + */ + +#ifndef parserutils_utils_dict_h_ +#define parserutils_utils_dict_h_ + +#include +#include + +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 + */ + +#include +#include + +#include + +#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 a0 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 + +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 + */ + +#include +#ifndef NDEBUG +#include +#endif + +#include +#include + +#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 + */ + +#ifndef parserutils_utils_rbtree_h_ +#define parserutils_utils_rbtree_h_ + +#include +#include + +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 +#include +#include + +#include + +#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 +#include +#include + +#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; +} + -- cgit v1.2.3