#include <stdlib.h>
#include <stdio.h>
+#include <stdarg.h>
#include <string.h>
#include <assert.h>
#include <memory.h>
{
return strdup_n(string, len);
}
+char* allocprintf(const char*format, ...)
+{
+ va_list arglist1;
+ va_start(arglist1, format);
+ char dummy;
+ int l = vsnprintf(&dummy, 1, format, arglist1);
+ va_end(arglist1);
+
+ va_list arglist2;
+ va_start(arglist2, format);
+ char*buf = malloc(l+1);
+ vsnprintf(buf, l+1, format, arglist2);
+ va_end(arglist2);
+ return buf;
+}
// ------------------------------- mem_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];
h->elements[0] = h->elements[--h->size];
down(h,0);
}
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;
}
static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
{
if(!*t) {
- (*t) = rfx_calloc(sizeof(trie_t));
+ (*t) = rfx_calloc(sizeof(trielayer_t));
(*t)->rest = (unsigned char*)strdup(id);
(*t)->data = data;
return 0;
} else {
char contains = trie_contains(t, id);
void*olddata = contains?trie_lookup(t, id):0;
- trie_rollback_removes(t, id, data);
_trie_put(&t->start, id, data);
if(contains) {
trie_rollback_adds(t, id, olddata);
}
+ trie_rollback_removes(t, id, data);
}
}
char trie_remove(trie_t*t, unsigned const char*id)
void*olddata = trie_lookup(t, id);
char exists = _trie_remove(t->start, id);
if(exists) {
- trie_rollback_removes(t, id, olddata);
+ trie_rollback_adds(t, id, olddata);
}
return exists;
}
typedef struct _triememory {
const unsigned char*key;
void*data;
+ char del; // 0/1
struct _triememory*next;
} triememory_t;
typedef struct _trierollback {
- triememory_t*add;
- triememory_t*remove;
+ triememory_t*ops;
struct _trierollback*prev;
} trierollback_t;
-static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
+static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
{
trierollback_t*rollback = (trierollback_t*)t->rollback;
triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
m->key = id;
m->data = data;
- m->next = rollback->add;
- rollback->add = m;
+ m->del = 0;
+ m->next = rollback->ops;
+ rollback->ops = m;
}
-static void trie_rollback_adds(trie_t*t, unsigned const char*id, void*data)
+static void trie_rollback_removes(trie_t*t, unsigned const char*id, void*data)
{
trierollback_t*rollback = (trierollback_t*)t->rollback;
triememory_t*m = (triememory_t*)rfx_calloc(sizeof(triememory_t));
m->key = id;
m->data = data;
- m->next = rollback->remove;
- rollback->remove = m;
+ m->del = 1;
+ m->next = rollback->ops;
+ rollback->ops = m;
+}
+
+void _trie_dump(trielayer_t*t, char*buffer, int pos)
+{
+ int i;
+ for(i=0;i<256;i++) {
+ if(t->row[i]) {
+ buffer[pos]=i;
+ _trie_dump(t->row[i], buffer, pos+1);
+ }
+ }
+ if(t->rest) {
+ buffer[pos]=0;
+ printf("%s%s %08x\n", buffer, t->rest, t->data);
+ }
+}
+
+void trie_dump(trie_t*t)
+{
+ char buffer[256];
+ _trie_dump(t->start, buffer, 0);
}
+
void trie_remember(trie_t*t)
{
trierollback_t*old = (trierollback_t*)t->rollback;
}
t->rollback = ((trierollback_t*)t->rollback)->prev;
- triememory_t*remove = rollback->remove;
- while(remove) {
- triememory_t*next = remove->next;
- if(!trie_remove(t, remove->key)) {
- fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", remove->key);
+ triememory_t*op = rollback->ops;
+ while(op) {
+ triememory_t*next = op->next;
+ if(op->del) {
+ if(!_trie_remove(t->start, op->key)) {
+ fprintf(stderr, "Internal error: can't delete key %s in trie during rollback\n", op->key);
+ }
+ } else {
+ if(_trie_put(&t->start, op->key, op->data)) {
+ fprintf(stderr, "Internal error: overwrote key %s in trie during rollback\n", op->key);
+ }
}
- free(remove);
- remove = next;
- }
- triememory_t*add = rollback->add;
- while(add) {
- triememory_t*next = add->next;
- trie_put(t, add->key, add->data);
- add = next;
+ free(op);
+ op = next;
}
}
{
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);
void dict_destroy(dict_t*dict)
{
+ if(!dict)
+ return;
dict_clear(dict);
rfx_free(dict);
}