X-Git-Url: http://git.asbjorn.biz/?a=blobdiff_plain;f=lib%2Fq.c;h=0083dcd56056cc3482d0d7e418e4499c12bf4cde;hb=3ef17c4cee41231e1eed731c08381d3ddf0c8d1a;hp=be54fb9bed3e2e501d333187876a3fb676e95a86;hpb=a12a13df2798b89ec5550a01544b74e4f3265784;p=swftools.git diff --git a/lib/q.c b/lib/q.c index be54fb9..0083dcd 100644 --- a/lib/q.c +++ b/lib/q.c @@ -2,9 +2,23 @@ Part of the swftools package. - Copyright (c) 2001 Matthias Kramm + Copyright (c) 2001,2002,2003,2004 Matthias Kramm + + This program is 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 + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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 + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + - This file is distributed under the GPL, see file COPYING for details */ #include #include #include @@ -22,30 +36,6 @@ char* strdup_n(const char*str, int size) return m; } #endif -void* qmalloc_internal(int len) -{ - void*val = malloc(len); - if(!val) { - printf("memory error! Couldn't reserve %d bytes\n", len); - fprintf(stderr, "memory error! Couldn't reserve %d bytes\n", len); - exit(1); - } - return val; -} -void* qrealloc_internal(void*old, int len) -{ - void*val = realloc(old, len); - if(!val) { - printf("memory error! Couldn't reserve %d bytes\n", len); - fprintf(stderr, "memory error! Couldn't reserve %d bytes\n", len); - exit(1); - } - return val; -} -void qfree_internal(void*old) -{ - free(old); -} char*qstrdup(const char*string) { return strdup(string); @@ -63,7 +53,7 @@ void mem_init(mem_t*mem) } void mem_clear(mem_t*mem) { - free(mem->buffer); + free(mem->buffer);mem->buffer = 0; } void mem_destroy(mem_t*mem) { @@ -177,7 +167,7 @@ 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); + free(i->buffer);i->buffer = 0; free(i); } @@ -394,6 +384,12 @@ void dictionary_put2(dictionary_t*dict, const char*t1, void* t2) string_set(&s, (char*)t1); dictionary_put(dict, s, t2); } +stringarray_t* dictionary_index(dictionary_t*dict) +{ + dictionary_internal_t*d = (dictionary_internal_t*)dict->internal; + return &d->keys; +} + void* dictionary_lookup(dictionary_t*dict, const char*name) { int s; @@ -439,3 +435,117 @@ void dictionary_destroy(dictionary_t*dict) dictionary_clear(dict); free(dict); } + +void dictionary_free_all(dictionary_t* dict, void (*freeFunction)(void*)) +{ + dictionary_internal_t*d = (dictionary_internal_t*)dict->internal; + int num = 0; + char* name = stringarray_at(&d->keys, num) ; + while (name) + { + freeFunction(dictionary_lookup(dict, name)); + num++; + name = stringarray_at(&d->keys, num); + } + dictionary_clear(dict); +} + +// ------------------------------- heap_t ------------------------------- + +void heap_init(heap_t*h,int n,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); +} +void heap_clear(heap_t*h) +{ + free(h->elements); + free(h->data); +} + +#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; + 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)); + + h->elements[node] = node_p; +} +static void down(heap_t*h, int node) +{ + void*node_p = h->elements[node]; + int child = node; + do { + node = child; + + /* determine new child's position */ + child = node<<1|1; + if(child >= h->size) + break; + if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child + child++; + + h->elements[node] = h->elements[child]; + } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child])); + + h->elements[node] = node_p; +} +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]; + up(h, pos); +} +int heap_size(heap_t*h) +{ + return h->size; +} +void* heap_max(heap_t*h) +{ + return h->elements[0]; +} +void* heap_chopmax(heap_t*h) +{ + void*p = h->elements[0]; + h->elements[0] = h->elements[--h->size]; + down(h,0); + return p; +} +void heap_dump(heap_t*h, FILE*fi) +{ + int t; + for(t=0;tsize;t++) { + int s; + for(s=0;s<=t;s=(s+1)*2-1) { + if(s==t) fprintf(fi,"\n"); + } + //fprintf(fi,"%d ", h->elements[t]->x); //? + } +} +void** heap_flatten(heap_t*h) +{ + void**nodes = (void**)malloc(h->size*sizeof(void*)); + void**p = nodes; + + while(h->size) { + /*printf("Heap Size: %d\n", h->size); + heap_print(stdout, h); + printf("\n");*/ + *p++ = heap_chopmax(h); + } + return nodes; +} +