47
by Alan Jenkins
modprobe: use binary index files |
1 |
/* index.c: module index file shared functions for modprobe and depmod
|
2 |
Copyright (C) 2008 Alan Jenkins <alan-jenkins@tuffmail.co.uk>.
|
|
3 |
||
4 |
These programs are free software; you can redistribute it and/or modify
|
|
5 |
it under the terms of the GNU General Public License as published by
|
|
6 |
the Free Software Foundation; either version 2 of the License, or
|
|
7 |
(at your option) any later version.
|
|
8 |
||
9 |
This program is distributed in the hope that it will be useful,
|
|
10 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
11 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
12 |
GNU General Public License for more details.
|
|
13 |
||
14 |
You should have received a copy of the GNU General Public License
|
|
15 |
along with these programs. If not, see <http://www.gnu.org/licenses/>.
|
|
16 |
*/
|
|
17 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
18 |
#include <arpa/inet.h> /* htonl */ |
46
by Jon Masters
depmod: Add binary index files |
19 |
#include <stdlib.h> |
20 |
#include <stdio.h> |
|
21 |
#include <string.h> |
|
22 |
#include <errno.h> |
|
23 |
#include <fnmatch.h> |
|
24 |
||
130.1.6
by Alan Jenkins
Move a few common functions and macros to "util" |
25 |
#include "util.h" |
46
by Jon Masters
depmod: Add binary index files |
26 |
#include "logging.h" |
27 |
#include "index.h" |
|
28 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
29 |
#include "testing.h" |
30 |
||
46
by Jon Masters
depmod: Add binary index files |
31 |
/*
|
32 |
* Index abstract data type (used only by depmod)
|
|
33 |
*/
|
|
34 |
||
35 |
struct index_node *index_create() |
|
36 |
{
|
|
37 |
struct index_node *node; |
|
38 |
||
39 |
node = NOFAIL(calloc(sizeof(struct index_node), 1)); |
|
40 |
node->prefix = NOFAIL(strdup("")); |
|
41 |
node->first = INDEX_CHILDMAX; |
|
42 |
||
43 |
return node; |
|
44 |
}
|
|
45 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
46 |
void index_values_free(struct index_value *values) |
47 |
{
|
|
48 |
while (values) { |
|
49 |
struct index_value *value = values; |
|
50 |
||
51 |
values = value->next; |
|
52 |
free(value); |
|
53 |
}
|
|
54 |
}
|
|
55 |
||
46
by Jon Masters
depmod: Add binary index files |
56 |
void index_destroy(struct index_node *node) |
57 |
{
|
|
58 |
int c; |
|
59 |
||
60 |
for (c = node->first; c <= node->last; c++) { |
|
61 |
struct index_node *child = node->children[c]; |
|
62 |
||
63 |
if (child) |
|
64 |
index_destroy(child); |
|
65 |
}
|
|
83
by Alan Jenkins
add module ordering support for binary indexes |
66 |
index_values_free(node->values); |
46
by Jon Masters
depmod: Add binary index files |
67 |
free(node->prefix); |
68 |
free(node); |
|
69 |
}
|
|
70 |
||
71 |
static void index__checkstring(const char *str) |
|
72 |
{
|
|
73 |
int i; |
|
74 |
||
75 |
for (i = 0; str[i]; i++) { |
|
76 |
int ch = str[i]; |
|
77 |
||
78 |
if (ch >= INDEX_CHILDMAX) |
|
79 |
fatal("Module index: bad character '%c'=0x%x - only 7-bit ASCII is supported:" |
|
80 |
"\n%s\n", (char) ch, (int) ch, str); |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
81 |
}
|
82 |
}
|
|
83 |
||
84 |
static int add_value(struct index_value **values, |
|
85 |
const char *value, unsigned int priority) |
|
86 |
{
|
|
87 |
struct index_value *v; |
|
159
by Alan Jenkins
depmod: fix uninitialized value error in "depmod --warn" code |
88 |
int duplicate = 0; |
83
by Alan Jenkins
add module ordering support for binary indexes |
89 |
int len; |
90 |
||
91 |
/* report the presence of duplicate values */
|
|
92 |
for (v = *values; v; v = v->next) { |
|
93 |
if (streq(v->value, value)) |
|
94 |
duplicate = 1; |
|
95 |
}
|
|
96 |
||
97 |
/* find position to insert value */
|
|
98 |
while (*values && (*values)->priority < priority) |
|
99 |
values = &(*values)->next; |
|
100 |
||
101 |
len = strlen(value); |
|
102 |
v = NOFAIL(calloc(sizeof(struct index_value) + len + 1, 1)); |
|
103 |
v->next = *values; |
|
104 |
v->priority = priority; |
|
105 |
memcpy(v->value, value, len + 1); |
|
106 |
*values = v; |
|
107 |
||
108 |
return duplicate; |
|
109 |
}
|
|
110 |
||
111 |
int index_insert(struct index_node *node, const char *key, |
|
112 |
const char *value, unsigned int priority) |
|
46
by Jon Masters
depmod: Add binary index files |
113 |
{
|
114 |
int i = 0; /* index within str */ |
|
115 |
int ch; |
|
116 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
117 |
index__checkstring(key); |
118 |
index__checkstring(value); |
|
46
by Jon Masters
depmod: Add binary index files |
119 |
|
120 |
while(1) { |
|
121 |
int j; /* index within node->prefix */ |
|
122 |
||
123 |
/* Ensure node->prefix is a prefix of &str[i].
|
|
124 |
If it is not already, then we must split node. */
|
|
125 |
for (j = 0; node->prefix[j]; j++) { |
|
126 |
ch = node->prefix[j]; |
|
127 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
128 |
if (ch != key[i+j]) { |
46
by Jon Masters
depmod: Add binary index files |
129 |
char *prefix = node->prefix; |
130 |
struct index_node *n; |
|
131 |
||
132 |
/* New child is copy of node with prefix[j+1..N] */
|
|
133 |
n = NOFAIL(calloc(sizeof(struct index_node), 1)); |
|
134 |
memcpy(n, node, sizeof(struct index_node)); |
|
135 |
n->prefix = NOFAIL(strdup(&prefix[j+1])); |
|
136 |
||
137 |
/* Parent has prefix[0..j], child at prefix[j] */
|
|
138 |
memset(node, 0, sizeof(struct index_node)); |
|
139 |
prefix[j] = '\0'; |
|
140 |
node->prefix = prefix; |
|
141 |
node->first = ch; |
|
142 |
node->last = ch; |
|
143 |
node->children[ch] = n; |
|
144 |
||
145 |
break; |
|
146 |
}
|
|
147 |
}
|
|
148 |
/* j is now length of node->prefix */
|
|
149 |
i += j; |
|
150 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
151 |
ch = key[i]; |
152 |
if(ch == '\0') |
|
153 |
return add_value(&node->values, value, priority); |
|
46
by Jon Masters
depmod: Add binary index files |
154 |
|
155 |
if (!node->children[ch]) { |
|
156 |
struct index_node *child; |
|
157 |
||
158 |
if (ch < node->first) |
|
159 |
node->first = ch; |
|
160 |
if (ch > node->last) |
|
161 |
node->last = ch; |
|
162 |
node->children[ch] = NOFAIL(calloc(sizeof(struct index_node), 1)); |
|
163 |
||
164 |
child = node->children[ch]; |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
165 |
child->prefix = NOFAIL(strdup(&key[i+1])); |
46
by Jon Masters
depmod: Add binary index files |
166 |
child->first = INDEX_CHILDMAX; |
83
by Alan Jenkins
add module ordering support for binary indexes |
167 |
add_value(&child->values, value, priority); |
168 |
||
169 |
return 0; |
|
46
by Jon Masters
depmod: Add binary index files |
170 |
}
|
171 |
||
172 |
/* Descend into child node and continue */
|
|
173 |
node = node->children[ch]; |
|
174 |
i++; |
|
175 |
}
|
|
176 |
}
|
|
177 |
||
178 |
static int index__haschildren(const struct index_node *node) |
|
179 |
{
|
|
180 |
return node->first < INDEX_CHILDMAX; |
|
181 |
}
|
|
182 |
||
183 |
/* Recursive post-order traversal
|
|
184 |
||
185 |
Pre-order would make for better read-side buffering / readahead / caching.
|
|
186 |
(post-order means you go backwards in the file as you descend the tree).
|
|
187 |
However, index reading is already fast enough.
|
|
188 |
Pre-order is simpler for writing, and depmod is already slow.
|
|
189 |
*/
|
|
190 |
static uint32_t index_write__node(const struct index_node *node, FILE *out) |
|
191 |
{
|
|
192 |
uint32_t *child_offs = NULL; |
|
193 |
int child_count = 0; |
|
194 |
long offset; |
|
195 |
||
196 |
if (!node) |
|
197 |
return 0; |
|
198 |
||
199 |
/* Write children and save their offsets */
|
|
200 |
if (index__haschildren(node)) { |
|
201 |
const struct index_node *child; |
|
202 |
int i; |
|
203 |
||
204 |
child_count = node->last - node->first + 1; |
|
205 |
child_offs = NOFAIL(malloc(child_count * sizeof(uint32_t))); |
|
206 |
||
207 |
for (i = 0; i < child_count; i++) { |
|
208 |
child = node->children[node->first + i]; |
|
209 |
child_offs[i] = htonl(index_write__node(child, out)); |
|
210 |
}
|
|
211 |
}
|
|
212 |
||
213 |
/* Now write this node */
|
|
214 |
offset = ftell(out); |
|
215 |
||
216 |
if (node->prefix[0]) { |
|
217 |
fputs(node->prefix, out); |
|
218 |
fputc('\0', out); |
|
219 |
offset |= INDEX_NODE_PREFIX; |
|
220 |
}
|
|
221 |
||
222 |
if (child_count) { |
|
223 |
fputc(node->first, out); |
|
224 |
fputc(node->last, out); |
|
225 |
fwrite(child_offs, sizeof(uint32_t), child_count, out); |
|
226 |
free(child_offs); |
|
227 |
offset |= INDEX_NODE_CHILDS; |
|
228 |
}
|
|
229 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
230 |
if (node->values) { |
231 |
const struct index_value *v; |
|
232 |
unsigned int value_count; |
|
233 |
uint32_t u; |
|
234 |
||
235 |
value_count = 0; |
|
236 |
for (v = node->values; v != NULL; v = v->next) |
|
237 |
value_count++; |
|
238 |
u = htonl(value_count); |
|
239 |
fwrite(&u, sizeof(u), 1, out); |
|
240 |
||
241 |
for (v = node->values; v != NULL; v = v->next) { |
|
242 |
u = htonl(v->priority); |
|
243 |
fwrite(&u, sizeof(u), 1, out); |
|
244 |
fputs(v->value, out); |
|
245 |
fputc('\0', out); |
|
246 |
}
|
|
247 |
offset |= INDEX_NODE_VALUES; |
|
248 |
}
|
|
46
by Jon Masters
depmod: Add binary index files |
249 |
|
250 |
return offset; |
|
251 |
}
|
|
252 |
||
253 |
void index_write(const struct index_node *node, FILE *out) |
|
254 |
{
|
|
255 |
long initial_offset, final_offset; |
|
256 |
uint32_t u; |
|
257 |
||
258 |
u = htonl(INDEX_MAGIC); |
|
259 |
fwrite(&u, sizeof(u), 1, out); |
|
68
by Jon Masters
add versioning to the binary module files |
260 |
u = htonl(INDEX_VERSION); |
261 |
fwrite(&u, sizeof(u), 1, out); |
|
46
by Jon Masters
depmod: Add binary index files |
262 |
|
68
by Jon Masters
add versioning to the binary module files |
263 |
/* Second word is reserved for the offset of the root node */
|
46
by Jon Masters
depmod: Add binary index files |
264 |
initial_offset = ftell(out); |
265 |
u = 0; |
|
266 |
fwrite(&u, sizeof(uint32_t), 1, out); |
|
267 |
||
268 |
/* Dump trie */
|
|
269 |
u = htonl(index_write__node(node, out)); |
|
270 |
||
271 |
/* Update first word */
|
|
272 |
final_offset = ftell(out); |
|
273 |
fseek(out, initial_offset, SEEK_SET); |
|
274 |
fwrite(&u, sizeof(uint32_t), 1, out); |
|
275 |
fseek(out, final_offset, SEEK_SET); |
|
276 |
}
|
|
277 |
||
278 |
||
47
by Alan Jenkins
modprobe: use binary index files |
279 |
|
280 |
static void read_error() |
|
281 |
{
|
|
282 |
fatal("Module index: unexpected error: %s\n" |
|
283 |
"Try re-running depmod\n", errno ? strerror(errno) : "EOF"); |
|
284 |
}
|
|
285 |
||
286 |
static int read_char(FILE *in) |
|
287 |
{
|
|
288 |
int ch; |
|
289 |
||
290 |
errno = 0; |
|
291 |
ch = getc_unlocked(in); |
|
292 |
if (ch == EOF) |
|
293 |
read_error(); |
|
294 |
return ch; |
|
295 |
}
|
|
296 |
||
297 |
static uint32_t read_long(FILE *in) |
|
298 |
{
|
|
299 |
uint32_t l; |
|
300 |
||
301 |
errno = 0; |
|
302 |
if (fread(&l, sizeof(uint32_t), 1, in) <= 0) |
|
303 |
read_error(); |
|
304 |
return ntohl(l); |
|
305 |
}
|
|
306 |
||
46
by Jon Masters
depmod: Add binary index files |
307 |
/*
|
308 |
* Buffer abstract data type
|
|
309 |
*
|
|
310 |
* Used internally to store the current path during tree traversal.
|
|
311 |
* They help build wildcard key strings to pass to fnmatch(),
|
|
312 |
* as well as building values of matching keys.
|
|
313 |
*/
|
|
314 |
||
315 |
struct buffer { |
|
316 |
char *bytes; |
|
317 |
unsigned size; |
|
318 |
unsigned used; |
|
319 |
};
|
|
320 |
||
321 |
static void buf__realloc(struct buffer *buf, unsigned size) |
|
322 |
{
|
|
323 |
if (size > buf->size) { |
|
324 |
buf->bytes = NOFAIL(realloc(buf->bytes, size)); |
|
325 |
buf->size = size; |
|
326 |
}
|
|
327 |
}
|
|
328 |
||
329 |
static struct buffer *buf_create() |
|
330 |
{
|
|
331 |
struct buffer *buf; |
|
332 |
||
333 |
buf = NOFAIL(calloc(sizeof(struct buffer), 1)); |
|
47
by Alan Jenkins
modprobe: use binary index files |
334 |
buf__realloc(buf, 256); |
46
by Jon Masters
depmod: Add binary index files |
335 |
return buf; |
336 |
}
|
|
47
by Alan Jenkins
modprobe: use binary index files |
337 |
|
338 |
static void buf_destroy(struct buffer *buf) |
|
339 |
{
|
|
340 |
free(buf->bytes); |
|
341 |
free(buf); |
|
342 |
}
|
|
343 |
||
344 |
/* Destroy buffer and return a copy as a C string */
|
|
345 |
static char *buf_detach(struct buffer *buf) |
|
346 |
{
|
|
347 |
char *bytes; |
|
348 |
||
349 |
bytes = NOFAIL(realloc(buf->bytes, buf->used + 1)); |
|
350 |
bytes[buf->used] = '\0'; |
|
351 |
||
352 |
free(buf); |
|
353 |
return bytes; |
|
354 |
}
|
|
355 |
||
356 |
/* Return a C string owned by the buffer
|
|
357 |
(invalidated if the buffer is changed).
|
|
358 |
*/
|
|
359 |
static const char *buf_str(struct buffer *buf) |
|
360 |
{
|
|
361 |
buf__realloc(buf, buf->used + 1); |
|
362 |
buf->bytes[buf->used] = '\0'; |
|
363 |
return buf->bytes; |
|
364 |
}
|
|
365 |
||
366 |
static int buf_fwrite(struct buffer *buf, FILE *out) |
|
367 |
{
|
|
368 |
return fwrite(buf->bytes, 1, buf->used, out); |
|
369 |
}
|
|
370 |
||
371 |
static void buf_pushchar(struct buffer *buf, char ch) |
|
372 |
{
|
|
373 |
buf__realloc(buf, buf->used + 1); |
|
374 |
buf->bytes[buf->used] = ch; |
|
375 |
buf->used++; |
|
376 |
}
|
|
377 |
||
378 |
static unsigned buf_pushchars(struct buffer *buf, const char *str) |
|
379 |
{
|
|
380 |
unsigned i = 0; |
|
381 |
int ch; |
|
382 |
||
383 |
while ((ch = str[i])) { |
|
384 |
buf_pushchar(buf, ch); |
|
385 |
i++; |
|
386 |
}
|
|
387 |
return i; |
|
388 |
}
|
|
389 |
||
390 |
/* like buf_pushchars(), but the string comes from a file */
|
|
391 |
static unsigned buf_freadchars(struct buffer *buf, FILE *in) |
|
392 |
{
|
|
393 |
unsigned i = 0; |
|
394 |
int ch; |
|
395 |
||
396 |
while ((ch = read_char(in))) { |
|
397 |
buf_pushchar(buf, ch); |
|
398 |
i++; |
|
399 |
}
|
|
400 |
||
401 |
return i; |
|
402 |
}
|
|
403 |
||
404 |
static void buf_popchar(struct buffer *buf) |
|
405 |
{
|
|
406 |
buf->used--; |
|
407 |
}
|
|
408 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
409 |
static void buf_popchars(struct buffer *buf, unsigned n) |
410 |
{
|
|
411 |
buf->used -= n; |
|
412 |
}
|
|
413 |
||
414 |
static void buf_clear(struct buffer *buf) |
|
415 |
{
|
|
416 |
buf->used = 0; |
|
417 |
}
|
|
418 |
||
47
by Alan Jenkins
modprobe: use binary index files |
419 |
/*
|
420 |
* Index file searching (used only by modprobe)
|
|
421 |
*/
|
|
422 |
||
423 |
struct index_node_f { |
|
424 |
FILE *file; |
|
425 |
char *prefix; /* path compression */ |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
426 |
struct index_value *values; |
47
by Alan Jenkins
modprobe: use binary index files |
427 |
unsigned char first; /* range of child nodes */ |
428 |
unsigned char last; |
|
429 |
uint32_t children[0]; |
|
430 |
};
|
|
431 |
||
432 |
static struct index_node_f *index_read(FILE *in, uint32_t offset) |
|
433 |
{
|
|
434 |
struct index_node_f *node; |
|
435 |
char *prefix; |
|
436 |
int i, child_count = 0; |
|
437 |
||
438 |
if ((offset & INDEX_NODE_MASK) == 0) |
|
439 |
return NULL; |
|
440 |
||
441 |
fseek(in, offset & INDEX_NODE_MASK, SEEK_SET); |
|
442 |
||
443 |
if (offset & INDEX_NODE_PREFIX) { |
|
444 |
struct buffer *buf = buf_create(); |
|
445 |
buf_freadchars(buf, in); |
|
446 |
prefix = buf_detach(buf); |
|
447 |
} else |
|
448 |
prefix = NOFAIL(strdup("")); |
|
449 |
||
450 |
if (offset & INDEX_NODE_CHILDS) { |
|
451 |
char first = read_char(in); |
|
452 |
char last = read_char(in); |
|
453 |
child_count = last - first + 1; |
|
454 |
||
455 |
node = NOFAIL(malloc(sizeof(struct index_node_f) + |
|
456 |
sizeof(uint32_t) * child_count)); |
|
457 |
||
458 |
node->first = first; |
|
459 |
node->last = last; |
|
460 |
||
461 |
for (i = 0; i < child_count; i++) |
|
462 |
node->children[i] = read_long(in); |
|
463 |
} else { |
|
464 |
node = NOFAIL(malloc(sizeof(struct index_node_f))); |
|
465 |
node->first = INDEX_CHILDMAX; |
|
466 |
node->last = 0; |
|
467 |
}
|
|
468 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
469 |
node->values = NULL; |
470 |
if (offset & INDEX_NODE_VALUES) { |
|
471 |
int value_count; |
|
472 |
struct buffer *buf = buf_create(); |
|
473 |
const char *value; |
|
474 |
unsigned int priority; |
|
475 |
||
476 |
value_count = read_long(in); |
|
477 |
||
478 |
while (value_count--) { |
|
479 |
priority = read_long(in); |
|
480 |
buf_freadchars(buf, in); |
|
481 |
value = buf_str(buf); |
|
482 |
add_value(&node->values, value, priority); |
|
483 |
buf_clear(buf); |
|
484 |
}
|
|
485 |
buf_destroy(buf); |
|
486 |
}
|
|
487 |
||
47
by Alan Jenkins
modprobe: use binary index files |
488 |
node->prefix = prefix; |
489 |
node->file = in; |
|
490 |
return node; |
|
491 |
}
|
|
492 |
||
493 |
static void index_close(struct index_node_f *node) |
|
494 |
{
|
|
495 |
free(node->prefix); |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
496 |
index_values_free(node->values); |
47
by Alan Jenkins
modprobe: use binary index files |
497 |
free(node); |
498 |
}
|
|
499 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
500 |
struct index_file { |
501 |
FILE *file; |
|
502 |
uint32_t root_offset; |
|
503 |
};
|
|
504 |
||
505 |
/* Failures are silent; modprobe will fall back to text files */
|
|
506 |
struct index_file *index_file_open(const char *filename) |
|
507 |
{
|
|
508 |
FILE *file; |
|
509 |
uint32_t magic, version; |
|
510 |
struct index_file *new; |
|
511 |
||
512 |
file = fopen(filename, "r"); |
|
513 |
if (!file) |
|
514 |
return NULL; |
|
515 |
errno = EINVAL; |
|
516 |
||
517 |
magic = read_long(file); |
|
518 |
if (magic != INDEX_MAGIC) |
|
519 |
return NULL; |
|
520 |
||
521 |
version = read_long(file); |
|
522 |
if (version >> 16 != INDEX_VERSION_MAJOR) |
|
523 |
return NULL; |
|
524 |
||
525 |
new = NOFAIL(malloc(sizeof(struct index_file))); |
|
526 |
new->file = file; |
|
527 |
new->root_offset = read_long(new->file); |
|
528 |
||
529 |
errno = 0; |
|
530 |
return new; |
|
531 |
}
|
|
532 |
||
533 |
void index_file_close(struct index_file *index) |
|
534 |
{
|
|
535 |
fclose(index->file); |
|
536 |
free(index); |
|
537 |
}
|
|
538 |
||
539 |
||
540 |
static struct index_node_f *index_readroot(struct index_file *in) |
|
541 |
{
|
|
542 |
return index_read(in->file, in->root_offset); |
|
543 |
}
|
|
544 |
||
47
by Alan Jenkins
modprobe: use binary index files |
545 |
static struct index_node_f *index_readchild(const struct index_node_f *parent, |
546 |
int ch) |
|
547 |
{
|
|
548 |
if (parent->first <= ch && ch <= parent->last) |
|
549 |
return index_read(parent->file, |
|
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
550 |
parent->children[ch - parent->first]); |
47
by Alan Jenkins
modprobe: use binary index files |
551 |
else
|
552 |
return NULL; |
|
553 |
}
|
|
554 |
||
555 |
/*
|
|
556 |
* Dump all strings as lines in a plain text file.
|
|
557 |
*/
|
|
558 |
||
559 |
static void index_dump_node(struct index_node_f *node, |
|
560 |
struct buffer *buf, |
|
561 |
FILE *out, |
|
562 |
const char *prefix) |
|
563 |
{
|
|
83
by Alan Jenkins
add module ordering support for binary indexes |
564 |
struct index_value *v; |
47
by Alan Jenkins
modprobe: use binary index files |
565 |
int ch, pushed; |
566 |
||
567 |
pushed = buf_pushchars(buf, node->prefix); |
|
568 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
569 |
for (v = node->values; v != NULL; v = v->next) { |
47
by Alan Jenkins
modprobe: use binary index files |
570 |
fputs(prefix, out); |
571 |
buf_fwrite(buf, out); |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
572 |
fputc(' ', out); |
573 |
fputs(v->value, out); |
|
47
by Alan Jenkins
modprobe: use binary index files |
574 |
fputc('\n', out); |
575 |
}
|
|
576 |
||
577 |
for (ch = node->first; ch <= node->last; ch++) { |
|
578 |
struct index_node_f *child = index_readchild(node, ch); |
|
579 |
||
580 |
if (!child) |
|
581 |
continue; |
|
582 |
||
583 |
buf_pushchar(buf, ch); |
|
584 |
index_dump_node(child, buf, out, prefix); |
|
585 |
buf_popchar(buf); |
|
586 |
}
|
|
587 |
||
588 |
buf_popchars(buf, pushed); |
|
589 |
index_close(node); |
|
590 |
}
|
|
591 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
592 |
void index_dump(struct index_file *in, FILE *out, const char *prefix) |
47
by Alan Jenkins
modprobe: use binary index files |
593 |
{
|
594 |
struct index_node_f *root; |
|
595 |
struct buffer *buf; |
|
596 |
||
597 |
buf = buf_create(); |
|
598 |
root = index_readroot(in); |
|
599 |
index_dump_node(root, buf, out, prefix); |
|
600 |
buf_destroy(buf); |
|
601 |
}
|
|
602 |
||
603 |
/*
|
|
604 |
* Search the index for a key
|
|
605 |
*
|
|
606 |
* Returns the value of the first match
|
|
607 |
*
|
|
83
by Alan Jenkins
add module ordering support for binary indexes |
608 |
* The recursive functions free their node argument (using index_close).
|
47
by Alan Jenkins
modprobe: use binary index files |
609 |
*/
|
610 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
611 |
char *index_search(struct index_file *in, const char *key); |
47
by Alan Jenkins
modprobe: use binary index files |
612 |
static char *index_search__node(struct index_node_f *node, const char *key, int i); |
613 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
614 |
char *index_search(struct index_file *in, const char *key) |
47
by Alan Jenkins
modprobe: use binary index files |
615 |
{
|
616 |
struct index_node_f *root; |
|
617 |
char *value; |
|
618 |
||
619 |
root = index_readroot(in); |
|
620 |
value = index_search__node(root, key, 0); |
|
621 |
||
622 |
return value; |
|
623 |
}
|
|
624 |
||
625 |
static char *index_search__node(struct index_node_f *node, const char *key, int i) |
|
626 |
{
|
|
196.1.14
by Alan Jenkins
modprobe: clean up minor memory leaks |
627 |
char *value; |
47
by Alan Jenkins
modprobe: use binary index files |
628 |
struct index_node_f *child; |
629 |
int ch; |
|
630 |
int j; |
|
631 |
||
632 |
while(node) { |
|
633 |
for (j = 0; node->prefix[j]; j++) { |
|
634 |
ch = node->prefix[j]; |
|
635 |
||
636 |
if (ch != key[i+j]) { |
|
637 |
index_close(node); |
|
638 |
return NULL; |
|
639 |
}
|
|
640 |
}
|
|
641 |
i += j; |
|
642 |
||
643 |
if (key[i] == '\0') { |
|
196.1.14
by Alan Jenkins
modprobe: clean up minor memory leaks |
644 |
if (node->values) { |
645 |
value = strdup(node->values[0].value); |
|
646 |
index_close(node); |
|
647 |
return value; |
|
648 |
} else { |
|
47
by Alan Jenkins
modprobe: use binary index files |
649 |
return NULL; |
196.1.14
by Alan Jenkins
modprobe: clean up minor memory leaks |
650 |
}
|
47
by Alan Jenkins
modprobe: use binary index files |
651 |
}
|
652 |
||
653 |
child = index_readchild(node, key[i]); |
|
654 |
index_close(node); |
|
655 |
node = child; |
|
656 |
i++; |
|
657 |
}
|
|
658 |
||
659 |
return NULL; |
|
660 |
}
|
|
661 |
||
662 |
/*
|
|
663 |
* Search the index for a key. The index may contain wildcards.
|
|
664 |
*
|
|
665 |
* Returns a list of all the values of matching keys.
|
|
666 |
*/
|
|
667 |
||
668 |
/* Level 1: interface function */
|
|
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
669 |
struct index_value *index_searchwild(struct index_file *in, const char *key); |
47
by Alan Jenkins
modprobe: use binary index files |
670 |
|
671 |
/* Level 2: descend the tree (until we hit a wildcard) */
|
|
672 |
static void index_searchwild__node(struct index_node_f *node, |
|
673 |
struct buffer *buf, |
|
674 |
const char *key, int i, |
|
675 |
struct index_value **out); |
|
676 |
||
677 |
/* Level 3: traverse a sub-keyspace which starts with a wildcard,
|
|
83
by Alan Jenkins
add module ordering support for binary indexes |
678 |
looking for matches.
|
47
by Alan Jenkins
modprobe: use binary index files |
679 |
*/
|
680 |
static void index_searchwild__all(struct index_node_f *node, int j, |
|
681 |
struct buffer *buf, |
|
682 |
const char *subkey, |
|
683 |
struct index_value **out); |
|
684 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
685 |
/* Level 4: add all the values from a matching node */
|
686 |
static void index_searchwild__allvalues(struct index_node_f *node, |
|
47
by Alan Jenkins
modprobe: use binary index files |
687 |
struct index_value **out); |
688 |
||
689 |
||
82
by Alan Jenkins
modprobe: fallback to text files if binary index is wrong version |
690 |
struct index_value *index_searchwild(struct index_file *in, const char *key) |
47
by Alan Jenkins
modprobe: use binary index files |
691 |
{
|
692 |
struct index_node_f *root = index_readroot(in); |
|
693 |
struct buffer *buf = buf_create(); |
|
694 |
struct index_value *out = NULL; |
|
695 |
||
696 |
index_searchwild__node(root, buf, key, 0, &out); |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
697 |
buf_destroy(buf); |
47
by Alan Jenkins
modprobe: use binary index files |
698 |
return out; |
699 |
}
|
|
700 |
||
701 |
static void index_searchwild__node(struct index_node_f *node, |
|
702 |
struct buffer *buf, |
|
703 |
const char *key, int i, |
|
704 |
struct index_value **out) |
|
705 |
{
|
|
706 |
struct index_node_f *child; |
|
707 |
int j; |
|
708 |
int ch; |
|
709 |
||
710 |
while(node) { |
|
711 |
for (j = 0; node->prefix[j]; j++) { |
|
712 |
ch = node->prefix[j]; |
|
713 |
||
714 |
if (ch == '*' || ch == '?' || ch == '[') { |
|
715 |
index_searchwild__all(node, j, buf, |
|
716 |
&key[i+j], out); |
|
717 |
return; |
|
718 |
}
|
|
719 |
||
720 |
if (ch != key[i+j]) { |
|
721 |
index_close(node); |
|
722 |
return; |
|
723 |
}
|
|
724 |
}
|
|
725 |
i += j; |
|
726 |
||
727 |
child = index_readchild(node, '*'); |
|
728 |
if (child) { |
|
729 |
buf_pushchar(buf, '*'); |
|
730 |
index_searchwild__all(child, 0, buf, &key[i], out); |
|
731 |
buf_popchar(buf); |
|
732 |
}
|
|
733 |
||
734 |
child = index_readchild(node, '?'); |
|
735 |
if (child) { |
|
81
by Jon Masters
index: fix copy/paste error |
736 |
buf_pushchar(buf, '?'); |
47
by Alan Jenkins
modprobe: use binary index files |
737 |
index_searchwild__all(child, 0, buf, &key[i], out); |
738 |
buf_popchar(buf); |
|
739 |
}
|
|
740 |
||
741 |
child = index_readchild(node, '['); |
|
742 |
if (child) { |
|
743 |
buf_pushchar(buf, '['); |
|
744 |
index_searchwild__all(child, 0, buf, &key[i], out); |
|
745 |
buf_popchar(buf); |
|
746 |
}
|
|
747 |
||
748 |
if (key[i] == '\0') { |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
749 |
index_searchwild__allvalues(node, out); |
750 |
||
47
by Alan Jenkins
modprobe: use binary index files |
751 |
return; |
752 |
}
|
|
753 |
||
754 |
child = index_readchild(node, key[i]); |
|
755 |
index_close(node); |
|
756 |
node = child; |
|
757 |
i++; |
|
758 |
}
|
|
759 |
}
|
|
760 |
||
761 |
static void index_searchwild__all(struct index_node_f *node, int j, |
|
762 |
struct buffer *buf, |
|
763 |
const char *subkey, |
|
764 |
struct index_value **out) |
|
765 |
{
|
|
766 |
int pushed = 0; |
|
767 |
int ch; |
|
768 |
||
769 |
while (node->prefix[j]) { |
|
770 |
ch = node->prefix[j]; |
|
771 |
||
772 |
buf_pushchar(buf, ch); |
|
773 |
pushed++; |
|
774 |
j++; |
|
775 |
}
|
|
776 |
||
777 |
for (ch = node->first; ch <= node->last; ch++) { |
|
778 |
struct index_node_f *child = index_readchild(node, ch); |
|
779 |
||
780 |
if (!child) |
|
781 |
continue; |
|
782 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
783 |
buf_pushchar(buf, ch); |
784 |
index_searchwild__all(child, 0, buf, subkey, out); |
|
785 |
buf_popchar(buf); |
|
786 |
}
|
|
787 |
||
788 |
if (node->values) { |
|
789 |
if (fnmatch(buf_str(buf), subkey, 0) == 0) |
|
790 |
index_searchwild__allvalues(node, out); |
|
196.1.14
by Alan Jenkins
modprobe: clean up minor memory leaks |
791 |
} else { |
792 |
index_close(node); |
|
47
by Alan Jenkins
modprobe: use binary index files |
793 |
}
|
794 |
||
795 |
buf_popchars(buf, pushed); |
|
796 |
}
|
|
797 |
||
83
by Alan Jenkins
add module ordering support for binary indexes |
798 |
static void index_searchwild__allvalues(struct index_node_f *node, |
47
by Alan Jenkins
modprobe: use binary index files |
799 |
struct index_value **out) |
800 |
{
|
|
83
by Alan Jenkins
add module ordering support for binary indexes |
801 |
struct index_value *v; |
47
by Alan Jenkins
modprobe: use binary index files |
802 |
|
83
by Alan Jenkins
add module ordering support for binary indexes |
803 |
for (v = node->values; v != NULL; v = v->next) |
804 |
add_value(out, v->value, v->priority); |
|
196.1.14
by Alan Jenkins
modprobe: clean up minor memory leaks |
805 |
|
806 |
index_close(node); |
|
47
by Alan Jenkins
modprobe: use binary index files |
807 |
}
|