got rid of some old code
[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 unsigned int crc32_add_bytes(unsigned int checksum, const void*_s, int len)
692 {
693     unsigned char*s = (unsigned char*)_s;
694     crc32_init();
695     if(!s || !len)
696         return checksum;
697     do {
698         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
699         s++;
700     } while(--len);
701     return checksum;
702 }
703
704 unsigned int string_hash(const string_t*str)
705 {
706     int t;
707     unsigned int checksum = 0;
708     crc32_init();
709     for(t=0;t<str->len;t++) {
710         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
711     }
712     return checksum;
713 }
714 unsigned int string_hash2(const char*str)
715 {
716     unsigned int checksum = 0;
717     const char*p = str;
718     crc32_init();
719     while(*p) {
720         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
721         p++;
722     }
723     return checksum;
724 }
725 unsigned int string_hash3(const char*str, int len)
726 {
727     string_t s;
728     s.str = str;
729     s.len = len;
730     return string_hash(&s);
731 }
732 void string_dup2(string_t*str, const char*text, int len)
733 {
734     str->len = len;
735     str->str = strdup_n(text, len);
736 }
737 void string_dup(string_t*str, const char*text)
738 {
739     str->len = strlen(text);
740     str->str = strdup(text);
741 }
742 int string_equals(string_t*str, const char*text)
743 {
744     int l = strlen(text);
745     if(str->len == l && !memcmp(str->str, text, l))
746         return 1;
747     return 0;
748 }
749 int string_equals2(string_t*str, string_t*str2)
750 {
751     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
752         return 1;
753     return 0;
754 }
755
756 // ------------------------------- stringarray_t ------------------------------
757
758 typedef struct _stringlist {
759     int index;
760     struct _stringlist*next;
761 } stringlist_t;
762
763 typedef struct _stringarray_internal_t
764 {
765     mem_t pos;
766     stringlist_t**hash;
767     int num;
768     int hashsize;
769 } stringarray_internal_t;
770
771 void stringarray_init(stringarray_t*sa, int hashsize)
772 {
773     stringarray_internal_t*s;
774     int t;
775     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t)); 
776     s = (stringarray_internal_t*)sa->internal;
777     mem_init(&s->pos);
778     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
779     s->hashsize = hashsize;
780 }
781 void stringarray_put(stringarray_t*sa, string_t str)
782 {
783     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
784     int pos;
785     int hash = string_hash(&str) % s->hashsize;
786
787     char*ss = string_cstr(&str);
788     mem_put(&s->pos, &ss, sizeof(char*));
789
790     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
791     l->index = s->num;
792     l->next = s->hash[hash];
793     s->hash[hash] = l;
794
795     s->num++;
796 }
797 char* stringarray_at(stringarray_t*sa, int pos)
798 {
799     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
800     char*p;
801     if(pos<0 || pos>=s->num)
802         return 0;
803     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
804     if(p<0)
805         return 0;
806     return p;
807 }
808 string_t stringarray_at2(stringarray_t*sa, int pos)
809 {
810     string_t s;
811     s.str = stringarray_at(sa, pos);
812     s.len = s.str?strlen(s.str):0;
813     return s;
814 }
815 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
816 {
817     stringlist_t*ll = l;
818     stringlist_t*old = l;
819     while(l) {
820         if(index==l->index) {
821             old->next = l->next;
822             memset(l, 0, sizeof(stringlist_t));
823             rfx_free(l);
824             if(old==l)
825                 return 0;
826             else
827                 return ll;
828         }
829         old = l;
830         l = l->next;
831     }
832     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
833     return ll;
834 }
835
836 void stringarray_del(stringarray_t*sa, int pos)
837 {
838     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
839     string_t str = stringarray_at2(sa, pos);
840     int hash = string_hash(&str) % s->hashsize;
841     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
842     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
843 }
844 int stringarray_find(stringarray_t*sa, string_t* str)
845 {
846     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
847     int hash = string_hash(str) % s->hashsize;
848     int t;
849     stringlist_t*l = s->hash[hash];
850     //TODO: statistics
851     while(l) {
852         string_t s = stringarray_at2(sa, l->index);
853         if(string_equals2(str, &s)) {
854             return l->index;
855         }
856         l = l->next;
857     }
858     return -1;
859 }
860 void stringarray_clear(stringarray_t*sa)
861 {
862     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
863     mem_clear(&s->pos);
864     int t;
865     for(t=0;t<s->hashsize;t++) {
866         stringlist_t*l = s->hash[t];
867         while(l) {
868             stringlist_t*next = l->next;
869             memset(l, 0, sizeof(stringlist_t));
870             rfx_free(l);
871             l = next;
872         }
873     }
874     rfx_free(s->hash);s->hash=0;
875     rfx_free(s);
876 }
877 void stringarray_destroy(stringarray_t*sa)
878 {
879     stringarray_clear(sa);
880     rfx_free(sa);
881 }
882
883 // ------------------------------- type_t -------------------------------
884
885 char ptr_equals(const void*o1, const void*o2) 
886 {
887     return o1==o2;
888 }
889 unsigned int ptr_hash(const void*o) 
890 {
891     return string_hash3((const char*)&o, sizeof(o));
892 }
893 void* ptr_dup(const void*o) 
894 {
895     return (void*)o;
896 }
897 void ptr_free(void*o) 
898 {
899     return;
900 }
901
902 char int_equals(const void*o1, const void*o2) 
903 {
904     return o1==o2;
905 }
906 unsigned int int_hash(const void*o) 
907 {
908     return string_hash3((const char*)&o, sizeof(o));
909 }
910 void* int_dup(const void*o) 
911 {
912     return (void*)o;
913 }
914 void int_free(void*o) 
915 {
916     return;
917 }
918
919 char charptr_equals(const void*o1, const void*o2) 
920 {
921     if(!o1 || !o2)
922         return o1==o2;
923     return !strcmp(o1,o2);
924 }
925 unsigned int charptr_hash(const void*o) 
926 {
927     if(!o)
928         return 0;
929     return string_hash2(o);
930 }
931 void* charptr_dup(const void*o) 
932 {
933     if(!o)
934         return 0;
935     return strdup(o);
936 }
937 void charptr_free(void*o) 
938 {
939     if(o) {
940         rfx_free(o);
941     }
942 }
943
944 char stringstruct_equals(const void*o1, const void*o2) 
945 {
946     if(!o1 || !o2) 
947         return o1==o2;
948     string_t*s1 = (string_t*)o1;
949     string_t*s2 = (string_t*)o2;
950     int l = s1->len<s2->len?s1->len:s2->len;
951     int r = memcmp(s1->str, s2->str, l);
952     if(r)
953         return 0;
954     else
955         return s1->len==s2->len;
956 }
957 unsigned int stringstruct_hash(const void*o) 
958 {
959     if(!o) return 0;
960     return string_hash(o);
961 }
962 string_t*string_dup3(string_t*o)
963 {
964     if(!o) return 0;
965     if(!o->str) {
966         string_t*s = malloc(sizeof(string_t));
967         s->str=0;
968         s->len=0;
969         return s;
970     }
971     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
972     s->len = o->len;
973     s->str = (const char*)(s+1);
974     memcpy((char*)s->str, o->str, s->len);
975     ((char*)s->str)[s->len]=0;
976     return s;
977 }
978 void stringstruct_free(void*o) 
979 {
980     if(o)
981         string_free(o);
982 }
983
984 type_t int_type = {
985     equals: int_equals,
986     hash: int_hash,
987     dup: int_dup,
988     free: int_free,
989 };
990
991 type_t ptr_type = {
992     equals: ptr_equals,
993     hash: ptr_hash,
994     dup: ptr_dup,
995     free: ptr_free,
996 };
997
998 type_t charptr_type = {
999     equals: charptr_equals,
1000     hash: charptr_hash,
1001     dup: charptr_dup,
1002     free: charptr_free,
1003 };
1004
1005 type_t stringstruct_type = {
1006     equals: stringstruct_equals,
1007     hash: stringstruct_hash,
1008     dup: (dup_func)string_dup3,
1009     free: stringstruct_free,
1010 };
1011
1012 // ------------------------------- dictionary_t -------------------------------
1013
1014 #define INITIAL_SIZE 1
1015
1016 static int max(int x, int y) {
1017     return x>y?x:y;
1018 }
1019
1020 dict_t*dict_new()
1021 {
1022     dict_t*d = rfx_alloc(sizeof(dict_t));
1023     dict_init(d, INITIAL_SIZE);
1024     return d;
1025 }
1026 dict_t*dict_new2(type_t*t)
1027 {
1028     dict_t*d = rfx_alloc(sizeof(dict_t));
1029     dict_init(d, INITIAL_SIZE);
1030     d->key_type = t;
1031     return d;
1032 }
1033 void dict_init(dict_t*h, int size) 
1034 {
1035     memset(h, 0, sizeof(dict_t));
1036     h->hashsize = size;
1037     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1038     h->num = 0;
1039     h->key_type = &charptr_type;
1040 }
1041 void dict_init2(dict_t*h, type_t*t, int size) 
1042 {
1043     memset(h, 0, sizeof(dict_t));
1044     h->hashsize = size;
1045     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1046     h->num = 0;
1047     h->key_type = t;
1048 }
1049
1050 dict_t*dict_clone(dict_t*o)
1051 {
1052     dict_t*h = rfx_alloc(sizeof(dict_t));
1053     memcpy(h, o, sizeof(dict_t));
1054     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1055     int t;
1056     for(t=0;t<o->hashsize;t++) {
1057         dictentry_t*e = o->slots[t];
1058         while(e) {
1059             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1060             memcpy(n, e, sizeof(dictentry_t));
1061             n->key = h->key_type->dup(e->key);
1062             n->data = e->data;
1063             n->next = h->slots[t];
1064             h->slots[t] = n;
1065             e = e->next;
1066         }
1067     }
1068     return h;
1069 }
1070
1071 static void dict_expand(dict_t*h, int newlen)
1072 {
1073     assert(h->hashsize < newlen);
1074     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
1075     int t; 
1076     for(t=0;t<h->hashsize;t++) {
1077         dictentry_t*e = h->slots[t];
1078         while(e) {
1079             dictentry_t*next = e->next;
1080             unsigned int newhash = e->hash%newlen;
1081             e->next = newslots[newhash];
1082             newslots[newhash] = e;
1083             e = next;
1084         }
1085     }
1086     if(h->slots)
1087         rfx_free(h->slots);
1088     h->slots = newslots;
1089     h->hashsize = newlen;
1090 }
1091
1092 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
1093 {
1094     unsigned int hash = h->key_type->hash(key);
1095     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1096     
1097     if(!h->hashsize)
1098         dict_expand(h, 1);
1099
1100     unsigned int hash2 = hash % h->hashsize;
1101     
1102     e->key = h->key_type->dup(key);
1103     e->hash = hash; //for resizing
1104     e->next = h->slots[hash2];
1105     e->data = data;
1106     h->slots[hash2] = e;
1107     h->num++;
1108     return e;
1109 }
1110 void dict_put2(dict_t*h, const char*s, void*data) 
1111 {
1112     assert(h->key_type == &charptr_type);
1113     dict_put(h, s, data);
1114 }
1115 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
1116 {
1117     int t;
1118     for(t=0;t<h->hashsize;t++) {
1119         dictentry_t*e = h->slots[t];
1120         while(e) {
1121             if(h->key_type!=&charptr_type) {
1122                 fprintf(fi, "%s%08x=%08x\n", prefix, (int)e->key, (int)e->data);
1123             } else {
1124                 fprintf(fi, "%s%s=%08x\n", prefix, (char*)e->key, (int)e->data);
1125             }
1126             e = e->next;
1127         }
1128     }
1129 }
1130
1131 int dict_count(dict_t*h)
1132 {
1133     return h->num;
1134 }
1135
1136 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
1137 {
1138     if(!h->num) {
1139         return 0;
1140     }
1141     
1142     unsigned int ohash = h->key_type->hash(key);
1143     unsigned int hash = ohash % h->hashsize;
1144
1145     /* check first entry for match */
1146     dictentry_t*e = h->slots[hash];
1147     if(e && h->key_type->equals(e->key, key)) {
1148         return e;
1149     } else if(e) {
1150         e = e->next;
1151     }
1152
1153     /* if dict is 2/3 filled, double the size. Do
1154        this the first time we have to actually iterate
1155        through a slot to find our data */
1156     if(e && h->num*3 >= h->hashsize*2) {
1157         int newsize = h->hashsize;
1158         while(h->num*3 >= newsize*2) {
1159             newsize = newsize<15?15:(newsize+1)*2-1;
1160         }
1161         dict_expand(h, newsize);
1162         hash = ohash % h->hashsize;
1163         e = h->slots[hash];
1164         if(e && h->key_type->equals(e->key, key)) {
1165             // omit move to front
1166             return e;
1167         } else if(e) {
1168             e = e->next;
1169         }
1170     }
1171
1172     /* check subsequent entries for a match */
1173     dictentry_t*last = h->slots[hash];
1174     while(e) {
1175         if(h->key_type->equals(e->key, key)) {
1176             /* move to front- makes a difference of about 10% in most applications */
1177             last->next = e->next;
1178             e->next = h->slots[hash];
1179             h->slots[hash] = e;
1180             return e;
1181         }
1182         last=e;
1183         e = e->next;
1184     }
1185     return 0;
1186 }
1187 void* dict_lookup(dict_t*h, const void*key)
1188 {
1189     dictentry_t*e = dict_do_lookup(h, key);
1190     if(e)
1191         return e->data;
1192     return 0;
1193 }
1194 char dict_contains(dict_t*h, const void*key)
1195 {
1196     dictentry_t*e = dict_do_lookup(h, key);
1197     return !!e;
1198 }
1199
1200 char dict_del(dict_t*h, const void*key)
1201 {
1202     if(!h->num)
1203         return 0;
1204     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1205     dictentry_t*head = h->slots[hash];
1206     dictentry_t*e = head, *prev=0;
1207     while(e) {
1208         if(h->key_type->equals(e->key, key)) {
1209             dictentry_t*next = e->next;
1210             h->key_type->free(e->key);
1211             memset(e, 0, sizeof(dictentry_t));
1212             rfx_free(e);
1213             if(e == head) {
1214                 h->slots[hash] = next;
1215             } else {
1216                 assert(prev);
1217                 prev->next = next;
1218             }
1219             h->num--;
1220             return 1;
1221         }
1222         prev = e;
1223         e = e->next;
1224     }
1225     return 0;
1226 }
1227
1228 char dict_del2(dict_t*h, const void*key, void*data)
1229 {
1230     if(!h->num)
1231         return 0;
1232     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1233     dictentry_t*head = h->slots[hash];
1234     dictentry_t*e = head, *prev=0;
1235     while(e) {
1236         if(h->key_type->equals(e->key, key) && e->data == data) {
1237             dictentry_t*next = e->next;
1238             h->key_type->free(e->key);
1239             memset(e, 0, sizeof(dictentry_t));
1240             rfx_free(e);
1241             if(e == head) {
1242                 h->slots[hash] = next;
1243             } else {
1244                 assert(prev);
1245                 prev->next = next;
1246             }
1247             h->num--;
1248             return 1;
1249         }
1250         prev = e;
1251         e = e->next;
1252     }
1253     return 0;
1254 }
1255
1256 dictentry_t* dict_get_slot(dict_t*h, const void*key)
1257 {
1258     if(!h->num)
1259         return 0;
1260     unsigned int ohash = h->key_type->hash(key);
1261     unsigned int hash = ohash % h->hashsize;
1262     return h->slots[hash];
1263 }
1264
1265 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
1266 {
1267     int t;
1268     for(t=0;t<h->hashsize;t++) {
1269         dictentry_t*e = h->slots[t];
1270         while(e) {
1271             dictentry_t*next = e->next;
1272             if(runFunction) {
1273                 runFunction(data, e->key, e->data);
1274             }
1275             e = e->next;
1276         }
1277     }
1278 }
1279 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
1280 {
1281     int t;
1282     for(t=0;t<h->hashsize;t++) {
1283         dictentry_t*e = h->slots[t];
1284         while(e) {
1285             dictentry_t*next = e->next;
1286             if(runFunction) {
1287                 runFunction(e->data);
1288             }
1289             e = e->next;
1290         }
1291     }
1292 }
1293
1294 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1295 {
1296     int t;
1297     for(t=0;t<h->hashsize;t++) {
1298         dictentry_t*e = h->slots[t];
1299         while(e) {
1300             dictentry_t*next = e->next;
1301             if(free_keys) {
1302                 h->key_type->free(e->key);
1303             }
1304             if(free_data_function) {
1305                 free_data_function(e->data);
1306             }
1307             memset(e, 0, sizeof(dictentry_t));
1308             rfx_free(e);
1309             e = next;
1310         }
1311         h->slots[t]=0;
1312     }
1313     rfx_free(h->slots);
1314     memset(h, 0, sizeof(dict_t));
1315 }
1316
1317 void dict_clear_shallow(dict_t*h) 
1318 {
1319     dict_free_all(h, 0, 0);
1320 }
1321
1322 void dict_clear(dict_t*h) 
1323 {
1324     dict_free_all(h, 1, 0);
1325 }
1326
1327 void dict_destroy_shallow(dict_t*dict)
1328 {
1329     dict_clear_shallow(dict);
1330     rfx_free(dict);
1331 }
1332
1333 void dict_destroy(dict_t*dict)
1334 {
1335     if(!dict)
1336         return;
1337     dict_clear(dict);
1338     rfx_free(dict);
1339 }
1340
1341 // ------------------------------- mtf_t --------------------------------------
1342 mtf_t* mtf_new(type_t*type)
1343 {
1344     NEW(mtf_t, mtf);
1345     mtf->type = type;
1346     return mtf;
1347 }
1348 void mtf_increase(mtf_t*m, const void*key)
1349 {
1350     mtf_item_t*item = m->first;
1351     mtf_item_t*last = 0;
1352     while(item) {
1353         if(m->type->equals(item->key, key)) {
1354             item->num++;
1355             if(item->num>m->first->num) {
1356                 if(last) last->next = item->next;
1357                 else m->first = item->next;
1358                 item->next = m->first;
1359                 m->first = item;
1360             }
1361             return;
1362         }
1363         last = item;
1364         item = item->next;
1365     }
1366     NEW(mtf_item_t,n);
1367     if(last) last->next = n;
1368     else m->first = n;
1369     n->key = key;
1370     n->num = 1;
1371 }
1372 void mtf_destroy(mtf_t*m)
1373 {
1374     if(!m) return;
1375     mtf_item_t*item = m->first;
1376     m->first = 0;
1377     while(item) {
1378         mtf_item_t*next = item->next;
1379         item->next = 0;
1380         free(item);
1381         item = next;
1382     }
1383     free(m);
1384 }
1385
1386 // ------------------------------- map_t --------------------------------------
1387
1388 typedef struct _map_internal_t
1389 {
1390     dict_t d;
1391 } map_internal_t;
1392
1393 void map_init(map_t*map)
1394 {
1395     map_internal_t*m;
1396     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1397     m = (map_internal_t*)map->internal;
1398     dict_init(&m->d, INITIAL_SIZE);
1399 }
1400 void map_put(map_t*map, string_t t1, string_t t2)
1401 {
1402     map_internal_t*m = (map_internal_t*)map->internal;
1403     string_t s;
1404     char* s1 = string_cstr(&t1);
1405     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1406     rfx_free(s1);
1407 }
1408 const char* map_lookup(map_t*map, const char*name)
1409 {
1410     map_internal_t*m = (map_internal_t*)map->internal;
1411     const char*value = dict_lookup(&m->d, name);
1412     return value;
1413 }
1414 static void freestring(void*data)
1415 {
1416     rfx_free(data);
1417 }
1418 static void dumpmapentry(void*data, const void*key, void*value)
1419 {
1420     FILE*fi = (FILE*)data;
1421     fprintf(fi, "%s=%s\n", (char*)key, (char*)value);
1422 }
1423 void map_dump(map_t*map, FILE*fi, const char*prefix)
1424 {
1425     int t;
1426     map_internal_t*m = (map_internal_t*)map->internal;
1427     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1428 }
1429 void map_clear(map_t*map)
1430 {
1431     map_internal_t*m = (map_internal_t*)map->internal;
1432     dict_free_all(&m->d, 1, freestring);
1433     rfx_free(m);
1434 }
1435 void map_destroy(map_t*map)
1436 {
1437     map_clear(map);
1438     rfx_free(map);
1439 }
1440
1441 // ------------------------------- array_t --------------------------------------
1442
1443 array_t* array_new() {
1444     array_t*d = malloc(sizeof(array_t));
1445     memset(d, 0, sizeof(array_t));
1446     d->entry2pos = dict_new();
1447     return d;
1448 }
1449 array_t* array_new2(type_t*type) {
1450     array_t*d = malloc(sizeof(array_t));
1451     memset(d, 0, sizeof(array_t));
1452     d->entry2pos = dict_new2(type);
1453     return d;
1454 }
1455 void*array_getkey(array_t*array, int nr) {
1456     if(nr > array->num || nr<0) {
1457         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1458         return 0;
1459     }
1460     return array->d[nr].name;
1461 }
1462 void*array_getvalue(array_t*array, int nr) {
1463     if(nr > array->num || nr<0) {
1464         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1465         return 0;
1466     }
1467     return array->d[nr].data;
1468 }
1469 int array_append(array_t*array, const void*name, void*data) {
1470     while(array->size <= array->num) {
1471         array->size += 64;
1472         if(!array->d) {
1473             array->d = malloc(sizeof(array_entry_t)*array->size);
1474         } else {
1475             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1476         }
1477     }
1478
1479     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1480
1481     if(name) {
1482         array->d[array->num].name = e->key;
1483     } else {
1484         array->d[array->num].name = 0;
1485     }
1486     array->d[array->num].data = (void*)data;
1487     return array->num++;
1488 }
1489 int array_find(array_t*array, const void*name)
1490 {
1491     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1492     return pos-1;
1493 }
1494 int array_find2(array_t*array, const void*name, void*data)
1495 {
1496     dict_t*h= array->entry2pos;
1497     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1498
1499     while(e) {
1500         int index = ((int)(ptroff_t)e->data) - 1;
1501         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1502             return index;
1503         }
1504         e = e->next;
1505     }
1506     return -1;
1507 }
1508 int array_update(array_t*array, const void*name, void*data) {
1509     int pos = array_find(array, name);
1510     if(pos>=0) {
1511         array->d[pos].data = data;
1512         return pos;
1513     }
1514     return array_append(array, name, data);
1515 }
1516 int array_append_if_new(array_t*array, const void*name, void*data) {
1517     int pos = array_find(array, name);
1518     if(pos>=0)
1519         return pos;
1520     return array_append(array, name, data);
1521 }
1522 void array_free(array_t*array) {
1523     dict_destroy(array->entry2pos);
1524     if(array->d) {
1525         free(array->d);array->d = 0;
1526     }
1527     free(array);
1528 }
1529
1530 // ------------------------------- list_t --------------------------------------
1531
1532 struct _commonlist;
1533 typedef struct _listinfo {
1534     int size;
1535     struct _commonlist*last;
1536 } listinfo_t;
1537
1538 typedef struct _commonlist {
1539     void*entry;
1540     struct _commonlist*next;
1541     listinfo_t info[0];
1542 } commonlist_t;
1543
1544 int list_length_(void*_list)
1545 {
1546     commonlist_t*l = (commonlist_t*)_list;
1547     if(!l)
1548         return 0;
1549     return l->info[0].size;
1550 }
1551 void list_concat_(void*_l1, void*_l2)
1552 {
1553     commonlist_t**l1 = (commonlist_t**)_l1;
1554     commonlist_t**l2 = (commonlist_t**)_l2;
1555
1556     if(!*l1) {
1557         *l1 = *l2;
1558     } else if(*l2) {
1559         (*l1)->info[0].last->next = *l2;
1560         (*l1)->info[0].last = (*l2)->info[0].last;
1561         (*l1)->info[0].size += (*l2)->info[0].size;
1562     }
1563     *l2 = 0;
1564 }
1565 void list_append_(void*_list, void*entry)
1566 {
1567     commonlist_t**list = (commonlist_t**)_list;
1568     commonlist_t* n = 0;
1569     if(!*list) {
1570         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1571         *list = n;
1572         (*list)->info[0].size = 0;
1573     } else {
1574         n = malloc(sizeof(commonlist_t));
1575         (*list)->info[0].last->next = n;
1576     }
1577     n->next = 0;
1578     n->entry = entry;
1579     (*list)->info[0].last = n;
1580     (*list)->info[0].size++;
1581 }
1582 /* notice: prepending uses slighly more space than appending */
1583 void list_prepend_(void*_list, void*entry)
1584 {
1585     commonlist_t**list = (commonlist_t**)_list;
1586     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1587     int size = 0;
1588     commonlist_t* last = 0;
1589     if(*list) {
1590         last = (*list)->info[0].last;
1591         size = (*list)->info[0].size;
1592     }
1593     n->next = *list;
1594     n->entry = entry;
1595     *list = n;
1596     (*list)->info[0].last = last;
1597     (*list)->info[0].size = size+1;
1598 }
1599 void list_free_(void*_list) 
1600 {
1601     commonlist_t**list = (commonlist_t**)_list;
1602     commonlist_t*l = *list;
1603     while(l) {
1604         commonlist_t*next = l->next;
1605         free(l);
1606         l = next;
1607     }
1608     *list = 0;
1609 }
1610 void list_deep_free_(void*_list)
1611 {
1612     commonlist_t**list = (commonlist_t**)_list;
1613     commonlist_t*l = *list;
1614     while(l) {
1615         commonlist_t*next = l->next;
1616         if(l->entry) {
1617             free(l->entry);l->entry=0;
1618         }
1619         free(l);
1620         l = next;
1621     }
1622     *list = 0;
1623 }
1624 void*list_clone_(void*_list) 
1625 {
1626     commonlist_t*l = *(commonlist_t**)_list;
1627
1628     void*dest = 0;
1629     while(l) {
1630         commonlist_t*next = l->next;
1631         list_append_(&dest, l->entry);
1632         l = next;
1633     }
1634     return dest;
1635
1636 }
1637