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     if(!crc32)
 648         crc32_init();
 649     return checksum>>8 ^ crc32[(b^checksum)&0xff];
 650 }
 651 unsigned int crc32_add_string(unsigned int checksum, const char*s)
 652 {
 653     if(!crc32)
 654         crc32_init();
 655     if(!s)
 656         return checksum;
 657     while(*s) {
 658         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
 659         s++;
 660     }
 661     return checksum;
 662 }
 663
 664 unsigned int string_hash(const string_t*str)
 665 {
 666     int t;
 667     unsigned int checksum = 0;
 668     if(!crc32)
 669         crc32_init();
 670     for(t=0;t<str->len;t++) {
 671         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
 672     }
 673     return checksum;
 674 }
 675 unsigned int string_hash2(const char*str)
 676 {
 677     unsigned int checksum = 0;
 678     const char*p = str;
 679     if(!crc32)
 680         crc32_init();
 681     while(*p) {
 682         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
 683         p++;
 684     }
 685     return checksum;
 686 }
 687 unsigned int string_hash3(const char*str, int len)
 688 {
 689     string_t s;
 690     s.str = str;
 691     s.len = len;
 692     return string_hash(&s);
 693 }
 694 void string_dup2(string_t*str, const char*text, int len)
 695 {
 696     str->len = len;
 697     str->str = strdup_n(text, len);
 698 }
 699 void string_dup(string_t*str, const char*text)
 700 {
 701     str->len = strlen(text);
 702     str->str = strdup(text);
 703 }
 704 int string_equals(string_t*str, const char*text)
 705 {
 706     int l = strlen(text);
 707     if(str->len == l && !memcmp(str->str, text, l))
 708         return 1;
 709     return 0;
 710 }
 711 int string_equals2(string_t*str, string_t*str2)
 712 {
 713     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
 714         return 1;
 715     return 0;
 716 }
 717
 718 // ------------------------------- stringarray_t ------------------------------
 719
 720 typedef struct _stringlist {
 721     int index;
 722     struct _stringlist*next;
 723 } stringlist_t;
 724
 725 typedef struct _stringarray_internal_t
 726 {
 727     mem_t pos;
 728     stringlist_t**hash;
 729     int num;
 730     int hashsize;
 731 } stringarray_internal_t;
 732
 733 void stringarray_init(stringarray_t*sa, int hashsize)
 734 {
 735     stringarray_internal_t*s;
 736     int t;
 737     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
 738     s = (stringarray_internal_t*)sa->internal;
 739     mem_init(&s->pos);
 740     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
 741     s->hashsize = hashsize;
 742 }
 743 void stringarray_put(stringarray_t*sa, string_t str)
 744 {
 745     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 746     int pos;
 747     int hash = string_hash(&str) % s->hashsize;
 748
 749     char*ss = string_cstr(&str);
 750     mem_put(&s->pos, &ss, sizeof(char*));
 751
 752     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
 753     l->index = s->num;
 754     l->next = s->hash[hash];
 755     s->hash[hash] = l;
 756
 757     s->num++;
 758 }
 759 char* stringarray_at(stringarray_t*sa, int pos)
 760 {
 761     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 762     char*p;
 763     if(pos<0 || pos>=s->num)
 764         return 0;
 765     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
 766     if(p<0)
 767         return 0;
 768     return p;
 769 }
 770 string_t stringarray_at2(stringarray_t*sa, int pos)
 771 {
 772     string_t s;
 773     s.str = stringarray_at(sa, pos);
 774     s.len = s.str?strlen(s.str):0;
 775     return s;
 776 }
 777 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
 778 {
 779     stringlist_t*ll = l;
 780     stringlist_t*old = l;
 781     while(l) {
 782         if(index==l->index) {
 783             old->next = l->next;
 784             memset(l, 0, sizeof(stringlist_t));
 785             rfx_free(l);
 786             if(old==l)
 787                 return 0;
 788             else
 789                 return ll;
 790         }
 791         old = l;
 792         l = l->next;
 793     }
 794     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
 795     return ll;
 796 }
 797
 798 void stringarray_del(stringarray_t*sa, int pos)
 799 {
 800     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 801     string_t str = stringarray_at2(sa, pos);
 802     int hash = string_hash(&str) % s->hashsize;
 803     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
 804     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
 805 }
 806 int stringarray_find(stringarray_t*sa, string_t* str)
 807 {
 808     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 809     int hash = string_hash(str) % s->hashsize;
 810     int t;
 811     stringlist_t*l = s->hash[hash];
 812     //TODO: statistics
 813     while(l) {
 814         string_t s = stringarray_at2(sa, l->index);
 815         if(string_equals2(str, &s)) {
 816             return l->index;
 817         }
 818         l = l->next;
 819     }
 820     return -1;
 821 }
 822 void stringarray_clear(stringarray_t*sa)
 823 {
 824     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 825     mem_clear(&s->pos);
 826     int t;
 827     for(t=0;t<s->hashsize;t++) {
 828         stringlist_t*l = s->hash[t];
 829         while(l) {
 830             stringlist_t*next = l->next;
 831             memset(l, 0, sizeof(stringlist_t));
 832             rfx_free(l);
 833             l = next;
 834         }
 835     }
 836     rfx_free(s->hash);s->hash=0;
 837     rfx_free(s);
 838 }
 839 void stringarray_destroy(stringarray_t*sa)
 840 {
 841     stringarray_clear(sa);
 842     rfx_free(sa);
 843 }
 844
 845 // ------------------------------- type_t -------------------------------
 846
 847 char ptr_equals(const void*o1, const void*o2)
 848 {
 849     return o1==o2;
 850 }
 851 unsigned int ptr_hash(const void*o)
 852 {
 853     return string_hash3((const char*)&o, sizeof(o));
 854 }
 855 void* ptr_dup(const void*o)
 856 {
 857     return (void*)o;
 858 }
 859 void ptr_free(void*o)
 860 {
 861     return;
 862 }
 863
 864 char charptr_equals(const void*o1, const void*o2)
 865 {
 866     if(!o1 || !o2)
 867         return o1==o2;
 868     return !strcmp(o1,o2);
 869 }
 870 unsigned int charptr_hash(const void*o)
 871 {
 872     if(!o)
 873         return 0;
 874     return string_hash2(o);
 875 }
 876 void* charptr_dup(const void*o)
 877 {
 878     if(!o)
 879         return 0;
 880     return strdup(o);
 881 }
 882 void charptr_free(void*o)
 883 {
 884     if(o) {
 885         rfx_free(o);
 886     }
 887 }
 888
 889 char stringstruct_equals(const void*o1, const void*o2)
 890 {
 891     if(!o1 || !o2)
 892         return o1==o2;
 893     string_t*s1 = (string_t*)o1;
 894     string_t*s2 = (string_t*)o2;
 895     int l = s1->len<s2->len?s1->len:s2->len;
 896     int r = memcmp(s1->str, s2->str, l);
 897     if(r)
 898         return 0;
 899     else
 900         return s1->len==s2->len;
 901 }
 902 unsigned int stringstruct_hash(const void*o)
 903 {
 904     if(!o) return 0;
 905     return string_hash(o);
 906 }
 907 string_t*string_dup3(string_t*o)
 908 {
 909     if(!o) return 0;
 910     if(!o->str) {
 911         string_t*s = malloc(sizeof(string_t));
 912         s->str=0;
 913         s->len=0;
 914         return s;
 915     }
 916     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
 917     s->len = o->len;
 918     s->str = (const char*)(s+1);
 919     memcpy((char*)s->str, o->str, s->len);
 920     ((char*)s->str)[s->len]=0;
 921     return s;
 922 }
 923 void stringstruct_free(void*o)
 924 {
 925     if(o)
 926         string_free(o);
 927 }
 928
 929 type_t ptr_type = {
 930     equals: ptr_equals,
 931     hash: ptr_hash,
 932     dup: ptr_dup,
 933     free: ptr_free,
 934 };
 935
 936 type_t charptr_type = {
 937     equals: charptr_equals,
 938     hash: charptr_hash,
 939     dup: charptr_dup,
 940     free: charptr_free,
 941 };
 942
 943 type_t stringstruct_type = {
 944     equals: stringstruct_equals,
 945     hash: stringstruct_hash,
 946     dup: (dup_func)string_dup3,
 947     free: stringstruct_free,
 948 };
 949
 950 // ------------------------------- dictionary_t -------------------------------
 951
 952 #define INITIAL_SIZE 1
 953
 954 static int max(int x, int y) {
 955     return x>y?x:y;
 956 }
 957
 958 dict_t*dict_new()
 959 {
 960     dict_t*d = rfx_alloc(sizeof(dict_t));
 961     dict_init(d, INITIAL_SIZE);
 962     return d;
 963 }
 964 dict_t*dict_new2(type_t*t)
 965 {
 966     dict_t*d = rfx_alloc(sizeof(dict_t));
 967     dict_init(d, INITIAL_SIZE);
 968     d->key_type = t;
 969     return d;
 970 }
 971 void dict_init(dict_t*h, int size)
 972 {
 973     memset(h, 0, sizeof(dict_t));
 974     h->hashsize = size;
 975     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 976     h->num = 0;
 977     h->key_type = &charptr_type;
 978 }
 979 void dict_init2(dict_t*h, type_t*t, int size)
 980 {
 981     memset(h, 0, sizeof(dict_t));
 982     h->hashsize = size;
 983     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 984     h->num = 0;
 985     h->key_type = t;
 986 }
 987
 988 dict_t*dict_clone(dict_t*o)
 989 {
 990     dict_t*h = rfx_alloc(sizeof(dict_t));
 991     memcpy(h, o, sizeof(dict_t));
 992     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 993     int t;
 994     for(t=0;t<o->hashsize;t++) {
 995         dictentry_t*e = o->slots[t];
 996         while(e) {
 997             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 998             memcpy(n, e, sizeof(dictentry_t));
 999             n->key = h->key_type->dup(e->key);
1000             n->data = e->data;
1001             n->next = h->slots[t];
1002             h->slots[t] = n;
1003             e = e->next;
1004         }
1005     }
1006     return h;
1007 }
1008
1009 static void dict_expand(dict_t*h, int newlen)
1010 {
1011     assert(h->hashsize < newlen);
1012     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
1013     int t;
1014     for(t=0;t<h->hashsize;t++) {
1015         dictentry_t*e = h->slots[t];
1016         while(e) {
1017             dictentry_t*next = e->next;
1018             unsigned int newhash = e->hash%newlen;
1019             e->next = newslots[newhash];
1020             newslots[newhash] = e;
1021             e = next;
1022         }
1023     }
1024     if(h->slots)
1025         rfx_free(h->slots);
1026     h->slots = newslots;
1027     h->hashsize = newlen;
1028 }
1029
1030 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
1031 {
1032     unsigned int hash = h->key_type->hash(key);
1033     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
1034
1035     if(!h->hashsize)
1036         dict_expand(h, 1);
1037
1038     unsigned int hash2 = hash % h->hashsize;
1039
1040     e->key = h->key_type->dup(key);
1041     e->hash = hash; //for resizing
1042     e->next = h->slots[hash2];
1043     e->data = data;
1044     h->slots[hash2] = e;
1045     h->num++;
1046     return e;
1047 }
1048 void dict_put2(dict_t*h, const char*s, void*data)
1049 {
1050     assert(h->key_type == &charptr_type);
1051     dict_put(h, s, data);
1052 }
1053 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
1054 {
1055     int t;
1056     for(t=0;t<h->hashsize;t++) {
1057         dictentry_t*e = h->slots[t];
1058         while(e) {
1059             if(h->key_type!=&charptr_type) {
1060                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
1061             } else {
1062                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
1063             }
1064             e = e->next;
1065         }
1066     }
1067 }
1068
1069 int dict_count(dict_t*h)
1070 {
1071     return h->num;
1072 }
1073
1074 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
1075 {
1076     if(!h->num) {
1077         return 0;
1078     }
1079
1080     unsigned int ohash = h->key_type->hash(key);
1081     unsigned int hash = ohash % h->hashsize;
1082
1083     /* check first entry for match */
1084     dictentry_t*e = h->slots[hash];
1085     if(e && h->key_type->equals(e->key, key)) {
1086         return e;
1087     } else if(e) {
1088         e = e->next;
1089     }
1090
1091     /* if dict is 2/3 filled, double the size. Do
1092        this the first time we have to actually iterate
1093        through a slot to find our data */
1094     if(e && h->num*3 >= h->hashsize*2) {
1095         int newsize = h->hashsize;
1096         while(h->num*3 >= newsize*2) {
1097             newsize = newsize<15?15:(newsize+1)*2-1;
1098         }
1099         dict_expand(h, newsize);
1100         hash = ohash % h->hashsize;
1101         e = h->slots[hash];
1102         if(e && h->key_type->equals(e->key, key)) {
1103             // omit move to front
1104             return e;
1105         } else if(e) {
1106             e = e->next;
1107         }
1108     }
1109
1110     /* check subsequent entries for a match */
1111     dictentry_t*last = h->slots[hash];
1112     while(e) {
1113         if(h->key_type->equals(e->key, key)) {
1114             /* move to front- makes a difference of about 10% in most applications */
1115             last->next = e->next;
1116             e->next = h->slots[hash];
1117             h->slots[hash] = e;
1118             return e;
1119         }
1120         last=e;
1121         e = e->next;
1122     }
1123     return 0;
1124 }
1125 void* dict_lookup(dict_t*h, const void*key)
1126 {
1127     dictentry_t*e = dict_do_lookup(h, key);
1128     if(e)
1129         return e->data;
1130     return 0;
1131 }
1132 char dict_contains(dict_t*h, const void*key)
1133 {
1134     dictentry_t*e = dict_do_lookup(h, key);
1135     return !!e;
1136 }
1137
1138 char dict_del(dict_t*h, const void*key)
1139 {
1140     if(!h->num)
1141         return 0;
1142     unsigned int hash = h->key_type->hash(key) % h->hashsize;
1143     dictentry_t*head = h->slots[hash];
1144     dictentry_t*e = head, *prev=0;
1145     while(e) {
1146         if(h->key_type->equals(e->key, key)) {
1147             dictentry_t*next = e->next;
1148             h->key_type->free(e->key);
1149             memset(e, 0, sizeof(dictentry_t));
1150             rfx_free(e);
1151             if(e == head) {
1152                 h->slots[hash] = next;
1153             } else {
1154                 assert(prev);
1155                 prev->next = next;
1156             }
1157             h->num--;
1158             return 1;
1159         }
1160         prev = e;
1161         e = e->next;
1162     }
1163     return 0;
1164 }
1165
1166 dictentry_t* dict_get_slot(dict_t*h, const void*key)
1167 {
1168     if(!h->num)
1169         return 0;
1170     unsigned int ohash = h->key_type->hash(key);
1171     unsigned int hash = ohash % h->hashsize;
1172     return h->slots[hash];
1173 }
1174
1175 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
1176 {
1177     int t;
1178     for(t=0;t<h->hashsize;t++) {
1179         dictentry_t*e = h->slots[t];
1180         while(e) {
1181             dictentry_t*next = e->next;
1182             if(runFunction) {
1183                 runFunction(data, e->key, e->data);
1184             }
1185             e = e->next;
1186         }
1187     }
1188 }
1189 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
1190 {
1191     int t;
1192     for(t=0;t<h->hashsize;t++) {
1193         dictentry_t*e = h->slots[t];
1194         while(e) {
1195             dictentry_t*next = e->next;
1196             if(runFunction) {
1197                 runFunction(e->data);
1198             }
1199             e = e->next;
1200         }
1201     }
1202 }
1203
1204 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
1205 {
1206     int t;
1207     for(t=0;t<h->hashsize;t++) {
1208         dictentry_t*e = h->slots[t];
1209         while(e) {
1210             dictentry_t*next = e->next;
1211             if(free_keys) {
1212                 h->key_type->free(e->key);
1213             }
1214             if(free_data_function) {
1215                 free_data_function(e->data);
1216             }
1217             memset(e, 0, sizeof(dictentry_t));
1218             rfx_free(e);
1219             e = next;
1220         }
1221         h->slots[t]=0;
1222     }
1223     rfx_free(h->slots);
1224     memset(h, 0, sizeof(dict_t));
1225 }
1226
1227 void dict_clear_shallow(dict_t*h)
1228 {
1229     dict_free_all(h, 0, 0);
1230 }
1231
1232 void dict_clear(dict_t*h)
1233 {
1234     dict_free_all(h, 1, 0);
1235 }
1236
1237 void dict_destroy_shallow(dict_t*dict)
1238 {
1239     dict_clear_shallow(dict);
1240     rfx_free(dict);
1241 }
1242
1243 void dict_destroy(dict_t*dict)
1244 {
1245     if(!dict)
1246         return;
1247     dict_clear(dict);
1248     rfx_free(dict);
1249 }
1250
1251 // ------------------------------- map_t --------------------------------------
1252
1253 typedef struct _map_internal_t
1254 {
1255     dict_t d;
1256 } map_internal_t;
1257
1258 void map_init(map_t*map)
1259 {
1260     map_internal_t*m;
1261     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
1262     m = (map_internal_t*)map->internal;
1263     dict_init(&m->d, INITIAL_SIZE);
1264 }
1265 void map_put(map_t*map, string_t t1, string_t t2)
1266 {
1267     map_internal_t*m = (map_internal_t*)map->internal;
1268     string_t s;
1269     char* s1 = string_cstr(&t1);
1270     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1271     rfx_free(s1);
1272 }
1273 const char* map_lookup(map_t*map, const char*name)
1274 {
1275     map_internal_t*m = (map_internal_t*)map->internal;
1276     const char*value = dict_lookup(&m->d, name);
1277     return value;
1278 }
1279 static void freestring(void*data)
1280 {
1281     rfx_free(data);
1282 }
1283 static void dumpmapentry(void*data, const void*key, void*value)
1284 {
1285     FILE*fi = (FILE*)data;
1286     fprintf(fi, "%s=%s\n", key, (char*)value);
1287 }
1288 void map_dump(map_t*map, FILE*fi, const char*prefix)
1289 {
1290     int t;
1291     map_internal_t*m = (map_internal_t*)map->internal;
1292     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1293 }
1294 void map_clear(map_t*map)
1295 {
1296     map_internal_t*m = (map_internal_t*)map->internal;
1297     dict_free_all(&m->d, 1, freestring);
1298     rfx_free(m);
1299 }
1300 void map_destroy(map_t*map)
1301 {
1302     map_clear(map);
1303     rfx_free(map);
1304 }
1305
1306 // ------------------------------- array_t --------------------------------------
1307
1308 array_t* array_new() {
1309     array_t*d = malloc(sizeof(array_t));
1310     memset(d, 0, sizeof(array_t));
1311     d->entry2pos = dict_new();
1312     return d;
1313 }
1314 array_t* array_new2(type_t*type) {
1315     array_t*d = malloc(sizeof(array_t));
1316     memset(d, 0, sizeof(array_t));
1317     d->entry2pos = dict_new2(type);
1318     return d;
1319 }
1320 void*array_getkey(array_t*array, int nr) {
1321     if(nr > array->num || nr<0) {
1322         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1323         return 0;
1324     }
1325     return array->d[nr].name;
1326 }
1327 void*array_getvalue(array_t*array, int nr) {
1328     if(nr > array->num || nr<0) {
1329         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1330         return 0;
1331     }
1332     return array->d[nr].data;
1333 }
1334 int array_append(array_t*array, const void*name, void*data) {
1335     while(array->size <= array->num) {
1336         array->size += 64;
1337         if(!array->d) {
1338             array->d = malloc(sizeof(array_entry_t)*array->size);
1339         } else {
1340             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1341         }
1342     }
1343
1344     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1345
1346     if(name) {
1347         array->d[array->num].name = e->key;
1348     } else {
1349         array->d[array->num].name = 0;
1350     }
1351     array->d[array->num].data = (void*)data;
1352     return array->num++;
1353 }
1354 int array_find(array_t*array, const void*name)
1355 {
1356     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1357     return pos-1;
1358 }
1359 int array_find2(array_t*array, const void*name, void*data)
1360 {
1361     dict_t*h= array->entry2pos;
1362     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1363
1364     while(e) {
1365         int index = ((int)(ptroff_t)e->data) - 1;
1366         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1367             return index;
1368         }
1369         e = e->next;
1370     }
1371     return -1;
1372 }
1373 int array_update(array_t*array, const void*name, void*data) {
1374     int pos = array_find(array, name);
1375     if(pos>=0) {
1376         array->d[pos].data = data;
1377         return pos;
1378     }
1379     return array_append(array, name, data);
1380 }
1381 int array_append_if_new(array_t*array, const void*name, void*data) {
1382     int pos = array_find(array, name);
1383     if(pos>=0)
1384         return pos;
1385     return array_append(array, name, data);
1386 }
1387 void array_free(array_t*array) {
1388     dict_destroy(array->entry2pos);
1389     if(array->d) {
1390         free(array->d);array->d = 0;
1391     }
1392     free(array);
1393 }
1394
1395 // ------------------------------- list_t --------------------------------------
1396
1397 struct _commonlist;
1398 typedef struct _listinfo {
1399     int size;
1400     struct _commonlist*last;
1401 } listinfo_t;
1402
1403 typedef struct _commonlist {
1404     void*entry;
1405     struct _commonlist*next;
1406     listinfo_t info[0];
1407 } commonlist_t;
1408
1409 int list_length_(void*_list)
1410 {
1411     commonlist_t*l = (commonlist_t*)_list;
1412     if(!l)
1413         return 0;
1414     return l->info[0].size;
1415 }
1416 void list_concat_(void*_l1, void*_l2)
1417 {
1418     commonlist_t**l1 = (commonlist_t**)_l1;
1419     commonlist_t**l2 = (commonlist_t**)_l2;
1420
1421     if(!*l1) {
1422         *l1 = *l2;
1423     } else if(*l2) {
1424         (*l1)->info[0].last->next = *l2;
1425         (*l1)->info[0].last = (*l2)->info[0].last;
1426         (*l1)->info[0].size += (*l2)->info[0].size;
1427     }
1428     *l2 = 0;
1429 }
1430 void list_append_(void*_list, void*entry)
1431 {
1432     commonlist_t**list = (commonlist_t**)_list;
1433     commonlist_t* n = 0;
1434     if(!*list) {
1435         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1436         *list = n;
1437         (*list)->info[0].size = 0;
1438     } else {
1439         n = malloc(sizeof(commonlist_t));
1440         (*list)->info[0].last->next = n;
1441     }
1442     n->next = 0;
1443     n->entry = entry;
1444     (*list)->info[0].last = n;
1445     (*list)->info[0].size++;
1446 }
1447 /* notice: prepending uses slighly more space than appending */
1448 void list_prepend_(void*_list, void*entry)
1449 {
1450     commonlist_t**list = (commonlist_t**)_list;
1451     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1452     int size = 0;
1453     commonlist_t* last = 0;
1454     if(*list) {
1455         last = (*list)->info[0].last;
1456         size = (*list)->info[0].size;
1457     }
1458     n->next = *list;
1459     n->entry = entry;
1460     *list = n;
1461     (*list)->info[0].last = last;
1462     (*list)->info[0].size = size+1;
1463 }
1464 void list_free_(void*_list)
1465 {
1466     commonlist_t**list = (commonlist_t**)_list;
1467     commonlist_t*l = *list;
1468     while(l) {
1469         commonlist_t*next = l->next;
1470         free(l);
1471         l = next;
1472     }
1473     *list = 0;
1474 }
1475 void list_deep_free_(void*_list)
1476 {
1477     commonlist_t**list = (commonlist_t**)_list;
1478     commonlist_t*l = *list;
1479     while(l) {
1480         commonlist_t*next = l->next;
1481         if(l->entry) {
1482             free(l->entry);l->entry=0;
1483         }
1484         free(l);
1485         l = next;
1486     }
1487     *list = 0;
1488 }
1489 void*list_clone_(void*_list)
1490 {
1491     commonlist_t*l = *(commonlist_t**)_list;
1492
1493     void*dest = 0;
1494     while(l) {
1495         commonlist_t*next = l->next;
1496         list_append_(&dest, l->entry);
1497         l = next;
1498     }
1499     return dest;
1500
1501 }
1502