added rollbacking functionality to trier (for namespaces)

[swftools.git] / lib / q.c

diff --git a/lib/q.c b/lib/q.c
index e578107..519da40 100644 (file)
--- a/lib/q.c
+++ b/lib/q.c
@@ -280,37 +280,168 @@ void** heap_flatten(heap_t*h)
 
 // ------------------------------- trie --------------------------------------
 
-void trie_put(trie_t**t, unsigned const char*id)
+trie_t*trie_new()
+{
+    return (trie_t*)rfx_calloc(sizeof(trie_t));
+}
+static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
 {
     if(!*t) {
         (*t) = rfx_calloc(sizeof(trie_t));
         (*t)->rest = (unsigned char*)strdup(id);
-        return;
+        (*t)->data = data;
+        return 0;
     } 
     if((*t)->rest && (*t)->rest[0]) {
-        // shift whatever's currently in here one node down
-        trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1);
+        // make room: shift whatever's currently in here one node down
+        _trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1, (*t)->data);
         (*t)->rest = 0;
     }
     if(id[0]) {
-        trie_put(&(*t)->row[id[0]], id+1);
+        return _trie_put(&(*t)->row[id[0]], id+1, data);
     } else {
-        (*t)->rest = "";
+        char overwrite = 0;
+        if((*t)->rest) 
+            overwrite = 1;
+        (*t)->rest = strdup("");
+        (*t)->data = data;
+        return overwrite;
     }
 }
+static char _trie_remove(trielayer_t*t, unsigned const char*id)
+{
+    while(t) {
+        if(t->rest && !strcmp(t->rest, id)) {
+            free(t->rest);
+            t->rest = 0;
+            return 1;
+        }
+        if(!*id) 
+            return 0;
+        t = t->row[*id++];
+    }
+    return 0;
+}
+
+static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data);
+static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data);
 
-int trie_lookup(trie_t*t, unsigned const char*id)
+void trie_put(trie_t*t, unsigned const char*id, void*data)
+{
+    if(!t->rollback) {
+        _trie_put(&t->start, id, data);
+    } else {
+        char contains = trie_contains(t, id);
+        void*olddata = contains?trie_lookup(t, id):0;
+        trie_rollback_removes(t, id, data);
+        _trie_put(&t->start, id, data);
+        if(contains) {
+            trie_rollback_adds(t, id, olddata);
+        }
+    }
+}
+char trie_remove(trie_t*t, unsigned const char*id)
 {
+    if(!t->rollback) {
+        return _trie_remove(t->start, id);
+    } else {
+        void*olddata = trie_lookup(t, id);
+        char exists = _trie_remove(t->start, id);
+        if(exists) {
+            trie_rollback_removes(t, id, olddata);
+        }
+        return exists;
+    }
+}
+int trie_contains(trie_t*trie, unsigned const char*id)
+{
+    trielayer_t*t = trie->start;
     while(t) {
         if(t->rest && !strcmp(t->rest, id))
             return 1;
-        t = t->row[id[0]];
         if(!*id) 
             return 0;
-        id++;
+        t = t->row[*id++];
     }
     return 0;
 }
+void* trie_lookup(trie_t*trie, unsigned const char*id)
+{
+    trielayer_t*t = trie->start;
+    while(t) {
+        if(t->rest && !strcmp(t->rest, id))
+            return t->data;
+        if(!*id) 
+            return 0;
+        t = t->row[*id++];
+    }
+    return 0;
+}
+
+typedef struct _triememory {
+    const unsigned char*key;
+    void*data;
+    struct _triememory*next;
+} triememory_t;
+
+typedef struct _trierollback {
+    triememory_t*add;
+    triememory_t*remove;
+    struct _trierollback*prev;
+} trierollback_t;
+
+static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
+{
+    trierollback_t*rollback = (trierollback_t*)t->rollback;
+    triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
+    m->key = id;
+    m->data = data;
+    m->next = rollback->add;
+    rollback->add = m;
+}
+static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
+{
+    trierollback_t*rollback = (trierollback_t*)t->rollback;
+    triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
+    m->key = id;
+    m->data = data;
+    m->next = rollback->remove;
+    rollback->remove = m;
+}
+
+void trie_remember(trie_t*t)
+{
+    trierollback_t*old = (trierollback_t*)t->rollback;
+    t->rollback = (trierollback_t*)rfx_calloc(sizeof(trierollback_t));
+    ((trierollback_t*)t->rollback)->prev = old;
+}
+
+void trie_rollback(trie_t*t)
+{
+    trierollback_t*rollback = (trierollback_t*)t->rollback;
+    if(!rollback) {
+        fprintf(stderr, "Internal error: can't roll back this trie any further\n");
+        return;
+    }
+    t->rollback = ((trierollback_t*)t->rollback)->prev;
+
+    triememory_t*remove = rollback->remove;
+    while(remove) {
+        triememory_t*next = remove->next;
+        if(!trie_remove(t, remove->key)) {
+            fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", remove->key);
+        }
+        free(remove);
+        remove = next;
+    }
+    triememory_t*add = rollback->add;
+    while(add) {
+        triememory_t*next = add->next;
+        trie_put(t, add->key, add->data);
+        add = next;
+    }
+}
+
 
 // ------------------------------- crc32 --------------------------------------
 static unsigned int*crc32 = 0;
@@ -764,6 +895,14 @@ void dict_init(dict_t*h, int size)
     h->num = 0;
     h->key_type = &charptr_type;
 }
+void dict_init2(dict_t*h, type_t*t, int size) 
+{
+    memset(h, 0, sizeof(dict_t));
+    h->hashsize = size;
+    h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
+    h->num = 0;
+    h->key_type = t;
+}
 
 dict_t*dict_clone(dict_t*o)
 {
@@ -925,7 +1064,7 @@ char dict_del(dict_t*h, const void*key)
             memset(e, 0, sizeof(dictentry_t));
             rfx_free(e);
             if(e == head) {
-                h->slots[hash] = 0;
+                h->slots[hash] = next;
             } else {
                 assert(prev);
                 prev->next = next;
@@ -1094,7 +1233,6 @@ array_t* array_new2(type_t*type) {
 void*array_getkey(array_t*array, int nr) {
     if(nr > array->num || nr<0) {
        printf("error: reference to element %d in array[%d]\n", nr, array->num);
-        *(int*)0 = 0xdead;
        return 0;
     }
     return array->d[nr].name;
@@ -1102,7 +1240,6 @@ void*array_getkey(array_t*array, int nr) {
 void*array_getvalue(array_t*array, int nr) {
     if(nr > array->num || nr<0) {
        printf("error: reference to element %d in array[%d]\n", nr, array->num);
-        *(int*)0 = 0xdead;
        return 0;
     }
     return array->d[nr].data;
@@ -1275,3 +1412,4 @@ void*list_clone_(void*_list)
     return dest;
 
 }
+