* 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 "malloc.h"
+#include "agedu.h"
+#include "alloc.h"
#include "trie.h"
#define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
-extern char pathsep;
-
/*
* Compare functions for pathnames. Returns the relative order of
* the names, like strcmp; also passes back the offset of the
*/
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,
char string[];
};
+static const char magic_ident_string[16] = "agedu index file";
+struct trie_magic {
+ /*
+ * 'Magic numbers' to go at the start of an agedu index file.
+ * These are checked (using trie_check_magic) by every agedu mode
+ * which reads a pre-existing index.
+ *
+ * As well as identifying an agedu file from any other kind of
+ * file, this magic-number structure is also intended to detect
+ * agedu files which were written on the wrong platform and hence
+ * whose structure layouts are incompatible. To make that as
+ * reliable as possible, I design the structure of magic numbers
+ * as follows: it contains one of each integer type I might use,
+ * each containing a different magic number, and each followed by
+ * a char to indicate where it ends in the file. One byte is set
+ * to the length of the magic-number structure itself, which means
+ * that no two structures of different lengths can possibly
+ * compare equal even if by some chance they match up to the
+ * length of the shorter one. Finally, the whole magic number
+ * structure is memset to another random byte value before
+ * initialising any of these fields, so that padding in between
+ * can be readily identified.
+ */
+ char ident[16]; /* human-readable string */
+
+ unsigned char magic_len;
+
+ unsigned long long longlong_magic;
+ unsigned char postlonglong_char_magic;
+
+ off_t offset_magic;
+ unsigned char postoffset_char_magic;
+
+ size_t size_magic;
+ unsigned char postsize_char_magic;
+
+ void *null_pointer;
+ unsigned char postptr_char_magic;
+
+ unsigned long long_magic;
+ unsigned char postlong_char_magic;
+
+ unsigned short short_magic;
+ unsigned char postshort_char_magic;
+};
+
struct trie_header {
- unsigned long magic;
+ struct trie_magic magic;
off_t root, indexroot;
int count;
size_t maxpathlen;
char string[1];
} str;
};
-#define TRIE_MAGIC 0x75646761UL
#define TRIE_ALIGN alignof(union trie_node)
+static void setup_magic(struct trie_magic *th)
+{
+ /*
+ * Magic values are chosen so that every byte value used is
+ * distinct (so that we can't fail to spot endianness issues), and
+ * we cast 64 bits of data into each integer type just in case
+ * the platform makes it longer than we expect it to be.
+ */
+
+ memset(th, 0xCDU, sizeof(*th));
+
+ th->magic_len = sizeof(*th);
+
+ memcpy(th->ident, magic_ident_string, 16);
+
+ th->longlong_magic = 0x5583F34D5D84F73CULL;
+ th->postlonglong_char_magic = 0xDDU;
+
+ th->offset_magic = (off_t)0xB39BF9AD56D48E0BULL;
+ th->postoffset_char_magic = 0x95U;
+
+ th->size_magic = (size_t)0x6EC752B0EEAEBAC1ULL;
+ th->postsize_char_magic = 0x77U;
+
+ th->null_pointer = NULL;
+ th->postptr_char_magic = 0x71U;
+
+ th->long_magic = (unsigned long)0xA81A5E1F44334716ULL;
+ th->postlong_char_magic = 0x99U;
+
+ th->short_magic = (unsigned short)0x0C8BD7984B68D9FCULL;
+ th->postshort_char_magic = 0x35U;
+}
+
/* ----------------------------------------------------------------------
* Trie-building functions.
*/
{
tb->offset = off;
if (lseek(tb->fd, off, SEEK_SET) < 0) {
- fprintf(stderr, "agedu: lseek: %s\n", strerror(errno));
+ fprintf(stderr, PNAME ": lseek: %s\n", strerror(errno));
exit(1);
}
}
while (len > 0) {
int ret = write(tb->fd, buf, len);
if (ret < 0) {
- fprintf(stderr, "agedu: write: %s\n", strerror(errno));
+ fprintf(stderr, PNAME ": write: %s\n", strerror(errno));
exit(1);
}
len -= ret;
tb->switchsize = 0;
tb->maxpathlen = 0;
- th.magic = TRIE_MAGIC;
+ setup_magic(&th.magic);
th.root = th.count = 0;
th.indexroot = 0;
th.maxpathlen = 0;
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) {
/*
{
struct trie_header th;
- th.magic = TRIE_MAGIC;
+ setup_magic(&th.magic);
th.root = triebuild_unwind(tb, 0, &th.count);
th.indexroot = 0;
th.maxpathlen = tb->maxpathlen;
}
/* ----------------------------------------------------------------------
+ * Memory-mapped trie modification.
+ */
+
+#define MNODE(t, off, type) \
+ ((struct type *)((char *)(t) + (off)))
+
+static unsigned long long fake_atime_recurse(void *t, struct trie_common *node,
+ int last_seen_pathsep)
+{
+ while (node->type == TRIE_STRING) {
+ struct trie_string *st = (struct trie_string *)node;
+ last_seen_pathsep = (st->string[st->stringlen-1] == pathsep);
+ node = MNODE(t, st->subnode, trie_common);
+ }
+
+ if (node->type == TRIE_LEAF) {
+ struct trie_leaf *leaf = (struct trie_leaf *)node;
+ return leaf->file.atime;
+ } else if (assert(node->type == TRIE_SWITCH), 1) {
+ struct trie_switch *sw = (struct trie_switch *)node;
+ const char *chars = (const char *)&sw->sw[sw->len];
+ unsigned long long max = 0, subdir, ret;
+ int i;
+ int slashindex = -1, bareindex = -1;
+
+ /*
+ * First, process all the children of this node whose
+ * switch characters are not \0 or pathsep. We do this in
+ * reverse order so as to maintain best cache locality
+ * (tracking generally backwards through the file), though
+ * it doesn't matter semantically.
+ *
+ * For each of these children, we're just recursing into
+ * it to do any fixups required below it, and amalgamating
+ * the max atimes we get back.
+ */
+ for (i = sw->len; i-- > 0 ;) {
+ if (chars[i] == '\0') {
+ bareindex = i;
+ } else if (chars[i] == pathsep) {
+ slashindex = i;
+ } else {
+ ret = fake_atime_recurse(t, MNODE(t, sw->sw[i].subnode,
+ trie_common), 0);
+ if (max < ret)
+ max = ret;
+ }
+ }
+
+ /*
+ * Now we have at most two child nodes left to deal with:
+ * one with a slash (or general pathsep) and one with \0.
+ *
+ * If there's a slash node and a bare node, then the slash
+ * node contains precisely everything inside the directory
+ * described by the bare node; so we must retrieve the max
+ * atime for the slash node and use it to fix up the bare
+ * node.
+ *
+ * If there's only a bare node but the pathname leading up
+ * to this point ends in a slash, then _all_ of the child
+ * nodes of this node contain stuff inside the directory
+ * described by the bare node; so we use the whole of the
+ * maximum value we've computed so far to update the bare
+ * node.
+ */
+ if (slashindex >= 0) {
+ ret = fake_atime_recurse(t, MNODE(t, sw->sw[slashindex].subnode,
+ trie_common), 1);
+ if (max < ret)
+ max = ret;
+
+ subdir = ret;
+ } else if (last_seen_pathsep) {
+ subdir = max;
+ } else {
+ /* Don't update the bare subnode at all. */
+ subdir = 0;
+ }
+
+ if (bareindex >= 0) {
+ struct trie_leaf *leaf;
+
+ leaf = MNODE(t, sw->sw[bareindex].subnode, trie_leaf);
+
+ if (leaf && leaf->c.type == TRIE_LEAF) {
+ if (leaf->file.atime < subdir)
+ leaf->file.atime = subdir;
+ ret = leaf->file.atime;
+ } else {
+ /* Shouldn't really happen, but be cautious anyway */
+ ret = fake_atime_recurse(t, &leaf->c, 0);
+ }
+
+ if (max < ret)
+ max = ret;
+ }
+
+ return max;
+ }
+ return 0; /* placate lint */
+}
+
+void trie_fake_dir_atimes(void *t)
+{
+ struct trie_header *hdr = MNODE(t, 0, trie_header);
+ struct trie_common *node = MNODE(t, hdr->root, trie_common);
+
+ fake_atime_recurse(t, node, 1);
+}
+
+/* ----------------------------------------------------------------------
* Querying functions.
*/
#define NODE(t, off, type) \
((const struct type *)((const char *)(t) + (off)))
+int trie_check_magic(const void *t)
+{
+ const struct trie_header *hdr = NODE(t, 0, trie_header);
+ struct trie_magic magic;
+
+ setup_magic(&magic);
+ return !memcmp(&magic, &hdr->magic, sizeof(magic));
+}
+
size_t trie_maxpathlen(const void *t)
{
const struct trie_header *hdr = NODE(t, 0, trie_header);
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;
{
return ((const struct trie_header *)t)->indexroot;
}
+
+void make_successor(char *pathbuf)
+{
+ int len = strlen(pathbuf);
+ if (len > 0 && pathbuf[len-1] == pathsep)
+ len--;
+ pathbuf[len] = '\001';
+ pathbuf[len+1] = '\0';
+}
~mdw / sgt / agedu / blobdiff