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