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         m->len = (m->pos+63)&~63;
  72         m->buffer = m->buffer?(char*)rfx_realloc(m->buffer,m->len):(char*)rfx_alloc(m->len);
  73     }
  74     assert(n+length <= m->len);
  75     memcpy(&m->buffer[n], data, length);
  76     if(null)
  77         m->buffer[n + length] = 0;
  78     return n;
  79 }
  80 int mem_put(mem_t*m,void*data, int length)
  81 {
  82     return mem_put_(m, data, length, 0);
  83 }
  84 int mem_putstring(mem_t*m,string_t str)
  85 {
  86     return mem_put_(m, str.str, str.len, 1);
  87 }
  88
  89 // ------------------------------- ringbuffer_t -------------------------------
  90
  91 typedef struct _ringbuffer_internal_t
  92 {
  93     unsigned char*buffer;
  94     int readpos;
  95     int writepos;
  96     int buffersize;
  97 } ringbuffer_internal_t;
  98
  99 void ringbuffer_init(ringbuffer_t*r)
 100 {
 101     ringbuffer_internal_t*i = (ringbuffer_internal_t*)rfx_calloc(sizeof(ringbuffer_internal_t));
 102     memset(r, 0, sizeof(ringbuffer_t));
 103     r->internal = i;
 104     i->buffer = (unsigned char*)rfx_alloc(1024);
 105     i->buffersize = 1024;
 106 }
 107 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
 108 {
 109     unsigned char* data = (unsigned char*)buf;
 110     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 111     if(r->available < len)
 112         len = r->available;
 113     if(!len)
 114         return 0;
 115     if(i->readpos + len > i->buffersize) {
 116         int read1 = i->buffersize-i->readpos;
 117         memcpy(data, &i->buffer[i->readpos], read1);
 118         memcpy(&data[read1], &i->buffer[0], len - read1);
 119         i->readpos = len - read1;
 120     } else {
 121         memcpy(data, &i->buffer[i->readpos], len);
 122         i->readpos += len;
 123         i->readpos %= i->buffersize;
 124     }
 125     r->available -= len;
 126     return len;
 127 }
 128 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
 129 {
 130     unsigned char* data = (unsigned char*)buf;
 131     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 132
 133     if(i->buffersize - r->available < len)
 134     {
 135         unsigned char* buf2;
 136         int newbuffersize = i->buffersize;
 137         int oldavailable = r->available;
 138         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
 139
 140         if(newbuffersize < r->available + len)
 141             newbuffersize = r->available + len + 1024;
 142
 143         buf2 = (unsigned char*)rfx_alloc(newbuffersize);
 144         ringbuffer_read(r, buf2, r->available);
 145         rfx_free(i->buffer);
 146         i->buffer = buf2;
 147         i->buffersize = newbuffersize;
 148         i->readpos = 0;
 149         i->writepos = oldavailable;
 150         r->available = oldavailable;
 151     }
 152     if(i->writepos + len > i->buffersize) {
 153         int read1 = i->buffersize-i->writepos;
 154         memcpy(&i->buffer[i->writepos], data, read1);
 155         memcpy(&i->buffer[0], &data[read1], len - read1);
 156         i->writepos = len - read1;
 157     } else {
 158         memcpy(&i->buffer[i->writepos], data, len);
 159         i->writepos += len;
 160         i->writepos %= i->buffersize;
 161     }
 162     r->available += len;
 163 }
 164 void ringbuffer_clear(ringbuffer_t*r)
 165 {
 166     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 167     rfx_free(i->buffer);i->buffer = 0;
 168     rfx_free(i);
 169 }
 170
 171 // ------------------------------- heap_t -------------------------------
 172
 173 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
 174 {
 175     memset(h, 0, sizeof(heap_t));
 176     h->max_size = n;
 177     h->size = 0;
 178     h->elem_size = elem_size;
 179     h->compare = compare;
 180     h->elements = (void**)rfx_calloc(n*sizeof(void*));
 181     h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
 182 }
 183 void heap_clear(heap_t*h)
 184 {
 185     rfx_free(h->elements);
 186     rfx_free(h->data);
 187 }
 188
 189 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
 190
 191 static void up(heap_t*h, int node)
 192 {
 193     void*node_p = h->elements[node];
 194     int parent = node;
 195     do {
 196         node = parent;
 197         if(!node) break;
 198         parent = (node-1)/2;
 199         h->elements[node] = h->elements[parent];
 200     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
 201
 202     h->elements[node] = node_p;
 203 }
 204 static void down(heap_t*h, int node)
 205 {
 206     void*node_p = h->elements[node];
 207     int child = node;
 208     do {
 209         node = child;
 210
 211         /* determine new child's position */
 212         child = node<<1|1;
 213         if(child >= h->size)
 214             break;
 215         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
 216             child++;
 217
 218         h->elements[node] = h->elements[child];
 219     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
 220
 221     h->elements[node] = node_p;
 222 }
 223 void heap_put(heap_t*h, void*e)
 224 {
 225     int pos = h->size++;
 226     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
 227     h->elements[pos] = &h->data[pos];
 228     up(h, pos);
 229 }
 230 int heap_size(heap_t*h)
 231 {
 232     return h->size;
 233 }
 234 void* heap_max(heap_t*h)
 235 {
 236     return h->elements[0];
 237 }
 238 void* heap_chopmax(heap_t*h)
 239 {
 240     void*p = h->elements[0];
 241     h->elements[0] = h->elements[--h->size];
 242     down(h,0);
 243     return p;
 244 }
 245 void heap_dump(heap_t*h, FILE*fi)
 246 {
 247     int t;
 248     for(t=0;t<h->size;t++) {
 249         int s;
 250         for(s=0;s<=t;s=(s+1)*2-1) {
 251             if(s==t) fprintf(fi,"\n");
 252         }
 253         //fprintf(fi,"%d ", h->elements[t]->x); //?
 254     }
 255 }
 256 void** heap_flatten(heap_t*h)
 257 {
 258     void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
 259     void**p = nodes;
 260
 261     while(h->size) {
 262         /*printf("Heap Size: %d\n", h->size);
 263         heap_print(stdout, h);
 264         printf("\n");*/
 265         *p++ = heap_chopmax(h);
 266     }
 267     return nodes;
 268 }
 269
 270 // ------------------------------- crc32 --------------------------------------
 271 static unsigned int*crc32 = 0;
 272 static void crc32_init(void)
 273 {
 274     int t;
 275     if(crc32)
 276         return;
 277     crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
 278     for(t=0; t<256; t++) {
 279         unsigned int c = t;
 280         int s;
 281         for (s = 0; s < 8; s++) {
 282           c = (0xedb88320L*(c&1)) ^ (c >> 1);
 283         }
 284         crc32[t] = c;
 285     }
 286 }
 287 // ------------------------------- string_t -----------------------------------
 288
 289 void string_set2(string_t*str, const char*text, int len)
 290 {
 291     str->len = len;
 292     str->str = text;
 293 }
 294 void string_set(string_t*str, const char*text)
 295 {
 296     if(text) {
 297         str->len = strlen(text);
 298     } else {
 299         str->len = 0;
 300     }
 301     str->str = text;
 302 }
 303 string_t string_new(const char*text, int len)
 304 {
 305     string_t s;
 306     s.len = len;
 307     s.str = text;
 308     return s;
 309 }
 310 string_t string_new2(const char*text)
 311 {
 312     string_t s;
 313     if(text) {
 314         s.len = strlen(text);
 315     } else {
 316         s.len = 0;
 317     }
 318     s.str = text;
 319     return s;
 320 }
 321 string_t* string_new3(const char*text, int len)
 322 {
 323     if(!text) {
 324         string_t*s = malloc(sizeof(string_t));
 325         s->len = 0;
 326         s->str = 0;
 327         return s;
 328     } else {
 329         string_t*s = malloc(sizeof(string_t)+len+1);
 330         s->len = len;
 331         s->str = (const char*)(s+1);
 332         memcpy((char*)s->str, text, len);
 333         ((char*)s->str)[len]=0;
 334         return s;
 335     }
 336 }
 337 string_t* string_new4(const char*text)
 338 {
 339     int l = strlen(text);
 340     return string_new3(text, l);
 341 }
 342
 343 void string_free(string_t*s)
 344 {
 345     if(!s)
 346         return;
 347     s->len = 0;
 348     if((string_t*)(s->str) == s+1) {
 349         s->str = 0;
 350         rfx_free(s);
 351     } else {
 352         rfx_free((char*)(s->str));
 353         s->str = 0;
 354         rfx_free(s);
 355     }
 356 }
 357 char* string_cstr(string_t*str)
 358 {
 359     return strdup_n(str->str, str->len);
 360 }
 361 char* string_escape(string_t*str)
 362 {
 363     int t;
 364     int len = 0;
 365     for(t=0;t<str->len;t++) {
 366         if(str->str[t]<0x20)
 367             len+=3;
 368         else
 369             len++;
 370     }
 371     char*s = malloc(len+1);
 372     char*p=s;
 373     for(t=0;t<str->len;t++) {
 374         if(str->str[t]<0x20) {
 375             *p++ ='\\';
 376             unsigned char c = str->str[t];
 377             *p++ = "0123456789abcdef"[c>>4];
 378             *p++ = "0123456789abcdef"[c&0x0f];
 379         } else {
 380             *p++ = str->str[t];
 381         }
 382     }
 383     *p++ = 0;
 384     assert(p == &s[len+1]);
 385     return s;
 386 }
 387
 388 unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
 389 {
 390     if(!crc32)
 391         crc32_init();
 392     return checksum>>8 ^ crc32[(b^checksum)&0xff];
 393 }
 394 unsigned int crc32_add_string(unsigned int checksum, const char*s)
 395 {
 396     if(!crc32)
 397         crc32_init();
 398     if(!s)
 399         return checksum;
 400     while(*s) {
 401         checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
 402         s++;
 403     }
 404     return checksum;
 405 }
 406
 407 unsigned int string_hash(const string_t*str)
 408 {
 409     int t;
 410     unsigned int checksum = 0;
 411     if(!crc32)
 412         crc32_init();
 413     for(t=0;t<str->len;t++) {
 414         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
 415     }
 416     return checksum;
 417 }
 418 unsigned int string_hash2(const char*str)
 419 {
 420     unsigned int checksum = 0;
 421     const char*p = str;
 422     if(!crc32)
 423         crc32_init();
 424     while(*p) {
 425         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
 426         p++;
 427     }
 428     return checksum;
 429 }
 430 unsigned int string_hash3(const char*str, int len)
 431 {
 432     string_t s;
 433     s.str = str;
 434     s.len = len;
 435     return string_hash(&s);
 436 }
 437 void string_dup2(string_t*str, const char*text, int len)
 438 {
 439     str->len = len;
 440     str->str = strdup_n(text, len);
 441 }
 442 void string_dup(string_t*str, const char*text)
 443 {
 444     str->len = strlen(text);
 445     str->str = strdup(text);
 446 }
 447 int string_equals(string_t*str, const char*text)
 448 {
 449     int l = strlen(text);
 450     if(str->len == l && !memcmp(str->str, text, l))
 451         return 1;
 452     return 0;
 453 }
 454 int string_equals2(string_t*str, string_t*str2)
 455 {
 456     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
 457         return 1;
 458     return 0;
 459 }
 460
 461 // ------------------------------- stringarray_t ------------------------------
 462
 463 typedef struct _stringlist {
 464     int index;
 465     struct _stringlist*next;
 466 } stringlist_t;
 467
 468 typedef struct _stringarray_internal_t
 469 {
 470     mem_t pos;
 471     stringlist_t**hash;
 472     int num;
 473     int hashsize;
 474 } stringarray_internal_t;
 475
 476 void stringarray_init(stringarray_t*sa, int hashsize)
 477 {
 478     stringarray_internal_t*s;
 479     int t;
 480     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
 481     s = (stringarray_internal_t*)sa->internal;
 482     mem_init(&s->pos);
 483     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
 484     s->hashsize = hashsize;
 485 }
 486 void stringarray_put(stringarray_t*sa, string_t str)
 487 {
 488     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 489     int pos;
 490     int hash = string_hash(&str) % s->hashsize;
 491
 492     char*ss = string_cstr(&str);
 493     mem_put(&s->pos, &ss, sizeof(char*));
 494
 495     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
 496     l->index = s->num;
 497     l->next = s->hash[hash];
 498     s->hash[hash] = l;
 499
 500     s->num++;
 501 }
 502 char* stringarray_at(stringarray_t*sa, int pos)
 503 {
 504     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 505     char*p;
 506     if(pos<0 || pos>=s->num)
 507         return 0;
 508     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
 509     if(p<0)
 510         return 0;
 511     return p;
 512 }
 513 string_t stringarray_at2(stringarray_t*sa, int pos)
 514 {
 515     string_t s;
 516     s.str = stringarray_at(sa, pos);
 517     s.len = s.str?strlen(s.str):0;
 518     return s;
 519 }
 520 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
 521 {
 522     stringlist_t*ll = l;
 523     stringlist_t*old = l;
 524     while(l) {
 525         if(index==l->index) {
 526             old->next = l->next;
 527             memset(l, 0, sizeof(stringlist_t));
 528             rfx_free(l);
 529             if(old==l)
 530                 return 0;
 531             else
 532                 return ll;
 533         }
 534         old = l;
 535         l = l->next;
 536     }
 537     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
 538     return ll;
 539 }
 540
 541 void stringarray_del(stringarray_t*sa, int pos)
 542 {
 543     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 544     string_t str = stringarray_at2(sa, pos);
 545     int hash = string_hash(&str) % s->hashsize;
 546     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
 547     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
 548 }
 549 int stringarray_find(stringarray_t*sa, string_t* str)
 550 {
 551     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 552     int hash = string_hash(str) % s->hashsize;
 553     int t;
 554     stringlist_t*l = s->hash[hash];
 555     //TODO: statistics
 556     while(l) {
 557         string_t s = stringarray_at2(sa, l->index);
 558         if(string_equals2(str, &s)) {
 559             return l->index;
 560         }
 561         l = l->next;
 562     }
 563     return -1;
 564 }
 565 void stringarray_clear(stringarray_t*sa)
 566 {
 567     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 568     mem_clear(&s->pos);
 569     int t;
 570     for(t=0;t<s->hashsize;t++) {
 571         stringlist_t*l = s->hash[t];
 572         while(l) {
 573             stringlist_t*next = l->next;
 574             memset(l, 0, sizeof(stringlist_t));
 575             rfx_free(l);
 576             l = next;
 577         }
 578     }
 579     rfx_free(s->hash);s->hash=0;
 580     rfx_free(s);
 581 }
 582 void stringarray_destroy(stringarray_t*sa)
 583 {
 584     stringarray_clear(sa);
 585     rfx_free(sa);
 586 }
 587
 588 // ------------------------------- type_t -------------------------------
 589
 590 char ptr_equals(const void*o1, const void*o2)
 591 {
 592     return o1==o2;
 593 }
 594 unsigned int ptr_hash(const void*o)
 595 {
 596     return string_hash3(o, sizeof(o));
 597 }
 598 void* ptr_dup(const void*o)
 599 {
 600     return (void*)o;
 601 }
 602 void ptr_free(void*o)
 603 {
 604     return;
 605 }
 606
 607 char charptr_equals(const void*o1, const void*o2)
 608 {
 609     if(!o1 || !o2)
 610         return o1==o2;
 611     return !strcmp(o1,o2);
 612 }
 613 unsigned int charptr_hash(const void*o)
 614 {
 615     if(!o)
 616         return 0;
 617     return string_hash2(o);
 618 }
 619 void* charptr_dup(const void*o)
 620 {
 621     if(!o)
 622         return 0;
 623     return strdup(o);
 624 }
 625 void charptr_free(void*o)
 626 {
 627     if(o) {
 628         rfx_free(o);
 629     }
 630 }
 631
 632 char stringstruct_equals(const void*o1, const void*o2)
 633 {
 634     if(!o1 || !o2)
 635         return o1==o2;
 636     string_t*s1 = (string_t*)o1;
 637     string_t*s2 = (string_t*)o2;
 638     int l = s1->len<s2->len?s1->len:s2->len;
 639     int r = memcmp(s1->str, s2->str, l);
 640     if(r)
 641         return 0;
 642     else
 643         return s1->len==s2->len;
 644 }
 645 unsigned int stringstruct_hash(const void*o)
 646 {
 647     if(!o) return 0;
 648     return string_hash(o);
 649 }
 650 string_t*string_dup3(string_t*o)
 651 {
 652     if(!o) return 0;
 653     if(!o->str) {
 654         string_t*s = malloc(sizeof(string_t));
 655         s->str=0;
 656         s->len=0;
 657         return s;
 658     }
 659     string_t*s = rfx_alloc(sizeof(string_t)+o->len+1);
 660     s->len = o->len;
 661     s->str = (const char*)(s+1);
 662     memcpy((char*)s->str, o->str, s->len);
 663     ((char*)s->str)[s->len]=0;
 664     return s;
 665 }
 666 void stringstruct_free(void*o)
 667 {
 668     if(o)
 669         string_free(o);
 670 }
 671
 672 type_t ptr_type = {
 673     equals: ptr_equals,
 674     hash: ptr_hash,
 675     dup: ptr_dup,
 676     free: ptr_free,
 677 };
 678
 679 type_t charptr_type = {
 680     equals: charptr_equals,
 681     hash: charptr_hash,
 682     dup: charptr_dup,
 683     free: charptr_free,
 684 };
 685
 686 type_t stringstruct_type = {
 687     equals: stringstruct_equals,
 688     hash: stringstruct_hash,
 689     dup: (dup_func)string_dup3,
 690     free: stringstruct_free,
 691 };
 692
 693 // ------------------------------- dictionary_t -------------------------------
 694
 695 #define INITIAL_SIZE 1
 696
 697 static int max(int x, int y) {
 698     return x>y?x:y;
 699 }
 700
 701 dict_t*dict_new()
 702 {
 703     dict_t*d = rfx_alloc(sizeof(dict_t));
 704     dict_init(d, INITIAL_SIZE);
 705     return d;
 706 }
 707 dict_t*dict_new2(type_t*t)
 708 {
 709     dict_t*d = rfx_alloc(sizeof(dict_t));
 710     dict_init(d, INITIAL_SIZE);
 711     d->key_type = t;
 712     return d;
 713 }
 714 void dict_init(dict_t*h, int size)
 715 {
 716     memset(h, 0, sizeof(dict_t));
 717     h->hashsize = size;
 718     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 719     h->num = 0;
 720     h->key_type = &charptr_type;
 721 }
 722
 723 dict_t*dict_clone(dict_t*o)
 724 {
 725     dict_t*h = rfx_alloc(sizeof(dict_t));
 726     memcpy(h, o, sizeof(dict_t));
 727     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 728     int t;
 729     for(t=0;t<o->hashsize;t++) {
 730         dictentry_t*e = o->slots[t];
 731         while(e) {
 732             dictentry_t*n = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 733             memcpy(n, e, sizeof(dictentry_t));
 734             n->key = h->key_type->dup(e->key);
 735             n->data = e->data;
 736             n->next = h->slots[t];
 737             h->slots[t] = n;
 738             e = e->next;
 739         }
 740     }
 741     return h;
 742 }
 743
 744 static void dict_expand(dict_t*h, int newlen)
 745 {
 746     assert(h->hashsize < newlen);
 747     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
 748     int t;
 749     for(t=0;t<h->hashsize;t++) {
 750         dictentry_t*e = h->slots[t];
 751         while(e) {
 752             dictentry_t*next = e->next;
 753             unsigned int newhash = e->hash%newlen;
 754             e->next = newslots[newhash];
 755             newslots[newhash] = e;
 756             e = next;
 757         }
 758     }
 759     if(h->slots)
 760         rfx_free(h->slots);
 761     h->slots = newslots;
 762     h->hashsize = newlen;
 763 }
 764
 765 dictentry_t* dict_put(dict_t*h, const void*key, void* data)
 766 {
 767     unsigned int hash = h->key_type->hash(key);
 768     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 769     unsigned int hash2 = hash % h->hashsize;
 770
 771     e->key = h->key_type->dup(key);
 772     e->hash = hash; //for resizing
 773     e->next = h->slots[hash2];
 774     e->data = data;
 775     h->slots[hash2] = e;
 776     h->num++;
 777     return e;
 778 }
 779 void dict_put2(dict_t*h, const char*s, void*data)
 780 {
 781     assert(h->key_type == &charptr_type);
 782     dict_put(h, s, data);
 783 }
 784 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
 785 {
 786     int t;
 787     for(t=0;t<h->hashsize;t++) {
 788         dictentry_t*e = h->slots[t];
 789         while(e) {
 790             if(h->key_type!=&charptr_type) {
 791                 fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
 792             } else {
 793                 fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
 794             }
 795             e = e->next;
 796         }
 797     }
 798 }
 799
 800 int dict_count(dict_t*h)
 801 {
 802     return h->num;
 803 }
 804
 805 static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
 806 {
 807     if(!h->num) {
 808         return 0;
 809     }
 810
 811     unsigned int ohash = h->key_type->hash(key);
 812     unsigned int hash = ohash % h->hashsize;
 813
 814     /* check first entry for match */
 815     dictentry_t*e = h->slots[hash];
 816     if(e && h->key_type->equals(e->key, key)) {
 817         return e;
 818     } else if(e) {
 819         e = e->next;
 820     }
 821
 822     /* if dict is 2/3 filled, double the size. Do
 823        this the first time we have to actually iterate
 824        through a slot to find our data */
 825     if(e && h->num*3 >= h->hashsize*2) {
 826         int newsize = h->hashsize;
 827         while(h->num*3 >= newsize*2) {
 828             newsize = newsize<15?15:(newsize+1)*2-1;
 829         }
 830         dict_expand(h, newsize);
 831         hash = ohash % h->hashsize;
 832         e = h->slots[hash];
 833         if(e && h->key_type->equals(e->key, key)) {
 834             // omit move to front
 835             return e;
 836         } else if(e) {
 837             e = e->next;
 838         }
 839     }
 840
 841     /* check subsequent entries for a match */
 842     dictentry_t*last = h->slots[hash];
 843     while(e) {
 844         if(h->key_type->equals(e->key, key)) {
 845             /* move to front- makes a difference of about 10% in most applications */
 846             last->next = e->next;
 847             e->next = h->slots[hash];
 848             h->slots[hash] = e;
 849             return e;
 850         }
 851         last=e;
 852         e = e->next;
 853     }
 854     return 0;
 855 }
 856 void* dict_lookup(dict_t*h, const void*key)
 857 {
 858     dictentry_t*e = dict_do_lookup(h, key);
 859     if(e)
 860         return e->data;
 861     return 0;
 862 }
 863 char dict_contains(dict_t*h, const void*key)
 864 {
 865     dictentry_t*e = dict_do_lookup(h, key);
 866     return !!e;
 867 }
 868
 869 char dict_del(dict_t*h, const void*key)
 870 {
 871     if(!h->num)
 872         return 0;
 873     unsigned int hash = h->key_type->hash(key) % h->hashsize;
 874     dictentry_t*head = h->slots[hash];
 875     dictentry_t*e = head, *prev=0;
 876     while(e) {
 877         if(h->key_type->equals(e->key, key)) {
 878             dictentry_t*next = e->next;
 879             rfx_free((void*)e->key);
 880             memset(e, 0, sizeof(dictentry_t));
 881             rfx_free(e);
 882             if(e == head) {
 883                 h->slots[hash] = 0;
 884             } else {
 885                 assert(prev);
 886                 prev->next = next;
 887             }
 888             h->num--;
 889             return 1;
 890         }
 891         prev = e;
 892         e = e->next;
 893     }
 894     return 0;
 895 }
 896
 897 dictentry_t* dict_get_slot(dict_t*h, const void*key)
 898 {
 899     if(!h->num)
 900         return 0;
 901     unsigned int ohash = h->key_type->hash(key);
 902     unsigned int hash = ohash % h->hashsize;
 903     return h->slots[hash];
 904 }
 905
 906 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*key, void*val), void*data)
 907 {
 908     int t;
 909     for(t=0;t<h->hashsize;t++) {
 910         dictentry_t*e = h->slots[t];
 911         while(e) {
 912             dictentry_t*next = e->next;
 913             if(runFunction) {
 914                 runFunction(data, e->key, e->data);
 915             }
 916             e = e->next;
 917         }
 918     }
 919 }
 920 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
 921 {
 922     int t;
 923     for(t=0;t<h->hashsize;t++) {
 924         dictentry_t*e = h->slots[t];
 925         while(e) {
 926             dictentry_t*next = e->next;
 927             if(runFunction) {
 928                 runFunction(e->data);
 929             }
 930             e = e->next;
 931         }
 932     }
 933 }
 934
 935 void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*))
 936 {
 937     int t;
 938     for(t=0;t<h->hashsize;t++) {
 939         dictentry_t*e = h->slots[t];
 940         while(e) {
 941             dictentry_t*next = e->next;
 942             if(free_keys) {
 943                 h->key_type->free(e->key);
 944             }
 945             if(free_data_function) {
 946                 free_data_function(e->data);
 947             }
 948             memset(e, 0, sizeof(dictentry_t));
 949             rfx_free(e);
 950             e = next;
 951         }
 952         h->slots[t]=0;
 953     }
 954     rfx_free(h->slots);
 955     memset(h, 0, sizeof(dict_t));
 956 }
 957
 958 void dict_clear_shallow(dict_t*h)
 959 {
 960     dict_free_all(h, 0, 0);
 961 }
 962
 963 void dict_clear(dict_t*h)
 964 {
 965     dict_free_all(h, 1, 0);
 966 }
 967
 968 void dict_destroy_shallow(dict_t*dict)
 969 {
 970     dict_clear_shallow(dict);
 971     rfx_free(dict);
 972 }
 973
 974 void dict_destroy(dict_t*dict)
 975 {
 976     dict_clear(dict);
 977     rfx_free(dict);
 978 }
 979
 980 // ------------------------------- map_t --------------------------------------
 981
 982 typedef struct _map_internal_t
 983 {
 984     dict_t d;
 985 } map_internal_t;
 986
 987 void map_init(map_t*map)
 988 {
 989     map_internal_t*m;
 990     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
 991     m = (map_internal_t*)map->internal;
 992     dict_init(&m->d, INITIAL_SIZE);
 993 }
 994 void map_put(map_t*map, string_t t1, string_t t2)
 995 {
 996     map_internal_t*m = (map_internal_t*)map->internal;
 997     string_t s;
 998     char* s1 = string_cstr(&t1);
 999     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
1000     rfx_free(s1);
1001 }
1002 const char* map_lookup(map_t*map, const char*name)
1003 {
1004     map_internal_t*m = (map_internal_t*)map->internal;
1005     const char*value = dict_lookup(&m->d, name);
1006     return value;
1007 }
1008 static void freestring(void*data)
1009 {
1010     rfx_free(data);
1011 }
1012 static void dumpmapentry(void*data, const void*key, void*value)
1013 {
1014     FILE*fi = (FILE*)data;
1015     fprintf(fi, "%s=%s\n", key, (char*)value);
1016 }
1017 void map_dump(map_t*map, FILE*fi, const char*prefix)
1018 {
1019     int t;
1020     map_internal_t*m = (map_internal_t*)map->internal;
1021     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
1022 }
1023 void map_clear(map_t*map)
1024 {
1025     map_internal_t*m = (map_internal_t*)map->internal;
1026     dict_free_all(&m->d, 1, freestring);
1027     rfx_free(m);
1028 }
1029 void map_destroy(map_t*map)
1030 {
1031     map_clear(map);
1032     rfx_free(map);
1033 }
1034
1035 // ------------------------------- array_t --------------------------------------
1036
1037 array_t* array_new() {
1038     array_t*d = malloc(sizeof(array_t));
1039     memset(d, 0, sizeof(array_t));
1040     d->entry2pos = dict_new();
1041     return d;
1042 }
1043 array_t* array_new2(type_t*type) {
1044     array_t*d = malloc(sizeof(array_t));
1045     memset(d, 0, sizeof(array_t));
1046     d->entry2pos = dict_new2(type);
1047     return d;
1048 }
1049 void*array_getkey(array_t*array, int nr) {
1050     if(nr > array->num || nr<0) {
1051         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1052         *(int*)0 = 0xdead;
1053         return 0;
1054     }
1055     return array->d[nr].name;
1056 }
1057 void*array_getvalue(array_t*array, int nr) {
1058     if(nr > array->num || nr<0) {
1059         printf("error: reference to element %d in array[%d]\n", nr, array->num);
1060         *(int*)0 = 0xdead;
1061         return 0;
1062     }
1063     return array->d[nr].data;
1064 }
1065 int array_append(array_t*array, const void*name, void*data) {
1066     while(array->size <= array->num) {
1067         array->size += 64;
1068         if(!array->d) {
1069             array->d = malloc(sizeof(array_entry_t)*array->size);
1070         } else {
1071             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
1072         }
1073     }
1074
1075     dictentry_t*e = dict_put(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
1076
1077     if(name) {
1078         array->d[array->num].name = e->key;
1079     } else {
1080         array->d[array->num].name = 0;
1081     }
1082     array->d[array->num].data = (void*)data;
1083     return array->num++;
1084 }
1085 int array_find(array_t*array, const void*name)
1086 {
1087     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
1088     return pos-1;
1089 }
1090 int array_find2(array_t*array, const void*name, void*data)
1091 {
1092     dict_t*h= array->entry2pos;
1093     dictentry_t*e = dict_get_slot(array->entry2pos, name);
1094
1095     while(e) {
1096         int index = ((int)(ptroff_t)e->data) - 1;
1097         if(h->key_type->equals(e->key, name) && array->d[index].data == data) {
1098             return index;
1099         }
1100         e = e->next;
1101     }
1102     return -1;
1103 }
1104 int array_update(array_t*array, const void*name, void*data) {
1105     int pos = array_find(array, name);
1106     if(pos>=0) {
1107         array->d[pos].data = data;
1108         return pos;
1109     }
1110     return array_append(array, name, data);
1111 }
1112 int array_append_if_new(array_t*array, const void*name, void*data) {
1113     int pos = array_find(array, name);
1114     if(pos>=0)
1115         return pos;
1116     return array_append(array, name, data);
1117 }
1118 void array_free(array_t*array) {
1119     dict_destroy(array->entry2pos);
1120     if(array->d) {
1121         free(array->d);array->d = 0;
1122     }
1123     free(array);
1124 }
1125
1126 // ------------------------------- list_t --------------------------------------
1127
1128 struct _commonlist;
1129 typedef struct _listinfo {
1130     int size;
1131     struct _commonlist*last;
1132 } listinfo_t;
1133
1134 typedef struct _commonlist {
1135     void*entry;
1136     struct _commonlist*next;
1137     listinfo_t info[0];
1138 } commonlist_t;
1139
1140 int list_length_(void*_list)
1141 {
1142     commonlist_t*l = (commonlist_t*)_list;
1143     if(!l)
1144         return 0;
1145     return l->info[0].size;
1146 }
1147 void list_concat_(void*_l1, void*_l2)
1148 {
1149     commonlist_t**l1 = (commonlist_t**)_l1;
1150     commonlist_t**l2 = (commonlist_t**)_l2;
1151
1152     if(!*l1) {
1153         *l1 = *l2;
1154     } else if(*l2) {
1155         (*l1)->info[0].last->next = *l2;
1156         (*l1)->info[0].last = (*l2)->info[0].last;
1157         (*l1)->info[0].size += (*l2)->info[0].size;
1158     }
1159     *l2 = 0;
1160 }
1161 void list_append_(void*_list, void*entry)
1162 {
1163     commonlist_t**list = (commonlist_t**)_list;
1164     commonlist_t* n = 0;
1165     if(!*list) {
1166         n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1167         *list = n;
1168         (*list)->info[0].size = 0;
1169     } else {
1170         n = malloc(sizeof(commonlist_t));
1171         (*list)->info[0].last->next = n;
1172     }
1173     n->next = 0;
1174     n->entry = entry;
1175     (*list)->info[0].last = n;
1176     (*list)->info[0].size++;
1177 }
1178 /* notice: prepending uses slighly more space than appending */
1179 void list_prepend_(void*_list, void*entry)
1180 {
1181     commonlist_t**list = (commonlist_t**)_list;
1182     commonlist_t* n = (commonlist_t*)malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
1183     int size = 0;
1184     commonlist_t* last = 0;
1185     if(*list) {
1186         last = (*list)->info[0].last;
1187         size = (*list)->info[0].size;
1188     }
1189     n->next = *list;
1190     n->entry = entry;
1191     *list = n;
1192     (*list)->info[0].last = last;
1193     (*list)->info[0].size = size+1;
1194 }
1195 void list_free_(void*_list)
1196 {
1197     commonlist_t**list = (commonlist_t**)_list;
1198     commonlist_t*l = *list;
1199     while(l) {
1200         commonlist_t*next = l->next;
1201         free(l);
1202         l = next;
1203     }
1204     *list = 0;
1205 }
1206 void*list_clone_(void*_list)
1207 {
1208     commonlist_t*l = *(commonlist_t**)_list;
1209
1210     void*dest = 0;
1211     while(l) {
1212         commonlist_t*next = l->next;
1213         list_append_(&dest, l->entry);
1214         l = next;
1215     }
1216     return dest;
1217
1218 }