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