Make PATRICIA tries available as a generic dictionary API.

1 files changed, 37 insertions, 219 deletions

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