#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 --------------------------------------
void* heap_chopmax(heap_t*h)
{
void*p = h->elements[0];
+ assert(h->size);
h->elements[0] = h->elements[--h->size];
down(h,0);
return p;
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;
}
}
void dict_destroy(dict_t*dict)
{
+ if(!dict)
+ return;
dict_clear(dict);
rfx_free(dict);
}