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

diff --git a/lib/q.c b/lib/q.c
index d6615ef..1d27b42 100644
--- a/lib/q.c
+++ b/lib/q.c
@@ -4,9 +4,9 @@
    
    Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
  
-   This program is free software; you can redistribute it and/or modify
+   This program is rfx_free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 2 of the License, or
+   the rfx_free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
@@ -15,14 +15,18 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
+   along with this program; if not, write to the rfx_free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
 
 #include <stdlib.h>
 #include <stdio.h>
+#include <stdarg.h>
 #include <string.h>
+#include <assert.h>
 #include <memory.h>
+#include "mem.h"
+#include "types.h"
 #include "q.h"
 
 // ------------------------------- malloc, alloc routines ---------------------
@@ -30,7 +34,7 @@
 #ifndef STRNDUP
 char* strdup_n(const char*str, int size)
 {
-    char*m = (char*)malloc(size+1);
+    char*m = (char*)rfx_alloc(size+1);
     memcpy(m, str, size);
     m[size] = 0;
     return m;
@@ -44,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 --------------------------------------
 
@@ -53,21 +72,24 @@ void mem_init(mem_t*mem)
 }
 void mem_clear(mem_t*mem)
 {
-    free(mem->buffer);mem->buffer = 0;
+    rfx_free(mem->buffer);mem->buffer = 0;
 }
 void mem_destroy(mem_t*mem)
 {
     mem_clear(mem);
-    free(mem);
+    rfx_free(mem);
 }
 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;
-	m->buffer = m->buffer?(char*)realloc(m->buffer,m->len):(char*)malloc(m->len);
+        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);
     memcpy(&m->buffer[n], data, length);
     if(null)
 	m->buffer[n + length] = 0;
@@ -81,6 +103,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 -------------------------------
 
@@ -94,11 +125,10 @@ typedef struct _ringbuffer_internal_t
 
 void ringbuffer_init(ringbuffer_t*r)
 {
-    ringbuffer_internal_t*i = (ringbuffer_internal_t*)malloc(sizeof(ringbuffer_internal_t)); 
+    ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t)); 
     memset(r, 0, sizeof(ringbuffer_t));
-    memset(i, 0, sizeof(ringbuffer_internal_t));
     r->internal = i;
-    i->buffer = (unsigned char*)malloc(1024);
+    i->buffer = (unsigned char*)rfx_alloc(1024);
     i->buffersize = 1024;
 }
 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
@@ -137,9 +167,9 @@ void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
 	if(newbuffersize < r->available + len)
 	    newbuffersize = r->available + len + 1024;
 
-	buf2 = (unsigned char*)malloc(newbuffersize);
+	buf2 = (unsigned char*)rfx_alloc(newbuffersize);
 	ringbuffer_read(r, buf2, r->available);
-	free(i->buffer);
+	rfx_free(i->buffer);
 	i->buffer = buf2;
 	i->buffersize = newbuffersize;
 	i->readpos = 0;
@@ -161,41 +191,68 @@ void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
 void ringbuffer_clear(ringbuffer_t*r)
 {
     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
-    free(i->buffer);i->buffer = 0;
-    free(i);
+    rfx_free(i->buffer);i->buffer = 0;
+    rfx_free(i);
 }
 
 // ------------------------------- 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**)malloc(n*sizeof(void*));memset(h->elements, 0, n*sizeof(void*));
-    h->data = (char*)malloc(h->max_size*h->elem_size);memset(h->data, 0, 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)
 {
-    free(h->elements);
-    free(h->data);
+    int t;
+    for(t=0;t<h->size;t++) {
+        rfx_free(h->elements[t]);
+        h->elements[t]=0;
+    }
+    rfx_free(h->elements);
+}
+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)
@@ -220,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);
@@ -252,7 +321,7 @@ void heap_dump(heap_t*h, FILE*fi)
 }
 void** heap_flatten(heap_t*h)
 {
-    void**nodes = (void**)malloc(h->size*sizeof(void*));
+    void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
     void**p = nodes;
    
     while(h->size) {
@@ -261,17 +330,208 @@ void** heap_flatten(heap_t*h)
 	printf("\n");*/
 	*p++ = heap_chopmax(h);
     }
+    *p++ = 0;
     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(trielayer_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_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;
+        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;
+    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*)malloc(sizeof(unsigned int)*256);
+    crc32_initialized = 1;
     for(t=0; t<256; t++) {
         unsigned int c = t;
         int s;
@@ -290,7 +550,11 @@ void string_set2(string_t*str, const char*text, int len)
 }
 void string_set(string_t*str, const char*text)
 {
-    str->len = strlen(text);
+    if(text) {
+        str->len = strlen(text);
+    } else {
+        str->len = 0;
+    }
     str->str = text;
 }
 string_t string_new(const char*text, int len)
@@ -303,16 +567,103 @@ string_t string_new(const char*text, int len)
 string_t string_new2(const char*text)
 {
     string_t s;
-    s.len = strlen(text);
+    if(text) {
+        s.len = strlen(text);
+    } else {
+        s.len = 0;
+    }
     s.str = text;
     return s;
 }
-unsigned int string_hash(string_t*str)
+string_t* string_new3(const char*text, int len)
+{
+    if(!text) {
+        string_t*s = malloc(sizeof(string_t));
+        s->len = 0;
+        s->str = 0;
+        return s;
+    } else {
+        string_t*s = malloc(sizeof(string_t)+len+1);
+        s->len = len;
+        s->str = (const char*)(s+1);
+        memcpy((char*)s->str, text, len);
+        ((char*)s->str)[len]=0;
+        return s;
+    }
+}
+string_t* string_new4(const char*text)
+{
+    int l = strlen(text);
+    return string_new3(text, l);
+}
+
+void string_free(string_t*s)
+{
+    if(!s) 
+        return;
+    s->len = 0;
+    if((string_t*)(s->str) == s+1) {
+        s->str = 0;
+        rfx_free(s);
+    } else {
+        rfx_free((char*)(s->str));
+        s->str = 0;
+        rfx_free(s);
+    }
+}
+char* string_cstr(string_t*str)
+{
+    return strdup_n(str->str, str->len);
+}
+char* string_escape(string_t*str)
+{
+    int t;
+    int len = 0;
+    for(t=0;t<str->len;t++) {
+        if(str->str[t]<0x20)
+            len+=3;
+        else
+            len++;
+    }
+    char*s = malloc(len+1);
+    char*p=s;
+    for(t=0;t<str->len;t++) {
+        if(str->str[t]<0x20) {
+            *p++ ='\\';
+            unsigned char c = str->str[t];
+            *p++ = "0123456789abcdef"[c>>4];
+            *p++ = "0123456789abcdef"[c&0x0f];
+        } else {
+            *p++ = str->str[t];
+        }
+    }
+    *p++ = 0;
+    assert(p == &s[len+1]);
+    return s;
+}
+
+unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
+{
+    crc32_init();
+    return checksum>>8 ^ crc32[(b^checksum)&0xff];
+}
+unsigned int crc32_add_string(unsigned int checksum, const char*s)
+{
+    crc32_init();
+    if(!s)
+        return checksum;
+    while(*s) {
+        checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
+        s++;
+    }
+    return checksum;
+}
+
+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];
     }
@@ -321,14 +672,21 @@ unsigned int string_hash(string_t*str)
 unsigned int string_hash2(const char*str)
 {
     unsigned int checksum = 0;
-    if(!crc32)
-        crc32_init();
-    while(*str) {
-        checksum = checksum>>8 ^ crc32[(*str^checksum)&0xff];
-        str++;
+    const char*p = str;
+    crc32_init();
+    while(*p) {
+        checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
+        p++;
     }
     return checksum;
 }
+unsigned int string_hash3(const char*str, int len)
+{
+    string_t s;
+    s.str = str;
+    s.len = len;
+    return string_hash(&s);
+}
 void string_dup2(string_t*str, const char*text, int len)
 {
     str->len = len;
@@ -352,15 +710,9 @@ int string_equals2(string_t*str, string_t*str2)
 	return 1;
     return 0;
 }
-char* string_cstr(string_t*str)
-{
-    return strdup_n(str->str, str->len);
-}
 
 // ------------------------------- stringarray_t ------------------------------
 
-#define DEFAULT_HASH_SIZE 257
-
 typedef struct _stringlist {
     int index;
     struct _stringlist*next;
@@ -378,12 +730,10 @@ void stringarray_init(stringarray_t*sa, int hashsize)
 {
     stringarray_internal_t*s;
     int t;
-    sa->internal = (stringarray_internal_t*)malloc(sizeof(stringarray_internal_t)); 
-    memset(sa->internal, 0, sizeof(stringarray_internal_t));
+    sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
     s = (stringarray_internal_t*)sa->internal;
     mem_init(&s->pos);
-    s->hash = malloc(sizeof(stringlist_t*)*hashsize);
-    memset(s->hash, 0, sizeof(stringlist_t*)*hashsize);
+    s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
     s->hashsize = hashsize;
 }
 void stringarray_put(stringarray_t*sa, string_t str)
@@ -395,7 +745,7 @@ void stringarray_put(stringarray_t*sa, string_t str)
     char*ss = string_cstr(&str);
     mem_put(&s->pos, &ss, sizeof(char*));
 
-    stringlist_t*l = malloc(sizeof(stringlist_t));
+    stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
     l->index = s->num;
     l->next = s->hash[hash];
     s->hash[hash] = l;
@@ -428,7 +778,7 @@ static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
         if(index==l->index) {
             old->next = l->next;
             memset(l, 0, sizeof(stringlist_t));
-            free(l);
+            rfx_free(l);
             if(old==l)
                 return 0;
             else
@@ -475,51 +825,226 @@ void stringarray_clear(stringarray_t*sa)
         while(l) {
             stringlist_t*next = l->next;
             memset(l, 0, sizeof(stringlist_t));
-            free(l);
+            rfx_free(l);
             l = next;
         }
     }
-    free(s->hash);s->hash=0;
-    free(s);
+    rfx_free(s->hash);s->hash=0;
+    rfx_free(s);
 }
 void stringarray_destroy(stringarray_t*sa)
 {
     stringarray_clear(sa);
-    free(sa);
+    rfx_free(sa);
+}
+
+// ------------------------------- type_t -------------------------------
+
+char ptr_equals(const void*o1, const void*o2) 
+{
+    return o1==o2;
+}
+unsigned int ptr_hash(const void*o) 
+{
+    return string_hash3((const char*)&o, sizeof(o));
+}
+void* ptr_dup(const void*o) 
+{
+    return (void*)o;
+}
+void ptr_free(void*o) 
+{
+    return;
+}
+
+char charptr_equals(const void*o1, const void*o2) 
+{
+    if(!o1 || !o2)
+        return o1==o2;
+    return !strcmp(o1,o2);
+}
+unsigned int charptr_hash(const void*o) 
+{
+    if(!o)
+        return 0;
+    return string_hash2(o);
+}
+void* charptr_dup(const void*o) 
+{
+    if(!o)
+        return 0;
+    return strdup(o);
+}
+void charptr_free(void*o) 
+{
+    if(o) {
+        rfx_free(o);
+    }
 }
 
+char stringstruct_equals(const void*o1, const void*o2) 
+{
+    if(!o1 || !o2) 
+        return o1==o2;
+    string_t*s1 = (string_t*)o1;
+    string_t*s2 = (string_t*)o2;
+    int l = s1->len<s2->len?s1->len:s2->len;
+    int r = memcmp(s1->str, s2->str, l);
+    if(r)
+        return 0;
+    else
+        return s1->len==s2->len;
+}
+unsigned int stringstruct_hash(const void*o) 
+{
+    if(!o) return 0;
+    return string_hash(o);
+}
+string_t*string_dup3(string_t*o)
+{
+    if(!o) return 0;
+    if(!o->str) {
+        string_t*s = malloc(sizeof(string_t));
+        s->str=0;
+        s->len=0;
+        return s;
+    }
+    string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
+    s->len = o->len;
+    s->str = (const char*)(s+1);
+    memcpy((char*)s->str, o->str, s->len);
+    ((char*)s->str)[s->len]=0;
+    return s;
+}
+void stringstruct_free(void*o) 
+{
+    if(o)
+        string_free(o);
+}
+
+type_t ptr_type = {
+    equals: ptr_equals,
+    hash: ptr_hash,
+    dup: ptr_dup,
+    free: ptr_free,
+};
+
+type_t charptr_type = {
+    equals: charptr_equals,
+    hash: charptr_hash,
+    dup: charptr_dup,
+    free: charptr_free,
+};
+
+type_t stringstruct_type = {
+    equals: stringstruct_equals,
+    hash: stringstruct_hash,
+    dup: (dup_func)string_dup3,
+    free: stringstruct_free,
+};
 
 // ------------------------------- dictionary_t -------------------------------
 
+#define INITIAL_SIZE 1
+
+static int max(int x, int y) {
+    return x>y?x:y;
+}
+
 dict_t*dict_new()
 {
-    dict_t*d = malloc(sizeof(dict_t));
-    dict_init(d);
+    dict_t*d = rfx_alloc(sizeof(dict_t));
+    dict_init(d, INITIAL_SIZE);
+    return d;
+}
+dict_t*dict_new2(type_t*t)
+{
+    dict_t*d = rfx_alloc(sizeof(dict_t));
+    dict_init(d, INITIAL_SIZE);
+    d->key_type = t;
     return d;
 }
-void dict_init(dict_t*h) 
+void dict_init(dict_t*h, int size) 
 {
     memset(h, 0, sizeof(dict_t));
-    h->hashsize = DEFAULT_HASH_SIZE;
-    h->slots = malloc(sizeof(dictentry_t*)*h->hashsize);
+    h->hashsize = size;
+    h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
     h->num = 0;
-    memset(h->slots, 0, sizeof(dictentry_t*)*h->hashsize);
+    h->key_type = &charptr_type;
 }
-void dict_put(dict_t*h, string_t s, void* data)
+void dict_init2(dict_t*h, type_t*t, int size) 
 {
-    unsigned int checksum = string_hash(&s) % h->hashsize;
-    dictentry_t*e = (dictentry_t*)malloc(sizeof(dictentry_t));
-    e->s = strdup(s.str);
-    e->next = h->slots[checksum];
+    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)
+{
+    dict_t*h = rfx_alloc(sizeof(dict_t));
+    memcpy(h, o, sizeof(dict_t));
+    h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
+    int t;
+    for(t=0;t<o->hashsize;t++) {
+        dictentry_t*e = o->slots[t];
+        while(e) {
+            dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+            memcpy(n, e, sizeof(dictentry_t));
+            n->key = h->key_type->dup(e->key);
+            n->data = e->data;
+            n->next = h->slots[t];
+            h->slots[t] = n;
+            e = e->next;
+        }
+    }
+    return h;
+}
+
+static void dict_expand(dict_t*h, int newlen)
+{
+    assert(h->hashsize < newlen);
+    dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
+    int t; 
+    for(t=0;t<h->hashsize;t++) {
+        dictentry_t*e = h->slots[t];
+        while(e) {
+            dictentry_t*next = e->next;
+            unsigned int newhash = e->hash%newlen;
+            e->next = newslots[newhash];
+            newslots[newhash] = e;
+            e = next;
+        }
+    }
+    if(h->slots)
+        rfx_free(h->slots);
+    h->slots = newslots;
+    h->hashsize = newlen;
+}
+
+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);
+    e->hash = hash; //for resizing
+    e->next = h->slots[hash2];
     e->data = data;
-    h->slots[checksum] = e;
+    h->slots[hash2] = e;
     h->num++;
+    return e;
 }
 void dict_put2(dict_t*h, const char*s, void*data) 
 {
-    string_t s2;
-    string_set(&s2, s);
-    dict_put(h, s2, data);
+    assert(h->key_type == &charptr_type);
+    dict_put(h, s, data);
 }
 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
 {
@@ -527,43 +1052,105 @@ void dict_dump(dict_t*h, FILE*fi, const char*prefix)
     for(t=0;t<h->hashsize;t++) {
         dictentry_t*e = h->slots[t];
         while(e) {
-            fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
+            if(h->key_type!=&charptr_type) {
+                fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
+            } else {
+                fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
+            }
             e = e->next;
         }
     }
 }
+
 int dict_count(dict_t*h)
 {
     return h->num;
 }
-void* dict_lookup(dict_t*h, const char*s)
+
+static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
 {
-    unsigned int checksum = string_hash2(s) % h->hashsize;
-    dictentry_t*e = h->slots[checksum];
+    if(!h->num) {
+        return 0;
+    }
+    
+    unsigned int ohash = h->key_type->hash(key);
+    unsigned int hash = ohash % h->hashsize;
+
+    /* check first entry for match */
+    dictentry_t*e = h->slots[hash];
+    if(e && h->key_type->equals(e->key, key)) {
+        return e;
+    } else if(e) {
+        e = e->next;
+    }
+
+    /* if dict is 2/3 filled, double the size. Do
+       this the first time we have to actually iterate
+       through a slot to find our data */
+    if(e && h->num*3 >= h->hashsize*2) {
+        int newsize = h->hashsize;
+        while(h->num*3 >= newsize*2) {
+            newsize = newsize<15?15:(newsize+1)*2-1;
+        }
+        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(!strcmp(e->s, s)) {
-            return e->data;
+        if(h->key_type->equals(e->key, key)) {
+            /* 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;
     }
     return 0;
 }
-char dict_del(dict_t*h, const char*s)
+void* dict_lookup(dict_t*h, const void*key)
+{
+    dictentry_t*e = dict_do_lookup(h, key);
+    if(e)
+        return e->data;
+    return 0;
+}
+char dict_contains(dict_t*h, const void*key)
+{
+    dictentry_t*e = dict_do_lookup(h, key);
+    return !!e;
+}
+
+char dict_del(dict_t*h, const void*key)
 {
-    unsigned int checksum = string_hash2(s) % h->hashsize;
-    dictentry_t*head = h->slots[checksum];
+    if(!h->num)
+        return 0;
+    unsigned int hash = h->key_type->hash(key) % h->hashsize;
+    dictentry_t*head = h->slots[hash];
     dictentry_t*e = head, *prev=0;
     while(e) {
-        if(!strcmp(e->s, s)) {
+        if(h->key_type->equals(e->key, key)) {
             dictentry_t*next = e->next;
-            free((void*)e->s);
+            h->key_type->free(e->key);
             memset(e, 0, sizeof(dictentry_t));
-            free(e);
+            rfx_free(e);
             if(e == head) {
-                h->slots[checksum] = 0;
+                h->slots[hash] = next;
             } else {
+                assert(prev);
                 prev->next = next;
             }
+            h->num--;
             return 1;
         }
         prev = e;
@@ -571,7 +1158,17 @@ char dict_del(dict_t*h, const char*s)
     }
     return 0;
 }
-void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
+
+dictentry_t* dict_get_slot(dict_t*h, const void*key)
+{
+    if(!h->num)
+        return 0;
+    unsigned int ohash = h->key_type->hash(key);
+    unsigned int hash = ohash % h->hashsize;
+    return h->slots[hash];
+}
+
+void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
 {
     int t;
     for(t=0;t<h->hashsize;t++) {
@@ -579,7 +1176,7 @@ void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*k
         while(e) {
             dictentry_t*next = e->next;
             if(runFunction) {
-                runFunction(data, e->s, e->data);
+                runFunction(data, e->key, e->data);
             }
             e = e->next;
         }
@@ -599,32 +1196,52 @@ 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;
-            free((void*)e->s);
-            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));
-            free(e);
+            rfx_free(e);
             e = next;
         }
+        h->slots[t]=0;
     }
-    free(h->slots);h->slots = 0;
+    rfx_free(h->slots);
+    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)
 {
+    if(!dict)
+        return;
     dict_clear(dict);
-    free(dict);
+    rfx_free(dict);
 }
 
 // ------------------------------- map_t --------------------------------------
@@ -637,15 +1254,17 @@ typedef struct _map_internal_t
 void map_init(map_t*map)
 {
     map_internal_t*m;
-    map->internal = (map_internal_t*)malloc(sizeof(map_internal_t));
-    memset(map->internal, 0, sizeof(map_internal_t));
+    map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
     m = (map_internal_t*)map->internal;
-    dict_init(&m->d);
+    dict_init(&m->d, INITIAL_SIZE);
 }
 void map_put(map_t*map, string_t t1, string_t t2)
 {
     map_internal_t*m = (map_internal_t*)map->internal;
-    dict_put2(&m->d, string_cstr(&t1), (void*)string_cstr(&t2));
+    string_t s;
+    char* s1 = string_cstr(&t1);
+    dict_put2(&m->d, s1, (void*)string_cstr(&t2));
+    rfx_free(s1);
 }
 const char* map_lookup(map_t*map, const char*name)
 {
@@ -653,7 +1272,11 @@ const char* map_lookup(map_t*map, const char*name)
     const char*value = dict_lookup(&m->d, name);
     return value;
 }
-void dumpmapentry(void*data, const char*key, void*value)
+static void freestring(void*data)
+{
+    rfx_free(data);
+}
+static void dumpmapentry(void*data, const void*key, void*value)
 {
     FILE*fi = (FILE*)data;
     fprintf(fi, "%s=%s\n", key, (char*)value);
@@ -662,18 +1285,214 @@ void map_dump(map_t*map, FILE*fi, const char*prefix)
 {
     int t;
     map_internal_t*m = (map_internal_t*)map->internal;
-    fprintf(fi, "ERROR: map dumping not implemented yet\n");
     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
 }
 void map_clear(map_t*map)
 {
     map_internal_t*m = (map_internal_t*)map->internal;
-    dict_clear(&m->d);
-    free(m);
+    dict_free_all(&m->d, 1, freestring);
+    rfx_free(m);
 }
 void map_destroy(map_t*map)
 {
     map_clear(map);
-    free(map);
+    rfx_free(map);
+}
+
+// ------------------------------- array_t --------------------------------------
+
+array_t* array_new() {
+    array_t*d = malloc(sizeof(array_t));
+    memset(d, 0, sizeof(array_t));
+    d->entry2pos = dict_new();
+    return d;
+}
+array_t* array_new2(type_t*type) {
+    array_t*d = malloc(sizeof(array_t));
+    memset(d, 0, sizeof(array_t));
+    d->entry2pos = dict_new2(type);
+    return d;
+}
+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);
+	return 0;
+    }
+    return array->d[nr].name;
+}
+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);
+	return 0;
+    }
+    return array->d[nr].data;
+}
+int array_append(array_t*array, const void*name, void*data) {
+    while(array->size <= array->num) {
+	array->size += 64;
+	if(!array->d) {
+	    array->d = malloc(sizeof(array_entry_t)*array->size);
+	} else {
+	    array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
+	}
+    }
+
+    dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
+
+    if(name) {
+	array->d[array->num].name = e->key;
+    } else {
+	array->d[array->num].name = 0;
+    }
+    array->d[array->num].data = (void*)data;
+    return array->num++;
+}
+int array_find(array_t*array, const void*name)
+{
+    int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
+    return pos-1;
+}
+int array_find2(array_t*array, const void*name, void*data)
+{
+    dict_t*h= array->entry2pos;
+    dictentry_t*e = dict_get_slot(array->entry2pos, name);
+
+    while(e) {
+        int index = ((int)(ptroff_t)e->data) - 1;
+        if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
+            return index;
+        }
+        e = e->next;
+    }
+    return -1;
+}
+int array_update(array_t*array, const void*name, void*data) {
+    int pos = array_find(array, name);
+    if(pos>=0) {
+	array->d[pos].data = data;
+	return pos;
+    }
+    return array_append(array, name, data);
+}
+int array_append_if_new(array_t*array, const void*name, void*data) {
+    int pos = array_find(array, name);
+    if(pos>=0)
+	return pos;
+    return array_append(array, name, data);
+}
+void array_free(array_t*array) {
+    dict_destroy(array->entry2pos);
+    if(array->d) {
+        free(array->d);array->d = 0;
+    }
+    free(array);
+}
+
+// ------------------------------- list_t --------------------------------------
+
+struct _commonlist;
+typedef struct _listinfo {
+    int size;
+    struct _commonlist*last;
+} listinfo_t;
+
+typedef struct _commonlist {
+    void*entry;
+    struct _commonlist*next;
+    listinfo_t info[0];
+} commonlist_t;
+
+int list_length_(void*_list)
+{
+    commonlist_t*l = (commonlist_t*)_list;
+    if(!l)
+        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;
+    commonlist_t* n = 0;
+    if(!*list) {
+        n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
+        *list = n;
+        (*list)->info[0].size = 0;
+    } else {
+        n = malloc(sizeof(commonlist_t));
+        (*list)->info[0].last->next = n;
+    }
+    n->next = 0;
+    n->entry = entry;
+    (*list)->info[0].last = n;
+    (*list)->info[0].size++;
+}
+/* notice: prepending uses slighly more space than appending */
+void list_prepend_(void*_list, void*entry)
+{
+    commonlist_t**list = (commonlist_t**)_list;
+    commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
+    int size = 0;
+    commonlist_t* last = 0;
+    if(*list) {
+        last = (*list)->info[0].last;
+        size = (*list)->info[0].size;
+    }
+    n->next = *list;
+    n->entry = entry;
+    *list = n;
+    (*list)->info[0].last = last;
+    (*list)->info[0].size = size+1;
+}
+void list_free_(void*_list) 
+{
+    commonlist_t**list = (commonlist_t**)_list;
+    commonlist_t*l = *list;
+    while(l) {
+        commonlist_t*next = l->next;
+        free(l);
+        l = next;
+    }
+    *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;
+
+    void*dest = 0;
+    while(l) {
+        commonlist_t*next = l->next;
+        list_append_(&dest, l->entry);
+        l = next;
+    }
+    return dest;
+
 }