darwin fixes
[swftools.git] / lib / q.c
1 /* q.c
2
3    Part of the swftools package.
4    
5    Copyright (c) 2001,2002,2003,2004 Matthias Kramm <kramm@quiss.org>
6  
7    This program is rfx_free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the rfx_free Software Foundation; either version 2 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program; if not, write to the rfx_free Software
19    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
20
21
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <stdarg.h>
25 #include <string.h>
26 #include <assert.h>
27 #include <memory.h>
28 #include "mem.h"
29 #include "types.h"
30 #include "q.h"
31
32 // ------------------------------- malloc, alloc routines ---------------------
33
34 #ifndef STRNDUP
35 char* strdup_n(const char*str, int size)
36 {
37     char*m = (char*)rfx_alloc(size+1);
38     memcpy(m, str, size);
39     m[size] = 0;
40     return m;
41 }
42 #endif
43 char*qstrdup(const char*string)
44 {
45     return strdup(string);
46 }
47 char*qstrndup(const char*string, int len)
48 {
49     return strdup_n(string, len);
50 }
51 char* allocprintf(const char*format, ...)
52 {
53     va_list arglist1;
54     va_start(arglist1, format);
55     char dummy;
56     int l = vsnprintf(&dummy, 1, format, arglist1);
57     va_end(arglist1);
58
59     va_list arglist2;
60     va_start(arglist2, format);
61     char*buf = malloc(l+1);
62     vsnprintf(buf, l+1, format, arglist2);
63     va_end(arglist2);
64     return buf;
65 }
66
67 // ------------------------------- mem_t --------------------------------------
68
69 void mem_init(mem_t*mem)
70 {
71     memset(mem, 0, sizeof(mem_t));
72 }
73 void mem_clear(mem_t*mem)
74 {
75     rfx_free(mem->buffer);mem->buffer = 0;
76 }
77 void mem_destroy(mem_t*mem)
78 {
79     mem_clear(mem);
80     rfx_free(mem);
81 }
82 static int mem_put_(mem_t*m,const void*data, int length, int null)
83 {
84     int n = m->pos;
85     m->pos += length + (null?1:0);
86     if(m->pos > m->len) { 
87         int v1 = (m->pos+63)&~63;
88         int v2 = m->len + m->len / 2;
89         m->len = v1>v2?v1:v2;
90         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
91     }
92     assert(n+length <= m->len);
93     memcpy(&m->buffer[n], data, length);
94     if(null)
95         m->buffer[n + length] = 0;
96     return n;
97 }
98 int mem_put(mem_t*m,void*data, int length)
99 {
100     return mem_put_(m, data, length, 0);
101 }
102 int mem_putstring(mem_t*m,string_t str)
103 {
104     return mem_put_(m, str.str, str.len, 1);
105 }
106 int mem_get(mem_t*m, void*data, int length)
107 {
108     if(m->read_pos + length > m->pos) {
109         length = m->pos - m->read_pos;
110     }
111     memcpy(data, m->buffer+m->read_pos, length);
112     m->read_pos += length;
113     return length;
114 }
115
116 // ------------------------------- median -------------------------------------
117
118 float medianf(float*a, int n)
119 {
120     int i,j,l,m;
121     float x;
122     int k=n&1?n/2:n/2-1;
123     l=0; 
124     m=n-1;
125     while(l<m) {
126         x=a[k];
127         i=l;j=m;
128         do {
129             while(a[i]<x) i++;
130             while(x<a[j]) j--;
131             if(i<=j) {
132                 //swap
133                 float t = a[i];
134                 a[i] = a[j];
135                 a[j] = t;
136                 i++;
137                 j--;
138             }
139         } while(i<=j);
140         if(j<k) l=i;
141         if(k<i) m=j;
142     }
143     return a[k];
144 }
145
146 // ------------------------------- ringbuffer_t -------------------------------
147
148 typedef struct _ringbuffer_internal_t
149 {
150     unsigned char*buffer;
151     int readpos;
152     int writepos;
153     int buffersize;
154 } ringbuffer_internal_t;
155
156 void ringbuffer_init(ringbuffer_t*r)
157 {
158     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t)); 
159     memset(r, 0, sizeof(ringbuffer_t));
160     r->internal = i;
161     i->buffer = (unsigned char*)rfx_alloc(1024);
162     i->buffersize = 1024;
163 }
164 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
165 {
166     unsigned char* data = (unsigned char*)buf;
167     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
168     if(r->available < len)
169         len = r->available;
170     if(!len)
171         return 0;
172     if(i->readpos + len > i->buffersize) {
173         int read1 = i->buffersize-i->readpos;
174         memcpy(data, &i->buffer[i->readpos], read1);
175         memcpy(&data[read1], &i->buffer[0], len - read1);
176         i->readpos = len - read1;
177     } else {
178         memcpy(data, &i->buffer[i->readpos], len);
179         i->readpos += len;
180         i->readpos %= i->buffersize;
181     }
182     r->available -= len;
183     return len;
184 }
185 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
186 {
187     unsigned char* data = (unsigned char*)buf;
188     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
189     
190     if(i->buffersize - r->available < len)
191     {
192         unsigned char* buf2;
193         int newbuffersize = i->buffersize;
194         int oldavailable = r->available;
195         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
196
197         if(newbuffersize < r->available + len)
198             newbuffersize = r->available + len + 1024;
199
200         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
201         ringbuffer_read(r, buf2, r->available);
202         rfx_free(i->buffer);
203         i->buffer = buf2;
204         i->buffersize = newbuffersize;
205         i->readpos = 0;
206         i->writepos = oldavailable;
207         r->available = oldavailable;
208     }
209     if(i->writepos + len > i->buffersize) {
210         int read1 = i->buffersize-i->writepos;
211         memcpy(&i->buffer[i->writepos], data, read1);
212         memcpy(&i->buffer[0], &data[read1], len - read1);
213         i->writepos = len - read1;
214     } else {
215         memcpy(&i->buffer[i->writepos], data, len);
216         i->writepos += len;
217         i->writepos %= i->buffersize;
218     }
219     r->available += len;
220 }
221 void ringbuffer_clear(ringbuffer_t*r)
222 {
223     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
224     rfx_free(i->buffer);i->buffer = 0;
225     rfx_free(i);
226 }
227
228 // ------------------------------- heap_t -------------------------------
229
230 void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
231 {
232     memset(h, 0, sizeof(heap_t));
233     h->size = 0;
234     h->elem_size = elem_size;
235     h->compare = compare;
236     h->elements = 0;
237     h->max_size = 0;
238 }
239 heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
240 {
241     heap_t*h = malloc(sizeof(heap_t));
242     heap_init(h, elem_size, compare);
243     return h;
244 }
245 heap_t* heap_clone(heap_t*o)
246 {
247     heap_t*h = malloc(sizeof(heap_t));
248     memcpy(h, o, sizeof(heap_t));
249     h->elements = rfx_alloc(sizeof(void*)*h->size);
250     int t;
251     for(t=0;t<h->size;t++) {
252         h->elements[t] = rfx_alloc(h->elem_size);
253         memcpy(h->elements[t], o->elements[t], h->elem_size);
254     }
255     return h;
256 }
257 void heap_clear(heap_t*h)
258 {
259     int t;
260     for(t=0;t<h->size;t++) {
261         rfx_free(h->elements[t]);
262         h->elements[t]=0;
263     }
264     rfx_free(h->elements);
265 }
266 void heap_destroy(heap_t*h)
267 {
268     heap_clear(h);
269     free(h);
270 }
271
272 #define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
273 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
274
275 static void up(heap_t*h, int node)
276 {
277     void*node_p = h->elements[node];
278     int parent = node;
279     int tmp = node;
280     do {
281         node = parent;
282         if(!node) break;
283         parent = (node-1)/2;
284         h->elements[node] = h->elements[parent];
285     } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
286     h->elements[node] = node_p;
287 }
288 static void down(heap_t*h, int node)
289 {
290     void*node_p = h->elements[node];
291     int child = node;
292     do {
293         node = child;
294
295         /* determine new child's position */
296         child = node<<1|1;
297         if(child >= h->size) 
298             break;
299         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
300             child++;
301
302         h->elements[node] = h->elements[child];
303     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
304     
305     h->elements[node] = node_p;
306 }
307 void heap_put(heap_t*h, void*e) 
308 {
309     int pos = h->size++;
310     void*data = rfx_alloc(h->elem_size);
311     memcpy(data,e,h->elem_size);
312
313     if(pos>=h->max_size) {
314         h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
315         h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
316         assert(pos<h->max_size);
317     }
318
319     h->elements[pos] = data;
320     up(h, pos);
321 }
322 int heap_size(heap_t*h)
323 {
324     return h->size;
325 }
326 void* heap_peek(heap_t*h)
327 {
328     if(!h || !h->size) 
329         return 0;
330     return h->elements[0];
331 }
332 void* heap_chopmax(heap_t*h)
333 {
334     if(!h->size)
335         return 0;
336     void*p = h->elements[0];
337     h->elements[0] = h->elements[--h->size];
338     down(h,0);
339     return p;
340 }
341 void heap_dump(heap_t*h, FILE*fi)
342 {
343     int t;
344     for(t=0;t<h->size;t++) {
345         int s;
346         for(s=0;s<=t;s=(s+1)*2-1) {
347             if(s==t) fprintf(fi,"\n");
348         }
349         //fprintf(fi,"%d ", h->elements[t]->x); //?
350     }
351 }
352 void** heap_flatten(heap_t*h)
353 {
354     void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
355     void**p = nodes;
356    
357     while(h->size) {
358         /*printf("Heap Size: %d\n", h->size);
359         heap_print(stdout, h);
360         printf("\n");*/
361         *p++ = heap_chopmax(h);
362     }
363     *p++ = 0;
364     return nodes;
365 }
366
367 // ------------------------------- trie --------------------------------------
368
369 trie_t*trie_new()
370 {
371     return (trie_t*)rfx_calloc(sizeof(trie_t));
372 }
373 static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
374 {
375     if(!*t) {
376         (*t) = rfx_calloc(sizeof(trielayer_t));
377         (*t)->rest = (unsigned char*)strdup((char*)id);
378         (*t)->data = data;
379         return 0;
380     } 
381     if((*t)->rest && (*t)->rest[0]) {
382         // make room: shift whatever's currently in here one node down
383         _trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1, (*t)->data);
384         (*t)->rest = 0;
385     }
386     if(id[0]) {
387         return _trie_put(&(*t)->row[id[0]], id+1, data);
388     } else {
389         char overwrite = 0;
390         if((*t)->rest) 
391             overwrite = 1;
392         (*t)->rest = (unsigned char*)strdup("");
393         (*t)->data = data;
394         return overwrite;
395     }
396 }
397 static char _trie_remove(trielayer_t*t, unsigned const char*id)
398 {
399     while(t) {
400         if(t->rest && !strcmp((char*)t->rest, (char*)id)) {
401             free(t->rest);
402             t->rest = 0;
403             return 1;
404         }
405         if(!*id) 
406             return 0;
407         t = t->row[*id++];
408     }
409     return 0;
410 }
411
412 static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data);
413 static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data);
414
415 void trie_put(trie_t*t, unsigned const char*id, void*data)
416 {
417     if(!t->rollback) {
418         _trie_put(&t->start, id, data);
419     } else {
420         char contains = trie_contains(t, id);
421         void*olddata = contains?trie_lookup(t, id):0;
422         _trie_put(&t->start, id, data);
423         if(contains) {
424             trie_rollback_adds(t, id, olddata);
425         }
426         trie_rollback_removes(t, id, data);
427     }
428 }
429 char trie_remove(trie_t*t, unsigned const char*id)
430 {
431     if(!t->rollback) {
432         return _trie_remove(t->start, id);
433     } else {
434         void*olddata = trie_lookup(t, id);
435         char exists = _trie_remove(t->start, id);
436         if(exists) {
437             trie_rollback_adds(t, id, olddata);
438         }
439         return exists;
440     }
441 }
442 int trie_contains(trie_t*trie, unsigned const char*id)
443 {
444     trielayer_t*t = trie->start;
445     while(t) {
446         if(t->rest && !strcmp((char*)t->rest, (char*)id))
447             return 1;
448         if(!*id) 
449             return 0;
450         t = t->row[*id++];
451     }
452     return 0;
453 }
454 void* trie_lookup(trie_t*trie, unsigned const char*id)
455 {
456     trielayer_t*t = trie->start;
457     while(t) {
458         if(t->rest && !strcmp((char*)t->rest, (char*)id))
459             return t->data;
460         if(!*id) 
461             return 0;
462         t = t->row[*id++];
463     }
464     return 0;
465 }
466
467 typedef struct _triememory {
468     const unsigned char*key;
469     void*data;
470     char del; // 0/1
471     struct _triememory*next;
472 } triememory_t;
473
474 typedef struct _trierollback {
475     triememory_t*ops;
476     struct _trierollback*prev;
477 } trierollback_t;
478
479 static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
480 {
481     trierollback_t*rollback = (trierollback_t*)t->rollback;
482     triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
483     m->key = id;
484     m->data = data;
485     m->del = 0;
486     m->next = rollback->ops;
487     rollback->ops = m;
488 }
489 static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
490 {
491     trierollback_t*rollback = (trierollback_t*)t->rollback;
492     triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
493     m->key = id;
494     m->data = data;
495     m->del = 1;
496     m->next = rollback->ops;
497     rollback->ops = m;
498 }
499
500 void _trie_dump(trielayer_t*t, char*buffer, int pos)
501 {
502     int i;
503     for(i=0;i<256;i++) {
504         if(t->row[i]) {
505             buffer[pos]=i;
506             _trie_dump(t->row[i], buffer, pos+1);
507         }
508     }
509     if(t->rest) {
510         buffer[pos]=0;
511         printf("%s%s %08x\n", buffer, t->rest, (int)t->data);
512     }
513 }
514
515 void trie_dump(trie_t*t) 
516 {
517     char buffer[256];
518     _trie_dump(t->start, buffer, 0);
519 }
520
521
522 void trie_remember(trie_t*t)
523 {
524     trierollback_t*old = (trierollback_t*)t->rollback;
525     t->rollback = (trierollback_t*)rfx_calloc(sizeof(trierollback_t));
526     ((trierollback_t*)t->rollback)->prev = old;
527 }
528
529 void trie_rollback(trie_t*t)
530 {
531     trierollback_t*rollback = (trierollback_t*)t->rollback;
532     if(!rollback) {
533         fprintf(stderr, "Internal error: can't roll back this trie any further\n");
534         return;
535     }
536     t->rollback = ((trierollback_t*)t->rollback)->prev;
537
538     triememory_t*op = rollback->ops;
539     while(op) {
540         triememory_t*next = op->next;
541         if(op->del) {
542             if(!_trie_remove(t->start, op->key)) {
543                 fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", op->key);
544             }
545         } else {
546             if(_trie_put(&t->start, op->key, op->data)) {
547                 fprintf(stderr, "Internal error: overwrote key %s in trie during rollback\n", op->key);
548             }
549         }
550         free(op);
551         op = next;
552     }
553 }
554
555
556 // ------------------------------- crc32 --------------------------------------
557 static unsigned int crc32[256];
558 static char crc32_initialized=0;
559 static void crc32_init(void)
560 {
561     int t;
562     if(crc32_initialized) 
563         return;
564     crc32_initialized = 1;
565     for(t=0; t<256; t++) {
566         unsigned int c = t;
567         int s;
568         for (s = 0; s < 8; s++) {
569           c = (0xedb88320L*(c&1)) ^ (c >> 1);
570         }
571         crc32[t] = c;
572     }
573 }
574 // ------------------------------- string_t -----------------------------------
575
576 void string_set2(string_t*str, const char*text, int len)
577 {
578     str->len = len;
579     str->str = text;
580 }
581 void string_set(string_t*str, const char*text)
582 {
583     if(text) {
584         str->len = strlen(text);
585     } else {
586         str->len = 0;
587     }
588     str->str = text;
589 }
590 string_t string_new(const char*text, int len)
591 {
592     string_t s;
593     s.len = len;
594     s.str = text;
595     return s;
596 }
597 string_t string_new2(const char*text)
598 {
599     string_t s;
600     if(text) {
601         s.len = strlen(text);
602     } else {
603         s.len = 0;
604     }
605     s.str = text;
606     return s;
607 }
608 string_t* string_new3(const char*text, int len)
609 {
610     if(!text) {
611         string_t*s = malloc(sizeof(string_t));
612         s->len = 0;
613         s->str = 0;
614         return s;
615     } else {
616         string_t*s = malloc(sizeof(string_t)+len+1);
617         s->len = len;
618         s->str = (const char*)(s+1);
619         memcpy((char*)s->str, text, len);
620         ((char*)s->str)[len]=0;
621         return s;
622     }
623 }
624 string_t* string_new4(const char*text)
625 {
626     int l = strlen(text);
627     return string_new3(text, l);
628 }
629
630 void string_free(string_t*s)
631 {
632     if(!s) 
633         return;
634     s->len = 0;
635     if((string_t*)(s->str) == s+1) {
636         s->str = 0;
637         rfx_free(s);
638     } else {
639         rfx_free((char*)(s->str));
640         s->str = 0;
641         rfx_free(s);
642     }
643 }
644 char* string_cstr(string_t*str)
645 {
646     return strdup_n(str->str, str->len);
647 }
648 char* string_escape(string_t*str)
649 {
650     int t;
651     int len = 0;
652     for(t=0;t<str->len;t++) {
653         if(str->str[t]<0x20)
654             len+=3;
655         else
656             len++;
657     }
658     char*s = malloc(len+1);
659     char*p=s;
660     for(t=0;t<str->len;t++) {
661         if(str->str[t]<0x20) {
662             *p++ ='\\';
663             unsigned char c = str->str[t];
664             *p++ = "0123456789abcdef"[c>>4];
665             *p++ = "0123456789abcdef"[c&0x0f];
666         } else {
667             *p++ = str->str[t];
668         }
669     }
670     *p++ = 0;
671     assert(p == &s[len+1]);
672     return s;
673 }
674
675 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b) 
676 {
677     crc32_init();
678     return checksum>>8 ^ crc32[(b^checksum)&0xff];
679 }
680 unsigned int crc32_add_string(unsigned int checksum, const char*s)
681 {
682     crc32_init();
683     if(!s)
684         return checksum;
685     while(*s) {
686         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
687         s++;
688     }
689     return checksum;
690 }
691
692 unsigned int string_hash(const string_t*str)
693 {
694     int t;
695     unsigned int checksum = 0;
696     crc32_init();
697     for(t=0;t<str->len;t++) {
698         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
699     }
700     return checksum;
701 }
702 unsigned int string_hash2(const char*str)
703 {
704     unsigned int checksum = 0;
705     const char*p = str;
706     crc32_init();
707     while(*p) {
708         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
709         p++;
710     }
711     return checksum;
712 }
713 unsigned int string_hash3(const char*str, int len)
714 {
715     string_t s;
716     s.str = str;
717     s.len = len;
718     return string_hash(&s);
719 }
720 void string_dup2(string_t*str, const char*text, int len)
721 {
722     str->len = len;
723     str->str = strdup_n(text, len);
724 }
725 void string_dup(string_t*str, const char*text)
726 {
727     str->len = strlen(text);
728     str->str = strdup(text);
729 }
730 int string_equals(string_t*str, const char*text)
731 {
732     int l = strlen(text);
733     if(str->len == l && !memcmp(str->str, text, l))
734         return 1;
735     return 0;
736 }
737 int string_equals2(string_t*str, string_t*str2)
738 {
739     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
740         return 1;
741     return 0;
742 }
743
744 // ------------------------------- stringarray_t ------------------------------
745
746 typedef struct _stringlist {
747     int index;
748     struct _stringlist*next;
749 } stringlist_t;
750
751 typedef struct _stringarray_internal_t
752 {
753     mem_t pos;
754     stringlist_t**hash;
755     int num;
756     int hashsize;
757 } stringarray_internal_t;
758
759 void stringarray_init(stringarray_t*sa, int hashsize)
760 {
761     stringarray_internal_t*s;
762     int t;
763     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
764     s = (stringarray_internal_t*)sa->internal;
765     mem_init(&s->pos);
766     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
767     s->hashsize = hashsize;
768 }
769 void stringarray_put(stringarray_t*sa, string_t str)
770 {
771     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
772     int pos;
773     int hash = string_hash(&str) % s->hashsize;
774
775     char*ss = string_cstr(&str);
776     mem_put(&s->pos, &ss, sizeof(char*));
777
778     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
779     l->index = s->num;
780     l->next = s->hash[hash];
781     s->hash[hash] = l;
782
783     s->num++;
784 }
785 char* stringarray_at(stringarray_t*sa, int pos)
786 {
787     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
788     char*p;
789     if(pos<0 || pos>=s->num)
790         return 0;
791     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
792     if(p<0)
793         return 0;
794     return p;
795 }
796 string_t stringarray_at2(stringarray_t*sa, int pos)
797 {
798     string_t s;
799     s.str = stringarray_at(sa, pos);
800     s.len = s.str?strlen(s.str):0;
801     return s;
802 }
803 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
804 {
805     stringlist_t*ll = l;
806     stringlist_t*old = l;
807     while(l) {
808         if(index==l->index) {
809             old->next = l->next;
810             memset(l, 0, sizeof(stringlist_t));
811             rfx_free(l);
812             if(old==l)
813                 return 0;
814             else
815                 return ll;
816         }
817         old = l;
818         l = l->next;
819     }
820     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
821     return ll;
822 }
823
824 void stringarray_del(stringarray_t*sa, int pos)
825 {
826     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
827     string_t str = stringarray_at2(sa, pos);
828     int hash = string_hash(&str) % s->hashsize;
829     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
830     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
831 }
832 int stringarray_find(stringarray_t*sa, string_t* str)
833 {
834     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
835     int hash = string_hash(str) % s->hashsize;
836     int t;
837     stringlist_t*l = s->hash[hash];
838     //TODO: statistics
839     while(l) {
840         string_t s = stringarray_at2(sa, l->index);
841         if(string_equals2(str, &s)) {
842             return l->index;
843         }
844         l = l->next;
845     }
846     return -1;
847 }
848 void stringarray_clear(stringarray_t*sa)
849 {
850     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
851     mem_clear(&s->pos);
852     int t;
853     for(t=0;t<s->hashsize;t++) {
854         stringlist_t*l = s->hash[t];
855         while(l) {
856             stringlist_t*next = l->next;
857             memset(l, 0, sizeof(stringlist_t));
858             rfx_free(l);
859             l = next;
860         }
861     }
862     rfx_free(s->hash);s->hash=0;
863     rfx_free(s);
864 }
865 void stringarray_destroy(stringarray_t*sa)
866 {
867     stringarray_clear(sa);
868     rfx_free(sa);
869 }
870
871 // ------------------------------- type_t -------------------------------
872
873 char ptr_equals(const void*o1, const void*o2) 
874 {
875     return o1==o2;
876 }
877 unsigned int ptr_hash(const void*o) 
878 {
879     return string_hash3((const char*)&o, sizeof(o));
880 }
881 void* ptr_dup(const void*o) 
882 {
883     return (void*)o;
884 }
885 void ptr_free(void*o) 
886 {
887     return;
888 }
889
890 char int_equals(const void*o1, const void*o2) 
891 {
892     return o1==o2;
893 }
894 unsigned int int_hash(const void*o) 
895 {
896     return string_hash3((const char*)&o, sizeof(o));
897 }
898 void* int_dup(const void*o) 
899 {
900     return (void*)o;
901 }
902 void int_free(void*o) 
903 {
904     return;
905 }
906
907 char charptr_equals(const void*o1, const void*o2) 
908 {
909     if(!o1 || !o2)
910         return o1==o2;
911     return !strcmp(o1,o2);
912 }
913 unsigned int charptr_hash(const void*o) 
914 {
915     if(!o)
916         return 0;
917     return string_hash2(o);
918 }
919 void* charptr_dup(const void*o) 
920 {
921     if(!o)
922         return 0;
923     return strdup(o);
924 }
925 void charptr_free(void*o) 
926 {
927     if(o) {
928         rfx_free(o);
929     }
930 }
931
932 char stringstruct_equals(const void*o1, const void*o2) 
933 {
934     if(!o1 || !o2) 
935         return o1==o2;
936     string_t*s1 = (string_t*)o1;
937     string_t*s2 = (string_t*)o2;
938     int l = s1->len<s2->len?s1->len:s2->len;
939     int r = memcmp(s1->str, s2->str, l);
940     if(r)
941         return 0;
942     else
943         return s1->len==s2->len;
944 }
945 unsigned int stringstruct_hash(const void*o) 
946 {
947     if(!o) return 0;
948     return string_hash(o);
949 }
950 string_t*string_dup3(string_t*o)
951 {
952     if(!o) return 0;
953     if(!o->str) {
954         string_t*s = malloc(sizeof(string_t));
955         s->str=0;
956         s->len=0;
957         return s;
958     }
959     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
960     s->len = o->len;
961     s->str = (const char*)(s+1);
962     memcpy((char*)s->str, o->str, s->len);
963     ((char*)s->str)[s->len]=0;
964     return s;
965 }
966 void stringstruct_free(void*o) 
967 {
968     if(o)
969         string_free(o);
970 }
971
972 type_t int_type = {
973     equals: int_equals,
974     hash: int_hash,
975     dup: int_dup,
976     free: int_free,
977 };
978
979 type_t ptr_type = {
980     equals: ptr_equals,
981     hash: ptr_hash,
982     dup: ptr_dup,
983     free: ptr_free,
984 };
985
986 type_t charptr_type = {
987     equals: charptr_equals,
988     hash: charptr_hash,
989     dup: charptr_dup,
990     free: charptr_free,
991 };
992
993 type_t stringstruct_type = {
994     equals: stringstruct_equals,
995     hash: stringstruct_hash,
996     dup: (dup_func)string_dup3,
997     free: stringstruct_free,
998 };
999
1000 // ------------------------------- dictionary_t -------------------------------
1001
1002 #define INITIAL_SIZE 1
1003
1004 static int max(int x, int y) {
1005     return x>y?x:y;
1006 }
1007
1008 dict_t*dict_new()
1009 {
1010     dict_t*d = rfx_alloc(sizeof(dict_t));
1011     dict_init(d, INITIAL_SIZE);
1012     return d;
1013 }
1014 dict_t*dict_new2(type_t*t)
1015 {
1016     dict_t*d = rfx_alloc(sizeof(dict_t));
1017     dict_init(d, INITIAL_SIZE);
1018     d->key_type = t;
1019     return d;
1020 }
1021 void dict_init(dict_t*h, int size) 
1022 {
1023     memset(h, 0, sizeof(dict_t));
1024     h->hashsize = size;
1025     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1026     h->num = 0;
1027     h->key_type = &charptr_type;
1028 }
1029 void dict_init2(dict_t*h, type_t*t, int size) 
1030 {
1031     memset(h, 0, sizeof(dict_t));
1032     h->hashsize = size;
1033     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1034     h->num = 0;
1035     h->key_type = t;
1036 }
1037
1038 dict_t*dict_clone(dict_t*o)
1039 {
1040     dict_t*h = rfx_alloc(sizeof(dict_t));
1041     memcpy(h, o, sizeof(dict_t));
1042     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1043     int t;
1044     for(t=0;t<o->hashsize;t++) {
1045         dictentry_t*e = o->slots[t];
1046         while(e) {
1047             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1048             memcpy(n, e, sizeof(dictentry_t));
1049             n->key = h->key_type->dup(e->key);
1050             n->data = e->data;
1051             n->next = h->slots[t];
1052             h->slots[t] = n;
1053             e = e->next;
1054         }
1055     }
1056     return h;
1057 }
1058
1059 static void dict_expand(dict_t*h, int newlen)
1060 {
1061     assert(h->hashsize < newlen);
1062     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
1063     int t; 
1064     for(t=0;t<h->hashsize;t++) {
1065         dictentry_t*e = h->slots[t];
1066         while(e) {
1067             dictentry_t*next = e->next;
1068             unsigned int newhash = e->hash%newlen;
1069             e->next = newslots[newhash];
1070             newslots[newhash] = e;
1071             e = next;
1072         }
1073     }
1074     if(h->slots)
1075         rfx_free(h->slots);
1076     h->slots = newslots;
1077     h->hashsize = newlen;
1078 }
1079
1080 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
1081 {
1082     unsigned int hash = h->key_type->hash(key);
1083     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1084     
1085     if(!h->hashsize)
1086         dict_expand(h, 1);
1087
1088     unsigned int hash2 = hash % h->hashsize;
1089     
1090     e->key = h->key_type->dup(key);
1091     e->hash = hash; //for resizing
1092     e->next = h->slots[hash2];
1093     e->data = data;
1094     h->slots[hash2] = e;
1095     h->num++;
1096     return e;
1097 }
1098 void dict_put2(dict_t*h, const char*s, void*data) 
1099 {
1100     assert(h->key_type == &charptr_type);
1101     dict_put(h, s, data);
1102 }
1103 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
1104 {
1105     int t;
1106     for(t=0;t<h->hashsize;t++) {
1107         dictentry_t*e = h->slots[t];
1108         while(e) {
1109             if(h->key_type!=&charptr_type) {
1110                 fprintf(fi, "%s%08x=%08x\n", prefix, (int)e->key, (int)e->data);
1111             } else {
1112                 fprintf(fi, "%s%s=%08x\n", prefix, (char*)e->key, (int)e->data);
1113             }
1114             e = e->next;
1115         }
1116     }
1117 }
1118
1119 int dict_count(dict_t*h)
1120 {
1121     return h->num;
1122 }
1123
1124 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
1125 {
1126     if(!h->num) {
1127         return 0;
1128     }
1129     
1130     unsigned int ohash = h->key_type->hash(key);
1131     unsigned int hash = ohash % h->hashsize;
1132
1133     /* check first entry for match */
1134     dictentry_t*e = h->slots[hash];
1135     if(e && h->key_type->equals(e->key, key)) {
1136         return e;
1137     } else if(e) {
1138         e = e->next;
1139     }
1140
1141     /* if dict is 2/3 filled, double the size. Do
1142        this the first time we have to actually iterate
1143        through a slot to find our data */
1144     if(e && h->num*3 >= h->hashsize*2) {
1145         int newsize = h->hashsize;
1146         while(h->num*3 >= newsize*2) {
1147             newsize = newsize<15?15:(newsize+1)*2-1;
1148         }
1149         dict_expand(h, newsize);
1150         hash = ohash % h->hashsize;
1151         e = h->slots[hash];
1152         if(e && h->key_type->equals(e->key, key)) {
1153             // omit move to front
1154             return e;
1155         } else if(e) {
1156             e = e->next;
1157         }
1158     }
1159
1160     /* check subsequent entries for a match */
1161     dictentry_t*last = h->slots[hash];
1162     while(e) {
1163         if(h->key_type->equals(e->key, key)) {
1164             /* move to front- makes a difference of about 10% in most applications */
1165             last->next = e->next;
1166             e->next = h->slots[hash];
1167             h->slots[hash] = e;
1168             return e;
1169         }
1170         last=e;
1171         e = e->next;
1172     }
1173     return 0;
1174 }
1175 void* dict_lookup(dict_t*h, const void*key)
1176 {
1177     dictentry_t*e = dict_do_lookup(h, key);
1178     if(e)
1179         return e->data;
1180     return 0;
1181 }
1182 char dict_contains(dict_t*h, const void*key)
1183 {
1184     dictentry_t*e = dict_do_lookup(h, key);
1185     return !!e;
1186 }
1187
1188 char dict_del(dict_t*h, const void*key)
1189 {
1190     if(!h->num)
1191         return 0;
1192     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1193     dictentry_t*head = h->slots[hash];
1194     dictentry_t*e = head, *prev=0;
1195     while(e) {
1196         if(h->key_type->equals(e->key, key)) {
1197             dictentry_t*next = e->next;
1198             h->key_type->free(e->key);
1199             memset(e, 0, sizeof(dictentry_t));
1200             rfx_free(e);
1201             if(e == head) {
1202                 h->slots[hash] = next;
1203             } else {
1204                 assert(prev);
1205                 prev->next = next;
1206             }
1207             h->num--;
1208             return 1;
1209         }
1210         prev = e;
1211         e = e->next;
1212     }
1213     return 0;
1214 }
1215
1216 char dict_del2(dict_t*h, const void*key, void*data)
1217 {
1218     if(!h->num)
1219         return 0;
1220     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1221     dictentry_t*head = h->slots[hash];
1222     dictentry_t*e = head, *prev=0;
1223     while(e) {
1224         if(h->key_type->equals(e->key, key) && e->data == data) {
1225             dictentry_t*next = e->next;
1226             h->key_type->free(e->key);
1227             memset(e, 0, sizeof(dictentry_t));
1228             rfx_free(e);
1229             if(e == head) {
1230                 h->slots[hash] = next;
1231             } else {
1232                 assert(prev);
1233                 prev->next = next;
1234             }
1235             h->num--;
1236             return 1;
1237         }
1238         prev = e;
1239         e = e->next;
1240     }
1241     return 0;
1242 }
1243
1244 dictentry_t* dict_get_slot(dict_t*h, const void*key)
1245 {
1246     if(!h->num)
1247         return 0;
1248     unsigned int ohash = h->key_type->hash(key);
1249     unsigned int hash = ohash % h->hashsize;
1250     return h->slots[hash];
1251 }
1252
1253 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
1254 {
1255     int t;
1256     for(t=0;t<h->hashsize;t++) {
1257         dictentry_t*e = h->slots[t];
1258         while(e) {
1259             dictentry_t*next = e->next;
1260             if(runFunction) {
1261                 runFunction(data, e->key, e->data);
1262             }
1263             e = e->next;
1264         }
1265     }
1266 }
1267 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
1268 {
1269     int t;
1270     for(t=0;t<h->hashsize;t++) {
1271         dictentry_t*e = h->slots[t];
1272         while(e) {
1273             dictentry_t*next = e->next;
1274             if(runFunction) {
1275                 runFunction(e->data);
1276             }
1277             e = e->next;
1278         }
1279     }
1280 }
1281
1282 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1283 {
1284     int t;
1285     for(t=0;t<h->hashsize;t++) {
1286         dictentry_t*e = h->slots[t];
1287         while(e) {
1288             dictentry_t*next = e->next;
1289             if(free_keys) {
1290                 h->key_type->free(e->key);
1291             }
1292             if(free_data_function) {
1293                 free_data_function(e->data);
1294             }
1295             memset(e, 0, sizeof(dictentry_t));
1296             rfx_free(e);
1297             e = next;
1298         }
1299         h->slots[t]=0;
1300     }
1301     rfx_free(h->slots);
1302     memset(h, 0, sizeof(dict_t));
1303 }
1304
1305 void dict_clear_shallow(dict_t*h) 
1306 {
1307     dict_free_all(h, 0, 0);
1308 }
1309
1310 void dict_clear(dict_t*h) 
1311 {
1312     dict_free_all(h, 1, 0);
1313 }
1314
1315 void dict_destroy_shallow(dict_t*dict)
1316 {
1317     dict_clear_shallow(dict);
1318     rfx_free(dict);
1319 }
1320
1321 void dict_destroy(dict_t*dict)
1322 {
1323     if(!dict)
1324         return;
1325     dict_clear(dict);
1326     rfx_free(dict);
1327 }
1328
1329 // ------------------------------- mtf_t --------------------------------------
1330 mtf_t* mtf_new(type_t*type)
1331 {
1332     NEW(mtf_t, mtf);
1333     mtf->type = type;
1334     return mtf;
1335 }
1336 void mtf_increase(mtf_t*m, const void*key)
1337 {
1338     mtf_item_t*item = m->first;
1339     mtf_item_t*last = 0;
1340     while(item) {
1341         if(m->type->equals(item->key, key)) {
1342             item->num++;
1343             if(item->num>m->first->num) {
1344                 if(last) last->next = item->next;
1345                 else m->first = item->next;
1346                 item->next = m->first;
1347                 m->first = item;
1348             }
1349             return;
1350         }
1351         last = item;
1352         item = item->next;
1353     }
1354     NEW(mtf_item_t,n);
1355     if(last) last->next = n;
1356     else m->first = n;
1357     n->key = key;
1358     n->num = 1;
1359 }
1360 void mtf_destroy(mtf_t*m)
1361 {
1362     if(!m) return;
1363     mtf_item_t*item = m->first;
1364     m->first = 0;
1365     while(item) {
1366         mtf_item_t*next = item->next;
1367         item->next = 0;
1368         free(item);
1369         item = next;
1370     }
1371     free(m);
1372 }
1373
1374 // ------------------------------- map_t --------------------------------------
1375
1376 typedef struct _map_internal_t
1377 {
1378     dict_t d;
1379 } map_internal_t;
1380
1381 void map_init(map_t*map)
1382 {
1383     map_internal_t*m;
1384     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1385     m = (map_internal_t*)map->internal;
1386     dict_init(&m->d, INITIAL_SIZE);
1387 }
1388 void map_put(map_t*map, string_t t1, string_t t2)
1389 {
1390     map_internal_t*m = (map_internal_t*)map->internal;
1391     string_t s;
1392     char* s1 = string_cstr(&t1);
1393     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1394     rfx_free(s1);
1395 }
1396 const char* map_lookup(map_t*map, const char*name)
1397 {
1398     map_internal_t*m = (map_internal_t*)map->internal;
1399     const char*value = dict_lookup(&m->d, name);
1400     return value;
1401 }
1402 static void freestring(void*data)
1403 {
1404     rfx_free(data);
1405 }
1406 static void dumpmapentry(void*data, const void*key, void*value)
1407 {
1408     FILE*fi = (FILE*)data;
1409     fprintf(fi, "%s=%s\n", (char*)key, (char*)value);
1410 }
1411 void map_dump(map_t*map, FILE*fi, const char*prefix)
1412 {
1413     int t;
1414     map_internal_t*m = (map_internal_t*)map->internal;
1415     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1416 }
1417 void map_clear(map_t*map)
1418 {
1419     map_internal_t*m = (map_internal_t*)map->internal;
1420     dict_free_all(&m->d, 1, freestring);
1421     rfx_free(m);
1422 }
1423 void map_destroy(map_t*map)
1424 {
1425     map_clear(map);
1426     rfx_free(map);
1427 }
1428
1429 // ------------------------------- array_t --------------------------------------
1430
1431 array_t* array_new() {
1432     array_t*d = malloc(sizeof(array_t));
1433     memset(d, 0, sizeof(array_t));
1434     d->entry2pos = dict_new();
1435     return d;
1436 }
1437 array_t* array_new2(type_t*type) {
1438     array_t*d = malloc(sizeof(array_t));
1439     memset(d, 0, sizeof(array_t));
1440     d->entry2pos = dict_new2(type);
1441     return d;
1442 }
1443 void*array_getkey(array_t*array, int nr) {
1444     if(nr > array->num || nr<0) {
1445         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1446         return 0;
1447     }
1448     return array->d[nr].name;
1449 }
1450 void*array_getvalue(array_t*array, int nr) {
1451     if(nr > array->num || nr<0) {
1452         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1453         return 0;
1454     }
1455     return array->d[nr].data;
1456 }
1457 int array_append(array_t*array, const void*name, void*data) {
1458     while(array->size <= array->num) {
1459         array->size += 64;
1460         if(!array->d) {
1461             array->d = malloc(sizeof(array_entry_t)*array->size);
1462         } else {
1463             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1464         }
1465     }
1466
1467     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1468
1469     if(name) {
1470         array->d[array->num].name = e->key;
1471     } else {
1472         array->d[array->num].name = 0;
1473     }
1474     array->d[array->num].data = (void*)data;
1475     return array->num++;
1476 }
1477 int array_find(array_t*array, const void*name)
1478 {
1479     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1480     return pos-1;
1481 }
1482 int array_find2(array_t*array, const void*name, void*data)
1483 {
1484     dict_t*h= array->entry2pos;
1485     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1486
1487     while(e) {
1488         int index = ((int)(ptroff_t)e->data) - 1;
1489         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1490             return index;
1491         }
1492         e = e->next;
1493     }
1494     return -1;
1495 }
1496 int array_update(array_t*array, const void*name, void*data) {
1497     int pos = array_find(array, name);
1498     if(pos>=0) {
1499         array->d[pos].data = data;
1500         return pos;
1501     }
1502     return array_append(array, name, data);
1503 }
1504 int array_append_if_new(array_t*array, const void*name, void*data) {
1505     int pos = array_find(array, name);
1506     if(pos>=0)
1507         return pos;
1508     return array_append(array, name, data);
1509 }
1510 void array_free(array_t*array) {
1511     dict_destroy(array->entry2pos);
1512     if(array->d) {
1513         free(array->d);array->d = 0;
1514     }
1515     free(array);
1516 }
1517
1518 // ------------------------------- list_t --------------------------------------
1519
1520 struct _commonlist;
1521 typedef struct _listinfo {
1522     int size;
1523     struct _commonlist*last;
1524 } listinfo_t;
1525
1526 typedef struct _commonlist {
1527     void*entry;
1528     struct _commonlist*next;
1529     listinfo_t info[0];
1530 } commonlist_t;
1531
1532 int list_length_(void*_list)
1533 {
1534     commonlist_t*l = (commonlist_t*)_list;
1535     if(!l)
1536         return 0;
1537     return l->info[0].size;
1538 }
1539 void list_concat_(void*_l1, void*_l2)
1540 {
1541     commonlist_t**l1 = (commonlist_t**)_l1;
1542     commonlist_t**l2 = (commonlist_t**)_l2;
1543
1544     if(!*l1) {
1545         *l1 = *l2;
1546     } else if(*l2) {
1547         (*l1)->info[0].last->next = *l2;
1548         (*l1)->info[0].last = (*l2)->info[0].last;
1549         (*l1)->info[0].size += (*l2)->info[0].size;
1550     }
1551     *l2 = 0;
1552 }
1553 void list_append_(void*_list, void*entry)
1554 {
1555     commonlist_t**list = (commonlist_t**)_list;
1556     commonlist_t* n = 0;
1557     if(!*list) {
1558         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1559         *list = n;
1560         (*list)->info[0].size = 0;
1561     } else {
1562         n = malloc(sizeof(commonlist_t));
1563         (*list)->info[0].last->next = n;
1564     }
1565     n->next = 0;
1566     n->entry = entry;
1567     (*list)->info[0].last = n;
1568     (*list)->info[0].size++;
1569 }
1570 /* notice: prepending uses slighly more space than appending */
1571 void list_prepend_(void*_list, void*entry)
1572 {
1573     commonlist_t**list = (commonlist_t**)_list;
1574     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1575     int size = 0;
1576     commonlist_t* last = 0;
1577     if(*list) {
1578         last = (*list)->info[0].last;
1579         size = (*list)->info[0].size;
1580     }
1581     n->next = *list;
1582     n->entry = entry;
1583     *list = n;
1584     (*list)->info[0].last = last;
1585     (*list)->info[0].size = size+1;
1586 }
1587 void list_free_(void*_list) 
1588 {
1589     commonlist_t**list = (commonlist_t**)_list;
1590     commonlist_t*l = *list;
1591     while(l) {
1592         commonlist_t*next = l->next;
1593         free(l);
1594         l = next;
1595     }
1596     *list = 0;
1597 }
1598 void list_deep_free_(void*_list)
1599 {
1600     commonlist_t**list = (commonlist_t**)_list;
1601     commonlist_t*l = *list;
1602     while(l) {
1603         commonlist_t*next = l->next;
1604         if(l->entry) {
1605             free(l->entry);l->entry=0;
1606         }
1607         free(l);
1608         l = next;
1609     }
1610     *list = 0;
1611 }
1612 void*list_clone_(void*_list) 
1613 {
1614     commonlist_t*l = *(commonlist_t**)_list;
1615
1616     void*dest = 0;
1617     while(l) {
1618         commonlist_t*next = l->next;
1619         list_append_(&dest, l->entry);
1620         l = next;
1621     }
1622     return dest;
1623
1624 }
1625