From 7b30a5520cfb56e651f0eb4da85a3e07747da7dc Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Sat, 23 Jun 2007 22:40:25 +0000 Subject: Import hubbub -- an HTML parsing library. Plenty of work still to do (like tree generation ;) svn path=/trunk/hubbub/; revision=3359 --- src/utils/dict.c | 219 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 219 insertions(+) create mode 100644 src/utils/dict.c (limited to 'src/utils/dict.c') diff --git a/src/utils/dict.c b/src/utils/dict.c new file mode 100644 index 0000000..f50ffab --- /dev/null +++ b/src/utils/dict.c @@ -0,0 +1,219 @@ +/* + * 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 + * If split == '\0', this stores the + * pointer to the actual data, not a + * subtree */ + struct hubbub_dict_node *gt; /**< Subtree for data greater than + * split */ +} hubbub_dict_node; + +/** Dictionary object */ +struct hubbub_dict { + hubbub_dict_node *dict; /**< Root of tree */ + + hubbub_alloc 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) + * \return Pointer to dictionary instance, or NULL on error + */ +hubbub_dict *hubbub_dict_create(hubbub_alloc alloc, void *pw) +{ + hubbub_dict *dict; + + if (alloc == NULL) + return NULL; + + dict = alloc(NULL, sizeof(hubbub_dict), pw); + if (dict == NULL) + return NULL; + + dict->dict = NULL; + + dict->alloc = alloc; + dict->pw = pw; + + return dict; +} + +/** + * Destroy a dictionary + * + * \param dict Dictionary to destroy + */ +void hubbub_dict_destroy(hubbub_dict *dict) +{ + if (dict == NULL) + return; + + hubbub_dict_destroy_internal(dict, dict->dict); + + dict->alloc(dict, 0, dict->pw); +} + +/** + * 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; + } + + 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->eq = (hubbub_dict_node *) value; + } else { + parent->eq = hubbub_dict_insert_internal(dict, + parent->eq, ++key, 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 = (const void *) p->eq->eq; + 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; +} -- cgit v1.2.3