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