lib/q.c

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