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 <string.h>
  25 #include <assert.h>
  26 #include <memory.h>
  27 #include "mem.h"
  28 #include "types.h"
  29 #include "q.h"
  30
  31 // ------------------------------- malloc, alloc routines ---------------------
  32
  33 #ifndef STRNDUP
  34 char* strdup_n(const char*str, int size)
  35 {
  36     char*m = (char*)rfx_alloc(size+1);
  37     memcpy(m, str, size);
  38     m[size] = 0;
  39     return m;
  40 }
  41 #endif
  42 char*qstrdup(const char*string)
  43 {
  44     return strdup(string);
  45 }
  46 char*qstrndup(const char*string, int len)
  47 {
  48     return strdup_n(string, len);
  49 }
  50
  51 // ------------------------------- mem_t --------------------------------------
  52
  53 void mem_init(mem_t*mem)
  54 {
  55     memset(mem, 0, sizeof(mem_t));
  56 }
  57 void mem_clear(mem_t*mem)
  58 {
  59     rfx_free(mem->buffer);mem->buffer = 0;
  60 }
  61 void mem_destroy(mem_t*mem)
  62 {
  63     mem_clear(mem);
  64     rfx_free(mem);
  65 }
  66 static int mem_put_(mem_t*m,const void*data, int length, int null)
  67 {
  68     int n = m->pos;
  69     m->pos += length + (null?1:0);
  70     if(m->pos > m->len) {
  71         int v1 = (m->pos+63)&~63;
  72         int v2 = m->len + m->len / 2;
  73         m->len = v1>v2?v1:v2;
  74         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
  75     }
  76     assert(n+length <= m->len);
  77     memcpy(&m->buffer[n], data, length);
  78     if(null)
  79         m->buffer[n + length] = 0;
  80     return n;
  81 }
  82 int mem_put(mem_t*m,void*data, int length)
  83 {
  84     return mem_put_(m, data, length, 0);
  85 }
  86 int mem_putstring(mem_t*m,string_t str)
  87 {
  88     return mem_put_(m, str.str, str.len, 1);
  89 }
  90 int mem_get(mem_t*m, void*data, int length)
  91 {
  92     if(m->read_pos + length > m->pos) {
  93         length = m->pos - m->read_pos;
  94     }
  95     memcpy(data, m->buffer+m->read_pos, length);
  96     m->read_pos += length;
  97     return length;
  98 }
  99
 100 // ------------------------------- ringbuffer_t -------------------------------
 101
 102 typedef struct _ringbuffer_internal_t
 103 {
 104     unsigned char*buffer;
 105     int readpos;
 106     int writepos;
 107     int buffersize;
 108 } ringbuffer_internal_t;
 109
 110 void ringbuffer_init(ringbuffer_t*r)
 111 {
 112     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t));
 113     memset(r, 0, sizeof(ringbuffer_t));
 114     r->internal = i;
 115     i->buffer = (unsigned char*)rfx_alloc(1024);
 116     i->buffersize = 1024;
 117 }
 118 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
 119 {
 120     unsigned char* data = (unsigned char*)buf;
 121     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 122     if(r->available < len)
 123         len = r->available;
 124     if(!len)
 125         return 0;
 126     if(i->readpos + len > i->buffersize) {
 127         int read1 = i->buffersize-i->readpos;
 128         memcpy(data, &i->buffer[i->readpos], read1);
 129         memcpy(&data[read1], &i->buffer[0], len - read1);
 130         i->readpos = len - read1;
 131     } else {
 132         memcpy(data, &i->buffer[i->readpos], len);
 133         i->readpos += len;
 134         i->readpos %= i->buffersize;
 135     }
 136     r->available -= len;
 137     return len;
 138 }
 139 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
 140 {
 141     unsigned char* data = (unsigned char*)buf;
 142     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 143
 144     if(i->buffersize - r->available < len)
 145     {
 146         unsigned char* buf2;
 147         int newbuffersize = i->buffersize;
 148         int oldavailable = r->available;
 149         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
 150
 151         if(newbuffersize < r->available + len)
 152             newbuffersize = r->available + len + 1024;
 153
 154         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
 155         ringbuffer_read(r, buf2, r->available);
 156         rfx_free(i->buffer);
 157         i->buffer = buf2;
 158         i->buffersize = newbuffersize;
 159         i->readpos = 0;
 160         i->writepos = oldavailable;
 161         r->available = oldavailable;
 162     }
 163     if(i->writepos + len > i->buffersize) {
 164         int read1 = i->buffersize-i->writepos;
 165         memcpy(&i->buffer[i->writepos], data, read1);
 166         memcpy(&i->buffer[0], &data[read1], len - read1);
 167         i->writepos = len - read1;
 168     } else {
 169         memcpy(&i->buffer[i->writepos], data, len);
 170         i->writepos += len;
 171         i->writepos %= i->buffersize;
 172     }
 173     r->available += len;
 174 }
 175 void ringbuffer_clear(ringbuffer_t*r)
 176 {
 177     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 178     rfx_free(i->buffer);i->buffer = 0;
 179     rfx_free(i);
 180 }
 181
 182 // ------------------------------- heap_t -------------------------------
 183
 184 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
 185 {
 186     memset(h, 0, sizeof(heap_t));
 187     h->max_size = n;
 188     h->size = 0;
 189     h->elem_size = elem_size;
 190     h->compare = compare;
 191     h->elements = (void**)rfx_calloc(n*sizeof(void*));
 192     h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
 193 }
 194 void heap_clear(heap_t*h)
 195 {
 196     rfx_free(h->elements);
 197     rfx_free(h->data);
 198 }
 199
 200 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
 201
 202 static void up(heap_t*h, int node)
 203 {
 204     void*node_p = h->elements[node];
 205     int parent = node;
 206     do {
 207         node = parent;
 208         if(!node) break;
 209         parent = (node-1)/2;
 210         h->elements[node] = h->elements[parent];
 211     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
 212
 213     h->elements[node] = node_p;
 214 }
 215 static void down(heap_t*h, int node)
 216 {
 217     void*node_p = h->elements[node];
 218     int child = node;
 219     do {
 220         node = child;
 221
 222         /* determine new child's position */
 223         child = node<<1|1;
 224         if(child >= h->size)
 225             break;
 226         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
 227             child++;
 228
 229         h->elements[node] = h->elements[child];
 230     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
 231
 232     h->elements[node] = node_p;
 233 }
 234 void heap_put(heap_t*h, void*e)
 235 {
 236     int pos = h->size++;
 237     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
 238     h->elements[pos] = &h->data[pos];
 239     up(h, pos);
 240 }
 241 int heap_size(heap_t*h)
 242 {
 243     return h->size;
 244 }
 245 void* heap_max(heap_t*h)
 246 {
 247     return h->elements[0];
 248 }
 249 void* heap_chopmax(heap_t*h)
 250 {
 251     void*p = h->elements[0];
 252     h->elements[0] = h->elements[--h->size];
 253     down(h,0);
 254     return p;
 255 }
 256 void heap_dump(heap_t*h, FILE*fi)
 257 {
 258     int t;
 259     for(t=0;t<h->size;t++) {
 260         int s;
 261         for(s=0;s<=t;s=(s+1)*2-1) {
 262             if(s==t) fprintf(fi,"\n");
 263         }
 264         //fprintf(fi,"%d ", h->elements[t]->x); //?
 265     }
 266 }
 267 void** heap_flatten(heap_t*h)
 268 {
 269     void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
 270     void**p = nodes;
 271
 272     while(h->size) {
 273         /*printf("Heap Size: %d\n", h->size);
 274         heap_print(stdout, h);
 275         printf("\n");*/
 276         *p++ = heap_chopmax(h);
 277     }
 278     return nodes;
 279 }
 280
 281 // ------------------------------- trie --------------------------------------
 282
 283 void trie_put(trie_t**t, unsigned const char*id)
 284 {
 285     if(!*t) {
 286         (*t) = rfx_calloc(sizeof(trie_t));
 287         (*t)->rest = (unsigned char*)strdup(id);
 288         return;
 289     }
 290     if((*t)->rest && (*t)->rest[0]) {
 291         // shift whatever's currently in here one node down
 292         trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1);
 293         (*t)->rest = 0;
 294     }
 295     if(id[0]) {
 296         trie_put(&(*t)->row[id[0]], id+1);
 297     } else {
 298         (*t)->rest = strdup("");
 299     }
 300 }
 301
 302 int trie_lookup(trie_t*t, unsigned const char*id)
 303 {
 304     while(t) {
 305         if(t->rest && !strcmp(t->rest, id))
 306             return 1;
 307         if(!*id)
 308             return 0;
 309         t = t->row[*id++];
 310     }
 311     return 0;
 312 }
 313
 314 char trie_remove(trie_t*t, unsigned const char*id)
 315 {
 316     while(t) {
 317         if(t->rest && !strcmp(t->rest, id)) {
 318             free(t->rest);
 319             t->rest = 0;
 320             return 1;
 321         }
 322         if(!*id)
 323             return 0;
 324         t = t->row[*id++];
 325     }
 326 }
 327
 328
 329 // ------------------------------- crc32 --------------------------------------
 330 static unsigned int*crc32 = 0;
 331 static void crc32_init(void)
 332 {
 333     int t;
 334     if(crc32)
 335         return;
 336     crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
 337     for(t=0; t<256; t++) {
 338         unsigned int c = t;
 339         int s;
 340         for (s = 0; s < 8; s++) {
 341           c = (0xedb88320L*(c&1)) ^ (c >> 1);
 342         }
 343         crc32[t] = c;
 344     }
 345 }
 346 // ------------------------------- string_t -----------------------------------
 347
 348 void string_set2(string_t*str, const char*text, int len)
 349 {
 350     str->len = len;
 351     str->str = text;
 352 }
 353 void string_set(string_t*str, const char*text)
 354 {
 355     if(text) {
 356         str->len = strlen(text);
 357     } else {
 358         str->len = 0;
 359     }
 360     str->str = text;
 361 }
 362 string_t string_new(const char*text, int len)
 363 {
 364     string_t s;
 365     s.len = len;
 366     s.str = text;
 367     return s;
 368 }
 369 string_t string_new2(const char*text)
 370 {
 371     string_t s;
 372     if(text) {
 373         s.len = strlen(text);
 374     } else {
 375         s.len = 0;
 376     }
 377     s.str = text;
 378     return s;
 379 }
 380 string_t* string_new3(const char*text, int len)
 381 {
 382     if(!text) {
 383         string_t*s = malloc(sizeof(string_t));
 384         s->len = 0;
 385         s->str = 0;
 386         return s;
 387     } else {
 388         string_t*s = malloc(sizeof(string_t)+len+1);
 389         s->len = len;
 390         s->str = (const char*)(s+1);
 391         memcpy((char*)s->str, text, len);
 392         ((char*)s->str)[len]=0;
 393         return s;
 394     }
 395 }
 396 string_t* string_new4(const char*text)
 397 {
 398     int l = strlen(text);
 399     return string_new3(text, l);
 400 }
 401
 402 void string_free(string_t*s)
 403 {
 404     if(!s)
 405         return;
 406     s->len = 0;
 407     if((string_t*)(s->str) == s+1) {
 408         s->str = 0;
 409         rfx_free(s);
 410     } else {
 411         rfx_free((char*)(s->str));
 412         s->str = 0;
 413         rfx_free(s);
 414     }
 415 }
 416 char* string_cstr(string_t*str)
 417 {
 418     return strdup_n(str->str, str->len);
 419 }
 420 char* string_escape(string_t*str)
 421 {
 422     int t;
 423     int len = 0;
 424     for(t=0;t<str->len;t++) {
 425         if(str->str[t]<0x20)
 426             len+=3;
 427         else
 428             len++;
 429     }
 430     char*s = malloc(len+1);
 431     char*p=s;
 432     for(t=0;t<str->len;t++) {
 433         if(str->str[t]<0x20) {
 434             *p++ ='\\';
 435             unsigned char c = str->str[t];
 436             *p++ = "0123456789abcdef"[c>>4];
 437             *p++ = "0123456789abcdef"[c&0x0f];
 438         } else {
 439             *p++ = str->str[t];
 440         }
 441     }
 442     *p++ = 0;
 443     assert(p == &s[len+1]);
 444     return s;
 445 }
 446
 447 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
 448 {
 449     if(!crc32)
 450         crc32_init();
 451     return checksum>>8 ^ crc32[(b^checksum)&0xff];
 452 }
 453 unsigned int crc32_add_string(unsigned int checksum, const char*s)
 454 {
 455     if(!crc32)
 456         crc32_init();
 457     if(!s)
 458         return checksum;
 459     while(*s) {
 460         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
 461         s++;
 462     }
 463     return checksum;
 464 }
 465
 466 unsigned int string_hash(const string_t*str)
 467 {
 468     int t;
 469     unsigned int checksum = 0;
 470     if(!crc32)
 471         crc32_init();
 472     for(t=0;t<str->len;t++) {
 473         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
 474     }
 475     return checksum;
 476 }
 477 unsigned int string_hash2(const char*str)
 478 {
 479     unsigned int checksum = 0;
 480     const char*p = str;
 481     if(!crc32)
 482         crc32_init();
 483     while(*p) {
 484         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
 485         p++;
 486     }
 487     return checksum;
 488 }
 489 unsigned int string_hash3(const char*str, int len)
 490 {
 491     string_t s;
 492     s.str = str;
 493     s.len = len;
 494     return string_hash(&s);
 495 }
 496 void string_dup2(string_t*str, const char*text, int len)
 497 {
 498     str->len = len;
 499     str->str = strdup_n(text, len);
 500 }
 501 void string_dup(string_t*str, const char*text)
 502 {
 503     str->len = strlen(text);
 504     str->str = strdup(text);
 505 }
 506 int string_equals(string_t*str, const char*text)
 507 {
 508     int l = strlen(text);
 509     if(str->len == l && !memcmp(str->str, text, l))
 510         return 1;
 511     return 0;
 512 }
 513 int string_equals2(string_t*str, string_t*str2)
 514 {
 515     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
 516         return 1;
 517     return 0;
 518 }
 519
 520 // ------------------------------- stringarray_t ------------------------------
 521
 522 typedef struct _stringlist {
 523     int index;
 524     struct _stringlist*next;
 525 } stringlist_t;
 526
 527 typedef struct _stringarray_internal_t
 528 {
 529     mem_t pos;
 530     stringlist_t**hash;
 531     int num;
 532     int hashsize;
 533 } stringarray_internal_t;
 534
 535 void stringarray_init(stringarray_t*sa, int hashsize)
 536 {
 537     stringarray_internal_t*s;
 538     int t;
 539     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
 540     s = (stringarray_internal_t*)sa->internal;
 541     mem_init(&s->pos);
 542     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
 543     s->hashsize = hashsize;
 544 }
 545 void stringarray_put(stringarray_t*sa, string_t str)
 546 {
 547     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 548     int pos;
 549     int hash = string_hash(&str) % s->hashsize;
 550
 551     char*ss = string_cstr(&str);
 552     mem_put(&s->pos, &ss, sizeof(char*));
 553
 554     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
 555     l->index = s->num;
 556     l->next = s->hash[hash];
 557     s->hash[hash] = l;
 558
 559     s->num++;
 560 }
 561 char* stringarray_at(stringarray_t*sa, int pos)
 562 {
 563     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 564     char*p;
 565     if(pos<0 || pos>=s->num)
 566         return 0;
 567     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
 568     if(p<0)
 569         return 0;
 570     return p;
 571 }
 572 string_t stringarray_at2(stringarray_t*sa, int pos)
 573 {
 574     string_t s;
 575     s.str = stringarray_at(sa, pos);
 576     s.len = s.str?strlen(s.str):0;
 577     return s;
 578 }
 579 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
 580 {
 581     stringlist_t*ll = l;
 582     stringlist_t*old = l;
 583     while(l) {
 584         if(index==l->index) {
 585             old->next = l->next;
 586             memset(l, 0, sizeof(stringlist_t));
 587             rfx_free(l);
 588             if(old==l)
 589                 return 0;
 590             else
 591                 return ll;
 592         }
 593         old = l;
 594         l = l->next;
 595     }
 596     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
 597     return ll;
 598 }
 599
 600 void stringarray_del(stringarray_t*sa, int pos)
 601 {
 602     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 603     string_t str = stringarray_at2(sa, pos);
 604     int hash = string_hash(&str) % s->hashsize;
 605     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
 606     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
 607 }
 608 int stringarray_find(stringarray_t*sa, string_t* str)
 609 {
 610     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 611     int hash = string_hash(str) % s->hashsize;
 612     int t;
 613     stringlist_t*l = s->hash[hash];
 614     //TODO: statistics
 615     while(l) {
 616         string_t s = stringarray_at2(sa, l->index);
 617         if(string_equals2(str, &s)) {
 618             return l->index;
 619         }
 620         l = l->next;
 621     }
 622     return -1;
 623 }
 624 void stringarray_clear(stringarray_t*sa)
 625 {
 626     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 627     mem_clear(&s->pos);
 628     int t;
 629     for(t=0;t<s->hashsize;t++) {
 630         stringlist_t*l = s->hash[t];
 631         while(l) {
 632             stringlist_t*next = l->next;
 633             memset(l, 0, sizeof(stringlist_t));
 634             rfx_free(l);
 635             l = next;
 636         }
 637     }
 638     rfx_free(s->hash);s->hash=0;
 639     rfx_free(s);
 640 }
 641 void stringarray_destroy(stringarray_t*sa)
 642 {
 643     stringarray_clear(sa);
 644     rfx_free(sa);
 645 }
 646
 647 // ------------------------------- type_t -------------------------------
 648
 649 char ptr_equals(const void*o1, const void*o2)
 650 {
 651     return o1==o2;
 652 }
 653 unsigned int ptr_hash(const void*o)
 654 {
 655     return string_hash3((const char*)&o, sizeof(o));
 656 }
 657 void* ptr_dup(const void*o)
 658 {
 659     return (void*)o;
 660 }
 661 void ptr_free(void*o)
 662 {
 663     return;
 664 }
 665
 666 char charptr_equals(const void*o1, const void*o2)
 667 {
 668     if(!o1 || !o2)
 669         return o1==o2;
 670     return !strcmp(o1,o2);
 671 }
 672 unsigned int charptr_hash(const void*o)
 673 {
 674     if(!o)
 675         return 0;
 676     return string_hash2(o);
 677 }
 678 void* charptr_dup(const void*o)
 679 {
 680     if(!o)
 681         return 0;
 682     return strdup(o);
 683 }
 684 void charptr_free(void*o)
 685 {
 686     if(o) {
 687         rfx_free(o);
 688     }
 689 }
 690
 691 char stringstruct_equals(const void*o1, const void*o2)
 692 {
 693     if(!o1 || !o2)
 694         return o1==o2;
 695     string_t*s1 = (string_t*)o1;
 696     string_t*s2 = (string_t*)o2;
 697     int l = s1->len<s2->len?s1->len:s2->len;
 698     int r = memcmp(s1->str, s2->str, l);
 699     if(r)
 700         return 0;
 701     else
 702         return s1->len==s2->len;
 703 }
 704 unsigned int stringstruct_hash(const void*o)
 705 {
 706     if(!o) return 0;
 707     return string_hash(o);
 708 }
 709 string_t*string_dup3(string_t*o)
 710 {
 711     if(!o) return 0;
 712     if(!o->str) {
 713         string_t*s = malloc(sizeof(string_t));
 714         s->str=0;
 715         s->len=0;
 716         return s;
 717     }
 718     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
 719     s->len = o->len;
 720     s->str = (const char*)(s+1);
 721     memcpy((char*)s->str, o->str, s->len);
 722     ((char*)s->str)[s->len]=0;
 723     return s;
 724 }
 725 void stringstruct_free(void*o)
 726 {
 727     if(o)
 728         string_free(o);
 729 }
 730
 731 type_t ptr_type = {
 732     equals: ptr_equals,
 733     hash: ptr_hash,
 734     dup: ptr_dup,
 735     free: ptr_free,
 736 };
 737
 738 type_t charptr_type = {
 739     equals: charptr_equals,
 740     hash: charptr_hash,
 741     dup: charptr_dup,
 742     free: charptr_free,
 743 };
 744
 745 type_t stringstruct_type = {
 746     equals: stringstruct_equals,
 747     hash: stringstruct_hash,
 748     dup: (dup_func)string_dup3,
 749     free: stringstruct_free,
 750 };
 751
 752 // ------------------------------- dictionary_t -------------------------------
 753
 754 #define INITIAL_SIZE 1
 755
 756 static int max(int x, int y) {
 757     return x>y?x:y;
 758 }
 759
 760 dict_t*dict_new()
 761 {
 762     dict_t*d = rfx_alloc(sizeof(dict_t));
 763     dict_init(d, INITIAL_SIZE);
 764     return d;
 765 }
 766 dict_t*dict_new2(type_t*t)
 767 {
 768     dict_t*d = rfx_alloc(sizeof(dict_t));
 769     dict_init(d, INITIAL_SIZE);
 770     d->key_type = t;
 771     return d;
 772 }
 773 void dict_init(dict_t*h, int size)
 774 {
 775     memset(h, 0, sizeof(dict_t));
 776     h->hashsize = size;
 777     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 778     h->num = 0;
 779     h->key_type = &charptr_type;
 780 }
 781 void dict_init2(dict_t*h, type_t*t, int size)
 782 {
 783     memset(h, 0, sizeof(dict_t));
 784     h->hashsize = size;
 785     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 786     h->num = 0;
 787     h->key_type = t;
 788 }
 789
 790 dict_t*dict_clone(dict_t*o)
 791 {
 792     dict_t*h = rfx_alloc(sizeof(dict_t));
 793     memcpy(h, o, sizeof(dict_t));
 794     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 795     int t;
 796     for(t=0;t<o->hashsize;t++) {
 797         dictentry_t*e = o->slots[t];
 798         while(e) {
 799             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 800             memcpy(n, e, sizeof(dictentry_t));
 801             n->key = h->key_type->dup(e->key);
 802             n->data = e->data;
 803             n->next = h->slots[t];
 804             h->slots[t] = n;
 805             e = e->next;
 806         }
 807     }
 808     return h;
 809 }
 810
 811 static void dict_expand(dict_t*h, int newlen)
 812 {
 813     assert(h->hashsize < newlen);
 814     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
 815     int t;
 816     for(t=0;t<h->hashsize;t++) {
 817         dictentry_t*e = h->slots[t];
 818         while(e) {
 819             dictentry_t*next = e->next;
 820             unsigned int newhash = e->hash%newlen;
 821             e->next = newslots[newhash];
 822             newslots[newhash] = e;
 823             e = next;
 824         }
 825     }
 826     if(h->slots)
 827         rfx_free(h->slots);
 828     h->slots = newslots;
 829     h->hashsize = newlen;
 830 }
 831
 832 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
 833 {
 834     unsigned int hash = h->key_type->hash(key);
 835     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 836     unsigned int hash2 = hash % h->hashsize;
 837
 838     e->key = h->key_type->dup(key);
 839     e->hash = hash; //for resizing
 840     e->next = h->slots[hash2];
 841     e->data = data;
 842     h->slots[hash2] = e;
 843     h->num++;
 844     return e;
 845 }
 846 void dict_put2(dict_t*h, const char*s, void*data)
 847 {
 848     assert(h->key_type == &charptr_type);
 849     dict_put(h, s, data);
 850 }
 851 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
 852 {
 853     int t;
 854     for(t=0;t<h->hashsize;t++) {
 855         dictentry_t*e = h->slots[t];
 856         while(e) {
 857             if(h->key_type!=&charptr_type) {
 858                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
 859             } else {
 860                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
 861             }
 862             e = e->next;
 863         }
 864     }
 865 }
 866
 867 int dict_count(dict_t*h)
 868 {
 869     return h->num;
 870 }
 871
 872 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
 873 {
 874     if(!h->num) {
 875         return 0;
 876     }
 877
 878     unsigned int ohash = h->key_type->hash(key);
 879     unsigned int hash = ohash % h->hashsize;
 880
 881     /* check first entry for match */
 882     dictentry_t*e = h->slots[hash];
 883     if(e && h->key_type->equals(e->key, key)) {
 884         return e;
 885     } else if(e) {
 886         e = e->next;
 887     }
 888
 889     /* if dict is 2/3 filled, double the size. Do
 890        this the first time we have to actually iterate
 891        through a slot to find our data */
 892     if(e && h->num*3 >= h->hashsize*2) {
 893         int newsize = h->hashsize;
 894         while(h->num*3 >= newsize*2) {
 895             newsize = newsize<15?15:(newsize+1)*2-1;
 896         }
 897         dict_expand(h, newsize);
 898         hash = ohash % h->hashsize;
 899         e = h->slots[hash];
 900         if(e && h->key_type->equals(e->key, key)) {
 901             // omit move to front
 902             return e;
 903         } else if(e) {
 904             e = e->next;
 905         }
 906     }
 907
 908     /* check subsequent entries for a match */
 909     dictentry_t*last = h->slots[hash];
 910     while(e) {
 911         if(h->key_type->equals(e->key, key)) {
 912             /* move to front- makes a difference of about 10% in most applications */
 913             last->next = e->next;
 914             e->next = h->slots[hash];
 915             h->slots[hash] = e;
 916             return e;
 917         }
 918         last=e;
 919         e = e->next;
 920     }
 921     return 0;
 922 }
 923 void* dict_lookup(dict_t*h, const void*key)
 924 {
 925     dictentry_t*e = dict_do_lookup(h, key);
 926     if(e)
 927         return e->data;
 928     return 0;
 929 }
 930 char dict_contains(dict_t*h, const void*key)
 931 {
 932     dictentry_t*e = dict_do_lookup(h, key);
 933     return !!e;
 934 }
 935
 936 char dict_del(dict_t*h, const void*key)
 937 {
 938     if(!h->num)
 939         return 0;
 940     unsigned int hash = h->key_type->hash(key) % h->hashsize;
 941     dictentry_t*head = h->slots[hash];
 942     dictentry_t*e = head, *prev=0;
 943     while(e) {
 944         if(h->key_type->equals(e->key, key)) {
 945             dictentry_t*next = e->next;
 946             rfx_free((void*)e->key);
 947             memset(e, 0, sizeof(dictentry_t));
 948             rfx_free(e);
 949             if(e == head) {
 950                 h->slots[hash] = next;
 951             } else {
 952                 assert(prev);
 953                 prev->next = next;
 954             }
 955             h->num--;
 956             return 1;
 957         }
 958         prev = e;
 959         e = e->next;
 960     }
 961     return 0;
 962 }
 963
 964 dictentry_t* dict_get_slot(dict_t*h, const void*key)
 965 {
 966     if(!h->num)
 967         return 0;
 968     unsigned int ohash = h->key_type->hash(key);
 969     unsigned int hash = ohash % h->hashsize;
 970     return h->slots[hash];
 971 }
 972
 973 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
 974 {
 975     int t;
 976     for(t=0;t<h->hashsize;t++) {
 977         dictentry_t*e = h->slots[t];
 978         while(e) {
 979             dictentry_t*next = e->next;
 980             if(runFunction) {
 981                 runFunction(data, e->key, e->data);
 982             }
 983             e = e->next;
 984         }
 985     }
 986 }
 987 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
 988 {
 989     int t;
 990     for(t=0;t<h->hashsize;t++) {
 991         dictentry_t*e = h->slots[t];
 992         while(e) {
 993             dictentry_t*next = e->next;
 994             if(runFunction) {
 995                 runFunction(e->data);
 996             }
 997             e = e->next;
 998         }
 999     }
1000 }
1001
1002 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1003 {
1004     int t;
1005     for(t=0;t<h->hashsize;t++) {
1006         dictentry_t*e = h->slots[t];
1007         while(e) {
1008             dictentry_t*next = e->next;
1009             if(free_keys) {
1010                 h->key_type->free(e->key);
1011             }
1012             if(free_data_function) {
1013                 free_data_function(e->data);
1014             }
1015             memset(e, 0, sizeof(dictentry_t));
1016             rfx_free(e);
1017             e = next;
1018         }
1019         h->slots[t]=0;
1020     }
1021     rfx_free(h->slots);
1022     memset(h, 0, sizeof(dict_t));
1023 }
1024
1025 void dict_clear_shallow(dict_t*h)
1026 {
1027     dict_free_all(h, 0, 0);
1028 }
1029
1030 void dict_clear(dict_t*h)
1031 {
1032     dict_free_all(h, 1, 0);
1033 }
1034
1035 void dict_destroy_shallow(dict_t*dict)
1036 {
1037     dict_clear_shallow(dict);
1038     rfx_free(dict);
1039 }
1040
1041 void dict_destroy(dict_t*dict)
1042 {
1043     dict_clear(dict);
1044     rfx_free(dict);
1045 }
1046
1047 // ------------------------------- map_t --------------------------------------
1048
1049 typedef struct _map_internal_t
1050 {
1051     dict_t d;
1052 } map_internal_t;
1053
1054 void map_init(map_t*map)
1055 {
1056     map_internal_t*m;
1057     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1058     m = (map_internal_t*)map->internal;
1059     dict_init(&m->d, INITIAL_SIZE);
1060 }
1061 void map_put(map_t*map, string_t t1, string_t t2)
1062 {
1063     map_internal_t*m = (map_internal_t*)map->internal;
1064     string_t s;
1065     char* s1 = string_cstr(&t1);
1066     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1067     rfx_free(s1);
1068 }
1069 const char* map_lookup(map_t*map, const char*name)
1070 {
1071     map_internal_t*m = (map_internal_t*)map->internal;
1072     const char*value = dict_lookup(&m->d, name);
1073     return value;
1074 }
1075 static void freestring(void*data)
1076 {
1077     rfx_free(data);
1078 }
1079 static void dumpmapentry(void*data, const void*key, void*value)
1080 {
1081     FILE*fi = (FILE*)data;
1082     fprintf(fi, "%s=%s\n", key, (char*)value);
1083 }
1084 void map_dump(map_t*map, FILE*fi, const char*prefix)
1085 {
1086     int t;
1087     map_internal_t*m = (map_internal_t*)map->internal;
1088     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1089 }
1090 void map_clear(map_t*map)
1091 {
1092     map_internal_t*m = (map_internal_t*)map->internal;
1093     dict_free_all(&m->d, 1, freestring);
1094     rfx_free(m);
1095 }
1096 void map_destroy(map_t*map)
1097 {
1098     map_clear(map);
1099     rfx_free(map);
1100 }
1101
1102 // ------------------------------- array_t --------------------------------------
1103
1104 array_t* array_new() {
1105     array_t*d = malloc(sizeof(array_t));
1106     memset(d, 0, sizeof(array_t));
1107     d->entry2pos = dict_new();
1108     return d;
1109 }
1110 array_t* array_new2(type_t*type) {
1111     array_t*d = malloc(sizeof(array_t));
1112     memset(d, 0, sizeof(array_t));
1113     d->entry2pos = dict_new2(type);
1114     return d;
1115 }
1116 void*array_getkey(array_t*array, int nr) {
1117     if(nr > array->num || nr<0) {
1118         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1119         return 0;
1120     }
1121     return array->d[nr].name;
1122 }
1123 void*array_getvalue(array_t*array, int nr) {
1124     if(nr > array->num || nr<0) {
1125         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1126         return 0;
1127     }
1128     return array->d[nr].data;
1129 }
1130 int array_append(array_t*array, const void*name, void*data) {
1131     while(array->size <= array->num) {
1132         array->size += 64;
1133         if(!array->d) {
1134             array->d = malloc(sizeof(array_entry_t)*array->size);
1135         } else {
1136             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1137         }
1138     }
1139
1140     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1141
1142     if(name) {
1143         array->d[array->num].name = e->key;
1144     } else {
1145         array->d[array->num].name = 0;
1146     }
1147     array->d[array->num].data = (void*)data;
1148     return array->num++;
1149 }
1150 int array_find(array_t*array, const void*name)
1151 {
1152     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1153     return pos-1;
1154 }
1155 int array_find2(array_t*array, const void*name, void*data)
1156 {
1157     dict_t*h= array->entry2pos;
1158     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1159
1160     while(e) {
1161         int index = ((int)(ptroff_t)e->data) - 1;
1162         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1163             return index;
1164         }
1165         e = e->next;
1166     }
1167     return -1;
1168 }
1169 int array_update(array_t*array, const void*name, void*data) {
1170     int pos = array_find(array, name);
1171     if(pos>=0) {
1172         array->d[pos].data = data;
1173         return pos;
1174     }
1175     return array_append(array, name, data);
1176 }
1177 int array_append_if_new(array_t*array, const void*name, void*data) {
1178     int pos = array_find(array, name);
1179     if(pos>=0)
1180         return pos;
1181     return array_append(array, name, data);
1182 }
1183 void array_free(array_t*array) {
1184     dict_destroy(array->entry2pos);
1185     if(array->d) {
1186         free(array->d);array->d = 0;
1187     }
1188     free(array);
1189 }
1190
1191 // ------------------------------- list_t --------------------------------------
1192
1193 struct _commonlist;
1194 typedef struct _listinfo {
1195     int size;
1196     struct _commonlist*last;
1197 } listinfo_t;
1198
1199 typedef struct _commonlist {
1200     void*entry;
1201     struct _commonlist*next;
1202     listinfo_t info[0];
1203 } commonlist_t;
1204
1205 int list_length_(void*_list)
1206 {
1207     commonlist_t*l = (commonlist_t*)_list;
1208     if(!l)
1209         return 0;
1210     return l->info[0].size;
1211 }
1212 void list_concat_(void*_l1, void*_l2)
1213 {
1214     commonlist_t**l1 = (commonlist_t**)_l1;
1215     commonlist_t**l2 = (commonlist_t**)_l2;
1216
1217     if(!*l1) {
1218         *l1 = *l2;
1219     } else if(*l2) {
1220         (*l1)->info[0].last->next = *l2;
1221         (*l1)->info[0].last = (*l2)->info[0].last;
1222         (*l1)->info[0].size += (*l2)->info[0].size;
1223     }
1224     *l2 = 0;
1225 }
1226 void list_append_(void*_list, void*entry)
1227 {
1228     commonlist_t**list = (commonlist_t**)_list;
1229     commonlist_t* n = 0;
1230     if(!*list) {
1231         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1232         *list = n;
1233         (*list)->info[0].size = 0;
1234     } else {
1235         n = malloc(sizeof(commonlist_t));
1236         (*list)->info[0].last->next = n;
1237     }
1238     n->next = 0;
1239     n->entry = entry;
1240     (*list)->info[0].last = n;
1241     (*list)->info[0].size++;
1242 }
1243 /* notice: prepending uses slighly more space than appending */
1244 void list_prepend_(void*_list, void*entry)
1245 {
1246     commonlist_t**list = (commonlist_t**)_list;
1247     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1248     int size = 0;
1249     commonlist_t* last = 0;
1250     if(*list) {
1251         last = (*list)->info[0].last;
1252         size = (*list)->info[0].size;
1253     }
1254     n->next = *list;
1255     n->entry = entry;
1256     *list = n;
1257     (*list)->info[0].last = last;
1258     (*list)->info[0].size = size+1;
1259 }
1260 void list_free_(void*_list)
1261 {
1262     commonlist_t**list = (commonlist_t**)_list;
1263     commonlist_t*l = *list;
1264     while(l) {
1265         commonlist_t*next = l->next;
1266         free(l);
1267         l = next;
1268     }
1269     *list = 0;
1270 }
1271 void list_deep_free_(void*_list)
1272 {
1273     commonlist_t**list = (commonlist_t**)_list;
1274     commonlist_t*l = *list;
1275     while(l) {
1276         commonlist_t*next = l->next;
1277         if(l->entry) {
1278             free(l->entry);l->entry=0;
1279         }
1280         free(l);
1281         l = next;
1282     }
1283     *list = 0;
1284 }
1285 void*list_clone_(void*_list)
1286 {
1287     commonlist_t*l = *(commonlist_t**)_list;
1288
1289     void*dest = 0;
1290     while(l) {
1291         commonlist_t*next = l->next;
1292         list_append_(&dest, l->entry);
1293         l = next;
1294     }
1295     return dest;
1296
1297 }