X-Git-Url: http://git.asbjorn.biz/?a=blobdiff_plain;f=lib%2Fq.c;h=519da40655a43f7b3f5dc7a158886558f782bb33;hb=71c8242a8242eeb6e8b6dcf57239550a6f35c88a;hp=8c67d06e0275525cbd90e12bab3f82ba68efbdeb;hpb=b1993c38d9f4ba57943c607b2151eca7d1c125b7;p=swftools.git

diff --git a/lib/q.c b/lib/q.c
index 8c67d06..519da40 100644
--- a/lib/q.c
+++ b/lib/q.c
@@ -68,7 +68,9 @@ static int mem_put_(mem_t*m,const void*data, int length, int null)
     int n = m->pos;
     m->pos += length + (null?1:0);
     if(m->pos > m->len) { 
-        m->len = (m->pos+63)&~63;
+        int v1 = (m->pos+63)&~63;
+        int v2 = m->len + m->len / 2;
+        m->len = v1>v2?v1:v2;
 	m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
     }
     assert(n+length <= m->len);
@@ -85,6 +87,15 @@ int mem_putstring(mem_t*m,string_t str)
 {
     return mem_put_(m, str.str, str.len, 1);
 }
+int mem_get(mem_t*m, void*data, int length)
+{
+    if(m->read_pos + length > m->pos) {
+        length = m->pos - m->read_pos;
+    }
+    memcpy(data, m->buffer+m->read_pos, length);
+    m->read_pos += length;
+    return length;
+}
 
 // ------------------------------- ringbuffer_t -------------------------------
 
@@ -267,6 +278,171 @@ void** heap_flatten(heap_t*h)
     return nodes;
 }
 
+// ------------------------------- trie --------------------------------------
+
+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);
+        (*t)->data = data;
+        return 0;
+    } 
+    if((*t)->rest && (*t)->rest[0]) {
+        // 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]) {
+        return _trie_put(&(*t)->row[id[0]], id+1, data);
+    } else {
+        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);
+
+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;
+        if(!*id) 
+            return 0;
+        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;
 static void crc32_init(void)
@@ -393,10 +569,12 @@ unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
 }
 unsigned int crc32_add_string(unsigned int checksum, const char*s)
 {
+    if(!crc32)
+        crc32_init();
     if(!s)
         return checksum;
     while(*s) {
-        checksum = crc32_add_byte(checksum, *s);
+        checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
         s++;
     }
     return checksum;
@@ -591,7 +769,7 @@ char ptr_equals(const void*o1, const void*o2)
 }
 unsigned int ptr_hash(const void*o) 
 {
-    return string_hash3(o, sizeof(o));
+    return string_hash3((const char*)&o, sizeof(o));
 }
 void* ptr_dup(const void*o) 
 {
@@ -717,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)
 {
@@ -800,11 +986,10 @@ int dict_count(dict_t*h)
     return h->num;
 }
 
-void dict_do_lookup(dict_t*h, const void*key, void***match)
+static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
 {
     if(!h->num) {
-        *match = 0;
-        return;
+        return 0;
     }
     
     unsigned int ohash = h->key_type->hash(key);
@@ -813,8 +998,7 @@ void dict_do_lookup(dict_t*h, const void*key, void***match)
     /* check first entry for match */
     dictentry_t*e = h->slots[hash];
     if(e && h->key_type->equals(e->key, key)) {
-        *match = &e->data;
-        return;
+        return e;
     } else if(e) {
         e = e->next;
     }
@@ -830,31 +1014,40 @@ void dict_do_lookup(dict_t*h, const void*key, void***match)
         dict_expand(h, newsize);
         hash = ohash % h->hashsize;
         e = h->slots[hash];
+        if(e && h->key_type->equals(e->key, key)) {
+            // omit move to front
+            return e;
+        } else if(e) {
+            e = e->next;
+        }
     }
 
     /* check subsequent entries for a match */
+    dictentry_t*last = h->slots[hash];
     while(e) {
         if(h->key_type->equals(e->key, key)) {
-            *match = &e->data;
-            return;
+            /* move to front- makes a difference of about 10% in most applications */
+            last->next = e->next;
+            e->next = h->slots[hash];
+            h->slots[hash] = e;
+            return e;
         }
+        last=e;
         e = e->next;
     }
-    *match = 0;
+    return 0;
 }
 void* dict_lookup(dict_t*h, const void*key)
 {
-    void**data = 0;
-    dict_do_lookup(h, key, &data);
-    if(data)
-        return *data;
+    dictentry_t*e = dict_do_lookup(h, key);
+    if(e)
+        return e->data;
     return 0;
 }
 char dict_contains(dict_t*h, const void*key)
 {
-    void**data = 0;
-    dict_do_lookup(h, key, &data);
-    return !!data;
+    dictentry_t*e = dict_do_lookup(h, key);
+    return !!e;
 }
 
 char dict_del(dict_t*h, const void*key)
@@ -871,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;
@@ -923,16 +1116,18 @@ void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
     }
 }
 
-void dict_free_all(dict_t*h, void (*freeFunction)(void*))
+void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
 {
     int t;
     for(t=0;t<h->hashsize;t++) {
         dictentry_t*e = h->slots[t];
         while(e) {
             dictentry_t*next = e->next;
-            h->key_type->free(e->key);
-            if(freeFunction) {
-                freeFunction(e->data);
+            if(free_keys) {
+                h->key_type->free(e->key);
+            }
+            if(free_data_function) {
+                free_data_function(e->data);
             }
             memset(e, 0, sizeof(dictentry_t));
             rfx_free(e);
@@ -944,9 +1139,20 @@ void dict_free_all(dict_t*h, void (*freeFunction)(void*))
     memset(h, 0, sizeof(dict_t));
 }
 
+void dict_clear_shallow(dict_t*h) 
+{
+    dict_free_all(h, 0, 0);
+}
+
 void dict_clear(dict_t*h) 
 {
-    dict_free_all(h, 0);
+    dict_free_all(h, 1, 0);
+}
+
+void dict_destroy_shallow(dict_t*dict)
+{
+    dict_clear_shallow(dict);
+    rfx_free(dict);
 }
 
 void dict_destroy(dict_t*dict)
@@ -1001,7 +1207,7 @@ void map_dump(map_t*map, FILE*fi, const char*prefix)
 void map_clear(map_t*map)
 {
     map_internal_t*m = (map_internal_t*)map->internal;
-    dict_free_all(&m->d, freestring);
+    dict_free_all(&m->d, 1, freestring);
     rfx_free(m);
 }
 void map_destroy(map_t*map)
@@ -1027,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;
@@ -1035,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;
@@ -1122,6 +1326,20 @@ int list_length_(void*_list)
         return 0;
     return l->info[0].size;
 }
+void list_concat_(void*_l1, void*_l2)
+{
+    commonlist_t**l1 = (commonlist_t**)_l1;
+    commonlist_t**l2 = (commonlist_t**)_l2;
+
+    if(!*l1) {
+        *l1 = *l2;
+    } else if(*l2) {
+        (*l1)->info[0].last->next = *l2;
+        (*l1)->info[0].last = (*l2)->info[0].last;
+        (*l1)->info[0].size += (*l2)->info[0].size;
+    }
+    *l2 = 0;
+}
 void list_append_(void*_list, void*entry)
 {
     commonlist_t**list = (commonlist_t**)_list;
@@ -1167,6 +1385,20 @@ void list_free_(void*_list)
     }
     *list = 0;
 }
+void list_deep_free_(void*_list)
+{
+    commonlist_t**list = (commonlist_t**)_list;
+    commonlist_t*l = *list;
+    while(l) {
+        commonlist_t*next = l->next;
+        if(l->entry) {
+            free(l->entry);l->entry=0;
+        }
+        free(l);
+        l = next;
+    }
+    *list = 0;
+}
 void*list_clone_(void*_list) 
 {
     commonlist_t*l = *(commonlist_t**)_list;
@@ -1180,3 +1412,4 @@ void*list_clone_(void*_list)
     return dest;
 
 }
+