* 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 "alloc.h"
#include "trie.h"
*/
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,
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) {
/*
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)
{
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;