70322ae3 |
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 { |
84849cbd |
12 | unsigned long long size; |
70322ae3 |
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 | /* ---------------------------------------------------------------------- |
05b0f827 |
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 | /* ---------------------------------------------------------------------- |
70322ae3 |
64 | * Functions to query a trie given a pointer to the start of the |
65 | * memory-mapped file. |
66 | */ |
67 | |
68 | /* |
269fa2d1 |
69 | * Return the path separator character in use in the trie. |
70 | */ |
71 | char trie_pathsep(const void *t); |
72 | |
73 | /* |
70322ae3 |
74 | * Return the length of the longest pathname stored in the trie, |
75 | * including its trailing NUL. |
76 | */ |
77 | size_t trie_maxpathlen(const void *t); |
78 | |
79 | /* |
80 | * Determine the total number of entries in the trie which sort |
81 | * strictly before the given pathname (irrespective of whether the |
82 | * pathname actually exists in the trie). |
83 | */ |
84 | unsigned long trie_before(const void *t, const char *pathname); |
85 | |
86 | /* |
87 | * Return the pathname for the nth entry in the trie, written into |
88 | * the supplied buffer (which must be large enough, i.e. at least |
89 | * trie_maxpathlen(t) bytes). |
90 | */ |
91 | void trie_getpath(const void *t, unsigned long n, char *buf); |
92 | |
93 | /* |
94 | * Return the total number of entries in the whole trie. |
95 | */ |
96 | unsigned long trie_count(const void *t); |
97 | |
98 | /* |
99 | * Enumerate all the trie_file records in the trie, in sequence, |
100 | * and return pointers to their trie_file structures. Returns NULL |
101 | * at end of list, naturally. |
102 | * |
103 | * Optionally returns the pathnames as well: if "buf" is non-NULL |
104 | * then it is expected to point to a buffer large enough to store |
105 | * all the pathnames in the trie (i.e. at least trie_maxpathlen(t) |
106 | * bytes). This buffer is also expected to remain unchanged |
107 | * between calls to triewalk_next(), or else the returned |
108 | * pathnames will be corrupted. |
109 | */ |
110 | typedef struct triewalk triewalk; |
111 | triewalk *triewalk_new(const void *t); |
112 | const struct trie_file *triewalk_next(triewalk *tw, char *buf); |
522edd92 |
113 | void triewalk_rebase(triewalk *tw, const void *t); |
70322ae3 |
114 | void triewalk_free(triewalk *tw); |
115 | |
116 | /* ---------------------------------------------------------------------- |
117 | * The trie file also contains an index managed by index.h, so we |
118 | * must be able to ask about that too. |
119 | */ |
120 | void trie_set_index_offset(void *t, off_t ptr); |
121 | off_t trie_get_index_offset(const void *t); |
256c29a2 |
122 | |
123 | /* ---------------------------------------------------------------------- |
124 | * Utility functions not directly involved with the trie. |
125 | */ |
126 | |
127 | /* |
128 | * Given a pathname in a buffer, adjust the pathname in place so |
129 | * that it points at a string which, when passed to trie_before, |
130 | * will reliably return the index of the thing that comes after |
131 | * that pathname and all its descendants. Usually this is done by |
132 | * suffixing ^A (since foo^A is guaranteeably the first thing that |
133 | * sorts after foo and foo/stuff); however, if the pathname |
134 | * actually ends in a path separator (e.g. if it's just "/"), that |
135 | * must be stripped off first. |
136 | */ |
137 | void make_successor(char *pathbuf); |