+// ------------------------------- trie --------------------------------------
+
+trie_t*trie_new()
+{
+ return (trie_t*)rfx_calloc(sizeof(trie_t));
+}
+static char _trie_put(trielayer_t**t, unsigned const char*id, void*data)
+{
+ if(!*t) {
+ (*t) = rfx_calloc(sizeof(trielayer_t));
+ (*t)->rest = (unsigned char*)strdup(id);
+ (*t)->data = data;
+ return 0;
+ }
+ if((*t)->rest && (*t)->rest[0]) {
+ // make room: shift whatever's currently in here one node down
+ _trie_put(&(*t)->row[(*t)->rest[0]], (*t)->rest+1, (*t)->data);
+ (*t)->rest = 0;
+ }
+ if(id[0]) {
+ return _trie_put(&(*t)->row[id[0]], id+1, data);
+ } else {
+ char overwrite = 0;
+ if((*t)->rest)
+ overwrite = 1;
+ (*t)->rest = 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)) {
+ free(t->rest);
+ t->rest = 0;
+ return 1;
+ }
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+
+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);
+
+void trie_put(trie_t*t, unsigned const char*id, void*data)
+{
+ if(!t->rollback) {
+ _trie_put(&t->start, id, data);
+ } else {
+ char contains = trie_contains(t, id);
+ void*olddata = contains?trie_lookup(t, id):0;
+ _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)
+{
+ if(!t->rollback) {
+ return _trie_remove(t->start, id);
+ } else {
+ void*olddata = trie_lookup(t, id);
+ char exists = _trie_remove(t->start, id);
+ if(exists) {
+ trie_rollback_adds(t, id, olddata);
+ }
+ return exists;
+ }
+}
+int trie_contains(trie_t*trie, unsigned const char*id)
+{
+ trielayer_t*t = trie->start;
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id))
+ return 1;
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+void* trie_lookup(trie_t*trie, unsigned const char*id)
+{
+ trielayer_t*t = trie->start;
+ while(t) {
+ if(t->rest && !strcmp(t->rest, id))
+ return t->data;
+ if(!*id)
+ return 0;
+ t = t->row[*id++];
+ }
+ return 0;
+}
+
+typedef struct _triememory {
+ const unsigned char*key;
+ void*data;
+ char del; // 0/1
+ struct _triememory*next;
+} triememory_t;
+
+typedef struct _trierollback {
+ triememory_t*ops;
+ struct _trierollback*prev;
+} trierollback_t;
+
+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->del = 0;
+ m->next = rollback->ops;
+ rollback->ops = m;
+}
+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->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*)rfx_calloc(sizeof(trierollback_t));
+ ((trierollback_t*)t->rollback)->prev = old;
+}
+
+void trie_rollback(trie_t*t)
+{
+ trierollback_t*rollback = (trierollback_t*)t->rollback;
+ if(!rollback) {
+ fprintf(stderr, "Internal error: can't roll back this trie any further\n");
+ return;
+ }
+ t->rollback = ((trierollback_t*)t->rollback)->prev;
+
+ 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(op);
+ op = next;
+ }
+}
+
+
+// ------------------------------- crc32 --------------------------------------
+static unsigned int crc32[256];
+static char crc32_initialized=0;
+static void crc32_init(void)
+{
+ int t;
+ if(crc32_initialized)
+ return;
+ crc32_initialized = 1;
+ for(t=0; t<256; t++) {
+ unsigned int c = t;
+ int s;
+ for (s = 0; s < 8; s++) {
+ c = (0xedb88320L*(c&1)) ^ (c >> 1);
+ }
+ crc32[t] = c;
+ }
+}