From bf44aeaf5cd7f03d3bd842c8046b7346c5035f06 Mon Sep 17 00:00:00 2001 From: Daniel Silverstone Date: Sat, 14 Feb 2009 19:18:33 +0000 Subject: Remove dict, hash and rbtree from libparserutils svn path=/trunk/libparserutils/; revision=6512 --- include/parserutils/utils/dict.h | 36 -- include/parserutils/utils/hash.h | 31 -- src/utils/Makefile | 3 +- src/utils/dict.c | 283 --------------- src/utils/hash.c | 316 ----------------- src/utils/rbtree.c | 742 --------------------------------------- src/utils/rbtree.h | 40 --- test/INDEX | 3 - test/Makefile | 2 +- test/dict.c | 54 --- test/hash.c | 56 --- test/rbtree.c | 88 ----- 12 files changed, 2 insertions(+), 1652 deletions(-) delete mode 100644 include/parserutils/utils/dict.h delete mode 100644 include/parserutils/utils/hash.h delete mode 100644 src/utils/dict.c delete mode 100644 src/utils/hash.c delete mode 100644 src/utils/rbtree.c delete mode 100644 src/utils/rbtree.h delete mode 100644 test/dict.c delete mode 100644 test/hash.c delete mode 100644 test/rbtree.c diff --git a/include/parserutils/utils/dict.h b/include/parserutils/utils/dict.h deleted file mode 100644 index ac6050c..0000000 --- a/include/parserutils/utils/dict.h +++ /dev/null @@ -1,36 +0,0 @@ -/* - * 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 - -/** - * A dictionary entry - */ -struct parserutils_dict_entry -{ - size_t len; /**< Length of data, in bytes */ - uint8_t *data; /**< Entry data */ -}; -typedef struct parserutils_dict_entry parserutils_dict_entry; - -struct parserutils_dict; -typedef struct parserutils_dict parserutils_dict; - -parserutils_error parserutils_dict_create(parserutils_alloc alloc, void *pw, - parserutils_dict **dict); -parserutils_error 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/include/parserutils/utils/hash.h b/include/parserutils/utils/hash.h deleted file mode 100644 index 92f0236..0000000 --- a/include/parserutils/utils/hash.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * 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_hash_h_ -#define parserutils_utils_hash_h_ - -#include -#include - -typedef struct parserutils_hash_entry { - uint16_t len; - const uint8_t data[]; -} parserutils_hash_entry; - -struct parserutils_hash; -typedef struct parserutils_hash parserutils_hash; - -parserutils_error parserutils_hash_create(parserutils_alloc alloc, void *pw, - parserutils_hash **hash); -parserutils_error parserutils_hash_destroy(parserutils_hash *hash); - -parserutils_error parserutils_hash_insert(parserutils_hash *hash, - const uint8_t *data, uint16_t len, - const parserutils_hash_entry **inserted); - -#endif - diff --git a/src/utils/Makefile b/src/utils/Makefile index f32ef72..ba978be 100644 --- a/src/utils/Makefile +++ b/src/utils/Makefile @@ -35,8 +35,7 @@ d := $(DIR) CFLAGS := $(CFLAGS) -I$(d) # Sources -SRCS_$(d) := chunkarray.c buffer.c dict.c errors.c hash.c rbtree.c stack.c \ - vector.c +SRCS_$(d) := chunkarray.c buffer.c errors.c stack.c vector.c # Append to sources for component SOURCES += $(addprefix $(d), $(SRCS_$(d))) diff --git a/src/utils/dict.c b/src/utils/dict.c deleted file mode 100644 index b4ee11a..0000000 --- a/src/utils/dict.c +++ /dev/null @@ -1,283 +0,0 @@ -/* - * 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" - -/** - * 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 - * \param dict Pointer to location to receive dictionary instance - * \return PARSERUTILS_OK on success, - * PARSERUTILS_NOMEM on memory exhaustion, - * PARSERUTILS_BADPARM on bad parameters. - */ -parserutils_error parserutils_dict_create(parserutils_alloc alloc, void *pw, - parserutils_dict **dict) -{ - parserutils_dict *d; - - if (alloc == NULL || dict == NULL) - return PARSERUTILS_BADPARM; - - d = alloc(NULL, sizeof(parserutils_dict), pw); - if (d == NULL) - return PARSERUTILS_NOMEM; - - memset(d->table, 0, TABLE_SIZE * sizeof(parserutils_rbtree *)); - - d->alloc = alloc; - d->pw = pw; - - *dict = d; - - return PARSERUTILS_OK; -} - -/** - * Destroy a dictionary - * - * \param dict The dictionary instance to destroy - * \return CSS_OK on success, appropriate error otherwise - */ -parserutils_error parserutils_dict_destroy(parserutils_dict *dict) -{ - int i; - if (dict == NULL) - return PARSERUTILS_BADPARM; - - for (i = 0; i < TABLE_SIZE; i++) { - parserutils_rbtree_destroy(dict->table[i], dict_del, dict); - } - - dict->alloc(dict, 0, dict->pw); - - return PARSERUTILS_OK; -} - -/** - * 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; - search.len = len; - search.data = (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 { - error = parserutils_rbtree_create(dict_cmp, - dict->alloc, dict->pw, &dict->table[index]); - if (error != PARSERUTILS_OK) - return error; - } - - 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; - int result = aa->len - bb->len; - - /* Sort first by length, and then by data equality */ - if (result == 0) { - result = memcmp(aa->data, bb->data, aa->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", (int)e->len, e->data); -} - -/** - * Print out a dictionary - * - * \param dict The dictionary to print - */ -void parserutils_dict_dump(parserutils_dict *dict) -{ - int i; - - if (dict == NULL) - return; - - for (i = 0; i < TABLE_SIZE; i++) { - printf("%d:\n", i); - parserutils_rbtree_dump(dict->table[i], dict_print); - } -} -#endif - diff --git a/src/utils/hash.c b/src/utils/hash.c deleted file mode 100644 index aa01137..0000000 --- a/src/utils/hash.c +++ /dev/null @@ -1,316 +0,0 @@ -/* - * 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/chunkarray.h" - -typedef struct slot_table slot_table; - -struct parserutils_hash { - slot_table *slots; - - parserutils_chunkarray *data; - - parserutils_alloc alloc; - void *pw; -}; - -struct slot_table { -#define DEFAULT_SLOTS (1<<6) - size_t n_slots; - size_t n_used; - - const parserutils_chunkarray_entry *slots[]; -}; - -static inline uint32_t _hash(const uint8_t *data, size_t len); -static inline int _cmp(const uint8_t *a, size_t alen, - const uint8_t *b, size_t blen); -static inline void grow_slots(parserutils_hash *hash); - -/** - * Create a hash - * - * \param alloc Memory (de)allocation function - * \param pw Pointer to client-specific private data - * \param hash Pointer to location to receive result - * \return PARSERUTILS_OK on success, appropriate error otherwise - */ -parserutils_error parserutils_hash_create(parserutils_alloc alloc, void *pw, - parserutils_hash **hash) -{ - parserutils_hash *h; - parserutils_error error; - - if (alloc == NULL || hash == NULL) - return PARSERUTILS_BADPARM; - - h = alloc(0, sizeof(parserutils_hash), pw); - if (h == NULL) - return PARSERUTILS_NOMEM; - - h->slots = alloc(0, sizeof(slot_table) + - DEFAULT_SLOTS * sizeof(parserutils_chunkarray_entry *), - pw); - if (h->slots == NULL) { - alloc(h, 0, pw); - return PARSERUTILS_NOMEM; - } - - memset(h->slots, 0, sizeof(slot_table) + - DEFAULT_SLOTS * sizeof(parserutils_chunkarray_entry *)); - h->slots->n_slots = DEFAULT_SLOTS; - - error = parserutils_chunkarray_create(alloc, pw, &h->data); - if (error != PARSERUTILS_OK) { - alloc(h->slots, 0, pw); - alloc(h, 0, pw); - return error; - } - - h->alloc = alloc; - h->pw = pw; - - *hash = h; - - return PARSERUTILS_OK; -} - -/** - * Destroy a hash - * - * \param hash The hash to destroy - * \return PARSERUTILS_OK on success, appropriate error otherwise - */ -parserutils_error parserutils_hash_destroy(parserutils_hash *hash) -{ - if (hash == NULL) - return PARSERUTILS_BADPARM; - - parserutils_chunkarray_destroy(hash->data); - - hash->alloc(hash->slots, 0, hash->pw); - - hash->alloc(hash, 0, hash->pw); - - return PARSERUTILS_OK; -} - -/** - * Insert an item into a hash - * - * \param hash The hash to insert into - * \param data Pointer to data - * \param len Length, in bytes, of data - * \param inserted Pointer to location to receive pointer to data in hash - * \return PARSERUTILS_OK on success, appropriate error otherwise - */ -parserutils_error parserutils_hash_insert(parserutils_hash *hash, - const uint8_t *data, uint16_t len, - const parserutils_hash_entry **inserted) -{ - uint32_t index, mask; - slot_table *slots; - const parserutils_chunkarray_entry **entries; - const parserutils_chunkarray_entry *entry; - parserutils_error error; - - if (hash == NULL || data == NULL || inserted == NULL) - return PARSERUTILS_BADPARM; - - slots = hash->slots; - entries = slots->slots; - - /* Find index */ - mask = slots->n_slots - 1; - index = _hash(data, len) & mask; - - /* Use linear probing to resolve collisions */ - while ((entry = entries[index]) != NULL) { - /* If this data is already in the hash, return it */ - if (_cmp(data, len, entry->data, entry->length) == 0) { - (*inserted) = (const parserutils_hash_entry *) entry; - return PARSERUTILS_OK; - } - - index = (index + 1) & mask; - } - - /* The data isn't in the hash. Index identifies the slot to use */ - error = parserutils_chunkarray_insert(hash->data, data, len, &entry); - if (error != PARSERUTILS_OK) - return error; - - entries[index] = entry; - (*inserted) = (const parserutils_hash_entry *) entry; - - /* If the table is 75% full, then increase its size */ - if (++slots->n_used >= (slots->n_slots >> 1) + (slots->n_slots >> 2)) - grow_slots(hash); - - return PARSERUTILS_OK; -} - -/****************************************************************************** - * Private functions * - ******************************************************************************/ - -/** - * Hsieh hash function - * - * \param data Pointer to data to hash - * \param len Length, in bytes, of data - * \return hash value - */ -uint32_t _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 >> 2; 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; -} - -/** - * Comparator for hash entries - * - * \param a First item to consider - * \param alen Length, in bytes, of a - * \param b Second item to consider - * \param blen Length, in bytes, of b - * \return <0 iff a0 iff a>b - */ -int _cmp(const uint8_t *a, size_t alen, const uint8_t *b, size_t blen) -{ - int result; - - /* Check for identity first */ - if (a == b) - return 0; - - /* Sort first by length, then by data equality */ - if ((result = alen - blen) == 0) - result = memcmp(a, b, alen); - - return result; -} - -/** - * Increase the size of the slot table - * - * \param hash The hash to process - */ -void grow_slots(parserutils_hash *hash) -{ - slot_table *s; - size_t new_size; - - if (hash == NULL) - return; - - new_size = hash->slots->n_slots << 1; - - /* Create new slot table */ - s = hash->alloc(0, sizeof(slot_table) + - new_size * sizeof(parserutils_chunkarray_entry *), - hash->pw); - if (s == NULL) - return; - - memset(s, 0, sizeof(slot_table) + - new_size * sizeof(parserutils_chunkarray_entry *)); - s->n_slots = new_size; - - /* Now, populate it with the contents of the current one */ - for (uint32_t i = 0; i < hash->slots->n_slots; i++) { - const parserutils_chunkarray_entry *e = hash->slots->slots[i]; - - if (e == NULL) - continue; - - /* Find new index */ - uint32_t mask = s->n_slots - 1; - uint32_t index = _hash(e->data, e->length) & mask; - - /* Use linear probing to resolve collisions */ - while (s->slots[index] != NULL) - index = (index + 1) & mask; - - /* Insert into new slot table */ - s->slots[index] = e; - s->n_used++; - } - - /* Destroy current table, and replace it with the new one */ - hash->alloc(hash->slots, 0, hash->pw); - hash->slots = s; - - return; -} - -extern void parserutils_chunkarray_dump(parserutils_chunkarray *array); -extern void parserutils_hash_dump(parserutils_hash *hash); - -/** - * Dump details of a hash to stdout - * - * \param hash The hash to dump - */ -void parserutils_hash_dump(parserutils_hash *hash) -{ - printf("%zu slots used (of %zu => %f%%)\n", hash->slots->n_used, - hash->slots->n_slots, - hash->slots->n_used * 100 / (float) hash->slots->n_slots); - - printf("Data:\n"); - parserutils_chunkarray_dump(hash->data); - - printf("Hash structures: %zu\n", - sizeof(parserutils_hash) + sizeof(slot_table) + - hash->slots->n_slots * sizeof(parserutils_chunkarray_entry *)); -} - diff --git a/src/utils/rbtree.c b/src/utils/rbtree.c deleted file mode 100644 index 4fd3c23..0000000 --- a/src/utils/rbtree.c +++ /dev/null @@ -1,742 +0,0 @@ -/* - * 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 - * \param tree Pointer to location to receive tree instance - * \return PARSERUTILS_OK on success, - * PARSERUTILS_BADPARM on bad parameters, - * PARSERUTILS_NOMEM on memory exhaustion - */ -parserutils_error parserutils_rbtree_create(parserutils_rbtree_cmp cmp, - parserutils_alloc alloc, void *pw, parserutils_rbtree **tree) -{ - parserutils_rbtree *t; - - if (cmp == NULL || alloc == NULL || tree == NULL) - return PARSERUTILS_BADPARM; - - t = alloc(NULL, sizeof(parserutils_rbtree), pw); - if (t == NULL) - return PARSERUTILS_NOMEM; - - t->root = NULL; - t->cmp = cmp; - t->alloc = alloc; - t->pw = pw; - - *tree = t; - - return PARSERUTILS_OK; -} - -/** - * 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 - * \return PARSERUTILS_OK on success, appropriate error otherwise - */ -parserutils_error parserutils_rbtree_destroy(parserutils_rbtree *tree, - parserutils_rbtree_del destructor, void *pw) -{ - if (tree == NULL) - return PARSERUTILS_BADPARM; - - 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); - - return PARSERUTILS_OK; -} - -/** - * 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) -{ - int cmp; - 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); - - 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) { - rbnode *successor; - *intkey = current->key; - *value = current->value; - - 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 deleted file mode 100644 index 074d390..0000000 --- a/src/utils/rbtree.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * 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_error parserutils_rbtree_create(parserutils_rbtree_cmp cmp, - parserutils_alloc alloc, void *pw, parserutils_rbtree **tree); -parserutils_error 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 f055717..d89e3fa 100644 --- a/test/INDEX +++ b/test/INDEX @@ -9,9 +9,6 @@ cscodec-utf8 UTF-8 charset codec implementation cscodec-utf8 cscodec-utf16 UTF-16 charset codec implementation cscodec-utf16 cscodec-ext8 Extended 8bit charset codec cscodec-ext8 cscodec-8859 ISO-8859-n codec cscodec-8859 -dict Dictionary handling -hash Hashtable implementation -rbtree Red-black tree implementation filter Input stream filtering inputstream Inputstream handling input diff --git a/test/Makefile b/test/Makefile index aeffc1e..e864cb3 100644 --- a/test/Makefile +++ b/test/Makefile @@ -36,7 +36,7 @@ CFLAGS := $(CFLAGS) -I$(TOP)/src/ -I$(d) # Tests TESTS_$(d) := aliases cscodec-8859 cscodec-ext8 cscodec-utf8 cscodec-utf16 \ - charset dict filter hash inputstream parserutils rbtree + charset filter inputstream parserutils TESTS_$(d) := $(TESTS_$(d)) regression/cscodec-segv regression/filter-segv \ regression/stream-nomem regression/filter-badenc-segv diff --git a/test/dict.c b/test/dict.c deleted file mode 100644 index cb25a8e..0000000 --- a/test/dict.c +++ /dev/null @@ -1,54 +0,0 @@ -#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'; - - assert(parserutils_dict_create(myrealloc, NULL, &dict) == - PARSERUTILS_OK); - - 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/hash.c b/test/hash.c deleted file mode 100644 index 8504cbd..0000000 --- a/test/hash.c +++ /dev/null @@ -1,56 +0,0 @@ -#include -#include -#include - -#include - -#include "testutils.h" - -extern void parserutils_hash_dump(parserutils_hash *hash); - -static void *myrealloc(void *ptr, size_t len, void *pw) -{ - UNUSED(pw); - - return realloc(ptr, len); -} - -int main(int argc, char **argv) -{ - parserutils_hash *hash; - 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'; - - assert(parserutils_hash_create(myrealloc, NULL, &hash) == - PARSERUTILS_OK); - - for (int i = 0; i < (int) sizeof(buf); i++) { - uint8_t *s = buf; - - while (s - buf <= i) { - const parserutils_hash_entry *e; - - parserutils_hash_insert(hash, - s, (size_t) (sizeof(buf) - i), &e); - - s++; - } - } - - parserutils_hash_dump(hash); - - parserutils_hash_destroy(hash); - - printf("PASS\n"); - - return 0; -} - diff --git a/test/rbtree.c b/test/rbtree.c deleted file mode 100644 index ac27964..0000000 --- a/test/rbtree.c +++ /dev/null @@ -1,88 +0,0 @@ -#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 ((intptr_t) a) - ((intptr_t) b); -} - -int main(int argc, char **argv) -{ - parserutils_rbtree *tree; - - UNUSED(argc); - UNUSED(argv); - - assert(parserutils_rbtree_create(mycmp, myrealloc, NULL, &tree) == - PARSERUTILS_OK); - -#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, - (char *) NULL + i, (char *) NULL + 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, (char *) NULL + 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, (char *) NULL + i, - &value) == PARSERUTILS_OK); - assert(value != NULL && value == (char *) NULL + 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, (char *) NULL + i, - &value) == PARSERUTILS_OK); - assert(value == NULL); - assert(parserutils_rbtree_delete(tree, (char *) NULL + 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