1 /* 2 * libkmod - interface to kernel module operations 3 * 4 * Copyright (C) 2011-2013 ProFUSION embedded systems 5 * 6 * This library is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Lesser General Public 8 * License as published by the Free Software Foundation; either 9 * version 2.1 of the License, or (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 * Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with this library; if not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 #include <arpa/inet.h> 21 #include <assert.h> 22 #include <errno.h> 23 #include <fnmatch.h> 24 #include <inttypes.h> 25 #include <stdio.h> 26 #include <stdlib.h> 27 #include <string.h> 28 29 #include <shared/macro.h> 30 #include <shared/strbuf.h> 31 #include <shared/util.h> 32 33 #include "libkmod-internal.h" 34 #include "libkmod-index.h" 35 36 /* libkmod-index.c: module index file implementation 37 * 38 * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first. 39 * All files start with a magic number. 40 * 41 * Magic spells "BOOTFAST". Second one used on newer versioned binary files. 42 * #define INDEX_MAGIC_OLD 0xB007FA57 43 * 44 * We use a version string to keep track of changes to the binary format 45 * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in 46 * case we ever decide to have minor changes that are not incompatible. 47 */ 48 #define INDEX_MAGIC 0xB007F457 49 #define INDEX_VERSION_MAJOR 0x0002 50 #define INDEX_VERSION_MINOR 0x0001 51 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR) 52 53 /* The index file maps keys to values. Both keys and values are ASCII strings. 54 * Each key can have multiple values. Values are sorted by an integer priority. 55 * 56 * The reader also implements a wildcard search (including range expressions) 57 * where the keys in the index are treated as patterns. 58 * This feature is required for module aliases. 59 */ 60 #define INDEX_CHILDMAX 128 61 62 /* Disk format: 63 * 64 * uint32_t magic = INDEX_MAGIC; 65 * uint32_t version = INDEX_VERSION; 66 * uint32_t root_offset; 67 * 68 * (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes: 69 * 70 * char[] prefix; // nul terminated 71 * 72 * char first; 73 * char last; 74 * uint32_t children[last - first + 1]; 75 * 76 * uint32_t value_count; 77 * struct { 78 * uint32_t priority; 79 * char[] value; // nul terminated 80 * } values[value_count]; 81 * 82 * (node_offset & INDEX_NODE_FLAGS) indicates which fields are present. 83 * Empty prefixes are omitted, leaf nodes omit the three child-related fields. 84 * 85 * This could be optimised further by adding a sparse child format 86 * (indicated using a new flag). 87 * 88 * 89 * Implementation is based on a radix tree, or "trie". 90 * Each arc from parent to child is labelled with a character. 91 * Each path from the root represents a string. 92 * 93 * == Example strings == 94 * 95 * ask 96 * ate 97 * on 98 * once 99 * one 100 * 101 * == Key == 102 * + Normal node 103 * * Marked node, representing a key and it's values. 104 * 105 * + 106 * |-a-+-s-+-k-* 107 * | | 108 * | `-t-+-e-* 109 * | 110 * `-o-+-n-*-c-+-e-* 111 * | 112 * `-e-* 113 * 114 * Naive implementations tend to be very space inefficient; child pointers 115 * are stored in arrays indexed by character, but most child pointers are null. 116 * 117 * Our implementation uses a scheme described by Wikipedia as a Patrica trie, 118 * 119 * "easiest to understand as a space-optimized trie where 120 * each node with only one child is merged with its child" 121 * 122 * + 123 * |-a-+-sk-* 124 * | | 125 * | `-te-* 126 * | 127 * `-on-*-ce-* 128 * | 129 * `-e-* 130 * 131 * We still use arrays of child pointers indexed by a single character; 132 * the remaining characters of the label are stored as a "prefix" in the child. 133 * 134 * The paper describing the original Patrica trie works on individiual bits - 135 * each node has a maximum of two children, which increases space efficiency. 136 * However for this application it is simpler to use the ASCII character set. 137 * Since the index file is read-only, it can be compressed by omitting null 138 * child pointers at the start and end of arrays. 139 */ 140 141 /* Format of node offsets within index file */ 142 enum node_offset { 143 INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */ 144 INDEX_NODE_PREFIX = 0x80000000, 145 INDEX_NODE_VALUES = 0x40000000, 146 INDEX_NODE_CHILDS = 0x20000000, 147 148 INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */ 149 }; 150 151 void index_values_free(struct index_value *values) 152 { 153 while (values) { 154 struct index_value *value = values; 155 156 values = value->next; 157 free(value); 158 } 159 } 160 161 static int add_value(struct index_value **values, 162 const char *value, unsigned len, unsigned int priority) 163 { 164 struct index_value *v; 165 166 /* find position to insert value */ 167 while (*values && (*values)->priority < priority) 168 values = &(*values)->next; 169 170 v = malloc(sizeof(struct index_value) + len + 1); 171 if (!v) 172 return -1; 173 v->next = *values; 174 v->priority = priority; 175 v->len = len; 176 memcpy(v->value, value, len); 177 v->value[len] = '\0'; 178 *values = v; 179 180 return 0; 181 } 182 183 static void read_error(void) 184 { 185 fatal("Module index: unexpected error: %s\n" 186 "Try re-running depmod\n", errno ? strerror(errno) : "EOF"); 187 } 188 189 static int read_char(FILE *in) 190 { 191 int ch; 192 193 errno = 0; 194 ch = getc_unlocked(in); 195 if (ch == EOF) 196 read_error(); 197 return ch; 198 } 199 200 static uint32_t read_long(FILE *in) 201 { 202 uint32_t l; 203 204 errno = 0; 205 if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t)) 206 read_error(); 207 return ntohl(l); 208 } 209 210 static unsigned buf_freadchars(struct strbuf *buf, FILE *in) 211 { 212 unsigned i = 0; 213 int ch; 214 215 while ((ch = read_char(in))) { 216 if (!strbuf_pushchar(buf, ch)) 217 break; 218 i++; 219 } 220 221 return i; 222 } 223 224 /* 225 * Index file searching 226 */ 227 struct index_node_f { 228 FILE *file; 229 char *prefix; /* path compression */ 230 struct index_value *values; 231 unsigned char first; /* range of child nodes */ 232 unsigned char last; 233 uint32_t children[0]; 234 }; 235 236 static struct index_node_f *index_read(FILE *in, uint32_t offset) 237 { 238 struct index_node_f *node; 239 char *prefix; 240 int i, child_count = 0; 241 242 if ((offset & INDEX_NODE_MASK) == 0) 243 return NULL; 244 245 if (fseek(in, offset & INDEX_NODE_MASK, SEEK_SET) < 0) 246 return NULL; 247 248 if (offset & INDEX_NODE_PREFIX) { 249 struct strbuf buf; 250 strbuf_init(&buf); 251 buf_freadchars(&buf, in); 252 prefix = strbuf_steal(&buf); 253 } else 254 prefix = NOFAIL(strdup("")); 255 256 if (offset & INDEX_NODE_CHILDS) { 257 char first = read_char(in); 258 char last = read_char(in); 259 child_count = last - first + 1; 260 261 node = NOFAIL(malloc(sizeof(struct index_node_f) + 262 sizeof(uint32_t) * child_count)); 263 264 node->first = first; 265 node->last = last; 266 267 for (i = 0; i < child_count; i++) 268 node->children[i] = read_long(in); 269 } else { 270 node = NOFAIL(malloc(sizeof(struct index_node_f))); 271 node->first = INDEX_CHILDMAX; 272 node->last = 0; 273 } 274 275 node->values = NULL; 276 if (offset & INDEX_NODE_VALUES) { 277 int value_count; 278 struct strbuf buf; 279 const char *value; 280 unsigned int priority; 281 282 value_count = read_long(in); 283 284 strbuf_init(&buf); 285 while (value_count--) { 286 priority = read_long(in); 287 buf_freadchars(&buf, in); 288 value = strbuf_str(&buf); 289 add_value(&node->values, value, buf.used, priority); 290 strbuf_clear(&buf); 291 } 292 strbuf_release(&buf); 293 } 294 295 node->prefix = prefix; 296 node->file = in; 297 return node; 298 } 299 300 static void index_close(struct index_node_f *node) 301 { 302 free(node->prefix); 303 index_values_free(node->values); 304 free(node); 305 } 306 307 struct index_file { 308 FILE *file; 309 uint32_t root_offset; 310 }; 311 312 struct index_file *index_file_open(const char *filename) 313 { 314 FILE *file; 315 uint32_t magic, version; 316 struct index_file *new; 317 318 file = fopen(filename, "re"); 319 if (!file) 320 return NULL; 321 errno = EINVAL; 322 323 magic = read_long(file); 324 if (magic != INDEX_MAGIC) { 325 fclose(file); 326 return NULL; 327 } 328 329 version = read_long(file); 330 if (version >> 16 != INDEX_VERSION_MAJOR) { 331 fclose(file); 332 return NULL; 333 } 334 335 new = NOFAIL(malloc(sizeof(struct index_file))); 336 new->file = file; 337 new->root_offset = read_long(new->file); 338 339 errno = 0; 340 return new; 341 } 342 343 void index_file_close(struct index_file *idx) 344 { 345 fclose(idx->file); 346 free(idx); 347 } 348 349 static struct index_node_f *index_readroot(struct index_file *in) 350 { 351 return index_read(in->file, in->root_offset); 352 } 353 354 static struct index_node_f *index_readchild(const struct index_node_f *parent, 355 int ch) 356 { 357 if (parent->first <= ch && ch <= parent->last) { 358 return index_read(parent->file, 359 parent->children[ch - parent->first]); 360 } 361 362 return NULL; 363 } 364 365 static void index_dump_node(struct index_node_f *node, struct strbuf *buf, 366 int fd) 367 { 368 struct index_value *v; 369 int ch, pushed; 370 371 pushed = strbuf_pushchars(buf, node->prefix); 372 373 for (v = node->values; v != NULL; v = v->next) { 374 write_str_safe(fd, buf->bytes, buf->used); 375 write_str_safe(fd, " ", 1); 376 write_str_safe(fd, v->value, strlen(v->value)); 377 write_str_safe(fd, "\n", 1); 378 } 379 380 for (ch = node->first; ch <= node->last; ch++) { 381 struct index_node_f *child = index_readchild(node, ch); 382 383 if (!child) 384 continue; 385 386 strbuf_pushchar(buf, ch); 387 index_dump_node(child, buf, fd); 388 strbuf_popchar(buf); 389 } 390 391 strbuf_popchars(buf, pushed); 392 index_close(node); 393 } 394 395 void index_dump(struct index_file *in, int fd, const char *prefix) 396 { 397 struct index_node_f *root; 398 struct strbuf buf; 399 400 root = index_readroot(in); 401 if (root == NULL) 402 return; 403 404 strbuf_init(&buf); 405 strbuf_pushchars(&buf, prefix); 406 index_dump_node(root, &buf, fd); 407 strbuf_release(&buf); 408 } 409 410 static char *index_search__node(struct index_node_f *node, const char *key, int i) 411 { 412 char *value; 413 struct index_node_f *child; 414 int ch; 415 int j; 416 417 while(node) { 418 for (j = 0; node->prefix[j]; j++) { 419 ch = node->prefix[j]; 420 421 if (ch != key[i+j]) { 422 index_close(node); 423 return NULL; 424 } 425 } 426 427 i += j; 428 429 if (key[i] == '\0') { 430 value = node->values != NULL 431 ? strdup(node->values[0].value) 432 : NULL; 433 434 index_close(node); 435 return value; 436 } 437 438 child = index_readchild(node, key[i]); 439 index_close(node); 440 node = child; 441 i++; 442 } 443 444 return NULL; 445 } 446 447 /* 448 * Search the index for a key 449 * 450 * Returns the value of the first match 451 * 452 * The recursive functions free their node argument (using index_close). 453 */ 454 char *index_search(struct index_file *in, const char *key) 455 { 456 // FIXME: return value by reference instead of strdup 457 struct index_node_f *root; 458 char *value; 459 460 root = index_readroot(in); 461 value = index_search__node(root, key, 0); 462 463 return value; 464 } 465 466 467 468 /* Level 4: add all the values from a matching node */ 469 static void index_searchwild__allvalues(struct index_node_f *node, 470 struct index_value **out) 471 { 472 struct index_value *v; 473 474 for (v = node->values; v != NULL; v = v->next) 475 add_value(out, v->value, v->len, v->priority); 476 477 index_close(node); 478 } 479 480 /* 481 * Level 3: traverse a sub-keyspace which starts with a wildcard, 482 * looking for matches. 483 */ 484 static void index_searchwild__all(struct index_node_f *node, int j, 485 struct strbuf *buf, 486 const char *subkey, 487 struct index_value **out) 488 { 489 int pushed = 0; 490 int ch; 491 492 while (node->prefix[j]) { 493 ch = node->prefix[j]; 494 495 strbuf_pushchar(buf, ch); 496 pushed++; 497 j++; 498 } 499 500 for (ch = node->first; ch <= node->last; ch++) { 501 struct index_node_f *child = index_readchild(node, ch); 502 503 if (!child) 504 continue; 505 506 strbuf_pushchar(buf, ch); 507 index_searchwild__all(child, 0, buf, subkey, out); 508 strbuf_popchar(buf); 509 } 510 511 if (node->values) { 512 if (fnmatch(strbuf_str(buf), subkey, 0) == 0) 513 index_searchwild__allvalues(node, out); 514 else 515 index_close(node); 516 } else { 517 index_close(node); 518 } 519 520 strbuf_popchars(buf, pushed); 521 } 522 523 /* Level 2: descend the tree (until we hit a wildcard) */ 524 static void index_searchwild__node(struct index_node_f *node, 525 struct strbuf *buf, 526 const char *key, int i, 527 struct index_value **out) 528 { 529 struct index_node_f *child; 530 int j; 531 int ch; 532 533 while(node) { 534 for (j = 0; node->prefix[j]; j++) { 535 ch = node->prefix[j]; 536 537 if (ch == '*' || ch == '?' || ch == '[') { 538 index_searchwild__all(node, j, buf, 539 &key[i+j], out); 540 return; 541 } 542 543 if (ch != key[i+j]) { 544 index_close(node); 545 return; 546 } 547 } 548 549 i += j; 550 551 child = index_readchild(node, '*'); 552 if (child) { 553 strbuf_pushchar(buf, '*'); 554 index_searchwild__all(child, 0, buf, &key[i], out); 555 strbuf_popchar(buf); 556 } 557 558 child = index_readchild(node, '?'); 559 if (child) { 560 strbuf_pushchar(buf, '?'); 561 index_searchwild__all(child, 0, buf, &key[i], out); 562 strbuf_popchar(buf); 563 } 564 565 child = index_readchild(node, '['); 566 if (child) { 567 strbuf_pushchar(buf, '['); 568 index_searchwild__all(child, 0, buf, &key[i], out); 569 strbuf_popchar(buf); 570 } 571 572 if (key[i] == '\0') { 573 index_searchwild__allvalues(node, out); 574 575 return; 576 } 577 578 child = index_readchild(node, key[i]); 579 index_close(node); 580 node = child; 581 i++; 582 } 583 } 584 585 /* 586 * Search the index for a key. The index may contain wildcards. 587 * 588 * Returns a list of all the values of matching keys. 589 */ 590 struct index_value *index_searchwild(struct index_file *in, const char *key) 591 { 592 struct index_node_f *root = index_readroot(in); 593 struct strbuf buf; 594 struct index_value *out = NULL; 595 596 strbuf_init(&buf); 597 index_searchwild__node(root, &buf, key, 0, &out); 598 strbuf_release(&buf); 599 return out; 600 } 601 602 /**************************************************************************/ 603 /* 604 * Alternative implementation, using mmap to map all the file to memory when 605 * starting 606 */ 607 #include <sys/mman.h> 608 #include <sys/stat.h> 609 #include <unistd.h> 610 611 static const char _idx_empty_str[] = ""; 612 613 struct index_mm { 614 struct kmod_ctx *ctx; 615 void *mm; 616 uint32_t root_offset; 617 size_t size; 618 }; 619 620 struct index_mm_value { 621 unsigned int priority; 622 unsigned int len; 623 const char *value; 624 }; 625 626 struct index_mm_value_array { 627 struct index_mm_value *values; 628 unsigned int len; 629 }; 630 631 struct index_mm_node { 632 struct index_mm *idx; 633 const char *prefix; /* mmape'd value */ 634 struct index_mm_value_array values; 635 unsigned char first; 636 unsigned char last; 637 uint32_t children[]; 638 }; 639 640 static inline uint32_t read_long_mm(void **p) 641 { 642 uint8_t *addr = *(uint8_t **)p; 643 uint32_t v; 644 645 /* addr may be unalined to uint32_t */ 646 v = get_unaligned((uint32_t *) addr); 647 648 *p = addr + sizeof(uint32_t); 649 return ntohl(v); 650 } 651 652 static inline uint8_t read_char_mm(void **p) 653 { 654 uint8_t *addr = *(uint8_t **)p; 655 uint8_t v = *addr; 656 *p = addr + sizeof(uint8_t); 657 return v; 658 } 659 660 static inline char *read_chars_mm(void **p, unsigned *rlen) 661 { 662 char *addr = *(char **)p; 663 size_t len = *rlen = strlen(addr); 664 *p = addr + len + 1; 665 return addr; 666 } 667 668 static struct index_mm_node *index_mm_read_node(struct index_mm *idx, 669 uint32_t offset) { 670 void *p = idx->mm; 671 struct index_mm_node *node; 672 const char *prefix; 673 int i, child_count, value_count, children_padding; 674 uint32_t children[INDEX_CHILDMAX]; 675 char first, last; 676 677 if ((offset & INDEX_NODE_MASK) == 0) 678 return NULL; 679 680 p = (char *)p + (offset & INDEX_NODE_MASK); 681 682 if (offset & INDEX_NODE_PREFIX) { 683 unsigned len; 684 prefix = read_chars_mm(&p, &len); 685 } else 686 prefix = _idx_empty_str; 687 688 if (offset & INDEX_NODE_CHILDS) { 689 first = read_char_mm(&p); 690 last = read_char_mm(&p); 691 child_count = last - first + 1; 692 for (i = 0; i < child_count; i++) 693 children[i] = read_long_mm(&p); 694 } else { 695 first = (char)INDEX_CHILDMAX; 696 last = 0; 697 child_count = 0; 698 } 699 700 children_padding = (sizeof(struct index_mm_node) + 701 (sizeof(uint32_t) * child_count)) % sizeof(void *); 702 703 if (offset & INDEX_NODE_VALUES) 704 value_count = read_long_mm(&p); 705 else 706 value_count = 0; 707 708 node = malloc(sizeof(struct index_mm_node) 709 + sizeof(uint32_t) * child_count + children_padding 710 + sizeof(struct index_mm_value) * value_count); 711 if (node == NULL) 712 return NULL; 713 714 node->idx = idx; 715 node->prefix = prefix; 716 if (value_count == 0) 717 node->values.values = NULL; 718 else { 719 node->values.values = (struct index_mm_value *) 720 ((char *)node + sizeof(struct index_mm_node) + 721 sizeof(uint32_t) * child_count + children_padding); 722 } 723 node->values.len = value_count; 724 node->first = first; 725 node->last = last; 726 memcpy(node->children, children, sizeof(uint32_t) * child_count); 727 728 for (i = 0; i < value_count; i++) { 729 struct index_mm_value *v = node->values.values + i; 730 v->priority = read_long_mm(&p); 731 v->value = read_chars_mm(&p, &v->len); 732 } 733 734 return node; 735 } 736 737 static void index_mm_free_node(struct index_mm_node *node) 738 { 739 free(node); 740 } 741 742 struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename, 743 unsigned long long *stamp) 744 { 745 int fd; 746 struct stat st; 747 struct index_mm *idx; 748 struct { 749 uint32_t magic; 750 uint32_t version; 751 uint32_t root_offset; 752 } hdr; 753 void *p; 754 755 DBG(ctx, "file=%s\n", filename); 756 757 idx = malloc(sizeof(*idx)); 758 if (idx == NULL) { 759 ERR(ctx, "malloc: %m\n"); 760 return NULL; 761 } 762 763 if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) { 764 DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename); 765 goto fail_open; 766 } 767 768 if (fstat(fd, &st) < 0) 769 goto fail_nommap; 770 if ((size_t) st.st_size < sizeof(hdr)) 771 goto fail_nommap; 772 773 if ((idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0)) 774 == MAP_FAILED) { 775 ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n", 776 st.st_size, fd); 777 goto fail_nommap; 778 } 779 780 p = idx->mm; 781 hdr.magic = read_long_mm(&p); 782 hdr.version = read_long_mm(&p); 783 hdr.root_offset = read_long_mm(&p); 784 785 if (hdr.magic != INDEX_MAGIC) { 786 ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic, 787 INDEX_MAGIC); 788 goto fail; 789 } 790 791 if (hdr.version >> 16 != INDEX_VERSION_MAJOR) { 792 ERR(ctx, "major version check fail: %u instead of %u\n", 793 hdr.version >> 16, INDEX_VERSION_MAJOR); 794 goto fail; 795 } 796 797 idx->root_offset = hdr.root_offset; 798 idx->size = st.st_size; 799 idx->ctx = ctx; 800 close(fd); 801 802 *stamp = stat_mstamp(&st); 803 804 return idx; 805 806 fail: 807 munmap(idx->mm, st.st_size); 808 fail_nommap: 809 close(fd); 810 fail_open: 811 free(idx); 812 return NULL; 813 } 814 815 void index_mm_close(struct index_mm *idx) 816 { 817 munmap(idx->mm, idx->size); 818 free(idx); 819 } 820 821 static struct index_mm_node *index_mm_readroot(struct index_mm *idx) 822 { 823 return index_mm_read_node(idx, idx->root_offset); 824 } 825 826 static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent, 827 int ch) 828 { 829 if (parent->first <= ch && ch <= parent->last) { 830 return index_mm_read_node(parent->idx, 831 parent->children[ch - parent->first]); 832 } 833 834 return NULL; 835 } 836 837 static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf, 838 int fd) 839 { 840 struct index_mm_value *itr, *itr_end; 841 int ch, pushed; 842 843 pushed = strbuf_pushchars(buf, node->prefix); 844 845 itr = node->values.values; 846 itr_end = itr + node->values.len; 847 for (; itr < itr_end; itr++) { 848 write_str_safe(fd, buf->bytes, buf->used); 849 write_str_safe(fd, " ", 1); 850 write_str_safe(fd, itr->value, itr->len); 851 write_str_safe(fd, "\n", 1); 852 } 853 854 for (ch = node->first; ch <= node->last; ch++) { 855 struct index_mm_node *child = index_mm_readchild(node, ch); 856 857 if (child == NULL) 858 continue; 859 860 strbuf_pushchar(buf, ch); 861 index_mm_dump_node(child, buf, fd); 862 strbuf_popchar(buf); 863 } 864 865 strbuf_popchars(buf, pushed); 866 index_mm_free_node(node); 867 } 868 869 void index_mm_dump(struct index_mm *idx, int fd, const char *prefix) 870 { 871 struct index_mm_node *root; 872 struct strbuf buf; 873 874 root = index_mm_readroot(idx); 875 if (root == NULL) 876 return; 877 878 strbuf_init(&buf); 879 strbuf_pushchars(&buf, prefix); 880 index_mm_dump_node(root, &buf, fd); 881 strbuf_release(&buf); 882 } 883 884 static char *index_mm_search_node(struct index_mm_node *node, const char *key, 885 int i) 886 { 887 char *value; 888 struct index_mm_node *child; 889 int ch; 890 int j; 891 892 while(node) { 893 for (j = 0; node->prefix[j]; j++) { 894 ch = node->prefix[j]; 895 896 if (ch != key[i+j]) { 897 index_mm_free_node(node); 898 return NULL; 899 } 900 } 901 902 i += j; 903 904 if (key[i] == '\0') { 905 value = node->values.len > 0 906 ? strdup(node->values.values[0].value) 907 : NULL; 908 909 index_mm_free_node(node); 910 return value; 911 } 912 913 child = index_mm_readchild(node, key[i]); 914 index_mm_free_node(node); 915 node = child; 916 i++; 917 } 918 919 return NULL; 920 } 921 922 /* 923 * Search the index for a key 924 * 925 * Returns the value of the first match 926 * 927 * The recursive functions free their node argument (using index_close). 928 */ 929 char *index_mm_search(struct index_mm *idx, const char *key) 930 { 931 // FIXME: return value by reference instead of strdup 932 struct index_mm_node *root; 933 char *value; 934 935 root = index_mm_readroot(idx); 936 value = index_mm_search_node(root, key, 0); 937 938 return value; 939 } 940 941 /* Level 4: add all the values from a matching node */ 942 static void index_mm_searchwild_allvalues(struct index_mm_node *node, 943 struct index_value **out) 944 { 945 struct index_mm_value *itr, *itr_end; 946 947 itr = node->values.values; 948 itr_end = itr + node->values.len; 949 for (; itr < itr_end; itr++) 950 add_value(out, itr->value, itr->len, itr->priority); 951 952 index_mm_free_node(node); 953 } 954 955 /* 956 * Level 3: traverse a sub-keyspace which starts with a wildcard, 957 * looking for matches. 958 */ 959 static void index_mm_searchwild_all(struct index_mm_node *node, int j, 960 struct strbuf *buf, 961 const char *subkey, 962 struct index_value **out) 963 { 964 int pushed = 0; 965 int ch; 966 967 while (node->prefix[j]) { 968 ch = node->prefix[j]; 969 970 strbuf_pushchar(buf, ch); 971 pushed++; 972 j++; 973 } 974 975 for (ch = node->first; ch <= node->last; ch++) { 976 struct index_mm_node *child = index_mm_readchild(node, ch); 977 978 if (!child) 979 continue; 980 981 strbuf_pushchar(buf, ch); 982 index_mm_searchwild_all(child, 0, buf, subkey, out); 983 strbuf_popchar(buf); 984 } 985 986 if (node->values.len > 0) { 987 if (fnmatch(strbuf_str(buf), subkey, 0) == 0) 988 index_mm_searchwild_allvalues(node, out); 989 else 990 index_mm_free_node(node); 991 } else { 992 index_mm_free_node(node); 993 } 994 995 strbuf_popchars(buf, pushed); 996 } 997 998 /* Level 2: descend the tree (until we hit a wildcard) */ 999 static void index_mm_searchwild_node(struct index_mm_node *node, 1000 struct strbuf *buf, 1001 const char *key, int i, 1002 struct index_value **out) 1003 { 1004 struct index_mm_node *child; 1005 int j; 1006 int ch; 1007 1008 while(node) { 1009 for (j = 0; node->prefix[j]; j++) { 1010 ch = node->prefix[j]; 1011 1012 if (ch == '*' || ch == '?' || ch == '[') { 1013 index_mm_searchwild_all(node, j, buf, 1014 &key[i+j], out); 1015 return; 1016 } 1017 1018 if (ch != key[i+j]) { 1019 index_mm_free_node(node); 1020 return; 1021 } 1022 } 1023 1024 i += j; 1025 1026 child = index_mm_readchild(node, '*'); 1027 if (child) { 1028 strbuf_pushchar(buf, '*'); 1029 index_mm_searchwild_all(child, 0, buf, &key[i], out); 1030 strbuf_popchar(buf); 1031 } 1032 1033 child = index_mm_readchild(node, '?'); 1034 if (child) { 1035 strbuf_pushchar(buf, '?'); 1036 index_mm_searchwild_all(child, 0, buf, &key[i], out); 1037 strbuf_popchar(buf); 1038 } 1039 1040 child = index_mm_readchild(node, '['); 1041 if (child) { 1042 strbuf_pushchar(buf, '['); 1043 index_mm_searchwild_all(child, 0, buf, &key[i], out); 1044 strbuf_popchar(buf); 1045 } 1046 1047 if (key[i] == '\0') { 1048 index_mm_searchwild_allvalues(node, out); 1049 1050 return; 1051 } 1052 1053 child = index_mm_readchild(node, key[i]); 1054 index_mm_free_node(node); 1055 node = child; 1056 i++; 1057 } 1058 } 1059 1060 /* 1061 * Search the index for a key. The index may contain wildcards. 1062 * 1063 * Returns a list of all the values of matching keys. 1064 */ 1065 struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key) 1066 { 1067 struct index_mm_node *root = index_mm_readroot(idx); 1068 struct strbuf buf; 1069 struct index_value *out = NULL; 1070 1071 strbuf_init(&buf); 1072 index_mm_searchwild_node(root, &buf, key, 0, &out); 1073 strbuf_release(&buf); 1074 return out; 1075 } 1076
