X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fq.c;h=a16d1b380753ef197c64d5594179ca2dfd6319de;hp=615f2fe252cdaef1911b0b62183e4307eaf3f34a;hb=2c719855eac434f01d47ba0717d76de65939d74e;hpb=e4687b3aa2aed49fb16ba9e9561344d808750297

diff --git a/lib/q.c b/lib/q.c
index 615f2fe..a16d1b3 100644
--- a/lib/q.c
+++ b/lib/q.c
@@ -113,6 +113,36 @@ int mem_get(mem_t*m, void*data, int length)
     return length;
 }
 
+// ------------------------------- median -------------------------------------
+
+float medianf(float*a, int n)
+{
+    int i,j,l,m;
+    float x;
+    int k=n&1?n/2:n/2-1;
+    l=0; 
+    m=n-1;
+    while(l<m) {
+        x=a[k];
+        i=l;j=m;
+        do {
+            while(a[i]<x) i++;
+            while(x<a[j]) j--;
+            if(i<=j) {
+		//swap
+		float t = a[i];
+		a[i] = a[j];
+		a[j] = t;
+                i++;
+		j--;
+            }
+        } while(i<=j);
+        if(j<k) l=i;
+        if(k<i) m=j;
+    }
+    return a[k];
+}
+
 // ------------------------------- ringbuffer_t -------------------------------
 
 typedef struct _ringbuffer_internal_t
@@ -197,35 +227,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)
@@ -250,20 +307,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);
@@ -282,7 +351,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) {
@@ -291,6 +360,7 @@ void** heap_flatten(heap_t*h)
 	printf("\n");*/
 	*p++ = heap_chopmax(h);
     }
+    *p++ = 0;
     return nodes;
 }
 
@@ -304,7 +374,7 @@ 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)->rest = (unsigned char*)strdup((char*)id);
         (*t)->data = data;
         return 0;
     } 
@@ -319,7 +389,7 @@ static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
         char overwrite = 0;
         if((*t)->rest) 
             overwrite = 1;
-        (*t)->rest = strdup("");
+        (*t)->rest = (unsigned char*)strdup("");
         (*t)->data = data;
         return overwrite;
     }
@@ -327,7 +397,7 @@ static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
 static char _trie_remove(trielayer_t*t, unsigned const char*id)
 {
     while(t) {
-        if(t->rest && !strcmp(t->rest, id)) {
+        if(t->rest && !strcmp((char*)t->rest, (char*)id)) {
             free(t->rest);
             t->rest = 0;
             return 1;
@@ -373,7 +443,7 @@ int trie_contains(trie_t*trie, unsigned const char*id)
 {
     trielayer_t*t = trie->start;
     while(t) {
-        if(t->rest && !strcmp(t->rest, id))
+        if(t->rest && !strcmp((char*)t->rest, (char*)id))
             return 1;
         if(!*id) 
             return 0;
@@ -385,7 +455,7 @@ void* trie_lookup(trie_t*trie, unsigned const char*id)
 {
     trielayer_t*t = trie->start;
     while(t) {
-        if(t->rest && !strcmp(t->rest, id))
+        if(t->rest && !strcmp((char*)t->rest, (char*)id))
             return t->data;
         if(!*id) 
             return 0;
@@ -438,7 +508,7 @@ void _trie_dump(trielayer_t*t, char*buffer, int pos)
     }
     if(t->rest) {
         buffer[pos]=0;
-        printf("%s%s %08x\n", buffer, t->rest, t->data);
+        printf("%s%s %08x\n", buffer, t->rest, (int)t->data);
     }
 }
 
@@ -484,13 +554,14 @@ void trie_rollback(trie_t*t)
 
 
 // ------------------------------- 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;
@@ -603,14 +674,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) {
@@ -624,8 +693,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];
     }
@@ -635,8 +703,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++;
@@ -820,6 +887,23 @@ void ptr_free(void*o)
     return;
 }
 
+char int_equals(const void*o1, const void*o2) 
+{
+    return o1==o2;
+}
+unsigned int int_hash(const void*o) 
+{
+    return string_hash3((const char*)&o, sizeof(o));
+}
+void* int_dup(const void*o) 
+{
+    return (void*)o;
+}
+void int_free(void*o) 
+{
+    return;
+}
+
 char charptr_equals(const void*o1, const void*o2) 
 {
     if(!o1 || !o2)
@@ -885,6 +969,13 @@ void stringstruct_free(void*o)
         string_free(o);
 }
 
+type_t int_type = {
+    equals: int_equals,
+    hash: int_hash,
+    dup: int_dup,
+    free: int_free,
+};
+
 type_t ptr_type = {
     equals: ptr_equals,
     hash: ptr_hash,
@@ -990,6 +1081,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);
@@ -1012,9 +1107,9 @@ void dict_dump(dict_t*h, FILE*fi, const char*prefix)
         dictentry_t*e = h->slots[t];
         while(e) {
             if(h->key_type!=&charptr_type) {
-                fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
+                fprintf(fi, "%s%08x=%08x\n", prefix, (int)e->key, (int)e->data);
             } else {
-                fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
+                fprintf(fi, "%s%s=%08x\n", prefix, (char*)e->key, (int)e->data);
             }
             e = e->next;
         }
@@ -1100,7 +1195,35 @@ 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] = next;
+            } else {
+                assert(prev);
+                prev->next = next;
+            }
+            h->num--;
+            return 1;
+        }
+        prev = e;
+        e = e->next;
+    }
+    return 0;
+}
+
+char dict_del2(dict_t*h, const void*key, void*data)
+{
+    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(h->key_type->equals(e->key, key) && e->data == data) {
+            dictentry_t*next = e->next;
+            h->key_type->free(e->key);
             memset(e, 0, sizeof(dictentry_t));
             rfx_free(e);
             if(e == head) {
@@ -1197,10 +1320,57 @@ void dict_destroy_shallow(dict_t*dict)
 
 void dict_destroy(dict_t*dict)
 {
+    if(!dict)
+        return;
     dict_clear(dict);
     rfx_free(dict);
 }
 
+// ------------------------------- mtf_t --------------------------------------
+mtf_t* mtf_new(type_t*type)
+{
+    NEW(mtf_t, mtf);
+    mtf->type = type;
+    return mtf;
+}
+void mtf_increase(mtf_t*m, const void*key)
+{
+    mtf_item_t*item = m->first;
+    mtf_item_t*last = 0;
+    while(item) {
+	if(m->type->equals(item->key, key)) {
+	    item->num++;
+	    if(item->num>m->first->num) {
+		if(last) last->next = item->next;
+		else m->first = item->next;
+		item->next = m->first;
+		m->first = item;
+	    }
+            return;
+	}
+	last = item;
+	item = item->next;
+    }
+    NEW(mtf_item_t,n);
+    if(last) last->next = n;
+    else m->first = n;
+    n->key = key;
+    n->num = 1;
+}
+void mtf_destroy(mtf_t*m)
+{
+    if(!m) return;
+    mtf_item_t*item = m->first;
+    m->first = 0;
+    while(item) {
+	mtf_item_t*next = item->next;
+	item->next = 0;
+	free(item);
+	item = next;
+    }
+    free(m);
+}
+
 // ------------------------------- map_t --------------------------------------
 
 typedef struct _map_internal_t
@@ -1236,7 +1406,7 @@ static void freestring(void*data)
 static void dumpmapentry(void*data, const void*key, void*value)
 {
     FILE*fi = (FILE*)data;
-    fprintf(fi, "%s=%s\n", key, (char*)value);
+    fprintf(fi, "%s=%s\n", (char*)key, (char*)value);
 }
 void map_dump(map_t*map, FILE*fi, const char*prefix)
 {
@@ -1272,14 +1442,14 @@ 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);
+	fprintf(stderr, "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);
+	fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
 	return 0;
     }
     return array->d[nr].data;