From 4f0c30aee2c56967895c981534414d1b04e9e0ce Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
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 <tavianator@gmail.com> *
+ * *
+ * 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 *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @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 <dimension/malloc.h>
#include <dimension/array.h>
#include <dimension/list.h>
+#include <dimension/dictionary.h>
#include <dimension/progress.h>
#include <dimension/timer.h>
#include <dimension/geometry.h>
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 <tavianator@gmail.com> *
+ * *
+ * 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 *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @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