+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;
+ struct _triememory*next;
+} triememory_t;
+
+typedef struct _trierollback {
+ triememory_t*add;
+ triememory_t*remove;
+ struct _trierollback*prev;
+} trierollback_t;
+
+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->add;
+ rollback->add = m;
+}
+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->remove;
+ rollback->remove = m;
+}
+
+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*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);
+ }
+ 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;
+ }
+}
+