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