summaryrefslogtreecommitdiff
path: root/src/utils
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils')
-rw-r--r--src/utils/Makefile3
-rw-r--r--src/utils/dict.c283
-rw-r--r--src/utils/hash.c316
-rw-r--r--src/utils/rbtree.c742
-rw-r--r--src/utils/rbtree.h40
5 files changed, 1 insertions, 1383 deletions
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 <jmb@netsurf-browser.org>
- */
-
-#include <assert.h>
-#include <string.h>
-
-#include <parserutils/utils/dict.h>
-
-#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 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;
- 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 <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", (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 <jmb@netsurf-browser.org>
- */
-
-#include <stdio.h>
-#include <string.h>
-
-#include <parserutils/utils/hash.h>
-
-#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 a<b, ==0 iff a=b, >0 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 <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
- * \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 <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_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
-