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 ++++++++---------------------------------------------- 1 file changed, 37 insertions(+), 219 deletions(-) (limited to 'dimension') 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; } -- cgit v1.2.3