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