From ef71b3d9674cc97e3a4b8a7cf62ab5ff043a2c77 Mon Sep 17 00:00:00 2001 From: Daniel Silverstone Date: Sat, 4 Dec 2010 19:03:19 +0000 Subject: Remove init/final and embed entity trie at build time. r=vince svn path=/trunk/hubbub/; revision=10976 --- src/utils/Makefile | 2 +- src/utils/dict.c | 236 ----------------------------------------------------- src/utils/dict.h | 32 -------- 3 files changed, 1 insertion(+), 269 deletions(-) delete mode 100644 src/utils/dict.c delete mode 100644 src/utils/dict.h (limited to 'src/utils') diff --git a/src/utils/Makefile b/src/utils/Makefile index 3918256..237c2bd 100644 --- a/src/utils/Makefile +++ b/src/utils/Makefile @@ -1,4 +1,4 @@ # Sources -DIR_SOURCES := dict.c errors.c string.c +DIR_SOURCES := errors.c string.c include build/makefiles/Makefile.subdir diff --git a/src/utils/dict.c b/src/utils/dict.c deleted file mode 100644 index 8dd6adf..0000000 --- a/src/utils/dict.c +++ /dev/null @@ -1,236 +0,0 @@ -/* - * This file is part of Hubbub. - * Licensed under the MIT License, - * http://www.opensource.org/licenses/mit-license.php - * Copyright 2007 John-Mark Bell - */ - -#include - -#include "utils/dict.h" - -/** Node in a dictionary tree */ -typedef struct hubbub_dict_node { - uint8_t split; /**< Data to split on */ - struct hubbub_dict_node *lt; /**< Subtree for data less than - * split */ - struct hubbub_dict_node *eq; /**< Subtree for data equal to split */ - struct hubbub_dict_node *gt; /**< Subtree for data greater than - * split */ - - const void *value; /**< Data for this node */ -} hubbub_dict_node; - -/** Dictionary object */ -struct hubbub_dict { - hubbub_dict_node *dict; /**< Root of tree */ - - hubbub_allocator_fn alloc; /**< Memory (de)allocation function */ - void *pw; /**< Pointer to client data */ -}; - -static void hubbub_dict_destroy_internal(hubbub_dict *dict, - hubbub_dict_node *root); -static hubbub_dict_node *hubbub_dict_insert_internal(hubbub_dict *dict, - hubbub_dict_node *parent, const char *key, - const void *value); - - -/** - * Create a dictionary - * - * \param alloc Memory (de)allocation function - * \param pw Pointer to client-specific private data (may be NULL) - * \param dict Pointer to location to receive dictionary instance - * \return HUBBUB_OK on success, - * HUBBUB_BADPARM on bad parameters, - * HUBBUB_NOMEM on memory exhaustion - */ -hubbub_error hubbub_dict_create(hubbub_allocator_fn alloc, void *pw, - hubbub_dict **dict) -{ - hubbub_dict *d; - - if (alloc == NULL || dict == NULL) - return HUBBUB_BADPARM; - - d = alloc(NULL, sizeof(hubbub_dict), pw); - if (d == NULL) - return HUBBUB_NOMEM; - - d->dict = NULL; - - d->alloc = alloc; - d->pw = pw; - - *dict = d; - - return HUBBUB_OK; -} - -/** - * Destroy a dictionary - * - * \param dict Dictionary to destroy - * \return HUBBUB_OK on success, appropriate error otherwise - */ -hubbub_error hubbub_dict_destroy(hubbub_dict *dict) -{ - if (dict == NULL) - return HUBBUB_BADPARM; - - hubbub_dict_destroy_internal(dict, dict->dict); - - dict->alloc(dict, 0, dict->pw); - - return HUBBUB_OK; -} - -/** - * Helper routine for dictionary destruction - * - * \param dict Dictionary being destroyed - * \param root Root node of dictionary (sub)tree to destroy - */ -void hubbub_dict_destroy_internal(hubbub_dict *dict, hubbub_dict_node *root) -{ - if (root == NULL) - return; - - hubbub_dict_destroy_internal(dict, root->lt); - if (root->split != '\0') - hubbub_dict_destroy_internal(dict, root->eq); - hubbub_dict_destroy_internal(dict, root->gt); - - dict->alloc(root, 0, dict->pw); -} - -/** - * Insert a key-value pair into a dictionary - * - * \param dict Dictionary to insert into - * \param key Key string - * \param value Value to associate with key (may be NULL) - * \return HUBBUB_OK on success, appropriate error otherwise - */ -hubbub_error hubbub_dict_insert(hubbub_dict *dict, const char *key, - const void *value) -{ - if (dict == NULL || key == NULL) - return HUBBUB_BADPARM; - - dict->dict = hubbub_dict_insert_internal(dict, dict->dict, - key, value); - - return HUBBUB_OK; -} - -/** - * Helper routine for insertion into dictionary - * - * \param dict Dictionary being inserted into - * \param parent Parent node of subtree to insert into - * \param key Key string - * \param value Value to associate with key - * \return Pointer to root of tree created - */ -hubbub_dict_node *hubbub_dict_insert_internal(hubbub_dict *dict, - hubbub_dict_node *parent, const char *key, const void *value) -{ - if (parent == NULL) { - parent = dict->alloc(NULL, - sizeof(hubbub_dict_node), dict->pw); - if (parent == NULL) - return NULL; - parent->split = (uint8_t) key[0]; - parent->lt = parent->eq = parent->gt = NULL; - parent->value = NULL; - } - - if ((uint8_t) key[0] < parent->split) { - parent->lt = hubbub_dict_insert_internal(dict, - parent->lt, key, value); - } else if ((uint8_t) key[0] == parent->split) { - if (key[0] == '\0') { - parent->value = value; - } else if (key[1] == '\0') { - parent->value = value; - parent->eq = hubbub_dict_insert_internal(dict, - parent->eq, key + 1, value); - } else { - parent->eq = hubbub_dict_insert_internal(dict, - parent->eq, key + 1, value); - } - } else { - parent->gt = hubbub_dict_insert_internal(dict, - parent->gt, key, value); - } - - return parent; -} - -/** - * Step-wise search for a key in a dictionary - * - * \param dict Dictionary to search - * \param c Character to look for - * \param result Pointer to location for result - * \param context Pointer to location for search context - * \return HUBBUB_OK if key found, - * HUBBUB_NEEDDATA if more steps are required - * HUBBUB_INVALID if nothing matches - * - * The value pointed to by ::context must be NULL for the first call. - * Thereafter, pass in the same value as returned by the previous call. - * The context is opaque to the caller and should not be inspected. - * - * The location pointed to by ::result will be set to NULL unless a match - * is found. - */ -hubbub_error hubbub_dict_search_step(hubbub_dict *dict, uint8_t c, - const void **result, void **context) -{ - bool match = false; - hubbub_dict_node *p; - - if (dict == NULL || result == NULL || context == NULL) - return HUBBUB_BADPARM; - - *result = NULL; - - if (*context == NULL) { - p = dict->dict; - } else { - p = (hubbub_dict_node *) *context; - } - - while (p != NULL) { - if (c < p->split) { - p = p->lt; - } else if (c == p->split) { - if (p->split == '\0') { - match = true; - p = NULL; - } else if (p->eq != NULL && p->eq->split == '\0') { - match = true; - *result = p->eq->value; - p = p->eq; - } else if (p->value) { - match = true; - *result = p->value; - p = p->eq; - } else { - p = p->eq; - } - - break; - } else { - p = p->gt; - } - } - - *context = (void *) p; - - return (match) ? HUBBUB_OK : - (p == NULL) ? HUBBUB_INVALID : HUBBUB_NEEDDATA; -} diff --git a/src/utils/dict.h b/src/utils/dict.h deleted file mode 100644 index 9718542..0000000 --- a/src/utils/dict.h +++ /dev/null @@ -1,32 +0,0 @@ -/* - * This file is part of Hubbub. - * Licensed under the MIT License, - * http://www.opensource.org/licenses/mit-license.php - * Copyright 2007 John-Mark Bell - */ - -#ifndef hubbub_utils_dict_h_ -#define hubbub_utils_dict_h_ - -#include - -#include -#include - -typedef struct hubbub_dict hubbub_dict; - -/* Create a dictionary */ -hubbub_error hubbub_dict_create(hubbub_allocator_fn alloc, void *pw, - hubbub_dict **dict); -/* Destroy a dictionary */ -hubbub_error hubbub_dict_destroy(hubbub_dict *dict); - -/* Insert a key-value pair into a dictionary */ -hubbub_error hubbub_dict_insert(hubbub_dict *dict, const char *key, - const void *value); - -/* Step-wise search for a key in a dictionary */ -hubbub_error hubbub_dict_search_step(hubbub_dict *dict, uint8_t c, - const void **result, void **context); - -#endif -- cgit v1.2.3