summaryrefslogtreecommitdiff
path: root/src/utils/dict.c
diff options
context:
space:
mode:
authorDaniel Silverstone <dsilvers@netsurf-browser.org>2010-12-04 19:03:19 +0000
committerDaniel Silverstone <dsilvers@netsurf-browser.org>2010-12-04 19:03:19 +0000
commitef71b3d9674cc97e3a4b8a7cf62ab5ff043a2c77 (patch)
treea8bf79d08ed4fa619e836880f499ec8b29165d42 /src/utils/dict.c
parentdeb36d37e23997aa5352e0a7c2cc99e4a29f0416 (diff)
downloadlibhubbub-ef71b3d9674cc97e3a4b8a7cf62ab5ff043a2c77.tar.gz
libhubbub-ef71b3d9674cc97e3a4b8a7cf62ab5ff043a2c77.tar.bz2
Remove init/final and embed entity trie at build time. r=vince
svn path=/trunk/hubbub/; revision=10976
Diffstat (limited to 'src/utils/dict.c')
-rw-r--r--src/utils/dict.c236
1 files changed, 0 insertions, 236 deletions
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 <jmb@netsurf-browser.org>
- */
-
-#include <stdbool.h>
-
-#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;
-}