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 char* string_cstr(string_t*str)
 322 {
 323     return strdup_n(str->str, str->len);
 324 }
 325 unsigned int string_hash(string_t*str)
 326 {
 327     int t;
 328     unsigned int checksum = 0;
 329     if(!crc32)
 330         crc32_init();
 331     for(t=0;t<str->len;t++) {
 332         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
 333     }
 334     return checksum;
 335 }
 336 unsigned int string_hash2(const char*str)
 337 {
 338     unsigned int checksum = 0;
 339     const char*p = str;
 340     if(!crc32)
 341         crc32_init();
 342     while(*p) {
 343         checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
 344         p++;
 345     }
 346     return checksum;
 347 }
 348 unsigned int string_hash3(const char*str, int len)
 349 {
 350     string_t s;
 351     s.str = str;
 352     s.len = len;
 353     return string_hash(&s);
 354 }
 355 void string_dup2(string_t*str, const char*text, int len)
 356 {
 357     str->len = len;
 358     str->str = strdup_n(text, len);
 359 }
 360 void string_dup(string_t*str, const char*text)
 361 {
 362     str->len = strlen(text);
 363     str->str = strdup(text);
 364 }
 365 int string_equals(string_t*str, const char*text)
 366 {
 367     int l = strlen(text);
 368     if(str->len == l && !memcmp(str->str, text, l))
 369         return 1;
 370     return 0;
 371 }
 372 int string_equals2(string_t*str, string_t*str2)
 373 {
 374     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
 375         return 1;
 376     return 0;
 377 }
 378
 379 // ------------------------------- stringarray_t ------------------------------
 380
 381 typedef struct _stringlist {
 382     int index;
 383     struct _stringlist*next;
 384 } stringlist_t;
 385
 386 typedef struct _stringarray_internal_t
 387 {
 388     mem_t pos;
 389     stringlist_t**hash;
 390     int num;
 391     int hashsize;
 392 } stringarray_internal_t;
 393
 394 void stringarray_init(stringarray_t*sa, int hashsize)
 395 {
 396     stringarray_internal_t*s;
 397     int t;
 398     sa->internal = (stringarray_internal_t*)rfx_calloc(sizeof(stringarray_internal_t));
 399     s = (stringarray_internal_t*)sa->internal;
 400     mem_init(&s->pos);
 401     s->hash = rfx_calloc(sizeof(stringlist_t*)*hashsize);
 402     s->hashsize = hashsize;
 403 }
 404 void stringarray_put(stringarray_t*sa, string_t str)
 405 {
 406     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 407     int pos;
 408     int hash = string_hash(&str) % s->hashsize;
 409
 410     char*ss = string_cstr(&str);
 411     mem_put(&s->pos, &ss, sizeof(char*));
 412
 413     stringlist_t*l = rfx_alloc(sizeof(stringlist_t));
 414     l->index = s->num;
 415     l->next = s->hash[hash];
 416     s->hash[hash] = l;
 417
 418     s->num++;
 419 }
 420 char* stringarray_at(stringarray_t*sa, int pos)
 421 {
 422     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 423     char*p;
 424     if(pos<0 || pos>=s->num)
 425         return 0;
 426     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
 427     if(p<0)
 428         return 0;
 429     return p;
 430 }
 431 string_t stringarray_at2(stringarray_t*sa, int pos)
 432 {
 433     string_t s;
 434     s.str = stringarray_at(sa, pos);
 435     s.len = s.str?strlen(s.str):0;
 436     return s;
 437 }
 438 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
 439 {
 440     stringlist_t*ll = l;
 441     stringlist_t*old = l;
 442     while(l) {
 443         if(index==l->index) {
 444             old->next = l->next;
 445             memset(l, 0, sizeof(stringlist_t));
 446             rfx_free(l);
 447             if(old==l)
 448                 return 0;
 449             else
 450                 return ll;
 451         }
 452         old = l;
 453         l = l->next;
 454     }
 455     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
 456     return ll;
 457 }
 458
 459 void stringarray_del(stringarray_t*sa, int pos)
 460 {
 461     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 462     string_t str = stringarray_at2(sa, pos);
 463     int hash = string_hash(&str) % s->hashsize;
 464     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
 465     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
 466 }
 467 int stringarray_find(stringarray_t*sa, string_t* str)
 468 {
 469     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 470     int hash = string_hash(str) % s->hashsize;
 471     int t;
 472     stringlist_t*l = s->hash[hash];
 473     //TODO: statistics
 474     while(l) {
 475         string_t s = stringarray_at2(sa, l->index);
 476         if(string_equals2(str, &s)) {
 477             return l->index;
 478         }
 479         l = l->next;
 480     }
 481     return -1;
 482 }
 483 void stringarray_clear(stringarray_t*sa)
 484 {
 485     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 486     mem_clear(&s->pos);
 487     int t;
 488     for(t=0;t<s->hashsize;t++) {
 489         stringlist_t*l = s->hash[t];
 490         while(l) {
 491             stringlist_t*next = l->next;
 492             memset(l, 0, sizeof(stringlist_t));
 493             rfx_free(l);
 494             l = next;
 495         }
 496     }
 497     rfx_free(s->hash);s->hash=0;
 498     rfx_free(s);
 499 }
 500 void stringarray_destroy(stringarray_t*sa)
 501 {
 502     stringarray_clear(sa);
 503     rfx_free(sa);
 504 }
 505
 506
 507 // ------------------------------- dictionary_t -------------------------------
 508
 509 #define INITIAL_SIZE 1
 510
 511 static int max(int x, int y) {
 512     return x>y?x:y;
 513 }
 514
 515 dict_t*dict_new()
 516 {
 517     dict_t*d = rfx_alloc(sizeof(dict_t));
 518     dict_init(d);
 519     return d;
 520 }
 521 void dict_init(dict_t*h)
 522 {
 523     memset(h, 0, sizeof(dict_t));
 524     h->hashsize = INITIAL_SIZE;
 525     h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
 526     h->num = 0;
 527 }
 528 static void dict_expand(dict_t*h, int newlen)
 529 {
 530     assert(h->hashsize < newlen);
 531     dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
 532     int t;
 533     for(t=0;t<h->hashsize;t++) {
 534         dictentry_t*e = h->slots[t];
 535         while(e) {
 536             dictentry_t*next = e->next;
 537             unsigned int newhash = e->hash%newlen;
 538             e->next = newslots[newhash];
 539             newslots[newhash] = e;
 540             e = next;
 541         }
 542     }
 543     if(h->slots)
 544         rfx_free(h->slots);
 545     h->slots = newslots;
 546     h->hashsize = newlen;
 547 }
 548 void dict_put(dict_t*h, string_t s, void* data)
 549 {
 550     /* TODO: should we look for duplicates here? */
 551     unsigned int hash = string_hash(&s);
 552     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
 553
 554     unsigned int hash2 = string_hash(&s) % h->hashsize;
 555     char*sdata = rfx_alloc(s.len);
 556     memcpy(sdata, s.str, s.len);
 557     e->s = sdata;
 558     e->len = s.len;
 559     e->hash = hash; //for resizing
 560     e->next = h->slots[hash2];
 561     e->data = data;
 562     h->slots[hash2] = e;
 563     h->num++;
 564 }
 565 void dict_put2(dict_t*h, const char*s, void*data)
 566 {
 567     string_t s2;
 568     string_set(&s2, s);
 569     dict_put(h, s2, data);
 570 }
 571 void dict_put3(dict_t*h, const char* s, int len, void*data)
 572 {
 573     string_t s3;
 574     string_set2(&s3, s, len);
 575     dict_put(h, s3, data);
 576 }
 577 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
 578 {
 579     int t;
 580     for(t=0;t<h->hashsize;t++) {
 581         dictentry_t*e = h->slots[t];
 582         while(e) {
 583             char*s = strdup_n(e->s, e->len);
 584             fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
 585             rfx_free(s);
 586             e = e->next;
 587         }
 588     }
 589 }
 590
 591 int dict_count(dict_t*h)
 592 {
 593     return h->num;
 594 }
 595 void* dict_lookup4(dict_t*h, const char*s, int len, const void*data)
 596 {
 597     if(!h->num)
 598         return 0;
 599
 600     unsigned int ohash = string_hash2(s);
 601     unsigned int hash = ohash % h->hashsize;
 602
 603     /* check first entry for match */
 604     dictentry_t*e = h->slots[hash];
 605     if(e && e->len == len && !memcmp(e->s, s, len)) {
 606         return e->data;
 607     } else if(e) {
 608         e = e->next;
 609     }
 610
 611     /* if dict is 2/3 filled, double the size. Do
 612        this the first time we have to actually iterate
 613        through a slot to find our data */
 614     if(e && h->num*3 >= h->hashsize*2) {
 615         int newsize = h->hashsize;
 616         while(h->num*3 >= newsize*2) {
 617             newsize = newsize<15?15:(newsize+1)*2-1;
 618         }
 619         dict_expand(h, newsize);
 620         hash = ohash % h->hashsize;
 621         e = h->slots[hash];
 622     }
 623
 624     /* check subsequent entries for a match */
 625     while(e) {
 626         if(e->len == len && !memcmp(e->s, s, len) && (!data || data==e->data)) {
 627             return e->data;
 628         }
 629         e = e->next;
 630     }
 631     return 0;
 632 }
 633 void* dict_lookup3(dict_t*h, const char*s, const void*data)
 634 {
 635     int l = strlen(s);
 636     return dict_lookup4(h, s, l, data);
 637 }
 638 void* dict_lookup2(dict_t*h, const char*s, int len)
 639 {
 640     return dict_lookup4(h, s, len, 0);
 641 }
 642 void* dict_lookup(dict_t*h, const char*s)
 643 {
 644     int l = strlen(s);
 645     return dict_lookup2(h, s, l);
 646 }
 647 char dict_del(dict_t*h, const char*s)
 648 {
 649     if(!h->num)
 650         return 0;
 651     unsigned int hash = string_hash2(s) % h->hashsize;
 652     int l = strlen(s);
 653     dictentry_t*head = h->slots[hash];
 654     dictentry_t*e = head, *prev=0;
 655     while(e) {
 656         if(e->len ==l && !memcmp(e->s, s, l)) {
 657             dictentry_t*next = e->next;
 658             rfx_free((void*)e->s);
 659             memset(e, 0, sizeof(dictentry_t));
 660             rfx_free(e);
 661             if(e == head) {
 662                 h->slots[hash] = 0;
 663             } else {
 664                 assert(prev);
 665                 prev->next = next;
 666             }
 667             h->num--;
 668             return 1;
 669         }
 670         prev = e;
 671         e = e->next;
 672     }
 673     return 0;
 674 }
 675
 676 static dictentry_t* dict_get_all(dict_t*h, const char*s)
 677 {
 678     if(!h->num)
 679         return 0;
 680     unsigned int ohash = string_hash2(s);
 681     unsigned int hash = ohash % h->hashsize;
 682     return h->slots[hash];
 683 }
 684
 685 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
 686 {
 687     int t;
 688     for(t=0;t<h->hashsize;t++) {
 689         dictentry_t*e = h->slots[t];
 690         while(e) {
 691             dictentry_t*next = e->next;
 692             if(runFunction) {
 693                 char*s = strdup_n(e->s, e->len); //append \0
 694                 runFunction(data, s, e->data);
 695                 rfx_free(s);
 696             }
 697             e = e->next;
 698         }
 699     }
 700 }
 701 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
 702 {
 703     int t;
 704     for(t=0;t<h->hashsize;t++) {
 705         dictentry_t*e = h->slots[t];
 706         while(e) {
 707             dictentry_t*next = e->next;
 708             if(runFunction) {
 709                 runFunction(e->data);
 710             }
 711             e = e->next;
 712         }
 713     }
 714 }
 715
 716 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
 717 {
 718     int t;
 719     for(t=0;t<h->hashsize;t++) {
 720         dictentry_t*e = h->slots[t];
 721         while(e) {
 722             dictentry_t*next = e->next;
 723             rfx_free((void*)e->s);
 724             if(freeFunction) {
 725                 freeFunction(e->data);
 726             }
 727             memset(e, 0, sizeof(dictentry_t));
 728             rfx_free(e);
 729             e = next;
 730         }
 731     }
 732     rfx_free(h->slots);
 733     memset(h, 0, sizeof(dict_t));
 734 }
 735
 736 void dict_clear(dict_t*h)
 737 {
 738     dict_free_all(h, 0);
 739 }
 740
 741 void dict_destroy(dict_t*dict)
 742 {
 743     dict_clear(dict);
 744     rfx_free(dict);
 745 }
 746
 747 // ------------------------------- map_t --------------------------------------
 748
 749 typedef struct _map_internal_t
 750 {
 751     dict_t d;
 752 } map_internal_t;
 753
 754 void map_init(map_t*map)
 755 {
 756     map_internal_t*m;
 757     map->internal = (map_internal_t*)rfx_calloc(sizeof(map_internal_t));
 758     m = (map_internal_t*)map->internal;
 759     dict_init(&m->d);
 760 }
 761 void map_put(map_t*map, string_t t1, string_t t2)
 762 {
 763     map_internal_t*m = (map_internal_t*)map->internal;
 764     string_t s;
 765     char* s1 = string_cstr(&t1);
 766     dict_put2(&m->d, s1, (void*)string_cstr(&t2));
 767     rfx_free(s1);
 768 }
 769 const char* map_lookup(map_t*map, const char*name)
 770 {
 771     map_internal_t*m = (map_internal_t*)map->internal;
 772     const char*value = dict_lookup(&m->d, name);
 773     return value;
 774 }
 775 static void freestring(void*data)
 776 {
 777     rfx_free(data);
 778 }
 779 static void dumpmapentry(void*data, const char*key, void*value)
 780 {
 781     FILE*fi = (FILE*)data;
 782     fprintf(fi, "%s=%s\n", key, (char*)value);
 783 }
 784 void map_dump(map_t*map, FILE*fi, const char*prefix)
 785 {
 786     int t;
 787     map_internal_t*m = (map_internal_t*)map->internal;
 788     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
 789 }
 790 void map_clear(map_t*map)
 791 {
 792     map_internal_t*m = (map_internal_t*)map->internal;
 793     dict_free_all(&m->d, freestring);
 794     rfx_free(m);
 795 }
 796 void map_destroy(map_t*map)
 797 {
 798     map_clear(map);
 799     rfx_free(map);
 800 }
 801
 802 // ------------------------------- array_t --------------------------------------
 803
 804 array_t* array_new() {
 805     array_t*d = malloc(sizeof(array_t));
 806     memset(d, 0, sizeof(array_t));
 807     d->entry2pos = dict_new();
 808     return d;
 809 }
 810 void array_free(array_t*array) {
 811     dict_destroy(array->entry2pos);
 812     array->entry2pos;
 813     if(array->d) {
 814         free(array->d);array->d = 0;
 815     }
 816     free(array);
 817 }
 818 const char*array_getkey(array_t*array, int nr) {
 819     if(nr > array->num || nr<0) {
 820         printf("error: reference to element %d in array[%d]\n", nr, array->num);
 821         *(int*)0 = 0;
 822         return 0;
 823     }
 824     return array->d[nr].name;
 825 }
 826 char*array_getvalue(array_t*array, int nr) {
 827     if(nr > array->num || nr<0) {
 828         printf("error: reference to element %d in array[%d]\n", nr, array->num);
 829         *(int*)0 = 0;
 830         return 0;
 831     }
 832     return array->d[nr].data;
 833 }
 834 int array_append(array_t*array, const char*name, const void*data) {
 835     while(array->size <= array->num) {
 836         array->size += 64;
 837         if(!array->d) {
 838             array->d = malloc(sizeof(array_entry_t)*array->size);
 839         } else {
 840             array->d = realloc(array->d, sizeof(array_entry_t)*array->size);
 841         }
 842     }
 843     if(name) {
 844         array->d[array->num].name = strdup(name);
 845     } else {
 846         array->d[array->num].name = 0;
 847     }
 848     array->d[array->num].data = (void*)data;
 849     dict_put2(array->entry2pos, name, (void*)(ptroff_t)(array->num+1));
 850     return array->num++;
 851 }
 852 int array_find(array_t*array, const char*name)
 853 {
 854     if(!name)
 855         name = "";
 856     int pos = (int)(ptroff_t)dict_lookup(array->entry2pos, name);
 857     return pos-1;
 858 }
 859 int array_find2(array_t*array, const char*name, void*data)
 860 {
 861     if(!name)
 862         name = "";
 863     int len= strlen(name);
 864
 865     dictentry_t*e = dict_get_all(array->entry2pos, name);
 866
 867     while(e) {
 868         int index = ((int)(ptroff_t)e->data) - 1;
 869         if(e->len == len && !memcmp(e->s, name, len) && array->d[index].data == data) {
 870             return index;
 871         }
 872         e = e->next;
 873     }
 874     return -1;
 875 }
 876 int array_update(array_t*array, const char*name, void*data) {
 877     int pos = array_find(array, name);
 878     if(pos>=0) {
 879         array->d[pos].data = data;
 880         return pos;
 881     }
 882     return array_append(array, name, data);
 883 }
 884 int array_append_if_new(array_t*array, const char*name, void*data) {
 885     int pos = array_find(array, name);
 886     if(pos>=0)
 887         return pos;
 888     return array_append(array, name, data);
 889 }
 890
 891 // ------------------------------- list_t --------------------------------------
 892
 893 struct _commonlist;
 894 typedef struct _listinfo {
 895     int size;
 896     struct _commonlist*last;
 897 } listinfo_t;
 898
 899 typedef struct _commonlist {
 900     void*entry;
 901     struct _commonlist*next;
 902     listinfo_t info[0];
 903 } commonlist_t;
 904
 905 int list_length(void*_list)
 906 {
 907     commonlist_t*l = (commonlist_t*)_list;
 908     if(!l)
 909         return 0;
 910     return l->info[0].size;
 911 }
 912 void list_append_(void*_list, void*entry)
 913 {
 914     commonlist_t**list = (commonlist_t**)_list;
 915     commonlist_t* n = 0;
 916     if(!*list) {
 917         n = malloc(sizeof(commonlist_t)+sizeof(listinfo_t));
 918         *list = n;
 919     } else {
 920         n = malloc(sizeof(commonlist_t));
 921         (*list)->info[0].last->next = n;
 922     }
 923     n->next = 0;
 924     n->entry = entry;
 925     (*list)->info[0].last = n;
 926     (*list)->info[0].size++;
 927 }
 928 void list_free_(void*_list)
 929 {
 930     commonlist_t**list = (commonlist_t**)_list;
 931     commonlist_t*l = *list;
 932     while(l) {
 933         commonlist_t*next = l->next;
 934         free(l);
 935         l = next;
 936     }
 937     *list = 0;
 938 }