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