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(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 = 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(t->rest, 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(t->rest, 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(t->rest, 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, 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 charptr_equals(const void*o1, const void*o2)
 891 {
 892     if(!o1 || !o2)
 893         return o1==o2;
 894     return !strcmp(o1,o2);
 895 }
 896 unsigned int charptr_hash(const void*o)
 897 {
 898     if(!o)
 899         return 0;
 900     return string_hash2(o);
 901 }
 902 void* charptr_dup(const void*o)
 903 {
 904     if(!o)
 905         return 0;
 906     return strdup(o);
 907 }
 908 void charptr_free(void*o)
 909 {
 910     if(o) {
 911         rfx_free(o);
 912     }
 913 }
 914
 915 char stringstruct_equals(const void*o1, const void*o2)
 916 {
 917     if(!o1 || !o2)
 918         return o1==o2;
 919     string_t*s1 = (string_t*)o1;
 920     string_t*s2 = (string_t*)o2;
 921     int l = s1->len<s2->len?s1->len:s2->len;
 922     int r = memcmp(s1->str, s2->str, l);
 923     if(r)
 924         return 0;
 925     else
 926         return s1->len==s2->len;
 927 }
 928 unsigned int stringstruct_hash(const void*o)
 929 {
 930     if(!o) return 0;
 931     return string_hash(o);
 932 }
 933 string_t*string_dup3(string_t*o)
 934 {
 935     if(!o) return 0;
 936     if(!o->str) {
 937         string_t*s = malloc(sizeof(string_t));
 938         s->str=0;
 939         s->len=0;
 940         return s;
 941     }
 942     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
 943     s->len = o->len;
 944     s->str = (const char*)(s+1);
 945     memcpy((char*)s->str, o->str, s->len);
 946     ((char*)s->str)[s->len]=0;
 947     return s;
 948 }
 949 void stringstruct_free(void*o)
 950 {
 951     if(o)
 952         string_free(o);
 953 }
 954
 955 type_t ptr_type = {
 956     equals: ptr_equals,
 957     hash: ptr_hash,
 958     dup: ptr_dup,
 959     free: ptr_free,
 960 };
 961
 962 type_t charptr_type = {
 963     equals: charptr_equals,
 964     hash: charptr_hash,
 965     dup: charptr_dup,
 966     free: charptr_free,
 967 };
 968
 969 type_t stringstruct_type = {
 970     equals: stringstruct_equals,
 971     hash: stringstruct_hash,
 972     dup: (dup_func)string_dup3,
 973     free: stringstruct_free,
 974 };
 975
 976 // ------------------------------- dictionary_t -------------------------------
 977
 978 #define INITIAL_SIZE 1
 979
 980 static int max(int x, int y) {
 981     return x>y?x:y;
 982 }
 983
 984 dict_t*dict_new()
 985 {
 986     dict_t*d = rfx_alloc(sizeof(dict_t));
 987     dict_init(d, INITIAL_SIZE);
 988     return d;
 989 }
 990 dict_t*dict_new2(type_t*t)
 991 {
 992     dict_t*d = rfx_alloc(sizeof(dict_t));
 993     dict_init(d, INITIAL_SIZE);
 994     d->key_type = t;
 995     return d;
 996 }
 997 void dict_init(dict_t*h, int size)
 998 {
 999     memset(h, 0, sizeof(dict_t));
1000     h->hashsize = size;
1001     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1002     h->num = 0;
1003     h->key_type = &charptr_type;
1004 }
1005 void dict_init2(dict_t*h, type_t*t, int size)
1006 {
1007     memset(h, 0, sizeof(dict_t));
1008     h->hashsize = size;
1009     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1010     h->num = 0;
1011     h->key_type = t;
1012 }
1013
1014 dict_t*dict_clone(dict_t*o)
1015 {
1016     dict_t*h = rfx_alloc(sizeof(dict_t));
1017     memcpy(h, o, sizeof(dict_t));
1018     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
1019     int t;
1020     for(t=0;t<o->hashsize;t++) {
1021         dictentry_t*e = o->slots[t];
1022         while(e) {
1023             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1024             memcpy(n, e, sizeof(dictentry_t));
1025             n->key = h->key_type->dup(e->key);
1026             n->data = e->data;
1027             n->next = h->slots[t];
1028             h->slots[t] = n;
1029             e = e->next;
1030         }
1031     }
1032     return h;
1033 }
1034
1035 static void dict_expand(dict_t*h, int newlen)
1036 {
1037     assert(h->hashsize < newlen);
1038     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
1039     int t;
1040     for(t=0;t<h->hashsize;t++) {
1041         dictentry_t*e = h->slots[t];
1042         while(e) {
1043             dictentry_t*next = e->next;
1044             unsigned int newhash = e->hash%newlen;
1045             e->next = newslots[newhash];
1046             newslots[newhash] = e;
1047             e = next;
1048         }
1049     }
1050     if(h->slots)
1051         rfx_free(h->slots);
1052     h->slots = newslots;
1053     h->hashsize = newlen;
1054 }
1055
1056 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
1057 {
1058     unsigned int hash = h->key_type->hash(key);
1059     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1060
1061     if(!h->hashsize)
1062         dict_expand(h, 1);
1063
1064     unsigned int hash2 = hash % h->hashsize;
1065
1066     e->key = h->key_type->dup(key);
1067     e->hash = hash; //for resizing
1068     e->next = h->slots[hash2];
1069     e->data = data;
1070     h->slots[hash2] = e;
1071     h->num++;
1072     return e;
1073 }
1074 void dict_put2(dict_t*h, const char*s, void*data)
1075 {
1076     assert(h->key_type == &charptr_type);
1077     dict_put(h, s, data);
1078 }
1079 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
1080 {
1081     int t;
1082     for(t=0;t<h->hashsize;t++) {
1083         dictentry_t*e = h->slots[t];
1084         while(e) {
1085             if(h->key_type!=&charptr_type) {
1086                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
1087             } else {
1088                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
1089             }
1090             e = e->next;
1091         }
1092     }
1093 }
1094
1095 int dict_count(dict_t*h)
1096 {
1097     return h->num;
1098 }
1099
1100 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
1101 {
1102     if(!h->num) {
1103         return 0;
1104     }
1105
1106     unsigned int ohash = h->key_type->hash(key);
1107     unsigned int hash = ohash % h->hashsize;
1108
1109     /* check first entry for match */
1110     dictentry_t*e = h->slots[hash];
1111     if(e && h->key_type->equals(e->key, key)) {
1112         return e;
1113     } else if(e) {
1114         e = e->next;
1115     }
1116
1117     /* if dict is 2/3 filled, double the size. Do
1118        this the first time we have to actually iterate
1119        through a slot to find our data */
1120     if(e && h->num*3 >= h->hashsize*2) {
1121         int newsize = h->hashsize;
1122         while(h->num*3 >= newsize*2) {
1123             newsize = newsize<15?15:(newsize+1)*2-1;
1124         }
1125         dict_expand(h, newsize);
1126         hash = ohash % h->hashsize;
1127         e = h->slots[hash];
1128         if(e && h->key_type->equals(e->key, key)) {
1129             // omit move to front
1130             return e;
1131         } else if(e) {
1132             e = e->next;
1133         }
1134     }
1135
1136     /* check subsequent entries for a match */
1137     dictentry_t*last = h->slots[hash];
1138     while(e) {
1139         if(h->key_type->equals(e->key, key)) {
1140             /* move to front- makes a difference of about 10% in most applications */
1141             last->next = e->next;
1142             e->next = h->slots[hash];
1143             h->slots[hash] = e;
1144             return e;
1145         }
1146         last=e;
1147         e = e->next;
1148     }
1149     return 0;
1150 }
1151 void* dict_lookup(dict_t*h, const void*key)
1152 {
1153     dictentry_t*e = dict_do_lookup(h, key);
1154     if(e)
1155         return e->data;
1156     return 0;
1157 }
1158 char dict_contains(dict_t*h, const void*key)
1159 {
1160     dictentry_t*e = dict_do_lookup(h, key);
1161     return !!e;
1162 }
1163
1164 char dict_del(dict_t*h, const void*key)
1165 {
1166     if(!h->num)
1167         return 0;
1168     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1169     dictentry_t*head = h->slots[hash];
1170     dictentry_t*e = head, *prev=0;
1171     while(e) {
1172         if(h->key_type->equals(e->key, key)) {
1173             dictentry_t*next = e->next;
1174             h->key_type->free(e->key);
1175             memset(e, 0, sizeof(dictentry_t));
1176             rfx_free(e);
1177             if(e == head) {
1178                 h->slots[hash] = next;
1179             } else {
1180                 assert(prev);
1181                 prev->next = next;
1182             }
1183             h->num--;
1184             return 1;
1185         }
1186         prev = e;
1187         e = e->next;
1188     }
1189     return 0;
1190 }
1191
1192 char dict_del2(dict_t*h, const void*key, void*data)
1193 {
1194     if(!h->num)
1195         return 0;
1196     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1197     dictentry_t*head = h->slots[hash];
1198     dictentry_t*e = head, *prev=0;
1199     while(e) {
1200         if(h->key_type->equals(e->key, key) && e->data == data) {
1201             dictentry_t*next = e->next;
1202             h->key_type->free(e->key);
1203             memset(e, 0, sizeof(dictentry_t));
1204             rfx_free(e);
1205             if(e == head) {
1206                 h->slots[hash] = next;
1207             } else {
1208                 assert(prev);
1209                 prev->next = next;
1210             }
1211             h->num--;
1212             return 1;
1213         }
1214         prev = e;
1215         e = e->next;
1216     }
1217     return 0;
1218 }
1219
1220 dictentry_t* dict_get_slot(dict_t*h, const void*key)
1221 {
1222     if(!h->num)
1223         return 0;
1224     unsigned int ohash = h->key_type->hash(key);
1225     unsigned int hash = ohash % h->hashsize;
1226     return h->slots[hash];
1227 }
1228
1229 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
1230 {
1231     int t;
1232     for(t=0;t<h->hashsize;t++) {
1233         dictentry_t*e = h->slots[t];
1234         while(e) {
1235             dictentry_t*next = e->next;
1236             if(runFunction) {
1237                 runFunction(data, e->key, e->data);
1238             }
1239             e = e->next;
1240         }
1241     }
1242 }
1243 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
1244 {
1245     int t;
1246     for(t=0;t<h->hashsize;t++) {
1247         dictentry_t*e = h->slots[t];
1248         while(e) {
1249             dictentry_t*next = e->next;
1250             if(runFunction) {
1251                 runFunction(e->data);
1252             }
1253             e = e->next;
1254         }
1255     }
1256 }
1257
1258 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1259 {
1260     int t;
1261     for(t=0;t<h->hashsize;t++) {
1262         dictentry_t*e = h->slots[t];
1263         while(e) {
1264             dictentry_t*next = e->next;
1265             if(free_keys) {
1266                 h->key_type->free(e->key);
1267             }
1268             if(free_data_function) {
1269                 free_data_function(e->data);
1270             }
1271             memset(e, 0, sizeof(dictentry_t));
1272             rfx_free(e);
1273             e = next;
1274         }
1275         h->slots[t]=0;
1276     }
1277     rfx_free(h->slots);
1278     memset(h, 0, sizeof(dict_t));
1279 }
1280
1281 void dict_clear_shallow(dict_t*h)
1282 {
1283     dict_free_all(h, 0, 0);
1284 }
1285
1286 void dict_clear(dict_t*h)
1287 {
1288     dict_free_all(h, 1, 0);
1289 }
1290
1291 void dict_destroy_shallow(dict_t*dict)
1292 {
1293     dict_clear_shallow(dict);
1294     rfx_free(dict);
1295 }
1296
1297 void dict_destroy(dict_t*dict)
1298 {
1299     if(!dict)
1300         return;
1301     dict_clear(dict);
1302     rfx_free(dict);
1303 }
1304
1305 // ------------------------------- map_t --------------------------------------
1306
1307 typedef struct _map_internal_t
1308 {
1309     dict_t d;
1310 } map_internal_t;
1311
1312 void map_init(map_t*map)
1313 {
1314     map_internal_t*m;
1315     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1316     m = (map_internal_t*)map->internal;
1317     dict_init(&m->d, INITIAL_SIZE);
1318 }
1319 void map_put(map_t*map, string_t t1, string_t t2)
1320 {
1321     map_internal_t*m = (map_internal_t*)map->internal;
1322     string_t s;
1323     char* s1 = string_cstr(&t1);
1324     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1325     rfx_free(s1);
1326 }
1327 const char* map_lookup(map_t*map, const char*name)
1328 {
1329     map_internal_t*m = (map_internal_t*)map->internal;
1330     const char*value = dict_lookup(&m->d, name);
1331     return value;
1332 }
1333 static void freestring(void*data)
1334 {
1335     rfx_free(data);
1336 }
1337 static void dumpmapentry(void*data, const void*key, void*value)
1338 {
1339     FILE*fi = (FILE*)data;
1340     fprintf(fi, "%s=%s\n", key, (char*)value);
1341 }
1342 void map_dump(map_t*map, FILE*fi, const char*prefix)
1343 {
1344     int t;
1345     map_internal_t*m = (map_internal_t*)map->internal;
1346     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1347 }
1348 void map_clear(map_t*map)
1349 {
1350     map_internal_t*m = (map_internal_t*)map->internal;
1351     dict_free_all(&m->d, 1, freestring);
1352     rfx_free(m);
1353 }
1354 void map_destroy(map_t*map)
1355 {
1356     map_clear(map);
1357     rfx_free(map);
1358 }
1359
1360 // ------------------------------- array_t --------------------------------------
1361
1362 array_t* array_new() {
1363     array_t*d = malloc(sizeof(array_t));
1364     memset(d, 0, sizeof(array_t));
1365     d->entry2pos = dict_new();
1366     return d;
1367 }
1368 array_t* array_new2(type_t*type) {
1369     array_t*d = malloc(sizeof(array_t));
1370     memset(d, 0, sizeof(array_t));
1371     d->entry2pos = dict_new2(type);
1372     return d;
1373 }
1374 void*array_getkey(array_t*array, int nr) {
1375     if(nr > array->num || nr<0) {
1376         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1377         return 0;
1378     }
1379     return array->d[nr].name;
1380 }
1381 void*array_getvalue(array_t*array, int nr) {
1382     if(nr > array->num || nr<0) {
1383         fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
1384         return 0;
1385     }
1386     return array->d[nr].data;
1387 }
1388 int array_append(array_t*array, const void*name, void*data) {
1389     while(array->size <= array->num) {
1390         array->size += 64;
1391         if(!array->d) {
1392             array->d = malloc(sizeof(array_entry_t)*array->size);
1393         } else {
1394             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1395         }
1396     }
1397
1398     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1399
1400     if(name) {
1401         array->d[array->num].name = e->key;
1402     } else {
1403         array->d[array->num].name = 0;
1404     }
1405     array->d[array->num].data = (void*)data;
1406     return array->num++;
1407 }
1408 int array_find(array_t*array, const void*name)
1409 {
1410     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1411     return pos-1;
1412 }
1413 int array_find2(array_t*array, const void*name, void*data)
1414 {
1415     dict_t*h= array->entry2pos;
1416     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1417
1418     while(e) {
1419         int index = ((int)(ptroff_t)e->data) - 1;
1420         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1421             return index;
1422         }
1423         e = e->next;
1424     }
1425     return -1;
1426 }
1427 int array_update(array_t*array, const void*name, void*data) {
1428     int pos = array_find(array, name);
1429     if(pos>=0) {
1430         array->d[pos].data = data;
1431         return pos;
1432     }
1433     return array_append(array, name, data);
1434 }
1435 int array_append_if_new(array_t*array, const void*name, void*data) {
1436     int pos = array_find(array, name);
1437     if(pos>=0)
1438         return pos;
1439     return array_append(array, name, data);
1440 }
1441 void array_free(array_t*array) {
1442     dict_destroy(array->entry2pos);
1443     if(array->d) {
1444         free(array->d);array->d = 0;
1445     }
1446     free(array);
1447 }
1448
1449 // ------------------------------- list_t --------------------------------------
1450
1451 struct _commonlist;
1452 typedef struct _listinfo {
1453     int size;
1454     struct _commonlist*last;
1455 } listinfo_t;
1456
1457 typedef struct _commonlist {
1458     void*entry;
1459     struct _commonlist*next;
1460     listinfo_t info[0];
1461 } commonlist_t;
1462
1463 int list_length_(void*_list)
1464 {
1465     commonlist_t*l = (commonlist_t*)_list;
1466     if(!l)
1467         return 0;
1468     return l->info[0].size;
1469 }
1470 void list_concat_(void*_l1, void*_l2)
1471 {
1472     commonlist_t**l1 = (commonlist_t**)_l1;
1473     commonlist_t**l2 = (commonlist_t**)_l2;
1474
1475     if(!*l1) {
1476         *l1 = *l2;
1477     } else if(*l2) {
1478         (*l1)->info[0].last->next = *l2;
1479         (*l1)->info[0].last = (*l2)->info[0].last;
1480         (*l1)->info[0].size += (*l2)->info[0].size;
1481     }
1482     *l2 = 0;
1483 }
1484 void list_append_(void*_list, void*entry)
1485 {
1486     commonlist_t**list = (commonlist_t**)_list;
1487     commonlist_t* n = 0;
1488     if(!*list) {
1489         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1490         *list = n;
1491         (*list)->info[0].size = 0;
1492     } else {
1493         n = malloc(sizeof(commonlist_t));
1494         (*list)->info[0].last->next = n;
1495     }
1496     n->next = 0;
1497     n->entry = entry;
1498     (*list)->info[0].last = n;
1499     (*list)->info[0].size++;
1500 }
1501 /* notice: prepending uses slighly more space than appending */
1502 void list_prepend_(void*_list, void*entry)
1503 {
1504     commonlist_t**list = (commonlist_t**)_list;
1505     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1506     int size = 0;
1507     commonlist_t* last = 0;
1508     if(*list) {
1509         last = (*list)->info[0].last;
1510         size = (*list)->info[0].size;
1511     }
1512     n->next = *list;
1513     n->entry = entry;
1514     *list = n;
1515     (*list)->info[0].last = last;
1516     (*list)->info[0].size = size+1;
1517 }
1518 void list_free_(void*_list)
1519 {
1520     commonlist_t**list = (commonlist_t**)_list;
1521     commonlist_t*l = *list;
1522     while(l) {
1523         commonlist_t*next = l->next;
1524         free(l);
1525         l = next;
1526     }
1527     *list = 0;
1528 }
1529 void list_deep_free_(void*_list)
1530 {
1531     commonlist_t**list = (commonlist_t**)_list;
1532     commonlist_t*l = *list;
1533     while(l) {
1534         commonlist_t*next = l->next;
1535         if(l->entry) {
1536             free(l->entry);l->entry=0;
1537         }
1538         free(l);
1539         l = next;
1540     }
1541     *list = 0;
1542 }
1543 void*list_clone_(void*_list)
1544 {
1545     commonlist_t*l = *(commonlist_t**)_list;
1546
1547     void*dest = 0;
1548     while(l) {
1549         commonlist_t*next = l->next;
1550         list_append_(&dest, l->entry);
1551         l = next;
1552     }
1553     return dest;
1554
1555 }
1556