mdw@git.distorted.org.uk Git - sgt/agedu/blob - trie.h

   1 /*
   2  * trie.h: functions to build and search a trie-like structure
   3  * mapping pathnames to file records.
   4  */
   5
   6 #include <sys/types.h>
   7
   8 /*
   9  * An entry in the trie file describing an actual file.
  10  */
  11 struct trie_file {
  12     unsigned long long size;
  13     unsigned long long atime;
  14 };
  15
  16 /* ----------------------------------------------------------------------
  17  * Functions which can be passed a list of pathnames and file data
  18  * in strict order, and will build up a trie and write it out to a
  19  * file.
  20  */
  21
  22 typedef struct triebuild triebuild;
  23
  24 /*
  25  * Create a new trie-building context given a writable file
  26  * descriptor, which should point to the start of an empty file.
  27  */
  28 triebuild *triebuild_new(int fd);
  29
  30 /*
  31  * Add a trie_file record to the trie. The pathnames should appear
  32  * in trie collation order (i.e. strict ASCII sorting order except
  33  * that / is moved so that it sorts before any other non-NUL
  34  * character), on penalty of assertion failure.
  35  */
  36 void triebuild_add(triebuild *tb, const char *pathname,
  37                    const struct trie_file *file);
  38
  39 /*
  40  * Put the finishing touches to the contents of the output file
  41  * once all the trie_file records are present. Returns the total
  42  * number of elements in the trie.
  43  */
  44 int triebuild_finish(triebuild *tb);
  45
  46 /*
  47  * Free the context. (Does not close the file, but may leave the
  48  * file pointer in an arbitrary place.)
  49  */
  50 void triebuild_free(triebuild *tb);
  51
  52 /* ----------------------------------------------------------------------
  53  * Anomalous function which modifies a trie after it's memory-mapped.
  54  */
  55
  56 /*
  57  * Invent new fake atimes for each directory in the trie, by
  58  * taking the maximum (latest) of the directory's previously
  59  * stored atime and the atimes of everything below it.
  60  */
  61 void trie_fake_dir_atimes(void *t);
  62
  63 /* ----------------------------------------------------------------------
  64  * Functions to query a trie given a pointer to the start of the
  65  * memory-mapped file.
  66  */
  67
  68 /*
  69  * Check the magic numbers at the start of the file. This should also
  70  * verify that the file was built on a platform whose structure layout
  71  * matches that of the agedu reading it. Returns nonzero on successful
  72  * match, zero on mismatch.
  73  */
  74 int trie_check_magic(const void *t);
  75
  76 /*
  77  * Return the path separator character in use in the trie.
  78  */
  79 char trie_pathsep(const void *t);
  80
  81 /*
  82  * Return the length of the longest pathname stored in the trie,
  83  * including its trailing NUL.
  84  */
  85 size_t trie_maxpathlen(const void *t);
  86
  87 /*
  88  * Determine the total number of entries in the trie which sort
  89  * strictly before the given pathname (irrespective of whether the
  90  * pathname actually exists in the trie).
  91  */
  92 unsigned long trie_before(const void *t, const char *pathname);
  93
  94 /*
  95  * Return the pathname for the nth entry in the trie, written into
  96  * the supplied buffer (which must be large enough, i.e. at least
  97  * trie_maxpathlen(t) bytes).
  98  */
  99 void trie_getpath(const void *t, unsigned long n, char *buf);
 100
 101 /*
 102  * Return the trie_file * for the nth entry in the trie.
 103  */
 104 const struct trie_file *trie_getfile(const void *t, unsigned long n);
 105
 106 /*
 107  * Return the total number of entries in the whole trie.
 108  */
 109 unsigned long trie_count(const void *t);
 110
 111 /*
 112  * Enumerate all the trie_file records in the trie, in sequence,
 113  * and return pointers to their trie_file structures. Returns NULL
 114  * at end of list, naturally.
 115  *
 116  * Optionally returns the pathnames as well: if "buf" is non-NULL
 117  * then it is expected to point to a buffer large enough to store
 118  * all the pathnames in the trie (i.e. at least trie_maxpathlen(t)
 119  * bytes). This buffer is also expected to remain unchanged
 120  * between calls to triewalk_next(), or else the returned
 121  * pathnames will be corrupted.
 122  */
 123 typedef struct triewalk triewalk;
 124 triewalk *triewalk_new(const void *t);
 125 const struct trie_file *triewalk_next(triewalk *tw, char *buf);
 126 void triewalk_rebase(triewalk *tw, const void *t);
 127 void triewalk_free(triewalk *tw);
 128
 129 /* ----------------------------------------------------------------------
 130  * The trie file also contains an index managed by index.h, so we
 131  * must be able to ask about that too.
 132  */
 133 void trie_set_index_offset(void *t, off_t ptr);
 134 off_t trie_get_index_offset(const void *t);
 135
 136 /* ----------------------------------------------------------------------
 137  * Utility functions not directly involved with the trie.
 138  */
 139
 140 /*
 141  * Given a pathname in a buffer, adjust the pathname in place so
 142  * that it points at a string which, when passed to trie_before,
 143  * will reliably return the index of the thing that comes after
 144  * that pathname and all its descendants. Usually this is done by
 145  * suffixing ^A (since foo^A is guaranteeably the first thing that
 146  * sorts after foo and foo/stuff); however, if the pathname
 147  * actually ends in a path separator (e.g. if it's just "/"), that
 148  * must be stripped off first.
 149  */
 150 void make_successor(char *pathbuf);