lib/q.c

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