X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/agedu/blobdiff_plain/05b0f827bf0178896f9484fe093fb0d99fa67ba2..2e6654103f93c61206cf60b65bc261ecd164e424:/trie.c

diff --git a/trie.c b/trie.c
index 1344bdf..ad0cd84 100644
--- a/trie.c
+++ b/trie.c
@@ -2,17 +2,8 @@
  * trie.c: implementation of trie.h.
  */
 
-#include <assert.h>
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include <errno.h>
-
-#include <sys/types.h>
-#include <unistd.h>
-
 #include "agedu.h"
-#include "malloc.h"
+#include "alloc.h"
 #include "trie.h"
 
 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
@@ -24,9 +15,9 @@
  */
 static int trieccmp(unsigned char a, unsigned char b)
 {
-    a = (a == '\0' ? '\0' : a == pathsep ? '\1' : a+1);
-    b = (b == '\0' ? '\0' : b == pathsep ? '\1' : b+1);
-    return (int)a - (int)b;
+    int ia = (a == '\0' ? '\0' : a == pathsep ? '\1' : a+1);
+    int ib = (b == '\0' ? '\0' : b == pathsep ? '\1' : b+1);
+    return ia - ib;
 }
 
 static int triencmp(const char *a, size_t alen,
@@ -227,7 +218,8 @@ static off_t triebuild_unwind(triebuild *tb, int targetdepth, int *outcount)
     while (depth > targetdepth) {
 	int odepth = depth;
 	while (depth > targetdepth &&
-	       (depth-1 > tb->switchsize || tb->switches[depth-1].len == 0))
+	       (depth-1 > tb->switchsize || !tb->switches ||
+		tb->switches[depth-1].len == 0))
 	    depth--;
 	if (odepth > depth) {
 	    /*
@@ -601,7 +593,36 @@ void trie_getpath(const void *t, unsigned long n, char *buf)
 	    assert(i < sw->len);
 	}
     }
-}    
+}
+
+const struct trie_file *trie_getfile(const void *t, unsigned long n)
+{
+    const struct trie_header *hdr = NODE(t, 0, trie_header);
+    off_t off = hdr->root;
+
+    while (1) {
+	const struct trie_common *node = NODE(t, off, trie_common);
+	if (node->type == TRIE_LEAF) {
+	    const struct trie_leaf *leaf = NODE(t, off, trie_leaf);
+	    return &leaf->file;
+	} else if (node->type == TRIE_STRING) {
+	    const struct trie_string *st = NODE(t, off, trie_string);
+	    off = st->subnode;
+	} else if (node->type == TRIE_SWITCH) {
+	    const struct trie_switch *sw = NODE(t, off, trie_switch);
+	    int i;
+
+	    for (i = 0; i < sw->len; i++) {
+		if (n < sw->sw[i].subcount) {
+		    off = sw->sw[i].subnode;
+		    break;
+		} else
+		    n -= sw->sw[i].subcount;
+	    }
+	    assert(i < sw->len);
+	}
+    }
+}
 
 unsigned long trie_count(const void *t)
 {
@@ -637,6 +658,19 @@ triewalk *triewalk_new(const void *vt)
 
     return tw;
 }
+
+void triewalk_rebase(triewalk *tw, const void *t)
+{
+    ptrdiff_t diff = ((const unsigned char *)t - (const unsigned char *)(tw->t));
+    int i;
+
+    tw->t = t;
+
+    for (i = 0; i < tw->nswitches; i++)
+	tw->switches[i].sw = (const struct trie_switch *)
+	    ((const unsigned char *)(tw->switches[i].sw) + diff);
+}
+
 const struct trie_file *triewalk_next(triewalk *tw, char *buf)
 {
     off_t off;