Make PATRICIA tries available as a generic dictionary API.

4 files changed, 320 insertions, 0 deletions

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, &copy);
+      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);