From 4f0c30aee2c56967895c981534414d1b04e9e0ce Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 29 Jan 2011 17:14:56 -0500 Subject: Make PATRICIA tries available as a generic dictionary API. --- dimension/parse.c | 256 ++++++------------------------------ libdimension/Makefile.am | 2 + libdimension/dictionary.c | 234 ++++++++++++++++++++++++++++++++ libdimension/dimension.h | 1 + libdimension/dimension/dictionary.h | 83 ++++++++++++ 5 files changed, 357 insertions(+), 219 deletions(-) create mode 100644 libdimension/dictionary.c create mode 100644 libdimension/dimension/dictionary.h diff --git a/dimension/parse.c b/dimension/parse.c index 64f633e..997fe24 100644 --- a/dimension/parse.c +++ b/dimension/parse.c @@ -30,211 +30,10 @@ * Symbol table */ -typedef struct dmnsn_patricia_trie { - char *prefix; - - bool leaf; - dmnsn_array *children; - dmnsn_astnode value; -} dmnsn_patricia_trie; - -static void -dmnsn_delete_patricia_trie(dmnsn_patricia_trie *trie) -{ - if (trie) { - dmnsn_free(trie->prefix); - - if (trie->leaf) - dmnsn_delete_astnode(trie->value); - - for (size_t i = 0; i < dmnsn_array_size(trie->children); ++i) { - dmnsn_patricia_trie *subtrie; - dmnsn_array_get(trie->children, i, &subtrie); - dmnsn_delete_patricia_trie(subtrie); - } - dmnsn_delete_array(trie->children); - - dmnsn_free(trie); - } -} - -static dmnsn_patricia_trie * -dmnsn_new_patricia_trie(void) -{ - dmnsn_patricia_trie *trie = dmnsn_malloc(sizeof(dmnsn_patricia_trie)); - trie->prefix = dmnsn_strdup(""); - trie->leaf = false; - trie->children = dmnsn_new_array(sizeof(dmnsn_patricia_trie *)); - return trie; -} - -static void -dmnsn_patricia_insert(dmnsn_patricia_trie *trie, - const char *id, dmnsn_astnode value) -{ - /* - * PATRICIA trie insertion: O(k), where k is the length of the longest string - * in the trie. - */ - - ++*value.refcount; - - while (true) { - if (trie->prefix[0] == '\0' && !trie->leaf - && dmnsn_array_size(trie->children) == 0) - { - /* Replace an empty tree with a single-element tree */ - trie->prefix = dmnsn_realloc(trie->prefix, strlen(id) + 1); - strcpy(trie->prefix, id); - - trie->leaf = true; - trie->value = value; - break; - } - - char *prefix = trie->prefix; - while (*prefix == *id && *prefix && *id) { - ++prefix; - ++id; - } - - if (*id == '\0' && *prefix == '\0') { - /* Complete match */ - if (trie->leaf) { - dmnsn_delete_astnode(trie->value); - } - trie->leaf = true; - trie->value = value; - break; - } else if (*prefix == '\0') { - /* Partial match; id starts with prefix */ - size_t i, size = dmnsn_array_size(trie->children); - for (i = 0; i < size; ++i) { - dmnsn_patricia_trie *subtrie; - dmnsn_array_get(trie->children, i, &subtrie); - - if (subtrie->prefix[0] == id[0]) { - trie = subtrie; - break; - } - } - - if (i == size) { - /* No submatch found, add a new child */ - dmnsn_patricia_trie *subtrie = dmnsn_new_patricia_trie(); - dmnsn_array_push(trie->children, &subtrie); - trie = subtrie; - } - } else { - /* Split the tree */ - dmnsn_patricia_trie *copy = dmnsn_new_patricia_trie(); - copy->prefix = dmnsn_realloc(copy->prefix, strlen(prefix) + 1); - strcpy(copy->prefix, prefix); - *prefix = '\0'; - - if (trie->leaf) { - copy->leaf = true; - copy->value = trie->value; - trie->leaf = false; - } - - dmnsn_delete_array(copy->children); - copy->children = trie->children; - trie->children = dmnsn_new_array(sizeof(dmnsn_patricia_trie *)); - - dmnsn_patricia_trie *subtrie = dmnsn_new_patricia_trie(); - dmnsn_array_push(trie->children, ©); - dmnsn_array_push(trie->children, &subtrie); - trie = subtrie; - } - } -} - -static bool -dmnsn_patricia_remove(dmnsn_patricia_trie *trie, const char *id) -{ - /* - * PATRICIA trie removal: O(k), where k is the length of the longest string - * in the trie. - * - * This implementation doesn't actually collapse the tree back upwards if a - * node is left with only one child, to reduce complexity. - */ - - size_t len = strlen(trie->prefix); - if (strncmp(id, trie->prefix, len) != 0) - return false; - id += len; - - while (true) { - if (*id == '\0' && trie->leaf) { - dmnsn_delete_astnode(trie->value); - trie->leaf = false; - return true; - } else { - size_t i, size = dmnsn_array_size(trie->children); - for (i = 0; i < size; ++i) { - dmnsn_patricia_trie *subtrie; - dmnsn_array_get(trie->children, i, &subtrie); - - len = strlen(subtrie->prefix); - if (strncmp(id, subtrie->prefix, len) == 0) { - trie = subtrie; - id += len; - break; - } - } - - if (i == size) - break; - } - } - - return false; -} - -static dmnsn_astnode * -dmnsn_patricia_find(dmnsn_patricia_trie *trie, const char *id) -{ - /* - * PATRICIA trie search: O(k), where k is the length of the longest string - * in the trie. - */ - - size_t len = strlen(trie->prefix); - if (strncmp(id, trie->prefix, len) != 0) - return NULL; - id += len; - - while (true) { - if (*id == '\0' && trie->leaf) { - return &trie->value; - } else { - size_t i, size = dmnsn_array_size(trie->children); - for (i = 0; i < size; ++i) { - dmnsn_patricia_trie *subtrie; - dmnsn_array_get(trie->children, i, &subtrie); - - len = strlen(subtrie->prefix); - if (strncmp(id, subtrie->prefix, len) == 0) { - trie = subtrie; - id += len; - break; - } - } - - if (i == size) - break; - } - } - - return NULL; -} - dmnsn_symbol_table * dmnsn_new_symbol_table(void) { - dmnsn_symbol_table *symtable = dmnsn_new_array(sizeof(dmnsn_patricia_trie *)); + dmnsn_symbol_table *symtable = dmnsn_new_array(sizeof(dmnsn_dictionary *)); dmnsn_push_scope(symtable); return symtable; } @@ -251,49 +50,71 @@ dmnsn_delete_symbol_table(dmnsn_symbol_table *symtable) void dmnsn_push_scope(dmnsn_symbol_table *symtable) { - dmnsn_patricia_trie *scope = dmnsn_new_patricia_trie(); + dmnsn_dictionary *scope = dmnsn_new_dictionary(sizeof(dmnsn_astnode)); dmnsn_array_push(symtable, &scope); } +static void +dmnsn_delete_symbol_table_entry(void *ptr) +{ + dmnsn_astnode *astnode = ptr; + dmnsn_delete_astnode(*astnode); +} + void dmnsn_pop_scope(dmnsn_symbol_table *symtable) { - dmnsn_patricia_trie *scope; + dmnsn_dictionary *scope; dmnsn_array_pop(symtable, &scope); - dmnsn_delete_patricia_trie(scope); + dmnsn_dictionary_apply(scope, &dmnsn_delete_symbol_table_entry); + dmnsn_delete_dictionary(scope); } void dmnsn_local_symbol(dmnsn_symbol_table *symtable, const char *id, dmnsn_astnode value) { - dmnsn_patricia_trie *trie; - dmnsn_array_get(symtable, dmnsn_array_size(symtable) - 1, &trie); - dmnsn_patricia_insert(trie, id, value); + ++*value.refcount; + + dmnsn_dictionary *dict; + dmnsn_array_get(symtable, dmnsn_array_size(symtable) - 1, &dict); + dmnsn_dictionary_insert(dict, id, &value); } void dmnsn_declare_symbol(dmnsn_symbol_table *symtable, const char *id, dmnsn_astnode value) { + ++*value.refcount; + dmnsn_astnode *node = dmnsn_find_symbol(symtable, id); if (node) { /* Always update the most local symbol */ dmnsn_delete_astnode(*node); - ++*value.refcount; *node = value; } else { /* but create new ones at the least local scope */ - dmnsn_patricia_trie *trie; - dmnsn_array_get(symtable, 0, &trie); - dmnsn_patricia_insert(trie, id, value); + dmnsn_dictionary *dict; + dmnsn_array_get(symtable, 0, &dict); + + node = dmnsn_dictionary_at(dict, id); + if (node) { + dmnsn_delete_astnode(*node); + *node = value; + } else { + dmnsn_dictionary_insert(dict, id, &value); + } } } void dmnsn_undef_symbol(dmnsn_symbol_table *symtable, const char *id) { - DMNSN_ARRAY_FOREACH (dmnsn_patricia_trie **, trie, symtable) { - if (dmnsn_patricia_remove(*trie, id)) + DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, dict, symtable) { + dmnsn_astnode *node = dmnsn_dictionary_at(*dict, id); + if (node) { + dmnsn_delete_astnode(*node); + dmnsn_dictionary_remove(*dict, id); break; + } } } @@ -302,11 +123,8 @@ dmnsn_find_symbol(dmnsn_symbol_table *symtable, const char *id) { dmnsn_astnode *symbol = NULL; - for (dmnsn_patricia_trie **trie = dmnsn_array_last(symtable); - trie >= (dmnsn_patricia_trie **)dmnsn_array_first(symtable); - --trie) - { - symbol = dmnsn_patricia_find(*trie, id); + DMNSN_ARRAY_FOREACH_REVERSE (dmnsn_dictionary **, dict, symtable) { + symbol = dmnsn_dictionary_at(*dict, id); if (symbol) break; } diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am index f2778de..1d5077c 100644 --- a/libdimension/Makefile.am +++ b/libdimension/Makefile.am @@ -27,6 +27,7 @@ nobase_include_HEADERS = dimension.h \ dimension/canvas.h \ dimension/color.h \ dimension/csg.h \ + dimension/dictionary.h \ dimension/error.h \ dimension/finish.h \ dimension/finishes.h \ @@ -67,6 +68,7 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \ cone.c \ cube.c \ csg.c \ + dictionary.c \ diffuse.c \ dimension-impl.h \ error.c \ diff --git a/libdimension/dictionary.c b/libdimension/dictionary.c new file mode 100644 index 0000000..281b4de --- /dev/null +++ b/libdimension/dictionary.c @@ -0,0 +1,234 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +/** + * @file + * Associative arrays, implemented with PATRICIA tries. + */ + +#include "dimension.h" + +struct dmnsn_dictionary { + size_t obj_size; /**< The size of the objects in the trie. */ + char *prefix; /**< The local string prefix of the current node. */ + void *value; /**< The node's stored object, if it's a leaf. */ + dmnsn_array *children; /**< The node's children. */ +}; + +dmnsn_dictionary * +dmnsn_new_dictionary(size_t obj_size) +{ + dmnsn_dictionary *dict = dmnsn_malloc(sizeof(dmnsn_dictionary)); + dict->obj_size = obj_size; + dict->prefix = dmnsn_strdup(""); + dict->value = NULL; + dict->children = dmnsn_new_array(sizeof(dmnsn_dictionary *)); + return dict; +} + +void +dmnsn_delete_dictionary(dmnsn_dictionary *dict) +{ + if (dict) { + dmnsn_free(dict->prefix); + dmnsn_free(dict->value); + DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) { + dmnsn_delete_dictionary(*subtrie); + } + dmnsn_delete_array(dict->children); + + dmnsn_free(dict); + } +} + +bool +dmnsn_dictionary_get(const dmnsn_dictionary *dict, const char *key, void *obj) +{ + const void *value = dmnsn_dictionary_at(dict, key); + if (value) { + memcpy(obj, value, dict->obj_size); + return true; + } else { + return false; + } +} + +void * +dmnsn_dictionary_at(const dmnsn_dictionary *dict, const char *key) +{ + /* + * PATRICIA trie search: O(k), where k is the length of the longest string + * in the trie. + */ + + size_t len = strlen(dict->prefix); + if (strncmp(key, dict->prefix, len) != 0) + return NULL; + key += len; + + while (true) { + if (*key == '\0' && dict->value) { + return dict->value; + } else { + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + size_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + len = strlen((*subtrie)->prefix); + if (strncmp(key, (*subtrie)->prefix, len) == 0) { + dict = *subtrie; + key += len; + break; + } + } + + if (subtrie - first == size) + break; + } + } + + return NULL; +} + +void +dmnsn_dictionary_insert(dmnsn_dictionary *dict, const char *key, + const void *obj) +{ + /* + * PATRICIA trie insertion: O(k), where k is the length of the longest string + * in the trie. + */ + + while (true) { + if (dict->prefix[0] == '\0' && !dict->value + && dmnsn_array_size(dict->children) == 0) + { + /* Replace an empty tree with a single-element tree */ + dict->prefix = dmnsn_realloc(dict->prefix, strlen(key) + 1); + strcpy(dict->prefix, key); + + dict->value = dmnsn_malloc(dict->obj_size); + memcpy(dict->value, obj, dict->obj_size); + break; + } + + char *prefix = dict->prefix; + while (*prefix == *key && *prefix && *key) { + ++prefix; + ++key; + } + + if (*key == '\0' && *prefix == '\0') { + /* Complete match */ + if (!dict->value) { + dict->value = dmnsn_malloc(dict->obj_size); + } + memcpy(dict->value, obj, dict->obj_size); + break; + } else if (*prefix == '\0') { + /* Partial match; key starts with prefix */ + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + size_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + if ((*subtrie)->prefix[0] == key[0]) { + dict = *subtrie; + break; + } + } + + if (subtrie - first == size) { + /* No submatch found, add a new child */ + dmnsn_dictionary *child = dmnsn_new_dictionary(dict->obj_size); + dmnsn_array_push(dict->children, &child); + dict = child; + } + } else { + /* Split the tree */ + dmnsn_dictionary *copy = dmnsn_new_dictionary(dict->obj_size); + copy->prefix = dmnsn_realloc(copy->prefix, strlen(prefix) + 1); + strcpy(copy->prefix, prefix); + *prefix = '\0'; + + copy->value = dict->value; + dict->value = NULL; + + dmnsn_array *temp = copy->children; + copy->children = dict->children; + dict->children = temp; + + dmnsn_dictionary *subtrie = dmnsn_new_dictionary(dict->obj_size); + dmnsn_array_push(dict->children, ©); + dmnsn_array_push(dict->children, &subtrie); + dict = subtrie; + } + } +} + +bool +dmnsn_dictionary_remove(dmnsn_dictionary *dict, const char *key) +{ + /* + * PATRICIA trie removal: O(k), where k is the length of the longest string + * in the trie. + * + * This implementation doesn't actually collapse the tree back upwards if a + * node is left with only one child, to reduce complexity. + */ + + size_t len = strlen(dict->prefix); + if (strncmp(key, dict->prefix, len) != 0) + return false; + key += len; + + while (true) { + if (*key == '\0' && dict->value) { + dmnsn_free(dict->value); + dict->value = NULL; + return true; + } else { + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + size_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + len = strlen((*subtrie)->prefix); + if (strncmp(key, (*subtrie)->prefix, len) == 0) { + dict = *subtrie; + key += len; + break; + } + } + + if (subtrie - first == size) + break; + } + } + + return false; +} + +void +dmnsn_dictionary_apply(dmnsn_dictionary *dict, dmnsn_callback_fn *callback) +{ + if (dict->value) { + (*callback)(dict->value); + } + + DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) { + dmnsn_dictionary_apply(*subtrie, callback); + } +} diff --git a/libdimension/dimension.h b/libdimension/dimension.h index 8e7b567..9f7fd67 100644 --- a/libdimension/dimension.h +++ b/libdimension/dimension.h @@ -64,6 +64,7 @@ typedef void dmnsn_free_fn(void *ptr); #include #include #include +#include #include #include #include diff --git a/libdimension/dimension/dictionary.h b/libdimension/dimension/dictionary.h new file mode 100644 index 0000000..61bce4d --- /dev/null +++ b/libdimension/dimension/dictionary.h @@ -0,0 +1,83 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +/** + * @file + * Simple associative arrays. + */ + +/** A string-object associative array. */ +typedef struct dmnsn_dictionary dmnsn_dictionary; + +/** + * Allocate a dictionary. + * @param[in] obj_size The size of the objects to store in the dictionary. + * @return An empty dictionary. + */ +dmnsn_dictionary *dmnsn_new_dictionary(size_t obj_size); + +/** + * Delete a dictionary. + * @param[in,out] dict The dictionary to delete. + */ +void dmnsn_delete_dictionary(dmnsn_dictionary *dict); + +/** + * Find an element in a dictionary. + * @param[in] dict The dictionary to search. + * @param[in] key The key to search for. + * @param[out] obj The location to store the found object. + * @return Whether the element was found. + */ +bool dmnsn_dictionary_get(const dmnsn_dictionary *dict, const char *key, + void *obj); + +/** + * Access an element in a dictionary. + * @param[in] dict The dictionary to search. + * @param[in] key The key to search for. + * @return A pointer to the element if found, otherwise NULL. + */ +void *dmnsn_dictionary_at(const dmnsn_dictionary *dict, const char *key); + +/** + * Insert a (key, value) pair into a dictionary. + * @param[in,out] dict The dictionary to modify. + * @param[in] key The key to insert. + * @param[in] obj The object to insert. + */ +void dmnsn_dictionary_insert(dmnsn_dictionary *dict, const char *key, + const void *obj); + +/** + * Remove a (key, value) pair from a dictionary. + * @param[in,out] dict The dictionary to modify. + * @param[in] key The key to remove. + * @return Whether the key existed in the dictionary. + */ +bool dmnsn_dictionary_remove(dmnsn_dictionary *dict, const char *key); + +/** + * Apply a callback to all elements in a dictionary. + * @param[in,out] dict The dictionary. + * @param[in] callback The callback to apply to the elements. + */ +void dmnsn_dictionary_apply(dmnsn_dictionary *dict, + dmnsn_callback_fn *callback); -- cgit v1.2.3