X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fq.c;h=1d27b4238ce810113c649a33ac0668096bb4b8ba;hp=55a4c06f8d50db3493a104658d5513d522afc444;hb=fec1ab31707e68c2396b186e0e4928632402d649;hpb=9f2b929b62347a78873023e78d837cb8765c3f54

diff --git a/lib/q.c b/lib/q.c
index 55a4c06..1d27b42 100644
--- a/lib/q.c
+++ b/lib/q.c
@@ -21,6 +21,7 @@
 
 #include <stdlib.h>
 #include <stdio.h>
+#include <stdarg.h>
 #include <string.h>
 #include <assert.h>
 #include <memory.h>
@@ -47,6 +48,21 @@ char*qstrndup(const char*string, int len)
 {
     return strdup_n(string, len);
 }
+char* allocprintf(const char*format, ...)
+{
+    va_list arglist1;
+    va_start(arglist1, format);
+    char dummy;
+    int l = vsnprintf(&dummy, 1, format, arglist1);
+    va_end(arglist1);
+
+    va_list arglist2;
+    va_start(arglist2, format);
+    char*buf = malloc(l+1);
+    vsnprintf(buf, l+1, format, arglist2);
+    va_end(arglist2);
+    return buf;
+}
 
 // ------------------------------- mem_t --------------------------------------
 
@@ -181,35 +197,62 @@ void ringbuffer_clear(ringbuffer_t*r)
 
 // ------------------------------- heap_t -------------------------------
 
-void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
+void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
 {
     memset(h, 0, sizeof(heap_t));
-    h->max_size = n;
     h->size = 0;
     h->elem_size = elem_size;
     h->compare = compare;
-    h->elements = (void**)rfx_calloc(n*sizeof(void*));
-    h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
+    h->elements = 0;
+    h->max_size = 0;
+}
+heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
+{
+    heap_t*h = malloc(sizeof(heap_t));
+    heap_init(h, elem_size, compare);
+    return h;
+}
+heap_t* heap_clone(heap_t*o)
+{
+    heap_t*h = malloc(sizeof(heap_t));
+    memcpy(h, o, sizeof(heap_t));
+    h->elements = rfx_alloc(sizeof(void*)*h->size);
+    int t;
+    for(t=0;t<h->size;t++) {
+        h->elements[t] = rfx_alloc(h->elem_size);
+        memcpy(h->elements[t], o->elements[t], h->elem_size);
+    }
+    return h;
 }
 void heap_clear(heap_t*h)
 {
+    int t;
+    for(t=0;t<h->size;t++) {
+        rfx_free(h->elements[t]);
+        h->elements[t]=0;
+    }
     rfx_free(h->elements);
-    rfx_free(h->data);
+}
+void heap_destroy(heap_t*h)
+{
+    heap_clear(h);
+    free(h);
 }
 
-#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
 
 static void up(heap_t*h, int node)
 {
     void*node_p = h->elements[node];
     int parent = node;
+    int tmp = node;
     do {
 	node = parent;
 	if(!node) break;
 	parent = (node-1)/2;
 	h->elements[node] = h->elements[parent];
-    } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
-
+    } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
     h->elements[node] = node_p;
 }
 static void down(heap_t*h, int node)
@@ -234,20 +277,32 @@ static void down(heap_t*h, int node)
 void heap_put(heap_t*h, void*e) 
 {
     int pos = h->size++;
-    memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
-    h->elements[pos] = &h->data[pos];
+    void*data = rfx_alloc(h->elem_size);
+    memcpy(data,e,h->elem_size);
+
+    if(pos>=h->max_size) {
+        h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
+        h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
+        assert(pos<h->max_size);
+    }
+
+    h->elements[pos] = data;
     up(h, pos);
 }
 int heap_size(heap_t*h)
 {
     return h->size;
 }
-void* heap_max(heap_t*h)
+void* heap_peek(heap_t*h)
 {
+    if(!h || !h->size) 
+        return 0;
     return h->elements[0];
 }
 void* heap_chopmax(heap_t*h)
 {
+    if(!h->size)
+        return 0;
     void*p = h->elements[0];
     h->elements[0] = h->elements[--h->size];
     down(h,0);
@@ -266,7 +321,7 @@ void heap_dump(heap_t*h, FILE*fi)
 }
 void** heap_flatten(heap_t*h)
 {
-    void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
+    void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
     void**p = nodes;
    
     while(h->size) {
@@ -275,51 +330,208 @@ void** heap_flatten(heap_t*h)
 	printf("\n");*/
 	*p++ = heap_chopmax(h);
     }
+    *p++ = 0;
     return nodes;
 }
 
 // ------------------------------- 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) = rfx_calloc(sizeof(trielayer_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;
 }
 
-int trie_lookup(trie_t*t, unsigned const char*id)
+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);
+
+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_put(&t->start, id, data);
+        if(contains) {
+            trie_rollback_adds(t, id, olddata);
+        }
+        trie_rollback_removes(t, id, data);
+    }
+}
+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_adds(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;
+    char del; // 0/1
+    struct _triememory*next;
+} triememory_t;
+
+typedef struct _trierollback {
+    triememory_t*ops;
+    struct _trierollback*prev;
+} trierollback_t;
+
+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->del = 0;
+    m->next = rollback->ops;
+    rollback->ops = m;
+}
+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->del = 1;
+    m->next = rollback->ops;
+    rollback->ops = m;
+}
+
+void _trie_dump(trielayer_t*t, char*buffer, int pos)
+{
+    int i;
+    for(i=0;i<256;i++) {
+        if(t->row[i]) {
+            buffer[pos]=i;
+            _trie_dump(t->row[i], buffer, pos+1);
+        }
+    }
+    if(t->rest) {
+        buffer[pos]=0;
+        printf("%s%s %08x\n", buffer, t->rest, t->data);
+    }
+}
+
+void trie_dump(trie_t*t) 
+{
+    char buffer[256];
+    _trie_dump(t->start, buffer, 0);
+}
+
+
+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*op = rollback->ops;
+    while(op) {
+        triememory_t*next = op->next;
+        if(op->del) {
+            if(!_trie_remove(t->start, op->key)) {
+                fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", op->key);
+            }
+        } else {
+            if(_trie_put(&t->start, op->key, op->data)) {
+                fprintf(stderr, "Internal error: overwrote key %s in trie during rollback\n", op->key);
+            }
+        }
+        free(op);
+        op = next;
+    }
+}
+
 
 // ------------------------------- crc32 --------------------------------------
-static unsigned int*crc32 = 0;
+static unsigned int crc32[256];
+static char crc32_initialized=0;
 static void crc32_init(void)
 {
     int t;
-    if(crc32) 
+    if(crc32_initialized) 
         return;
-    crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
+    crc32_initialized = 1;
     for(t=0; t<256; t++) {
         unsigned int c = t;
         int s;
@@ -432,14 +644,12 @@ char* string_escape(string_t*str)
 
 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
 {
-    if(!crc32)
-        crc32_init();
+    crc32_init();
     return checksum>>8 ^ crc32[(b^checksum)&0xff];
 }
 unsigned int crc32_add_string(unsigned int checksum, const char*s)
 {
-    if(!crc32)
-        crc32_init();
+    crc32_init();
     if(!s)
         return checksum;
     while(*s) {
@@ -453,8 +663,7 @@ unsigned int string_hash(const string_t*str)
 {
     int t;
     unsigned int checksum = 0;
-    if(!crc32)
-        crc32_init();
+    crc32_init();
     for(t=0;t<str->len;t++) {
         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
     }
@@ -464,8 +673,7 @@ unsigned int string_hash2(const char*str)
 {
     unsigned int checksum = 0;
     const char*p = str;
-    if(!crc32)
-        crc32_init();
+    crc32_init();
     while(*p) {
         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
         p++;
@@ -764,6 +972,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)
 {
@@ -811,6 +1027,10 @@ dictentry_t* dict_put(dict_t*h, const void*key, void* data)
 {
     unsigned int hash = h->key_type->hash(key);
     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+    
+    if(!h->hashsize)
+        dict_expand(h, 1);
+
     unsigned int hash2 = hash % h->hashsize;
     
     e->key = h->key_type->dup(key);
@@ -921,11 +1141,11 @@ char dict_del(dict_t*h, const void*key)
     while(e) {
         if(h->key_type->equals(e->key, key)) {
             dictentry_t*next = e->next;
-            rfx_free((void*)e->key);
+            h->key_type->free(e->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;
@@ -1018,6 +1238,8 @@ void dict_destroy_shallow(dict_t*dict)
 
 void dict_destroy(dict_t*dict)
 {
+    if(!dict)
+        return;
     dict_clear(dict);
     rfx_free(dict);
 }
@@ -1273,3 +1495,4 @@ void*list_clone_(void*_list)
     return dest;
 
 }
+