diff options
Diffstat (limited to 'src/libmowgli/container')
| -rw-r--r-- | src/libmowgli/container/Makefile | 23 | ||||
| -rw-r--r-- | src/libmowgli/container/dictionary.c | 899 | ||||
| -rw-r--r-- | src/libmowgli/container/dictionary.h | 166 | ||||
| -rw-r--r-- | src/libmowgli/container/index.c | 187 | ||||
| -rw-r--r-- | src/libmowgli/container/index.h | 51 | ||||
| -rw-r--r-- | src/libmowgli/container/list.c | 390 | ||||
| -rw-r--r-- | src/libmowgli/container/list.h | 76 | ||||
| -rw-r--r-- | src/libmowgli/container/patricia.c | 1037 | ||||
| -rw-r--r-- | src/libmowgli/container/patricia.h | 155 | ||||
| -rw-r--r-- | src/libmowgli/container/queue.c | 231 | ||||
| -rw-r--r-- | src/libmowgli/container/queue.h | 44 |
11 files changed, 3259 insertions, 0 deletions
diff --git a/src/libmowgli/container/Makefile b/src/libmowgli/container/Makefile new file mode 100644 index 0000000..1c97ee9 --- /dev/null +++ b/src/libmowgli/container/Makefile @@ -0,0 +1,23 @@ +include ../../../extra.mk + +STATIC_PIC_LIB_NOINST = ${LIBMOWGLI_SHARED_CONTAINER} +STATIC_LIB_NOINST = ${LIBMOWGLI_STATIC_CONTAINER} + +SRCS = dictionary.c \ + list.c \ + queue.c \ + index.c \ + patricia.c + +INCLUDES = dictionary.h \ + list.h \ + queue.h \ + index.h \ + patricia.h + +include ../../../buildsys.mk + +includesubdir = $(PACKAGE_NAME)/container + +CPPFLAGS += -I. -I.. -I../../.. -DMOWGLI_CORE + diff --git a/src/libmowgli/container/dictionary.c b/src/libmowgli/container/dictionary.c new file mode 100644 index 0000000..22445d7 --- /dev/null +++ b/src/libmowgli/container/dictionary.c @@ -0,0 +1,899 @@ +/* + * libmowgli: A collection of useful routines for programming. + * dictionary.c: Dictionary-based information storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *elem_heap = NULL; + +struct mowgli_dictionary_ +{ + mowgli_dictionary_comparator_func_t compare_cb; + mowgli_dictionary_elem_t *root, *head, *tail; + unsigned int count; + char *id; + bool dirty; +}; + +/* + * mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb) + * + * Dictionary object factory. + * + * Inputs: + * - function to use for comparing two entries in the dtree + * + * Outputs: + * - on success, a new dictionary object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_dictionary_t *mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb) +{ + mowgli_dictionary_t *dtree = (mowgli_dictionary_t *) mowgli_alloc(sizeof(mowgli_dictionary_t)); + + dtree->compare_cb = compare_cb; + + if (!elem_heap) + elem_heap = mowgli_heap_create(sizeof(mowgli_dictionary_elem_t), 1024, BH_NOW); + + return dtree; +} + +/* + * mowgli_dictionary_create_named(const char *name, + * mowgli_dictionary_comparator_func_t compare_cb) + * + * Dictionary object factory. + * + * Inputs: + * - dictionary name + * - function to use for comparing two entries in the dtree + * + * Outputs: + * - on success, a new dictionary object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_dictionary_t *mowgli_dictionary_create_named(const char *name, + mowgli_dictionary_comparator_func_t compare_cb) +{ + mowgli_dictionary_t *dtree = (mowgli_dictionary_t *) mowgli_alloc(sizeof(mowgli_dictionary_t)); + + dtree->compare_cb = compare_cb; + dtree->id = strdup(name); + + if (!elem_heap) + elem_heap = mowgli_heap_create(sizeof(mowgli_dictionary_elem_t), 1024, BH_NOW); + + return dtree; +} + +/* + * mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + * mowgli_dictionary_comparator_func_t compare_cb) + * + * Resets the comparator function used by the dictionary code for + * updating the DTree structure. + * + * Inputs: + * - dictionary object + * - new comparator function (passed as functor) + * + * Outputs: + * - nothing + * + * Side Effects: + * - the dictionary comparator function is reset. + */ +void mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + mowgli_dictionary_comparator_func_t compare_cb) +{ + return_if_fail(dict != NULL); + return_if_fail(compare_cb != NULL); + + dict->compare_cb = compare_cb; +} + +/* + * mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict) + * + * Returns the current comparator function used by the dictionary. + * + * Inputs: + * - dictionary object + * + * Outputs: + * - comparator function (returned as functor) + * + * Side Effects: + * - none + */ +mowgli_dictionary_comparator_func_t +mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict) +{ + return_val_if_fail(dict != NULL, NULL); + + return dict->compare_cb; +} + +/* + * mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, + * const void *key) + * + * Gets a linear index number for key. + * + * Inputs: + * - dictionary tree object + * - pointer to data + * + * Outputs: + * - position, from zero. + * + * Side Effects: + * - rebuilds the linear index if the tree is marked as dirty. + */ +int +mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, const void *key) +{ + mowgli_dictionary_elem_t *elem; + + return_val_if_fail(dict != NULL, 0); + return_val_if_fail(key != NULL, 0); + + elem = mowgli_dictionary_find(dict, key); + if (elem == NULL) + return -1; + + if (!dict->dirty) + return elem->position; + else + { + mowgli_dictionary_elem_t *delem; + int i; + + for (delem = dict->head, i = 0; delem != NULL; delem = delem->next, i++) + delem->position = i; + + dict->dirty = false; + } + + return elem->position; +} + +/* + * mowgli_dictionary_retune(mowgli_dictionary_t *dict, const void *key) + * + * Retunes the tree, self-optimizing for the element which belongs to key. + * + * Tuning the tree structure is a very complex operation. Unlike + * 2-3-4 trees and BTree/BTree+ structures, this structure is a + * constantly evolving algorithm. + * + * Instead of maintaining a balanced tree, we constantly adapt the + * tree by nominating a new root nearby the most recently looked up + * or added data. We are constantly retuning ourselves instead of + * doing massive O(n) rebalance operations as seen in BTrees, + * and the level of data stored in a tree is dynamic, instead of being + * held to a restricted design like other trees. + * + * Moreover, we are different than a radix/patricia tree, because we + * don't statically allocate positions. Radix trees have the advantage + * of not requiring tuning or balancing operations while having the + * disadvantage of requiring a large amount of memory to store + * large trees. Our efficiency as far as speed goes is not as + * fast as a radix tree; but is close to it. + * + * The retuning algorithm uses the comparison callback that is + * passed in the initialization of the tree container. If the + * comparator returns a value which is less than zero, we push the + * losing node out of the way, causing it to later be reparented + * with another node. The winning child of this comparison is always + * the right-most node. + * + * Once we have reached the key which has been targeted, or have reached + * a deadend, we nominate the nearest node as the new root of the tree. + * If an exact match has been found, the new root becomes the node which + * represents key. + * + * This results in a tree which can self-optimize for both critical + * conditions: nodes which are distant and similar and trees which + * have ordered lookups. + * + * Inputs: + * - node to begin search from + * + * Outputs: + * - none + * + * Side Effects: + * - a new root node is nominated. + */ +void +mowgli_dictionary_retune(mowgli_dictionary_t *dict, const void *key) +{ + mowgli_dictionary_elem_t n, *tn, *left, *right, *node; + ptrdiff_t ret; + + return_if_fail(dict != NULL); + + if (dict->root == NULL) + return; + + /* + * we initialize n with known values, since it's on stack + * memory. otherwise the dict would become corrupted. + * + * n is used for temporary storage while the tree is retuned. + * -nenolod + */ + n.left = n.right = NULL; + left = right = &n; + + /* this for(;;) loop is the main workhorse of the rebalancing */ + for (node = dict->root; ; ) + { + if ((ret = dict->compare_cb(key, node->key)) == 0) + break; + + if (ret < 0) + { + if (node->left == NULL) + break; + + if ((ret = dict->compare_cb(key, node->left->key)) < 0) + { + tn = node->left; + node->left = tn->right; + tn->right = node; + node = tn; + + if (node->left == NULL) + break; + } + + right->left = node; + right = node; + node = node->left; + } + else + { + if (node->right == NULL) + break; + + if ((ret = dict->compare_cb(key, node->right->key)) > 0) + { + tn = node->right; + node->right = tn->left; + tn->left = node; + node = tn; + + if (node->right == NULL) + break; + } + + left->right = node; + left = node; + node = node->right; + } + } + + left->right = node->left; + right->left = node->right; + + node->left = n.right; + node->right = n.left; + + dict->root = node; +} + +/* + * mowgli_dictionary_link(mowgli_dictionary_t *dict, + * mowgli_dictionary_elem_t *delem) + * + * Links a dictionary tree element to the dictionary. + * + * When we add new nodes to the tree, it becomes the + * next nominated root. This is perhaps not a wise + * optimization because of automatic retuning, but + * it keeps the code simple. + * + * Inputs: + * - dictionary tree + * - dictionary tree element + * + * Outputs: + * - nothing + * + * Side Effects: + * - a node is linked to the dictionary tree + */ +void +mowgli_dictionary_link(mowgli_dictionary_t *dict, + mowgli_dictionary_elem_t *delem) +{ + return_if_fail(dict != NULL); + return_if_fail(delem != NULL); + + dict->dirty = true; + + dict->count++; + + if (dict->root == NULL) + { + delem->left = delem->right = NULL; + delem->next = delem->prev = NULL; + dict->head = dict->tail = dict->root = delem; + } + else + { + int ret; + + mowgli_dictionary_retune(dict, delem->key); + + if ((ret = dict->compare_cb(delem->key, dict->root->key)) < 0) + { + delem->left = dict->root->left; + delem->right = dict->root; + dict->root->left = NULL; + + if (dict->root->prev) + dict->root->prev->next = delem; + else + dict->head = delem; + + delem->prev = dict->root->prev; + delem->next = dict->root; + dict->root->prev = delem; + dict->root = delem; + } + else if (ret > 0) + { + delem->right = dict->root->right; + delem->left = dict->root; + dict->root->right = NULL; + + if (dict->root->next) + dict->root->next->prev = delem; + else + dict->tail = delem; + + delem->next = dict->root->next; + delem->prev = dict->root; + dict->root->next = delem; + dict->root = delem; + } + else + { + dict->root->key = delem->key; + dict->root->data = delem->data; + dict->count--; + + mowgli_heap_free(elem_heap, delem); + } + } +} + +/* + * mowgli_dictionary_unlink_root(mowgli_dictionary_t *dict) + * + * Unlinks the root dictionary tree element from the dictionary. + * + * Inputs: + * - dictionary tree + * + * Outputs: + * - nothing + * + * Side Effects: + * - the root node is unlinked from the dictionary tree + */ +void +mowgli_dictionary_unlink_root(mowgli_dictionary_t *dict) +{ + mowgli_dictionary_elem_t *delem, *nextnode, *parentofnext; + + dict->dirty = true; + + delem = dict->root; + if (delem == NULL) + return; + + if (dict->root->left == NULL) + dict->root = dict->root->right; + else if (dict->root->right == NULL) + dict->root = dict->root->left; + else + { + /* Make the node with the next highest key the new root. + * This node has a NULL left pointer. */ + nextnode = delem->next; + soft_assert(nextnode->left == NULL); + if (nextnode == delem->right) + { + dict->root = nextnode; + dict->root->left = delem->left; + } + else + { + parentofnext = delem->right; + while (parentofnext->left != NULL && parentofnext->left != nextnode) + parentofnext = parentofnext->left; + soft_assert(parentofnext->left == nextnode); + parentofnext->left = nextnode->right; + dict->root = nextnode; + dict->root->left = delem->left; + dict->root->right = delem->right; + } + } + + /* linked list */ + if (delem->prev != NULL) + delem->prev->next = delem->next; + + if (dict->head == delem) + dict->head = delem->next; + + if (delem->next) + delem->next->prev = delem->prev; + + if (dict->tail == delem) + dict->tail = delem->prev; + + dict->count--; +} + +/* + * mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Recursively destroys all nodes in a dictionary tree. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree and optionally it's children are destroyed. + * + * Notes: + * - if this is called without a callback, the objects bound to the + * DTree will not be destroyed. + */ +void mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + + return_if_fail(dtree != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + if (destroy_cb != NULL) + (*destroy_cb)(n, privdata); + + mowgli_heap_free(elem_heap, n); + } + + mowgli_free(dtree); +} + +/* + * mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Iterates over all entries in a DTree. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree is iterated + */ +void mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + int (*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + + return_if_fail(dtree != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + /* delem_t is a subclass of node_t. */ + mowgli_dictionary_elem_t *delem = (mowgli_dictionary_elem_t *) n; + + if (foreach_cb != NULL) + (*foreach_cb)(delem, privdata); + } +} + +/* + * mowgli_dictionary_search(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Searches all entries in a DTree using a custom callback. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - on success, the requested object + * - on failure, NULL. + * + * Side Effects: + * - a dtree is iterated until the requested conditions are met + */ +void *mowgli_dictionary_search(mowgli_dictionary_t *dtree, + void *(*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + void *ret = NULL; + + return_val_if_fail(dtree != NULL, NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + /* delem_t is a subclass of node_t. */ + mowgli_dictionary_elem_t *delem = (mowgli_dictionary_elem_t *) n; + + if (foreach_cb != NULL) + ret = (*foreach_cb)(delem, privdata); + + if (ret) + break; + } + + return ret; +} + +/* + * mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Initializes a static DTree iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is initialized. + */ +void mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_if_fail(dtree != NULL); + return_if_fail(state != NULL); + + state->cur = NULL; + state->next = NULL; + + /* find first item */ + state->cur = dtree->head; + + if (state->cur == NULL) + return; + + /* make state->cur point to first item and state->next point to + * second item */ + state->next = state->cur; + mowgli_dictionary_foreach_next(dtree, state); +} + +/* + * mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Returns the data from the current node being iterated by the + * static iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - reference to data in the current dtree node being iterated + * + * Side Effects: + * - none + */ +void *mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_val_if_fail(dtree != NULL, NULL); + return_val_if_fail(state != NULL, NULL); + + return state->cur != NULL ? state->cur->data : NULL; +} + +/* + * mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Advances a static DTree iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is advanced to a new DTree node. + */ +void mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_if_fail(dtree != NULL); + return_if_fail(state != NULL); + + if (state->cur == NULL) + { + mowgli_log("mowgli_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree); + return; + } + + state->cur = state->next; + + if (state->next == NULL) + return; + + state->next = state->next->next; +} + +/* + * mowgli_dictionary_find(mowgli_dictionary_t *dtree, const void *key) + * + * Looks up a DTree node by name. + * + * Inputs: + * - dictionary tree object + * - name of node to lookup + * + * Outputs: + * - on success, the dtree node requested + * - on failure, NULL + * + * Side Effects: + * - none + */ +mowgli_dictionary_elem_t *mowgli_dictionary_find(mowgli_dictionary_t *dict, const void *key) +{ + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + + /* retune for key, key will be the tree's root if it's available */ + mowgli_dictionary_retune(dict, key); + + if (dict->root && !dict->compare_cb(key, dict->root->key)) + return dict->root; + + return NULL; +} + +/* + * mowgli_dictionary_add(mowgli_dictionary_t *dtree, const void *key, void *data) + * + * Creates a new DTree node and binds data to it. + * + * Inputs: + * - dictionary tree object + * - name for new DTree node + * - data to bind to the new DTree node + * + * Outputs: + * - on success, a new DTree node + * - on failure, NULL + * + * Side Effects: + * - data is inserted into the DTree. + */ +mowgli_dictionary_elem_t *mowgli_dictionary_add(mowgli_dictionary_t *dict, const void *key, void *data) +{ + mowgli_dictionary_elem_t *delem; + + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + return_val_if_fail(data != NULL, NULL); + return_val_if_fail(mowgli_dictionary_find(dict, key) == NULL, NULL); + + delem = mowgli_heap_alloc(elem_heap); + delem->key = key; + delem->data = data; + + if (delem->key == NULL) + { + mowgli_log("major WTF: delem->key is NULL, not adding node.", key); + mowgli_heap_free(elem_heap, delem); + return NULL; + } + + mowgli_dictionary_link(dict, delem); + + return delem; +} + +/* + * mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const void *key) + * + * Deletes data from a dictionary tree. + * + * Inputs: + * - dictionary tree object + * - name of DTree node to delete + * + * Outputs: + * - on success, the remaining data that needs to be mowgli_freed + * - on failure, NULL + * + * Side Effects: + * - data is removed from the DTree. + * + * Notes: + * - the returned data needs to be mowgli_freed/released manually! + */ +void *mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const void *key) +{ + mowgli_dictionary_elem_t *delem = mowgli_dictionary_find(dtree, key); + void *data; + + if (delem == NULL) + return NULL; + + data = delem->data; + + mowgli_dictionary_unlink_root(dtree); + mowgli_heap_free(elem_heap, delem); + + return data; +} + +/* + * mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const void *key) + * + * Retrieves data from a dictionary. + * + * Inputs: + * - dictionary tree object + * - name of node to lookup + * + * Outputs: + * - on success, the data bound to the DTree node. + * - on failure, NULL + * + * Side Effects: + * - none + */ +void *mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const void *key) +{ + mowgli_dictionary_elem_t *delem = mowgli_dictionary_find(dtree, key); + + if (delem != NULL) + return delem->data; + + return NULL; +} + +/* + * mowgli_dictionary_size(mowgli_dictionary_t *dict) + * + * Returns the size of a dictionary. + * + * Inputs: + * - dictionary tree object + * + * Outputs: + * - size of dictionary + * + * Side Effects: + * - none + */ +unsigned int mowgli_dictionary_size(mowgli_dictionary_t *dict) +{ + return_val_if_fail(dict != NULL, 0); + + return dict->count; +} + +/* returns the sum of the depths of the subtree rooted in delem at depth depth */ +static int +stats_recurse(mowgli_dictionary_elem_t *delem, int depth, int *pmaxdepth) +{ + int result; + + if (depth > *pmaxdepth) + *pmaxdepth = depth; + result = depth; + if (delem->left) + result += stats_recurse(delem->left, depth + 1, pmaxdepth); + if (delem->right) + result += stats_recurse(delem->right, depth + 1, pmaxdepth); + return result; +} + +/* + * mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) + * + * Returns the size of a dictionary. + * + * Inputs: + * - dictionary tree object + * - callback + * - data for callback + * + * Outputs: + * - none + * + * Side Effects: + * - callback called with stats text + */ +void mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) +{ + char str[256]; + int sum, maxdepth; + + return_if_fail(dict != NULL); + + if (dict->id != NULL) + snprintf(str, sizeof str, "Dictionary stats for %s (%d)", + dict->id, dict->count); + else + snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)", + dict, dict->count); + cb(str, privdata); + maxdepth = 0; + if (dict->root != NULL) + { + sum = stats_recurse(dict->root, 0, &maxdepth); + snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth); + } + else + snprintf(str, sizeof str, "Depth sum 0 Avg depth 0 Max depth 0"); + cb(str, privdata); + return; +} diff --git a/src/libmowgli/container/dictionary.h b/src/libmowgli/container/dictionary.h new file mode 100644 index 0000000..3c2f4e5 --- /dev/null +++ b/src/libmowgli/container/dictionary.h @@ -0,0 +1,166 @@ +/* + * libmowgli: A collection of useful routines for programming. + * dictionary.h: Dictionary-based storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_DICTIONARY_H__ +#define __MOWGLI_DICTIONARY_H__ + +struct mowgli_dictionary_; /* defined in src/dictionary.c */ + +typedef struct mowgli_dictionary_ mowgli_dictionary_t; + +typedef struct mowgli_dictionary_elem_ mowgli_dictionary_elem_t; + +typedef ptrdiff_t (*mowgli_dictionary_comparator_func_t)(const void *a, const void *b); + +struct mowgli_dictionary_elem_ +{ + mowgli_dictionary_elem_t *left, *right, *prev, *next; + void *data; + const void *key; + int position; +}; + +/* + * mowgli_dictionary_iteration_state_t, private. + */ +struct mowgli_dictionary_iteration_state_ +{ + mowgli_dictionary_elem_t *cur, *next; + void *pspare[4]; + int ispare[4]; +}; + +typedef struct mowgli_dictionary_iteration_state_ mowgli_dictionary_iteration_state_t; + +/* + * this is a convenience macro for inlining iteration of dictionaries. + */ +#define MOWGLI_DICTIONARY_FOREACH(element, state, dict) for (mowgli_dictionary_foreach_start((dict), (state)); (element = mowgli_dictionary_foreach_cur((dict), (state))); mowgli_dictionary_foreach_next((dict), (state))) + +/* + * mowgli_dictionary_create() creates a new dictionary tree. + * compare_cb is the comparison function, typically strcmp, strcasecmp or + * irccasecmp. + */ +extern mowgli_dictionary_t *mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb); + +/* + * mowgli_dictionary_create_named() creates a new dictionary tree which has a name. + * name is the name, compare_cb is the comparator. + */ +extern mowgli_dictionary_t *mowgli_dictionary_create_named(const char *name, mowgli_dictionary_comparator_func_t compare_cb); + +/* + * mowgli_dictionary_set_comparator_func() resets the comparator used for lookups and + * insertions in the DTree structure. + */ +extern void mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + mowgli_dictionary_comparator_func_t compare_cb); + +/* + * mowgli_dictionary_get_comparator_func() returns the comparator used for lookups and + * insertions in the DTree structure. + */ +extern mowgli_dictionary_comparator_func_t mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict); + +/* + * mowgli_dictionary_get_linear_index() returns the linear index of an object in the + * DTree structure. + */ +extern int mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, const void *key); + +/* + * mowgli_dictionary_destroy() destroys all entries in a dtree, and also optionally calls + * a defined callback function to destroy any data attached to it. + */ +extern void mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata); + +/* + * mowgli_dictionary_foreach() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * To shortcircuit iteration, return non-zero from the callback function. + */ +extern void mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + int (*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata); + +/* + * mowgli_dictionary_search() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * When the object is found, a non-NULL is returned from the callback, which results + * in that object being returned to the user. + */ +extern void *mowgli_dictionary_search(mowgli_dictionary_t *dtree, + void *(*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata); + +/* + * mowgli_dictionary_foreach_start() begins an iteration over all items + * keeping state in the given struct. If there is only one iteration + * in progress at a time, it is permitted to remove the current element + * of the iteration (but not any other element). + */ +extern void mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state); + +/* + * mowgli_dictionary_foreach_cur() returns the current element of the iteration, + * or NULL if there are no more elements. + */ +extern void *mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state); + +/* + * mowgli_dictionary_foreach_next() moves to the next element. + */ +extern void mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state); + +/* + * mowgli_dictionary_add() adds a key->value entry to the dictionary tree. + */ +extern mowgli_dictionary_elem_t *mowgli_dictionary_add(mowgli_dictionary_t *dtree, const void *key, void *data); + +/* + * mowgli_dictionary_find() returns a mowgli_dictionary_elem_t container from a dtree for key 'key'. + */ +extern mowgli_dictionary_elem_t *mowgli_dictionary_find(mowgli_dictionary_t *dtree, const void *key); + +/* + * mowgli_dictionary_find() returns data from a dtree for key 'key'. + */ +extern void *mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const void *key); + +/* + * mowgli_dictionary_delete() deletes a key->value entry from the dictionary tree. + */ +extern void *mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const void *key); + +void mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata); + +#endif diff --git a/src/libmowgli/container/index.c b/src/libmowgli/container/index.c new file mode 100644 index 0000000..81776f5 --- /dev/null +++ b/src/libmowgli/container/index.c @@ -0,0 +1,187 @@ +/* + * Copyright 2009-2011 John Lindgren + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdlib.h> +#include <string.h> +#include "mowgli.h" + +struct mowgli_index_ +{ + void * * data; + int count, size; + int (* compare) (const void * a, const void * b, void * data); + void * compare_data; +}; + +static mowgli_heap_t *index_heap = NULL; + +void mowgli_index_init (void) +{ + index_heap = mowgli_heap_create(sizeof(mowgli_index_t), 32, BH_NOW); +} + +mowgli_index_t * mowgli_index_create (void) +{ + mowgli_index_t * index = mowgli_heap_alloc(index_heap); + + index->data = NULL; + index->count = 0; + index->size = 0; + index->compare = NULL; + index->compare_data = NULL; + + return index; +} + +void mowgli_index_destroy (mowgli_index_t * index) +{ + mowgli_free (index->data); + mowgli_heap_free (index_heap, index); +} + +int mowgli_index_count (mowgli_index_t * index) +{ + return index->count; +} + +void mowgli_index_allocate (mowgli_index_t * index, int size) +{ + size_t oldsize; + void *new_ptr; + + if (size <= index->size) + return; + + if (! index->size) + index->size = 64; + + oldsize = index->size; + while (size > index->size) + index->size <<= 1; + + new_ptr = mowgli_alloc_array(sizeof (void *), index->size); + + if (index->data != NULL) + { + memcpy(new_ptr, index->data, oldsize); + mowgli_free(index->data); + } + + index->data = new_ptr; +} + +void mowgli_index_set (mowgli_index_t * index, int at, void * value) +{ + index->data[at] = value; +} + +void * mowgli_index_get (mowgli_index_t * index, int at) +{ + return index->data[at]; +} + +static void make_room (mowgli_index_t * index, int at, int count) +{ + mowgli_index_allocate (index, index->count + count); + + if (at < index->count) + memmove (index->data + at + count, index->data + at, sizeof (void *) * + (index->count - at)); + + index->count += count; +} + +void mowgli_index_insert (mowgli_index_t * index, int at, void * value) +{ + make_room (index, at, 1); + index->data[at] = value; +} + +void mowgli_index_append (mowgli_index_t * index, void * value) +{ + mowgli_index_insert (index, index->count, value); +} + +void mowgli_index_copy_set (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count) +{ + memcpy (target->data + to, source->data + from, sizeof (void *) * count); +} + +void mowgli_index_copy_insert (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count) +{ + make_room (target, to, count); + memcpy (target->data + to, source->data + from, sizeof (void *) * count); +} + +void mowgli_index_copy_append (mowgli_index_t * source, int from, mowgli_index_t * target, + int count) +{ + mowgli_index_copy_insert (source, from, target, target->count, count); +} + +void mowgli_index_merge_insert (mowgli_index_t * first, int at, mowgli_index_t * second) +{ + mowgli_index_copy_insert (second, 0, first, at, second->count); +} + +void mowgli_index_merge_append (mowgli_index_t * first, mowgli_index_t * second) +{ + mowgli_index_copy_insert (second, 0, first, first->count, second->count); +} + +void mowgli_index_move (mowgli_index_t * index, int from, int to, int count) +{ + memmove (index->data + to, index->data + from, sizeof (void *) * count); +} + +void mowgli_index_delete (mowgli_index_t * index, int at, int count) +{ + index->count -= count; + memmove (index->data + at, index->data + at + count, sizeof (void *) * + (index->count - at)); +} + +void mowgli_index_sort (mowgli_index_t * index, int (* compare) (const void *, const void *)) +{ + qsort(index->data, index->count, sizeof (void *), compare); +} + +#ifdef NOTYET +static int mowgli_index_compare_with_data (const void * a, const void * b, void * _index) +{ + mowgli_index_t * index = _index; + + return index->compare (* (const void * *) a, * (const void * *) b, + index->compare_data); +} + +void mowgli_index_sort_with_data (mowgli_index_t * index, int (* compare) + (const void * a, const void * b, void * data), void * data) +{ + index->compare = compare; + index->compare_data = data; + g_qsort_with_data (index->data, index->count, sizeof (void *), + mowgli_index_compare_with_data, index); + index->compare = NULL; + index->compare_data = NULL; +} +#endif diff --git a/src/libmowgli/container/index.h b/src/libmowgli/container/index.h new file mode 100644 index 0000000..85e9e72 --- /dev/null +++ b/src/libmowgli/container/index.h @@ -0,0 +1,51 @@ +/* + * Copyright 2009-2011 John Lindgren + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_INDEX_H__ +#define __MOWGLI_INDEX_H__ + +struct mowgli_index_; + +typedef struct mowgli_index_ mowgli_index_t; + +mowgli_index_t * mowgli_index_create (void); +void mowgli_index_destroy (mowgli_index_t * index); +int mowgli_index_count (mowgli_index_t * index); +void mowgli_index_allocate (mowgli_index_t * index, int size); +void mowgli_index_set (mowgli_index_t * index, int at, void * value); +void * mowgli_index_get (mowgli_index_t * index, int at); +void mowgli_index_insert (mowgli_index_t * index, int at, void * value); +void mowgli_index_append (mowgli_index_t * index, void * value); +void mowgli_index_copy_set (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count); +void mowgli_index_copy_insert (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count); +void mowgli_index_copy_append (mowgli_index_t * source, int from, mowgli_index_t * target, + int count); +void mowgli_index_merge_insert (mowgli_index_t * first, int at, mowgli_index_t * second); +void mowgli_index_merge_append (mowgli_index_t * first, mowgli_index_t * second); +void mowgli_index_move (mowgli_index_t * index, int from, int to, int count); +void mowgli_index_delete (mowgli_index_t * index, int at, int count); +void mowgli_index_sort (mowgli_index_t * index, int (* compare) (const void * a, + const void * b)); +void mowgli_index_sort_with_data (mowgli_index_t * index, int (* compare) + (const void * a, const void * b, void * data), void * data); + +#endif diff --git a/src/libmowgli/container/list.c b/src/libmowgli/container/list.c new file mode 100644 index 0000000..6283910 --- /dev/null +++ b/src/libmowgli/container/list.c @@ -0,0 +1,390 @@ +/* + * libmowgli: A collection of useful routines for programming. + * list.c: Linked lists. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *mowgli_node_heap; +static mowgli_heap_t *mowgli_list_heap; + +void mowgli_node_bootstrap(void) +{ + mowgli_node_heap = mowgli_heap_create(sizeof(mowgli_node_t), 1024, BH_NOW); + mowgli_list_heap = mowgli_heap_create(sizeof(mowgli_list_t), 64, BH_NOW); + + if (mowgli_node_heap == NULL || mowgli_list_heap == NULL) + { + mowgli_log("heap allocator failure."); + abort(); + } +} + +/* creates a new node */ +mowgli_node_t *mowgli_node_create(void) +{ + mowgli_node_t *n; + + /* allocate it */ + n = mowgli_heap_alloc(mowgli_node_heap); + + /* initialize */ + n->next = n->prev = n->data = NULL; + + /* return a pointer to the new node */ + return n; +} + +/* frees a node */ +void mowgli_node_free(mowgli_node_t *n) +{ + return_if_fail(n != NULL); + + /* free it */ + mowgli_heap_free(mowgli_node_heap, n); +} + +/* adds a node to the end of a list */ +void mowgli_node_add(void *data, mowgli_node_t *n, mowgli_list_t *l) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + n->next = n->prev = NULL; + n->data = data; + + /* first node? */ + if (l->head == NULL) + { + l->head = n; + l->tail = n; + l->count++; + return; + } + + /* use the cached tail. */ + tn = l->tail; + + /* set the our `prev' to the last node */ + n->prev = tn; + + /* set the last node's `next' to us */ + n->prev->next = n; + + /* set the list's `tail' to us */ + l->tail = n; + + /* up the count */ + l->count++; +} + +/* adds a node to the head of a list */ +void mowgli_node_add_head(void *data, mowgli_node_t *n, mowgli_list_t *l) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + n->next = n->prev = NULL; + n->data = data; + + /* first node? */ + if (!l->head) + { + l->head = n; + l->tail = n; + l->count++; + return; + } + + tn = l->head; + n->next = tn; + tn->prev = n; + l->head = n; + l->count++; +} + +/* adds a node to a list before another node, or to the end */ +void mowgli_node_add_before(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + if (before == NULL) + mowgli_node_add(data, n, l); + else if (before == l->head) + mowgli_node_add_head(data, n, l); + else + { + n->data = data; + n->prev = before->prev; + n->next = before; + before->prev = n; + + if (n->prev != NULL) + n->prev->next = n; + + l->count++; + } +} + +/* adds a node to a list after another node, or to the end */ +void mowgli_node_add_after(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + if (before == NULL || before->next == NULL) + mowgli_node_add(data, n, l); + else + { + n->data = data; + n->prev = before; + n->next = before->next; + before->next = n; + n->next->prev = n; + l->count++; + } +} + +/* retrieves a node at `position` position. */ +mowgli_node_t *mowgli_node_nth(mowgli_list_t *l, size_t pos) +{ + size_t iter; + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + /* locate the proper position. */ + if (pos < MOWGLI_LIST_LENGTH(l) / 2) + for (iter = 0, n = l->head; iter != pos && n != NULL; iter++, n = n->next); + else + for (iter = MOWGLI_LIST_LENGTH(l) - 1, n = l->tail; + iter != pos && n != NULL; iter--, n = n->prev); + + return n; +} + +/* returns the data from node at `position` position, or NULL. */ +void *mowgli_node_nth_data(mowgli_list_t *l, size_t pos) +{ + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + n = mowgli_node_nth(l, pos); + + if (n == NULL) + return NULL; + + return n->data; +} + +/* inserts a node at `position` position. */ +void mowgli_node_insert(void *data, mowgli_node_t *n, mowgli_list_t *l, size_t pos) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + /* locate the proper position. */ + tn = mowgli_node_nth(l, pos); + + mowgli_node_add_before(data, n, l, tn); +} + +/* retrieves the index position of a node in a list. */ +ssize_t mowgli_node_index(mowgli_node_t *n, mowgli_list_t *l) +{ + ssize_t iter; + mowgli_node_t *tn; + + return_val_if_fail(n != NULL, -1); + return_val_if_fail(l != NULL, -1); + + /* locate the proper position. */ + for (iter = 0, tn = l->head; tn != n && tn != NULL; iter++, tn = tn->next); + + return iter < (ssize_t) MOWGLI_LIST_LENGTH(l) ? iter : -1; +} + +/* deletes a link between a node and a list. */ +void mowgli_node_delete(mowgli_node_t *n, mowgli_list_t *l) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + /* are we the head? */ + if (!n->prev) + l->head = n->next; + else + n->prev->next = n->next; + + /* are we the tail? */ + if (!n->next) + l->tail = n->prev; + else + n->next->prev = n->prev; + + /* down the count */ + l->count--; +} + +/* finds a node by `data' */ +mowgli_node_t *mowgli_node_find(void *data, mowgli_list_t *l) +{ + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + MOWGLI_LIST_FOREACH(n, l->head) if (n->data == data) + return n; + + return NULL; +} + +/* moves a node from one list to another. */ +void mowgli_node_move(mowgli_node_t *m, mowgli_list_t *oldlist, mowgli_list_t *newlist) +{ + return_if_fail(m != NULL); + return_if_fail(oldlist != NULL); + return_if_fail(newlist != NULL); + + /* Assumption: If m->next == NULL, then list->tail == m + * and: If m->prev == NULL, then list->head == m + */ + if (m->next != NULL) + m->next->prev = m->prev; + else + oldlist->tail = m->prev; + + if (m->prev != NULL) + m->prev->next = m->next; + else + oldlist->head = m->next; + + m->prev = NULL; + m->next = newlist->head; + + if (newlist->head != NULL) + newlist->head->prev = m; + else if (newlist->tail == NULL) + newlist->tail = m; + + newlist->head = m; + + oldlist->count--; + newlist->count++; +} + +/* creates a new list. */ +mowgli_list_t *mowgli_list_create(void) +{ + mowgli_list_t *out = mowgli_heap_alloc(mowgli_list_heap); + + return out; +} + +/* frees a created list. */ +void mowgli_list_free(mowgli_list_t *l) +{ + mowgli_heap_free(mowgli_list_heap, l); +} + +/* concatenates two lists together. */ +void mowgli_list_concat(mowgli_list_t *l, mowgli_list_t *l2) +{ + return_if_fail(l != NULL); + return_if_fail(l2 != NULL); + + if (l->tail != NULL) + l->tail->next = l2->head; + + if (l->tail->next != NULL) + l->tail->next->prev = l->tail; + + l->tail = l2->tail; + l->count += l2->count; + + /* clear out l2 as it is no longer needed. */ + l2->head = l2->tail = NULL; + l2->count = 0; +} + +/* reverse a list -- O(n)! */ +void mowgli_list_reverse(mowgli_list_t *l) +{ + mowgli_node_t *n, *tn; + + return_if_fail(l != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, l->head) + { + mowgli_node_t *tn2 = n->next; + n->next = n->prev; + n->prev = tn2; + } + + tn = l->head; + l->head = l->tail; + l->tail = tn; +} + +/* sorts a list -- O(n ^ 2) most likely, i don't want to think about it. --nenolod */ +void mowgli_list_sort(mowgli_list_t *l, mowgli_list_comparator_t comp, void *opaque) +{ + mowgli_node_t *n, *tn, *n2, *tn2; + + return_if_fail(l != NULL); + return_if_fail(comp != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, l->head) + { + MOWGLI_LIST_FOREACH_SAFE(n2, tn2, l->head) + { + int result; + int i, i2; + + if (n == n2) + continue; + + i = mowgli_node_index(n, l); + i2 = mowgli_node_index(n2, l); + + if ((result = comp(n, n2, opaque)) == 0) + continue; + else if (result < 0 && i > i2) + { + mowgli_node_delete(n, l); + mowgli_node_add_before(n->data, n, l, n2); + } + else if (result > 0 && i < i2) + { + mowgli_node_delete(n, l); + mowgli_node_add_after(n->data, n, l, n2); + } + } + } +} diff --git a/src/libmowgli/container/list.h b/src/libmowgli/container/list.h new file mode 100644 index 0000000..19905b4 --- /dev/null +++ b/src/libmowgli/container/list.h @@ -0,0 +1,76 @@ +/* + * libmowgli: A collection of useful routines for programming. + * list.h: Linked lists. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_LIST_H__ +#define __MOWGLI_LIST_H__ + +/* macros for linked lists */ +#define MOWGLI_LIST_FOREACH(n, head) for (n = (head); n; n = n->next) +#define MOWGLI_LIST_FOREACH_NEXT(n, head) for (n = (head); n->next; n = n->next) +#define MOWGLI_LIST_FOREACH_PREV(n, tail) for (n = (tail); n; n = n->prev) + +#define MOWGLI_LIST_LENGTH(list) (list)->count + +#define MOWGLI_LIST_FOREACH_SAFE(n, tn, head) for (n = (head), tn = n ? n->next : NULL; n != NULL; n = tn, tn = n ? n->next : NULL) + +/* list node struct */ +typedef struct mowgli_node_ mowgli_node_t; +typedef struct mowgli_list_ mowgli_list_t; + +struct mowgli_node_ +{ + struct mowgli_node_ *next, *prev; + void *data; /* pointer to real structure */ +}; + +/* node list struct */ +struct mowgli_list_ +{ + mowgli_node_t *head, *tail; + size_t count; /* how many entries in the list */ +}; + +extern void mowgli_node_bootstrap(void); +extern mowgli_node_t *mowgli_node_create(void); +extern void mowgli_node_free(mowgli_node_t *n); +extern void mowgli_node_add(void *data, mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_add_head(void *data, mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_add_before(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before); +extern void mowgli_node_add_after(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before); +extern void mowgli_node_insert(void *data, mowgli_node_t *n, mowgli_list_t *l, size_t position); +extern ssize_t mowgli_node_index(mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_delete(mowgli_node_t *n, mowgli_list_t *l); +extern mowgli_node_t *mowgli_node_find(void *data, mowgli_list_t *l); +extern void mowgli_node_move(mowgli_node_t *m, mowgli_list_t *oldlist, mowgli_list_t *newlist); +extern mowgli_node_t *mowgli_node_nth(mowgli_list_t *l, size_t pos); +extern void *mowgli_node_nth_data(mowgli_list_t *l, size_t pos); + +typedef int (*mowgli_list_comparator_t)(mowgli_node_t *n, mowgli_node_t *n2, void *opaque); + +extern mowgli_list_t *mowgli_list_create(void); +extern void mowgli_list_free(mowgli_list_t *l); +extern void mowgli_list_concat(mowgli_list_t *l, mowgli_list_t *l2); +extern void mowgli_list_reverse(mowgli_list_t *l); +extern void mowgli_list_sort(mowgli_list_t *l, mowgli_list_comparator_t comp, void *opaque); + +#endif diff --git a/src/libmowgli/container/patricia.c b/src/libmowgli/container/patricia.c new file mode 100644 index 0000000..b530d33 --- /dev/null +++ b/src/libmowgli/container/patricia.c @@ -0,0 +1,1037 @@ +/* + * libmowgli: A collection of useful routines for programming. + * patricia.c: Dictionary-based information storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007-2010 Jilles Tjoelker <jilles -at- stack.nl> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *leaf_heap = NULL; +static mowgli_heap_t *node_heap = NULL; + +/* + * Patricia tree. + * + * A radix trie that avoids one-way branching and redundant nodes. + * + * To find a node, the tree is traversed starting from the root. The + * nibnum in each node indicates which nibble of the key needs to be + * tested, and the appropriate branch is taken. + * + * The nibnum values are strictly increasing while going down the tree. + * + * -- jilles + */ + +union patricia_elem; + +struct mowgli_patricia_ +{ + void (*canonize_cb)(char *key); + union patricia_elem *root; + unsigned int count; + char *id; +}; + +#define POINTERS_PER_NODE 16 +#define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF) + +struct patricia_node +{ + /* nibble to test (nibble NUM%2 of byte NUM/2) */ + int nibnum; + /* branches of the tree */ + union patricia_elem *down[POINTERS_PER_NODE]; + union patricia_elem *parent; + char parent_val; +}; + +/* mowgli_patricia_elem_ is the name used in mowgli_patricia.h. + * patricia_leaf is the name historically used here. */ +#define patricia_leaf mowgli_patricia_elem_ + +struct patricia_leaf +{ + /* -1 to indicate this is a leaf, not a node */ + int nibnum; + /* data associated with the key */ + void *data; + /* key (canonized copy) */ + char *key; + union patricia_elem *parent; + char parent_val; +}; + +union patricia_elem +{ + int nibnum; + struct patricia_node node; + struct patricia_leaf leaf; +}; + +#define IS_LEAF(elem) ((elem)->nibnum == -1) + +/* Preserve compatibility with the old mowgli_patricia.h */ +#define STATE_CUR(state) ((state)->pspare[0]) +#define STATE_NEXT(state) ((state)->pspare[1]) + +/* + * first_leaf() + * + * Find the smallest leaf hanging off a subtree. + * + * Inputs: + * - element (may be leaf or node) heading subtree + * + * Outputs: + * - lowest leaf in subtree + * + * Side Effects: + * - none + */ +static union patricia_elem *first_leaf(union patricia_elem *delem) +{ + int val; + + while (!IS_LEAF(delem)) + { + for (val = 0; val < POINTERS_PER_NODE; val++) + { + if (delem->node.down[val] != NULL) + { + delem = delem->node.down[val]; + break; + } + } + } + return delem; +} + +/* + * mowgli_patricia_create(void (*canonize_cb)(char *key)) + * + * Dictionary object factory. + * + * Inputs: + * - function to use for canonizing keys (for example, use + * a function that makes the string upper case to create + * a patricia with case-insensitive matching) + * + * Outputs: + * - on success, a new patricia object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_patricia_t *mowgli_patricia_create(void (*canonize_cb)(char *key)) +{ + mowgli_patricia_t *dtree = (mowgli_patricia_t *) mowgli_alloc(sizeof(mowgli_patricia_t)); + + dtree->canonize_cb = canonize_cb; + + if (!leaf_heap) + leaf_heap = mowgli_heap_create(sizeof(struct patricia_leaf), 1024, BH_NOW); + if (!node_heap) + node_heap = mowgli_heap_create(sizeof(struct patricia_node), 128, BH_NOW); + + dtree->root = NULL; + + return dtree; +} + +/* + * mowgli_patricia_create_named(const char *name, + * void (*canonize_cb)(char *key)) + * + * Dictionary object factory. + * + * Inputs: + * - patricia name + * - function to use for canonizing keys (for example, use + * a function that makes the string upper case to create + * a patricia with case-insensitive matching) + * + * Outputs: + * - on success, a new patricia object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_patricia_t *mowgli_patricia_create_named(const char *name, + void (*canonize_cb)(char *key)) +{ + mowgli_patricia_t *dtree = (mowgli_patricia_t *) mowgli_alloc(sizeof(mowgli_patricia_t)); + + dtree->canonize_cb = canonize_cb; + dtree->id = mowgli_strdup(name); + + if (!leaf_heap) + leaf_heap = mowgli_heap_create(sizeof(struct patricia_leaf), 1024, BH_NOW); + if (!node_heap) + node_heap = mowgli_heap_create(sizeof(struct patricia_node), 128, BH_NOW); + + dtree->root = NULL; + + return dtree; +} + +/* + * mowgli_patricia_shutdown(void) + * + * Clean up after patricia to ensure all memory is released as soon as + * possible (destroys both heaps). + * + * Inputs: + * - nothing + * + * Outputs: + * - nothing + * + * Side Effects: + * - patricia's internal heaps are destroyed and deallocated + */ +void mowgli_patricia_shutdown(void) +{ + if(leaf_heap) + mowgli_heap_destroy(leaf_heap); + if(node_heap) + mowgli_heap_destroy(node_heap); + + return; +} + +/* + * mowgli_patricia_destroy(mowgli_patricia_t *dtree, + * void (*destroy_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Recursively destroys all nodes in a patricia tree. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree and optionally it's children are destroyed. + * + * Notes: + * - if this is called without a callback, the objects bound to the + * DTree will not be destroyed. + */ +void mowgli_patricia_destroy(mowgli_patricia_t *dtree, + void (*destroy_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + mowgli_patricia_iteration_state_t state; + union patricia_elem *delem; + void *entry; + + return_if_fail(dtree != NULL); + + MOWGLI_PATRICIA_FOREACH(entry, &state, dtree) + { + delem = STATE_CUR(&state); + if (destroy_cb != NULL) + (*destroy_cb)(delem->leaf.key, delem->leaf.data, + privdata); + mowgli_patricia_delete(dtree, delem->leaf.key); + } + + mowgli_free(dtree); +} + +/* + * mowgli_patricia_foreach(mowgli_patricia_t *dtree, + * int (*foreach_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Iterates over all entries in a DTree. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree is iterated + */ +void mowgli_patricia_foreach(mowgli_patricia_t *dtree, + int (*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + union patricia_elem *delem, *next; + int val; + + return_if_fail(dtree != NULL); + + delem = dtree->root; + if (delem == NULL) + return; + /* Only one element in the tree */ + if (IS_LEAF(delem)) + { + if (foreach_cb != NULL) + (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); + return; + } + val = 0; + do + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + if (foreach_cb != NULL) + (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } while (delem != NULL); +} + +/* + * mowgli_patricia_search(mowgli_patricia_t *dtree, + * void *(*foreach_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Searches all entries in a DTree using a custom callback. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - on success, the requested object + * - on failure, NULL. + * + * Side Effects: + * - a dtree is iterated until the requested conditions are met + */ +void *mowgli_patricia_search(mowgli_patricia_t *dtree, + void *(*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + union patricia_elem *delem, *next; + int val; + void *ret = NULL; + + return_val_if_fail(dtree != NULL, NULL); + + delem = dtree->root; + if (delem == NULL) + return NULL; + /* Only one element in the tree */ + if (IS_LEAF(delem)) + { + if (foreach_cb != NULL) + return (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); + return NULL; + } + val = 0; + for (;;) + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + if (foreach_cb != NULL) + ret = (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); + if (ret != NULL) + break; + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } + return ret; +} + +/* + * mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Initializes a static DTree iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is initialized. + */ +void mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + if (dtree == NULL) + return; + + return_if_fail(state != NULL); + + if (dtree->root != NULL) + STATE_NEXT(state) = first_leaf(dtree->root); + else + STATE_NEXT(state) = NULL; + STATE_CUR(state) = STATE_NEXT(state); + + if (STATE_NEXT(state) == NULL) + return; + + /* make STATE_CUR point to first item and STATE_NEXT point to + * second item */ + mowgli_patricia_foreach_next(dtree, state); +} + +/* + * mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Returns the data from the current node being iterated by the + * static iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - reference to data in the current dtree node being iterated + * + * Side Effects: + * - none + */ +void *mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + if (dtree == NULL) + return NULL; + + return_val_if_fail(state != NULL, NULL); + + return STATE_CUR(state) != NULL ? + ((struct patricia_leaf *)STATE_CUR(state))->data : NULL; +} + +/* + * mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Advances a static DTree iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is advanced to a new DTree node. + */ +void mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + struct patricia_leaf *leaf; + union patricia_elem *delem, *next; + int val; + + if (dtree == NULL) + return; + + return_if_fail(state != NULL); + + if (STATE_CUR(state) == NULL) + { + mowgli_log("mowgli_patricia_foreach_next(): called again after iteration finished on dtree<%p>", dtree); + return; + } + + STATE_CUR(state) = STATE_NEXT(state); + + if (STATE_NEXT(state) == NULL) + return; + + leaf = STATE_NEXT(state); + delem = leaf->parent; + val = leaf->parent_val; + + while (delem != NULL) + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + /* We will find the original leaf first. */ + if (&next->leaf != leaf) + { + if (strcmp(next->leaf.key, leaf->key) < 0) + { + mowgli_log("mowgli_patricia_foreach_next(): iteration went backwards (libmowgli bug) on dtree<%p>", dtree); + STATE_NEXT(state) = NULL; + return; + } + STATE_NEXT(state) = next; + return; + } + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } + STATE_NEXT(state) = NULL; +} + +/* + * mowgli_patricia_elem_find(mowgli_patricia_t *dtree, const char *key) + * + * Looks up a DTree node by name. + * + * Inputs: + * - patricia tree object + * - name of node to lookup + * + * Outputs: + * - on success, the dtree node requested + * - on failure, NULL + * + * Side Effects: + * - none + */ +struct patricia_leaf *mowgli_patricia_elem_find(mowgli_patricia_t *dict, const char *key) +{ + char ckey_store[256]; + char *ckey_buf = NULL; + const char *ckey; + union patricia_elem *delem; + int val, keylen; + + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + + keylen = strlen(key); + + if (dict->canonize_cb == NULL) + ckey = key; + else + { + if (keylen >= (int) sizeof(ckey_store)) + { + ckey_buf = mowgli_strdup(key); + dict->canonize_cb(ckey_buf); + ckey = ckey_buf; + } + else + { + mowgli_strlcpy(ckey_store, key, sizeof ckey_store); + dict->canonize_cb(ckey_store); + ckey = ckey_store; + } + } + + delem = dict->root; + while (delem != NULL && !IS_LEAF(delem)) + { + if (delem->nibnum / 2 < keylen) + val = NIBBLE_VAL(ckey, delem->nibnum); + else + val = 0; + delem = delem->node.down[val]; + } + /* Now, if the key is in the tree, delem contains it. */ + if (delem != NULL && strcmp(delem->leaf.key, ckey)) + delem = NULL; + + if (ckey_buf != NULL) + mowgli_free(ckey_buf); + + return &delem->leaf; +} + +/* + * mowgli_patricia_add(mowgli_patricia_t *dtree, const char *key, void *data) + * + * Creates a new DTree node and binds data to it. + * + * Inputs: + * - patricia tree object + * - name for new DTree node + * - data to bind to the new DTree node + * + * Outputs: + * - on success, TRUE + * - on failure, FALSE + * + * Side Effects: + * - data is inserted into the DTree. + */ +struct patricia_leaf *mowgli_patricia_elem_add(mowgli_patricia_t *dict, const char *key, void *data) +{ + char *ckey; + union patricia_elem *delem, *prev, *newnode; + union patricia_elem **place1; + int val, keylen; + int i, j; + + return_val_if_fail(dict != NULL, FALSE); + return_val_if_fail(key != NULL, FALSE); + return_val_if_fail(data != NULL, FALSE); + + keylen = strlen(key); + ckey = mowgli_strdup(key); + if (ckey == NULL) + { + mowgli_log("major WTF: ckey is NULL, not adding node."); + return NULL; + } + if (dict->canonize_cb != NULL) + dict->canonize_cb(ckey); + + prev = NULL; + val = POINTERS_PER_NODE + 2; /* trap value */ + delem = dict->root; + while (delem != NULL && !IS_LEAF(delem)) + { + prev = delem; + if (delem->nibnum / 2 < keylen) + val = NIBBLE_VAL(ckey, delem->nibnum); + else + val = 0; + delem = delem->node.down[val]; + } + /* Now, if the key is in the tree, delem contains it. */ + if (delem != NULL && !strcmp(delem->leaf.key, ckey)) + { + mowgli_log("Key is already in dict, ignoring duplicate"); + mowgli_free(ckey); + return NULL; + } + + if (delem == NULL && prev != NULL) + { + /* Get a leaf to compare with. */ + delem = first_leaf(prev); + } + + if (delem == NULL) + { + soft_assert(prev == NULL); + soft_assert(dict->count == 0); + place1 = &dict->root; + *place1 = mowgli_heap_alloc(leaf_heap); + return_val_if_fail(*place1 != NULL, NULL); + (*place1)->nibnum = -1; + (*place1)->leaf.data = data; + (*place1)->leaf.key = ckey; + (*place1)->leaf.parent = prev; + (*place1)->leaf.parent_val = val; + dict->count++; + return &(*place1)->leaf; + } + + /* Find the first nibble where they differ. */ + for (i = 0; NIBBLE_VAL(ckey, i) == NIBBLE_VAL(delem->leaf.key, i); i++) + ; + /* Find where to insert the new node. */ + while (prev != NULL && prev->nibnum > i) + { + val = prev->node.parent_val; + prev = prev->node.parent; + } + if (prev == NULL || prev->nibnum < i) + { + /* Insert new node below prev */ + newnode = mowgli_heap_alloc(node_heap); + return_val_if_fail(newnode != NULL, NULL); + newnode->nibnum = i; + newnode->node.parent = prev; + newnode->node.parent_val = val; + for (j = 0; j < POINTERS_PER_NODE; j++) + newnode->node.down[j] = NULL; + if (prev == NULL) + { + newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = dict->root; + if (IS_LEAF(dict->root)) + { + dict->root->leaf.parent = newnode; + dict->root->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + else + { + soft_assert(dict->root->nibnum > i); + dict->root->node.parent = newnode; + dict->root->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + dict->root = newnode; + } + else + { + newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = prev->node.down[val]; + if (IS_LEAF(prev->node.down[val])) + { + prev->node.down[val]->leaf.parent = newnode; + prev->node.down[val]->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + else + { + prev->node.down[val]->node.parent = newnode; + prev->node.down[val]->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + prev->node.down[val] = newnode; + } + } + else + { + /* This nibble is already checked. */ + soft_assert(prev->nibnum == i); + newnode = prev; + } + val = NIBBLE_VAL(ckey, i); + place1 = &newnode->node.down[val]; + soft_assert(*place1 == NULL); + *place1 = mowgli_heap_alloc(leaf_heap); + return_val_if_fail(*place1 != NULL, NULL); + (*place1)->nibnum = -1; + (*place1)->leaf.data = data; + (*place1)->leaf.key = ckey; + (*place1)->leaf.parent = newnode; + (*place1)->leaf.parent_val = val; + dict->count++; + return &(*place1)->leaf; +} + +mowgli_boolean_t mowgli_patricia_add(mowgli_patricia_t *dict, const char *key, void *data) +{ + return (mowgli_patricia_elem_add(dict, key, data) != NULL) ? TRUE : FALSE; +} + +/* + * mowgli_patricia_delete(mowgli_patricia_t *dtree, const char *key) + * + * Deletes data from a patricia tree. + * + * Inputs: + * - patricia tree object + * - name of DTree node to delete + * + * Outputs: + * - on success, the remaining data that needs to be mowgli_freed + * - on failure, NULL + * + * Side Effects: + * - data is removed from the DTree. + * + * Notes: + * - the returned data needs to be mowgli_freed/released manually! + */ +void *mowgli_patricia_delete(mowgli_patricia_t *dict, const char *key) +{ + void *data; + struct patricia_leaf *leaf; + + leaf = mowgli_patricia_elem_find(dict, key); + if (leaf == NULL) + return NULL; + + data = leaf->data; + mowgli_patricia_elem_delete(dict, leaf); + return data; +} + +void mowgli_patricia_elem_delete(mowgli_patricia_t *dict, struct patricia_leaf *leaf) +{ + union patricia_elem *delem, *prev, *next; + int val, i, used; + + return_if_fail(dict != NULL); + return_if_fail(leaf != NULL); + + delem = (union patricia_elem *)leaf; + + val = delem->leaf.parent_val; + prev = delem->leaf.parent; + + mowgli_free(delem->leaf.key); + mowgli_heap_free(leaf_heap, delem); + + if (prev != NULL) + { + prev->node.down[val] = NULL; + + /* Leaf is gone, now consider the node it was in. */ + delem = prev; + + used = -1; + for (i = 0; i < POINTERS_PER_NODE; i++) + if (delem->node.down[i] != NULL) + used = used == -1 ? i : -2; + soft_assert(used == -2 || used >= 0); + if (used >= 0) + { + /* Only one pointer in this node, remove it. + * Replace the pointer that pointed to it by + * the sole pointer in it. + */ + next = delem->node.down[used]; + val = delem->node.parent_val; + prev = delem->node.parent; + if (prev != NULL) + prev->node.down[val] = next; + else + dict->root = next; + if (IS_LEAF(next)) + next->leaf.parent = prev, next->leaf.parent_val = val; + else + next->node.parent = prev, next->node.parent_val = val; + mowgli_heap_free(node_heap, delem); + } + } + else + { + /* This was the last leaf. */ + dict->root = NULL; + } + + dict->count--; + if (dict->count == 0) + { + soft_assert(dict->root == NULL); + dict->root = NULL; + } +} + +/* + * mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key) + * + * Retrieves data from a patricia. + * + * Inputs: + * - patricia tree object + * - name of node to lookup + * + * Outputs: + * - on success, the data bound to the DTree node. + * - on failure, NULL + * + * Side Effects: + * - none + */ +void *mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key) +{ + struct patricia_leaf *delem = mowgli_patricia_elem_find(dtree, key); + + if (delem != NULL) + return delem->data; + + return NULL; +} + +const char *mowgli_patricia_elem_get_key(struct patricia_leaf *leaf) +{ + return_val_if_fail(leaf != NULL, NULL); + + return leaf->key; +} + +void mowgli_patricia_elem_set_data(struct patricia_leaf *leaf, void *data) +{ + return_if_fail(leaf != NULL); + + leaf->data = data; +} + +void *mowgli_patricia_elem_get_data(struct patricia_leaf *leaf) +{ + return_val_if_fail(leaf != NULL, NULL); + + return leaf->data; +} + +/* + * mowgli_patricia_size(mowgli_patricia_t *dict) + * + * Returns the size of a patricia. + * + * Inputs: + * - patricia tree object + * + * Outputs: + * - size of patricia + * + * Side Effects: + * - none + */ +unsigned int mowgli_patricia_size(mowgli_patricia_t *dict) +{ + return_val_if_fail(dict != NULL, 0); + + return dict->count; +} + +/* returns the sum of the depths of the subtree rooted in delem at depth depth */ +/* there is no need for this to be recursive, but it is easier... */ +static int +stats_recurse(union patricia_elem *delem, int depth, int *pmaxdepth) +{ + int result = 0; + int val; + union patricia_elem *next; + + if (depth > *pmaxdepth) + *pmaxdepth = depth; + if (depth == 0) + { + if (IS_LEAF(delem)) + { + soft_assert(delem->leaf.parent == NULL); + } + else + { + soft_assert(delem->node.parent == NULL); + } + } + if (IS_LEAF(delem)) + return depth; + for (val = 0; val < POINTERS_PER_NODE; val++) + { + next = delem->node.down[val]; + if (next == NULL) + continue; + result += stats_recurse(next, depth + 1, pmaxdepth); + if (IS_LEAF(next)) + { + soft_assert(next->leaf.parent == delem); + soft_assert(next->leaf.parent_val == val); + } + else + { + soft_assert(next->node.parent == delem); + soft_assert(next->node.parent_val == val); + soft_assert(next->node.nibnum > delem->node.nibnum); + } + } + return result; +} + +/* + * mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) + * + * Returns the size of a patricia. + * + * Inputs: + * - patricia tree object + * - callback + * - data for callback + * + * Outputs: + * - none + * + * Side Effects: + * - callback called with stats text + */ +void mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) +{ + char str[256]; + int sum, maxdepth; + + return_if_fail(dict != NULL); + + if (dict->id != NULL) + snprintf(str, sizeof str, "Dictionary stats for %s (%d)", + dict->id, dict->count); + else + snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)", + dict, dict->count); + cb(str, privdata); + maxdepth = 0; + if (dict->count > 0) + { + sum = stats_recurse(dict->root, 0, &maxdepth); + snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth); + } + else + snprintf(str, sizeof str, "Depth sum 0 Avg depth 0 Max depth 0"); + cb(str, privdata); + return; +} diff --git a/src/libmowgli/container/patricia.h b/src/libmowgli/container/patricia.h new file mode 100644 index 0000000..417ba62 --- /dev/null +++ b/src/libmowgli/container/patricia.h @@ -0,0 +1,155 @@ +/* + * libmowgli: A collection of useful routines for programming. + * patricia.h: Dictionary-based storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007-2008 Jilles Tjoelker <jilles -at- stack.nl> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_PATRICIA_H__ +#define __MOWGLI_PATRICIA_H__ + +struct mowgli_patricia_; /* defined in src/patricia.c */ +struct mowgli_patricia_elem_; /* defined in src/patricia.c */ + +typedef struct mowgli_patricia_ mowgli_patricia_t; +typedef struct mowgli_patricia_elem_ mowgli_patricia_elem_t; + +/* + * mowgli_patricia_iteration_state_t, private. + */ +struct mowgli_patricia_iteration_state_ +{ + mowgli_patricia_elem_t *cur, *next; + void *pspare[4]; + int ispare[4]; +}; + +typedef struct mowgli_patricia_iteration_state_ mowgli_patricia_iteration_state_t; + +/* + * this is a convenience macro for inlining iteration of dictionaries. + */ +#define MOWGLI_PATRICIA_FOREACH(element, state, dict) for (mowgli_patricia_foreach_start((dict), (state)); (element = mowgli_patricia_foreach_cur((dict), (state))); mowgli_patricia_foreach_next((dict), (state))) + +/* + * mowgli_patricia_create() creates a new patricia tree of the defined resolution. + * compare_cb is the canonizing function. + */ + +/* defined if this version of Mowgli allows canonize_cb to be NULL */ +#define MOWGLI_PATRICIA_ALLOWS_NULL_CANONIZE + +extern mowgli_patricia_t *mowgli_patricia_create(void (*canonize_cb)(char *key)); + +/* + * mowgli_patricia_shutdown() deallocates all heaps used in patricia trees. This is + * useful on embedded devices with little memory, and/or when you know you won't need + * any more patricia trees. + */ +extern void mowgli_patricia_shutdown(void); + +/* + * mowgli_patricia_destroy() destroys all entries in a dtree, and also optionally calls + * a defined callback function to destroy any data attached to it. + */ +extern void mowgli_patricia_destroy(mowgli_patricia_t *dtree, + void (*destroy_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_foreach() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * To shortcircuit iteration, return non-zero from the callback function. + */ +extern void mowgli_patricia_foreach(mowgli_patricia_t *dtree, + int (*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_search() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * When the object is found, a non-NULL is returned from the callback, which results + * in that object being returned to the user. + */ +extern void *mowgli_patricia_search(mowgli_patricia_t *dtree, + void *(*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_foreach_start() begins an iteration over all items + * keeping state in the given struct. If there is only one iteration + * in progress at a time, it is permitted to remove the current element + * of the iteration (but not any other element). + */ +extern void mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_foreach_cur() returns the current element of the iteration, + * or NULL if there are no more elements. + */ +extern void *mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_foreach_next() moves to the next element. + */ +extern void mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_add() adds a key->value entry to the patricia tree. + */ +extern mowgli_boolean_t mowgli_patricia_add(mowgli_patricia_t *dtree, const char *key, void *data); + +/* + * mowgli_patricia_find() returns data from a dtree for key 'key'. + */ +extern void *mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key); + +/* + * mowgli_patricia_delete() deletes a key->value entry from the patricia tree. + */ +extern void *mowgli_patricia_delete(mowgli_patricia_t *dtree, const char *key); + +/* Low-level functions */ +mowgli_patricia_elem_t *mowgli_patricia_elem_add(mowgli_patricia_t *dtree, const char *key, void *data); +mowgli_patricia_elem_t *mowgli_patricia_elem_find(mowgli_patricia_t *dtree, const char *key); +void mowgli_patricia_elem_delete(mowgli_patricia_t *dtree, mowgli_patricia_elem_t *elem); +const char *mowgli_patricia_elem_get_key(mowgli_patricia_elem_t *elem); +void mowgli_patricia_elem_set_data(mowgli_patricia_elem_t *elem, void *data); +void *mowgli_patricia_elem_get_data(mowgli_patricia_elem_t *elem); + +unsigned int mowgli_patricia_size(mowgli_patricia_t *dict); +void mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata); + +#endif diff --git a/src/libmowgli/container/queue.c b/src/libmowgli/container/queue.c new file mode 100644 index 0000000..39150d3 --- /dev/null +++ b/src/libmowgli/container/queue.c @@ -0,0 +1,231 @@ +/* + * libmowgli: A collection of useful routines for programming. + * queue.c: Double-ended queues, also known as deque. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *mowgli_queue_heap = NULL; + +void +mowgli_queue_bootstrap(void) +{ + mowgli_queue_heap = mowgli_heap_create(sizeof(mowgli_queue_t), 256, BH_NOW); + + if (mowgli_queue_heap == NULL) + mowgli_log("mowgli_queue_heap was not created, expect problems."); +} + +mowgli_queue_t * +mowgli_queue_shift(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + return_val_if_fail(head != NULL, NULL); + + out->next = head; + out->data = data; + + if (head != NULL) + { + out->prev = head->prev; + + if (out->prev != NULL) + out->prev->next = out; + + head->prev = out; + } + + return out; +} + +mowgli_queue_t * +mowgli_queue_push(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + return_val_if_fail(head != NULL, NULL); + + out->prev = head; + out->data = data; + + if (head != NULL) + head->next = out; + + return out; +} + +mowgli_queue_t * +mowgli_queue_remove(mowgli_queue_t *head) +{ + mowgli_queue_t *out; + + return_val_if_fail(head != NULL, NULL); + + if (head->prev != NULL) + head->prev->next = head->next; + + if (head->next != NULL) + head->next->prev = head->prev; + + out = head->prev != NULL ? head->prev : head->next; + + mowgli_heap_free(mowgli_queue_heap, head); + + return out; +} + +mowgli_queue_t * +mowgli_queue_find(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n; + + return_val_if_fail(head != NULL, NULL); + + for (n = head; n != NULL; n = n->next) + if (n->data == data) + return n; + + return NULL; +} + +mowgli_queue_t * +mowgli_queue_remove_data(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n = mowgli_queue_find(head, data); + + return_val_if_fail(head != NULL, NULL); + + if (n != NULL) + return mowgli_queue_remove(n); + + return NULL; +} + +void +mowgli_queue_destroy(mowgli_queue_t *head) +{ + mowgli_queue_t *n, *n2; + + return_if_fail(head != NULL); + + for (n = head, n2 = n ? n->next : NULL; n != NULL; n = n2, n2 = n ? n->next : NULL) + mowgli_queue_remove(n); +} + +mowgli_queue_t * +mowgli_queue_skip(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + return_val_if_fail(head != NULL, NULL); + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->next, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_rewind(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + return_val_if_fail(head != NULL, NULL); + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->prev, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_head(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + return_val_if_fail(n != NULL, NULL); + + for (tn = n; tn != NULL && tn->prev != NULL; tn = tn->prev); + + return tn; +} + +mowgli_queue_t * +mowgli_queue_tail(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + return_val_if_fail(n != NULL, NULL); + + for (tn = n; tn != NULL && tn->next != NULL; tn = tn->next); + + return tn; +} + +void * +mowgli_queue_pop_head(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->next; + + mowgli_queue_remove(tn); + + return out; +} + +void * +mowgli_queue_pop_tail(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->prev; + + mowgli_queue_remove(tn); + + return out; +} + +int +mowgli_queue_length(mowgli_queue_t *head) +{ + int iter; + mowgli_queue_t *n; + + return_val_if_fail(head != NULL, -1); + + for (n = head, iter = 0; n != NULL; n = n->next, iter++); + + return iter; +} diff --git a/src/libmowgli/container/queue.h b/src/libmowgli/container/queue.h new file mode 100644 index 0000000..7f8d995 --- /dev/null +++ b/src/libmowgli/container/queue.h @@ -0,0 +1,44 @@ +/* + * libmowgli: A collection of useful routines for programming. + * queue.h: Double-ended queues, also known as deque. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_QUEUE_H__ +#define __MOWGLI_QUEUE_H__ + +typedef mowgli_iterator_t mowgli_queue_t; + +extern void mowgli_queue_bootstrap(void); +extern mowgli_queue_t *mowgli_queue_push(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_shift(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_remove(mowgli_queue_t *head); +extern mowgli_queue_t *mowgli_queue_find(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_remove_data(mowgli_queue_t *head, void *data); +extern void mowgli_queue_destroy(mowgli_queue_t *head); +extern mowgli_queue_t *mowgli_queue_skip(mowgli_queue_t *head, int amt); +extern mowgli_queue_t *mowgli_queue_rewind(mowgli_queue_t *head, int amt); +extern mowgli_queue_t *mowgli_queue_head(mowgli_queue_t *n); +extern mowgli_queue_t *mowgli_queue_tail(mowgli_queue_t *n); +extern void *mowgli_queue_pop_head(mowgli_queue_t **n); +extern void *mowgli_queue_pop_tail(mowgli_queue_t **n); +extern int mowgli_queue_length(mowgli_queue_t *head); + +#endif |