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 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 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 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 <memory.h>
  26 #include "q.h"
  27
  28 // ------------------------------- malloc, alloc routines ---------------------
  29
  30 #ifndef STRNDUP
  31 char* strdup_n(const char*str, int size)
  32 {
  33     char*m = (char*)malloc(size+1);
  34     memcpy(m, str, size);
  35     m[size] = 0;
  36     return m;
  37 }
  38 #endif
  39 char*qstrdup(const char*string)
  40 {
  41     return strdup(string);
  42 }
  43 char*qstrndup(const char*string, int len)
  44 {
  45     return strdup_n(string, len);
  46 }
  47
  48 // ------------------------------- mem_t --------------------------------------
  49
  50 void mem_init(mem_t*mem)
  51 {
  52     memset(mem, 0, sizeof(mem_t));
  53 }
  54 void mem_clear(mem_t*mem)
  55 {
  56     free(mem->buffer);mem->buffer = 0;
  57 }
  58 void mem_destroy(mem_t*mem)
  59 {
  60     mem_clear(mem);
  61     free(mem);
  62 }
  63 static int mem_put_(mem_t*m,const void*data, int length, int null)
  64 {
  65     int n = m->pos;
  66     m->pos += length + (null?1:0);
  67     if(m->pos > m->len) {
  68         m->len = (m->pos+63)&~63;
  69         m->buffer = m->buffer?(char*)realloc(m->buffer,m->len):(char*)malloc(m->len);
  70     }
  71     memcpy(&m->buffer[n], data, length);
  72     if(null)
  73         m->buffer[n + length] = 0;
  74     return n;
  75 }
  76 int mem_put(mem_t*m,void*data, int length)
  77 {
  78     return mem_put_(m, data, length, 0);
  79 }
  80 int mem_putstring(mem_t*m,string_t str)
  81 {
  82     return mem_put_(m, str.str, str.len, 1);
  83 }
  84
  85 // ------------------------------- ringbuffer_t -------------------------------
  86
  87 typedef struct _ringbuffer_internal_t
  88 {
  89     unsigned char*buffer;
  90     int readpos;
  91     int writepos;
  92     int buffersize;
  93 } ringbuffer_internal_t;
  94
  95 void ringbuffer_init(ringbuffer_t*r)
  96 {
  97     ringbuffer_internal_t*i = (ringbuffer_internal_t*)malloc(sizeof(ringbuffer_internal_t));
  98     memset(r, 0, sizeof(ringbuffer_t));
  99     memset(i, 0, sizeof(ringbuffer_internal_t));
 100     r->internal = i;
 101     i->buffer = (unsigned char*)malloc(1024);
 102     i->buffersize = 1024;
 103 }
 104 int ringbuffer_read(ringbuffer_t*r, void*buf, int len)
 105 {
 106     unsigned char* data = (unsigned char*)buf;
 107     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 108     if(r->available < len)
 109         len = r->available;
 110     if(!len)
 111         return 0;
 112     if(i->readpos + len > i->buffersize) {
 113         int read1 = i->buffersize-i->readpos;
 114         memcpy(data, &i->buffer[i->readpos], read1);
 115         memcpy(&data[read1], &i->buffer[0], len - read1);
 116         i->readpos = len - read1;
 117     } else {
 118         memcpy(data, &i->buffer[i->readpos], len);
 119         i->readpos += len;
 120         i->readpos %= i->buffersize;
 121     }
 122     r->available -= len;
 123     return len;
 124 }
 125 void ringbuffer_put(ringbuffer_t*r, void*buf, int len)
 126 {
 127     unsigned char* data = (unsigned char*)buf;
 128     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 129
 130     if(i->buffersize - r->available < len)
 131     {
 132         unsigned char* buf2;
 133         int newbuffersize = i->buffersize;
 134         int oldavailable = r->available;
 135         newbuffersize*=3;newbuffersize/=2; /*grow at least by 50% each time */
 136
 137         if(newbuffersize < r->available + len)
 138             newbuffersize = r->available + len + 1024;
 139
 140         buf2 = (unsigned char*)malloc(newbuffersize);
 141         ringbuffer_read(r, buf2, r->available);
 142         free(i->buffer);
 143         i->buffer = buf2;
 144         i->buffersize = newbuffersize;
 145         i->readpos = 0;
 146         i->writepos = oldavailable;
 147         r->available = oldavailable;
 148     }
 149     if(i->writepos + len > i->buffersize) {
 150         int read1 = i->buffersize-i->writepos;
 151         memcpy(&i->buffer[i->writepos], data, read1);
 152         memcpy(&i->buffer[0], &data[read1], len - read1);
 153         i->writepos = len - read1;
 154     } else {
 155         memcpy(&i->buffer[i->writepos], data, len);
 156         i->writepos += len;
 157         i->writepos %= i->buffersize;
 158     }
 159     r->available += len;
 160 }
 161 void ringbuffer_clear(ringbuffer_t*r)
 162 {
 163     ringbuffer_internal_t*i = (ringbuffer_internal_t*)r->internal;
 164     free(i->buffer);i->buffer = 0;
 165     free(i);
 166 }
 167
 168 // ------------------------------- heap_t -------------------------------
 169
 170 void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
 171 {
 172     memset(h, 0, sizeof(heap_t));
 173     h->max_size = n;
 174     h->size = 0;
 175     h->elem_size = elem_size;
 176     h->compare = compare;
 177     h->elements = (void**)malloc(n*sizeof(void*));memset(h->elements, 0, n*sizeof(void*));
 178     h->data = (char*)malloc(h->max_size*h->elem_size);memset(h->data, 0, h->max_size*h->elem_size);
 179 }
 180 void heap_clear(heap_t*h)
 181 {
 182     free(h->elements);
 183     free(h->data);
 184 }
 185
 186 #define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
 187
 188 static void up(heap_t*h, int node)
 189 {
 190     void*node_p = h->elements[node];
 191     int parent = node;
 192     do {
 193         node = parent;
 194         if(!node) break;
 195         parent = (node-1)/2;
 196         h->elements[node] = h->elements[parent];
 197     } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
 198
 199     h->elements[node] = node_p;
 200 }
 201 static void down(heap_t*h, int node)
 202 {
 203     void*node_p = h->elements[node];
 204     int child = node;
 205     do {
 206         node = child;
 207
 208         /* determine new child's position */
 209         child = node<<1|1;
 210         if(child >= h->size)
 211             break;
 212         if(child+1 < h->size && HEAP_NODE_SMALLER(h,h->elements[child],h->elements[child+1])) // search for bigger child
 213             child++;
 214
 215         h->elements[node] = h->elements[child];
 216     } while(HEAP_NODE_SMALLER(h,node_p, h->elements[child]));
 217
 218     h->elements[node] = node_p;
 219 }
 220 void heap_put(heap_t*h, void*e)
 221 {
 222     int pos = h->size++;
 223     memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
 224     h->elements[pos] = &h->data[pos];
 225     up(h, pos);
 226 }
 227 int heap_size(heap_t*h)
 228 {
 229     return h->size;
 230 }
 231 void* heap_max(heap_t*h)
 232 {
 233     return h->elements[0];
 234 }
 235 void* heap_chopmax(heap_t*h)
 236 {
 237     void*p = h->elements[0];
 238     h->elements[0] = h->elements[--h->size];
 239     down(h,0);
 240     return p;
 241 }
 242 void heap_dump(heap_t*h, FILE*fi)
 243 {
 244     int t;
 245     for(t=0;t<h->size;t++) {
 246         int s;
 247         for(s=0;s<=t;s=(s+1)*2-1) {
 248             if(s==t) fprintf(fi,"\n");
 249         }
 250         //fprintf(fi,"%d ", h->elements[t]->x); //?
 251     }
 252 }
 253 void** heap_flatten(heap_t*h)
 254 {
 255     void**nodes = (void**)malloc(h->size*sizeof(void*));
 256     void**p = nodes;
 257
 258     while(h->size) {
 259         /*printf("Heap Size: %d\n", h->size);
 260         heap_print(stdout, h);
 261         printf("\n");*/
 262         *p++ = heap_chopmax(h);
 263     }
 264     return nodes;
 265 }
 266
 267 // ------------------------------- crc32 --------------------------------------
 268 static unsigned int*crc32 = 0;
 269 static void crc32_init(void)
 270 {
 271     int t;
 272     if(crc32)
 273         return;
 274     crc32= (unsigned int*)malloc(sizeof(unsigned int)*256);
 275     for(t=0; t<256; t++) {
 276         unsigned int c = t;
 277         int s;
 278         for (s = 0; s < 8; s++) {
 279           c = (0xedb88320L*(c&1)) ^ (c >> 1);
 280         }
 281         crc32[t] = c;
 282     }
 283 }
 284 // ------------------------------- string_t -----------------------------------
 285
 286 void string_set2(string_t*str, const char*text, int len)
 287 {
 288     str->len = len;
 289     str->str = text;
 290 }
 291 void string_set(string_t*str, const char*text)
 292 {
 293     str->len = strlen(text);
 294     str->str = text;
 295 }
 296 string_t string_new(const char*text, int len)
 297 {
 298     string_t s;
 299     s.len = len;
 300     s.str = text;
 301     return s;
 302 }
 303 string_t string_new2(const char*text)
 304 {
 305     string_t s;
 306     s.len = strlen(text);
 307     s.str = text;
 308     return s;
 309 }
 310 unsigned int string_hash(string_t*str)
 311 {
 312     int t;
 313     unsigned int checksum = 0;
 314     if(!crc32)
 315         crc32_init();
 316     for(t=0;t<str->len;t++) {
 317         checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
 318     }
 319     return checksum;
 320 }
 321 unsigned int string_hash2(const char*str)
 322 {
 323     unsigned int checksum = 0;
 324     if(!crc32)
 325         crc32_init();
 326     while(*str) {
 327         checksum = checksum>>8 ^ crc32[(*str^checksum)&0xff];
 328         str++;
 329     }
 330     return checksum;
 331 }
 332 void string_dup2(string_t*str, const char*text, int len)
 333 {
 334     str->len = len;
 335     str->str = strdup_n(text, len);
 336 }
 337 void string_dup(string_t*str, const char*text)
 338 {
 339     str->len = strlen(text);
 340     str->str = strdup(text);
 341 }
 342 int string_equals(string_t*str, const char*text)
 343 {
 344     int l = strlen(text);
 345     if(str->len == l && !memcmp(str->str, text, l))
 346         return 1;
 347     return 0;
 348 }
 349 int string_equals2(string_t*str, string_t*str2)
 350 {
 351     if(str->len == str2->len && !memcmp(str->str, str2->str, str->len))
 352         return 1;
 353     return 0;
 354 }
 355 char* string_cstr(string_t*str)
 356 {
 357     return strdup_n(str->str, str->len);
 358 }
 359
 360 // ------------------------------- stringarray_t ------------------------------
 361
 362 #define DEFAULT_HASH_SIZE 257
 363
 364 typedef struct _stringlist {
 365     int index;
 366     struct _stringlist*next;
 367 } stringlist_t;
 368
 369 typedef struct _stringarray_internal_t
 370 {
 371     mem_t pos;
 372     stringlist_t**hash;
 373     int num;
 374     int hashsize;
 375 } stringarray_internal_t;
 376
 377 void stringarray_init(stringarray_t*sa, int hashsize)
 378 {
 379     stringarray_internal_t*s;
 380     int t;
 381     sa->internal = (stringarray_internal_t*)malloc(sizeof(stringarray_internal_t));
 382     memset(sa->internal, 0, sizeof(stringarray_internal_t));
 383     s = (stringarray_internal_t*)sa->internal;
 384     mem_init(&s->pos);
 385     s->hash = malloc(sizeof(stringlist_t*)*hashsize);
 386     memset(s->hash, 0, sizeof(stringlist_t*)*hashsize);
 387     s->hashsize = hashsize;
 388 }
 389 void stringarray_put(stringarray_t*sa, string_t str)
 390 {
 391     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 392     int pos;
 393     int hash = string_hash(&str) % s->hashsize;
 394
 395     char*ss = string_cstr(&str);
 396     mem_put(&s->pos, &ss, sizeof(char*));
 397
 398     stringlist_t*l = malloc(sizeof(stringlist_t));
 399     l->index = s->num;
 400     l->next = s->hash[hash];
 401     s->hash[hash] = l;
 402
 403     s->num++;
 404 }
 405 char* stringarray_at(stringarray_t*sa, int pos)
 406 {
 407     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 408     char*p;
 409     if(pos<0 || pos>=s->num)
 410         return 0;
 411     p = *(char**)&s->pos.buffer[pos*sizeof(char*)];
 412     if(p<0)
 413         return 0;
 414     return p;
 415 }
 416 string_t stringarray_at2(stringarray_t*sa, int pos)
 417 {
 418     string_t s;
 419     s.str = stringarray_at(sa, pos);
 420     s.len = s.str?strlen(s.str):0;
 421     return s;
 422 }
 423 static stringlist_t* stringlist_del(stringarray_t*sa, stringlist_t*l, int index)
 424 {
 425     stringlist_t*ll = l;
 426     stringlist_t*old = l;
 427     while(l) {
 428         if(index==l->index) {
 429             old->next = l->next;
 430             memset(l, 0, sizeof(stringlist_t));
 431             free(l);
 432             if(old==l)
 433                 return 0;
 434             else
 435                 return ll;
 436         }
 437         old = l;
 438         l = l->next;
 439     }
 440     fprintf(stderr, "Internal error: did not find string %d in hash\n", index);
 441     return ll;
 442 }
 443
 444 void stringarray_del(stringarray_t*sa, int pos)
 445 {
 446     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 447     string_t str = stringarray_at2(sa, pos);
 448     int hash = string_hash(&str) % s->hashsize;
 449     s->hash[hash] = stringlist_del(sa, s->hash[hash], pos);
 450     *(char**)&s->pos.buffer[pos*sizeof(char*)] = 0;
 451 }
 452 int stringarray_find(stringarray_t*sa, string_t* str)
 453 {
 454     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 455     int hash = string_hash(str) % s->hashsize;
 456     int t;
 457     stringlist_t*l = s->hash[hash];
 458     //TODO: statistics
 459     while(l) {
 460         string_t s = stringarray_at2(sa, l->index);
 461         if(string_equals2(str, &s)) {
 462             return l->index;
 463         }
 464         l = l->next;
 465     }
 466     return -1;
 467 }
 468 void stringarray_clear(stringarray_t*sa)
 469 {
 470     stringarray_internal_t*s = (stringarray_internal_t*)sa->internal;
 471     mem_clear(&s->pos);
 472     int t;
 473     for(t=0;t<s->hashsize;t++) {
 474         stringlist_t*l = s->hash[t];
 475         while(l) {
 476             stringlist_t*next = l->next;
 477             memset(l, 0, sizeof(stringlist_t));
 478             free(l);
 479             l = next;
 480         }
 481     }
 482     free(s->hash);s->hash=0;
 483     free(s);
 484 }
 485 void stringarray_destroy(stringarray_t*sa)
 486 {
 487     stringarray_clear(sa);
 488     free(sa);
 489 }
 490
 491
 492 // ------------------------------- dictionary_t -------------------------------
 493
 494 dict_t*dict_new()
 495 {
 496     dict_t*d = malloc(sizeof(dict_t));
 497     dict_init(d);
 498     return d;
 499 }
 500 void dict_init(dict_t*h)
 501 {
 502     memset(h, 0, sizeof(dict_t));
 503     h->hashsize = DEFAULT_HASH_SIZE;
 504     h->slots = malloc(sizeof(dictentry_t*)*h->hashsize);
 505     h->num = 0;
 506     memset(h->slots, 0, sizeof(dictentry_t*)*h->hashsize);
 507 }
 508 void dict_put(dict_t*h, string_t s, void* data)
 509 {
 510     unsigned int checksum = string_hash(&s) % h->hashsize;
 511     dictentry_t*e = (dictentry_t*)malloc(sizeof(dictentry_t));
 512     e->s = strdup(s.str);
 513     e->next = h->slots[checksum];
 514     e->data = data;
 515     h->slots[checksum] = e;
 516     h->num++;
 517 }
 518 void dict_put2(dict_t*h, const char*s, void*data)
 519 {
 520     string_t s2;
 521     string_set(&s2, s);
 522     dict_put(h, s2, data);
 523 }
 524 void dict_dump(dict_t*h, FILE*fi, const char*prefix)
 525 {
 526     int t;
 527     for(t=0;t<h->hashsize;t++) {
 528         dictentry_t*e = h->slots[t];
 529         while(e) {
 530             fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
 531             e = e->next;
 532         }
 533     }
 534 }
 535 int dict_count(dict_t*h)
 536 {
 537     return h->num;
 538 }
 539 void* dict_lookup(dict_t*h, const char*s)
 540 {
 541     unsigned int checksum = string_hash2(s) % h->hashsize;
 542     dictentry_t*e = h->slots[checksum];
 543     while(e) {
 544         if(!strcmp(e->s, s)) {
 545             return e->data;
 546         }
 547         e = e->next;
 548     }
 549     return 0;
 550 }
 551 char dict_del(dict_t*h, const char*s)
 552 {
 553     unsigned int checksum = string_hash2(s) % h->hashsize;
 554     dictentry_t*head = h->slots[checksum];
 555     dictentry_t*e = head, *prev=0;
 556     while(e) {
 557         if(!strcmp(e->s, s)) {
 558             dictentry_t*next = e->next;
 559             free((void*)e->s);
 560             memset(e, 0, sizeof(dictentry_t));
 561             free(e);
 562             if(e == head) {
 563                 h->slots[checksum] = 0;
 564             } else {
 565                 prev->next = next;
 566             }
 567             return 1;
 568         }
 569         prev = e;
 570         e = e->next;
 571     }
 572     return 0;
 573 }
 574 void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
 575 {
 576     int t;
 577     for(t=0;t<h->hashsize;t++) {
 578         dictentry_t*e = h->slots[t];
 579         while(e) {
 580             dictentry_t*next = e->next;
 581             if(runFunction) {
 582                 runFunction(data, e->s, e->data);
 583             }
 584             e = e->next;
 585         }
 586     }
 587 }
 588 void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
 589 {
 590     int t;
 591     for(t=0;t<h->hashsize;t++) {
 592         dictentry_t*e = h->slots[t];
 593         while(e) {
 594             dictentry_t*next = e->next;
 595             if(runFunction) {
 596                 runFunction(e->data);
 597             }
 598             e = e->next;
 599         }
 600     }
 601 }
 602 void dict_free_all(dict_t*h, void (*freeFunction)(void*))
 603 {
 604     int t;
 605     for(t=0;t<h->hashsize;t++) {
 606         dictentry_t*e = h->slots[t];
 607         while(e) {
 608             dictentry_t*next = e->next;
 609             free((void*)e->s);
 610             if(freeFunction) {
 611                 freeFunction(e->data);
 612             }
 613             memset(e, 0, sizeof(dictentry_t));
 614             free(e);
 615             e = next;
 616         }
 617     }
 618     free(h->slots);h->slots = 0;
 619 }
 620 void dict_clear(dict_t*h)
 621 {
 622     dict_free_all(h, 0);
 623 }
 624 void dict_destroy(dict_t*dict)
 625 {
 626     dict_clear(dict);
 627     free(dict);
 628 }
 629
 630 // ------------------------------- map_t --------------------------------------
 631
 632 typedef struct _map_internal_t
 633 {
 634     dict_t d;
 635 } map_internal_t;
 636
 637 void map_init(map_t*map)
 638 {
 639     map_internal_t*m;
 640     map->internal = (map_internal_t*)malloc(sizeof(map_internal_t));
 641     memset(map->internal, 0, sizeof(map_internal_t));
 642     m = (map_internal_t*)map->internal;
 643     dict_init(&m->d);
 644 }
 645 void map_put(map_t*map, string_t t1, string_t t2)
 646 {
 647     map_internal_t*m = (map_internal_t*)map->internal;
 648     dict_put2(&m->d, string_cstr(&t1), (void*)string_cstr(&t2));
 649 }
 650 const char* map_lookup(map_t*map, const char*name)
 651 {
 652     map_internal_t*m = (map_internal_t*)map->internal;
 653     const char*value = dict_lookup(&m->d, name);
 654     return value;
 655 }
 656 void dumpmapentry(void*data, const char*key, void*value)
 657 {
 658     FILE*fi = (FILE*)data;
 659     fprintf(fi, "%s=%s\n", key, (char*)value);
 660 }
 661 void map_dump(map_t*map, FILE*fi, const char*prefix)
 662 {
 663     int t;
 664     map_internal_t*m = (map_internal_t*)map->internal;
 665     fprintf(fi, "ERROR: map dumping not implemented yet\n");
 666     dict_foreach_keyvalue(&m->d, dumpmapentry, fi);
 667 }
 668 void map_clear(map_t*map)
 669 {
 670     map_internal_t*m = (map_internal_t*)map->internal;
 671     dict_clear(&m->d);
 672     free(m);
 673 }
 674 void map_destroy(map_t*map)
 675 {
 676     map_clear(map);
 677     free(map);
 678 }
 679