return length;
}
+// ------------------------------- median -------------------------------------
+
+float medianf(float*a, int n)
+{
+ int i,j,l,m;
+ float x;
+ int k=n&1?n/2:n/2-1;
+ l=0;
+ m=n-1;
+ while(l<m) {
+ x=a[k];
+ i=l;j=m;
+ do {
+ while(a[i]<x) i++;
+ while(x<a[j]) j--;
+ if(i<=j) {
+ //swap
+ float t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ i++;
+ j--;
+ }
+ } while(i<=j);
+ if(j<k) l=i;
+ if(k<i) m=j;
+ }
+ return a[k];
+}
+
// ------------------------------- ringbuffer_t -------------------------------
typedef struct _ringbuffer_internal_t
// ------------------------------- heap_t -------------------------------
-void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
+void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
{
memset(h, 0, sizeof(heap_t));
- h->max_size = n;
h->size = 0;
h->elem_size = elem_size;
h->compare = compare;
- h->elements = (void**)rfx_calloc(n*sizeof(void*));
- h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
+ h->elements = 0;
+ h->max_size = 0;
+}
+heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
+{
+ heap_t*h = malloc(sizeof(heap_t));
+ heap_init(h, elem_size, compare);
+ return h;
+}
+heap_t* heap_clone(heap_t*o)
+{
+ heap_t*h = malloc(sizeof(heap_t));
+ memcpy(h, o, sizeof(heap_t));
+ h->elements = rfx_alloc(sizeof(void*)*h->size);
+ int t;
+ for(t=0;t<h->size;t++) {
+ h->elements[t] = rfx_alloc(h->elem_size);
+ memcpy(h->elements[t], o->elements[t], h->elem_size);
+ }
+ return h;
}
void heap_clear(heap_t*h)
{
+ int t;
+ for(t=0;t<h->size;t++) {
+ rfx_free(h->elements[t]);
+ h->elements[t]=0;
+ }
rfx_free(h->elements);
- rfx_free(h->data);
+}
+void heap_destroy(heap_t*h)
+{
+ heap_clear(h);
+ free(h);
}
-#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
static void up(heap_t*h, int node)
{
void*node_p = h->elements[node];
int parent = node;
+ int tmp = node;
do {
node = parent;
if(!node) break;
parent = (node-1)/2;
h->elements[node] = h->elements[parent];
- } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
-
+ } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
h->elements[node] = node_p;
}
static void down(heap_t*h, int node)
void heap_put(heap_t*h, void*e)
{
int pos = h->size++;
- memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
- h->elements[pos] = &h->data[pos];
+ void*data = rfx_alloc(h->elem_size);
+ memcpy(data,e,h->elem_size);
+
+ if(pos>=h->max_size) {
+ h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
+ h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
+ assert(pos<h->max_size);
+ }
+
+ h->elements[pos] = data;
up(h, pos);
}
int heap_size(heap_t*h)
{
return h->size;
}
-void* heap_max(heap_t*h)
+void* heap_peek(heap_t*h)
{
+ if(!h || !h->size)
+ return 0;
return h->elements[0];
}
void* heap_chopmax(heap_t*h)
{
+ if(!h->size)
+ return 0;
void*p = h->elements[0];
- assert(h->size);
h->elements[0] = h->elements[--h->size];
down(h,0);
return p;
}
void** heap_flatten(heap_t*h)
{
- void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
+ void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
void**p = nodes;
while(h->size) {
printf("\n");*/
*p++ = heap_chopmax(h);
}
+ *p++ = 0;
return nodes;
}
{
if(!*t) {
(*t) = rfx_calloc(sizeof(trielayer_t));
- (*t)->rest = (unsigned char*)strdup(id);
+ (*t)->rest = (unsigned char*)strdup((char*)id);
(*t)->data = data;
return 0;
}
char overwrite = 0;
if((*t)->rest)
overwrite = 1;
- (*t)->rest = strdup("");
+ (*t)->rest = (unsigned char*)strdup("");
(*t)->data = data;
return overwrite;
}
static char _trie_remove(trielayer_t*t, unsigned const char*id)
{
while(t) {
- if(t->rest && !strcmp(t->rest, id)) {
+ if(t->rest && !strcmp((char*)t->rest, (char*)id)) {
free(t->rest);
t->rest = 0;
return 1;
{
trielayer_t*t = trie->start;
while(t) {
- if(t->rest && !strcmp(t->rest, id))
+ if(t->rest && !strcmp((char*)t->rest, (char*)id))
return 1;
if(!*id)
return 0;
{
trielayer_t*t = trie->start;
while(t) {
- if(t->rest && !strcmp(t->rest, id))
+ if(t->rest && !strcmp((char*)t->rest, (char*)id))
return t->data;
if(!*id)
return 0;
}
if(t->rest) {
buffer[pos]=0;
- printf("%s%s %08x\n", buffer, t->rest, t->data);
+ printf("%s%s %08x\n", buffer, t->rest, (int)t->data);
}
}
// ------------------------------- crc32 --------------------------------------
-static unsigned int*crc32 = 0;
+static unsigned int crc32[256];
+static char crc32_initialized=0;
static void crc32_init(void)
{
int t;
- if(crc32)
+ if(crc32_initialized)
return;
- crc32= (unsigned int*)rfx_alloc(sizeof(unsigned int)*256);
+ crc32_initialized = 1;
for(t=0; t<256; t++) {
unsigned int c = t;
int s;
unsigned int crc32_add_byte(unsigned int checksum, unsigned char b)
{
- if(!crc32)
- crc32_init();
+ crc32_init();
return checksum>>8 ^ crc32[(b^checksum)&0xff];
}
unsigned int crc32_add_string(unsigned int checksum, const char*s)
{
- if(!crc32)
- crc32_init();
+ crc32_init();
if(!s)
return checksum;
while(*s) {
}
return checksum;
}
+unsigned int crc32_add_bytes(unsigned int checksum, const void*_s, int len)
+{
+ unsigned char*s = (unsigned char*)_s;
+ crc32_init();
+ if(!s || !len)
+ return checksum;
+ do {
+ checksum = checksum>>8 ^ crc32[(*s^checksum)&0xff];
+ s++;
+ } while(--len);
+ return checksum;
+}
unsigned int string_hash(const string_t*str)
{
int t;
unsigned int checksum = 0;
- if(!crc32)
- crc32_init();
+ crc32_init();
for(t=0;t<str->len;t++) {
checksum = checksum>>8 ^ crc32[(str->str[t]^checksum)&0xff];
}
{
unsigned int checksum = 0;
const char*p = str;
- if(!crc32)
- crc32_init();
+ crc32_init();
while(*p) {
checksum = checksum>>8 ^ crc32[(*p^checksum)&0xff];
p++;
return;
}
+char int_equals(const void*o1, const void*o2)
+{
+ return o1==o2;
+}
+unsigned int int_hash(const void*o)
+{
+ return string_hash3((const char*)&o, sizeof(o));
+}
+void* int_dup(const void*o)
+{
+ return (void*)o;
+}
+void int_free(void*o)
+{
+ return;
+}
+
char charptr_equals(const void*o1, const void*o2)
{
if(!o1 || !o2)
string_free(o);
}
+type_t int_type = {
+ equals: int_equals,
+ hash: int_hash,
+ dup: int_dup,
+ free: int_free,
+};
+
type_t ptr_type = {
equals: ptr_equals,
hash: ptr_hash,
{
unsigned int hash = h->key_type->hash(key);
dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+
+ if(!h->hashsize)
+ dict_expand(h, 1);
+
unsigned int hash2 = hash % h->hashsize;
e->key = h->key_type->dup(key);
dictentry_t*e = h->slots[t];
while(e) {
if(h->key_type!=&charptr_type) {
- fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
+ fprintf(fi, "%s%08x=%08x\n", prefix, (int)e->key, (int)e->data);
} else {
- fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
+ fprintf(fi, "%s%s=%08x\n", prefix, (char*)e->key, (int)e->data);
}
e = e->next;
}
while(e) {
if(h->key_type->equals(e->key, key)) {
dictentry_t*next = e->next;
- rfx_free((void*)e->key);
+ h->key_type->free(e->key);
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ if(e == head) {
+ h->slots[hash] = next;
+ } else {
+ assert(prev);
+ prev->next = next;
+ }
+ h->num--;
+ return 1;
+ }
+ prev = e;
+ e = e->next;
+ }
+ return 0;
+}
+
+char dict_del2(dict_t*h, const void*key, void*data)
+{
+ if(!h->num)
+ return 0;
+ unsigned int hash = h->key_type->hash(key) % h->hashsize;
+ dictentry_t*head = h->slots[hash];
+ dictentry_t*e = head, *prev=0;
+ while(e) {
+ if(h->key_type->equals(e->key, key) && e->data == data) {
+ dictentry_t*next = e->next;
+ h->key_type->free(e->key);
memset(e, 0, sizeof(dictentry_t));
rfx_free(e);
if(e == head) {
rfx_free(dict);
}
+// ------------------------------- mtf_t --------------------------------------
+mtf_t* mtf_new(type_t*type)
+{
+ NEW(mtf_t, mtf);
+ mtf->type = type;
+ return mtf;
+}
+void mtf_increase(mtf_t*m, const void*key)
+{
+ mtf_item_t*item = m->first;
+ mtf_item_t*last = 0;
+ while(item) {
+ if(m->type->equals(item->key, key)) {
+ item->num++;
+ if(item->num>m->first->num) {
+ if(last) last->next = item->next;
+ else m->first = item->next;
+ item->next = m->first;
+ m->first = item;
+ }
+ return;
+ }
+ last = item;
+ item = item->next;
+ }
+ NEW(mtf_item_t,n);
+ if(last) last->next = n;
+ else m->first = n;
+ n->key = key;
+ n->num = 1;
+}
+void mtf_destroy(mtf_t*m)
+{
+ if(!m) return;
+ mtf_item_t*item = m->first;
+ m->first = 0;
+ while(item) {
+ mtf_item_t*next = item->next;
+ item->next = 0;
+ free(item);
+ item = next;
+ }
+ free(m);
+}
+
// ------------------------------- map_t --------------------------------------
typedef struct _map_internal_t
static void dumpmapentry(void*data, const void*key, void*value)
{
FILE*fi = (FILE*)data;
- fprintf(fi, "%s=%s\n", key, (char*)value);
+ fprintf(fi, "%s=%s\n", (char*)key, (char*)value);
}
void map_dump(map_t*map, FILE*fi, const char*prefix)
{
}
void*array_getkey(array_t*array, int nr) {
if(nr > array->num || nr<0) {
- printf("error: reference to element %d in array[%d]\n", nr, array->num);
+ fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
return 0;
}
return array->d[nr].name;
}
void*array_getvalue(array_t*array, int nr) {
if(nr > array->num || nr<0) {
- printf("error: reference to element %d in array[%d]\n", nr, array->num);
+ fprintf(stderr, "error: reference to element %d in array[%d]\n", nr, array->num);
return 0;
}
return array->d[nr].data;
git.asbjorn.biz / swftools.git / blobdiff