lib/q.c

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