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