Lines Matching +full:node +full:- +full:version
2 * libkmod - interface to kernel module operations
4 * Copyright (C) 2011-2013 ProFUSION embedded systems
9 * version 2.1 of the License, or (at your option) any later version.
33 #include "libkmod-internal.h"
34 #include "libkmod-index.h"
36 /* libkmod-index.c: module index file implementation
44 * We use a version string to keep track of changes to the binary format
65 * uint32_t version = INDEX_VERSION;
74 * uint32_t children[last - first + 1];
83 * Empty prefixes are omitted, leaf nodes omit the three child-related fields.
102 * + Normal node
103 * * Marked node, representing a key and it's values.
106 * |-a-+-s-+-k-*
108 * | `-t-+-e-*
110 * `-o-+-n-*-c-+-e-*
112 * `-e-*
119 * "easiest to understand as a space-optimized trie where
120 * each node with only one child is merged with its child"
123 * |-a-+-sk-*
125 * | `-te-*
127 * `-on-*-ce-*
129 * `-e-*
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.
137 * Since the index file is read-only, it can be compressed by omitting null
141 /* Format of node offsets within index file */
156 values = value->next; in index_values_free()
167 while (*values && (*values)->priority < priority) in add_value()
168 values = &(*values)->next; in add_value()
172 return -1; in add_value()
173 v->next = *values; in add_value()
174 v->priority = priority; in add_value()
175 v->len = len; in add_value()
176 memcpy(v->value, value, len); in add_value()
177 v->value[len] = '\0'; in add_value()
186 "Try re-running depmod\n", errno ? strerror(errno) : "EOF"); in read_error()
238 struct index_node_f *node; in index_read() local
259 child_count = last - first + 1; in index_read()
261 node = NOFAIL(malloc(sizeof(struct index_node_f) + in index_read()
264 node->first = first; in index_read()
265 node->last = last; in index_read()
268 node->children[i] = read_long(in); in index_read()
270 node = NOFAIL(malloc(sizeof(struct index_node_f))); in index_read()
271 node->first = INDEX_CHILDMAX; in index_read()
272 node->last = 0; in index_read()
275 node->values = NULL; in index_read()
285 while (value_count--) { in index_read()
289 add_value(&node->values, value, buf.used, priority); in index_read()
295 node->prefix = prefix; in index_read()
296 node->file = in; in index_read()
297 return node; in index_read()
300 static void index_close(struct index_node_f *node) in index_close() argument
302 free(node->prefix); in index_close()
303 index_values_free(node->values); in index_close()
304 free(node); in index_close()
315 uint32_t magic, version; in index_file_open() local
329 version = read_long(file); in index_file_open()
330 if (version >> 16 != INDEX_VERSION_MAJOR) { in index_file_open()
336 new->file = file; in index_file_open()
337 new->root_offset = read_long(new->file); in index_file_open()
345 fclose(idx->file); in index_file_close()
351 return index_read(in->file, in->root_offset); in index_readroot()
357 if (parent->first <= ch && ch <= parent->last) { in index_readchild()
358 return index_read(parent->file, in index_readchild()
359 parent->children[ch - parent->first]); in index_readchild()
365 static void index_dump_node(struct index_node_f *node, struct strbuf *buf, in index_dump_node() argument
371 pushed = strbuf_pushchars(buf, node->prefix); in index_dump_node()
373 for (v = node->values; v != NULL; v = v->next) { in index_dump_node()
374 write_str_safe(fd, buf->bytes, buf->used); in index_dump_node()
376 write_str_safe(fd, v->value, strlen(v->value)); in index_dump_node()
380 for (ch = node->first; ch <= node->last; ch++) { in index_dump_node()
381 struct index_node_f *child = index_readchild(node, ch); in index_dump_node()
392 index_close(node); in index_dump_node()
410 static char *index_search__node(struct index_node_f *node, const char *key, int i) in index_search__node() argument
417 while(node) { in index_search__node()
418 for (j = 0; node->prefix[j]; j++) { in index_search__node()
419 ch = node->prefix[j]; in index_search__node()
422 index_close(node); in index_search__node()
430 value = node->values != NULL in index_search__node()
431 ? strdup(node->values[0].value) in index_search__node()
434 index_close(node); in index_search__node()
438 child = index_readchild(node, key[i]); in index_search__node()
439 index_close(node); in index_search__node()
440 node = child; in index_search__node()
452 * The recursive functions free their node argument (using index_close).
468 /* Level 4: add all the values from a matching node */
469 static void index_searchwild__allvalues(struct index_node_f *node, in index_searchwild__allvalues() argument
474 for (v = node->values; v != NULL; v = v->next) in index_searchwild__allvalues()
475 add_value(out, v->value, v->len, v->priority); in index_searchwild__allvalues()
477 index_close(node); in index_searchwild__allvalues()
481 * Level 3: traverse a sub-keyspace which starts with a wildcard,
484 static void index_searchwild__all(struct index_node_f *node, int j, in index_searchwild__all() argument
492 while (node->prefix[j]) { in index_searchwild__all()
493 ch = node->prefix[j]; in index_searchwild__all()
500 for (ch = node->first; ch <= node->last; ch++) { in index_searchwild__all()
501 struct index_node_f *child = index_readchild(node, ch); in index_searchwild__all()
511 if (node->values) { in index_searchwild__all()
513 index_searchwild__allvalues(node, out); in index_searchwild__all()
515 index_close(node); in index_searchwild__all()
517 index_close(node); in index_searchwild__all()
524 static void index_searchwild__node(struct index_node_f *node, in index_searchwild__node() argument
533 while(node) { in index_searchwild__node()
534 for (j = 0; node->prefix[j]; j++) { in index_searchwild__node()
535 ch = node->prefix[j]; in index_searchwild__node()
538 index_searchwild__all(node, j, buf, in index_searchwild__node()
544 index_close(node); in index_searchwild__node()
551 child = index_readchild(node, '*'); in index_searchwild__node()
558 child = index_readchild(node, '?'); in index_searchwild__node()
565 child = index_readchild(node, '['); in index_searchwild__node()
573 index_searchwild__allvalues(node, out); in index_searchwild__node()
578 child = index_readchild(node, key[i]); in index_searchwild__node()
579 index_close(node); in index_searchwild__node()
580 node = child; in index_searchwild__node()
670 void *p = idx->mm; in index_mm_read_node()
671 struct index_mm_node *node; in index_mm_read_node() local
691 child_count = last - first + 1; in index_mm_read_node()
708 node = malloc(sizeof(struct index_mm_node) in index_mm_read_node()
711 if (node == NULL) in index_mm_read_node()
714 node->idx = idx; in index_mm_read_node()
715 node->prefix = prefix; in index_mm_read_node()
717 node->values.values = NULL; in index_mm_read_node()
719 node->values.values = (struct index_mm_value *) in index_mm_read_node()
720 ((char *)node + sizeof(struct index_mm_node) + in index_mm_read_node()
723 node->values.len = value_count; in index_mm_read_node()
724 node->first = first; in index_mm_read_node()
725 node->last = last; in index_mm_read_node()
726 memcpy(node->children, children, sizeof(uint32_t) * child_count); in index_mm_read_node()
729 struct index_mm_value *v = node->values.values + i; in index_mm_read_node()
730 v->priority = read_long_mm(&p); in index_mm_read_node()
731 v->value = read_chars_mm(&p, &v->len); in index_mm_read_node()
734 return node; in index_mm_read_node()
737 static void index_mm_free_node(struct index_mm_node *node) in index_mm_free_node() argument
739 free(node); in index_mm_free_node()
750 uint32_t version; in index_mm_open() member
762 return -ENOMEM; in index_mm_open()
767 err = -errno; in index_mm_open()
772 err = -EINVAL; in index_mm_open()
776 idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0); in index_mm_open()
777 if (idx->mm == MAP_FAILED) { in index_mm_open()
780 err = -errno; in index_mm_open()
784 p = idx->mm; in index_mm_open()
786 hdr.version = read_long_mm(&p); in index_mm_open()
792 err = -EINVAL; in index_mm_open()
796 if (hdr.version >> 16 != INDEX_VERSION_MAJOR) { in index_mm_open()
797 ERR(ctx, "major version check fail: %u instead of %u\n", in index_mm_open()
798 hdr.version >> 16, INDEX_VERSION_MAJOR); in index_mm_open()
799 err = -EINVAL; in index_mm_open()
803 idx->root_offset = hdr.root_offset; in index_mm_open()
804 idx->size = st.st_size; in index_mm_open()
805 idx->ctx = ctx; in index_mm_open()
814 munmap(idx->mm, st.st_size); in index_mm_open()
824 munmap(idx->mm, idx->size); in index_mm_close()
830 return index_mm_read_node(idx, idx->root_offset); in index_mm_readroot()
836 if (parent->first <= ch && ch <= parent->last) { in index_mm_readchild()
837 return index_mm_read_node(parent->idx, in index_mm_readchild()
838 parent->children[ch - parent->first]); in index_mm_readchild()
844 static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf, in index_mm_dump_node() argument
850 pushed = strbuf_pushchars(buf, node->prefix); in index_mm_dump_node()
852 itr = node->values.values; in index_mm_dump_node()
853 itr_end = itr + node->values.len; in index_mm_dump_node()
855 write_str_safe(fd, buf->bytes, buf->used); in index_mm_dump_node()
857 write_str_safe(fd, itr->value, itr->len); in index_mm_dump_node()
861 for (ch = node->first; ch <= node->last; ch++) { in index_mm_dump_node()
862 struct index_mm_node *child = index_mm_readchild(node, ch); in index_mm_dump_node()
873 index_mm_free_node(node); in index_mm_dump_node()
891 static char *index_mm_search_node(struct index_mm_node *node, const char *key, in index_mm_search_node() argument
899 while(node) { in index_mm_search_node()
900 for (j = 0; node->prefix[j]; j++) { in index_mm_search_node()
901 ch = node->prefix[j]; in index_mm_search_node()
904 index_mm_free_node(node); in index_mm_search_node()
912 value = node->values.len > 0 in index_mm_search_node()
913 ? strdup(node->values.values[0].value) in index_mm_search_node()
916 index_mm_free_node(node); in index_mm_search_node()
920 child = index_mm_readchild(node, key[i]); in index_mm_search_node()
921 index_mm_free_node(node); in index_mm_search_node()
922 node = child; in index_mm_search_node()
934 * The recursive functions free their node argument (using index_close).
948 /* Level 4: add all the values from a matching node */
949 static void index_mm_searchwild_allvalues(struct index_mm_node *node, in index_mm_searchwild_allvalues() argument
954 itr = node->values.values; in index_mm_searchwild_allvalues()
955 itr_end = itr + node->values.len; in index_mm_searchwild_allvalues()
957 add_value(out, itr->value, itr->len, itr->priority); in index_mm_searchwild_allvalues()
959 index_mm_free_node(node); in index_mm_searchwild_allvalues()
963 * Level 3: traverse a sub-keyspace which starts with a wildcard,
966 static void index_mm_searchwild_all(struct index_mm_node *node, int j, in index_mm_searchwild_all() argument
974 while (node->prefix[j]) { in index_mm_searchwild_all()
975 ch = node->prefix[j]; in index_mm_searchwild_all()
982 for (ch = node->first; ch <= node->last; ch++) { in index_mm_searchwild_all()
983 struct index_mm_node *child = index_mm_readchild(node, ch); in index_mm_searchwild_all()
993 if (node->values.len > 0) { in index_mm_searchwild_all()
995 index_mm_searchwild_allvalues(node, out); in index_mm_searchwild_all()
997 index_mm_free_node(node); in index_mm_searchwild_all()
999 index_mm_free_node(node); in index_mm_searchwild_all()
1006 static void index_mm_searchwild_node(struct index_mm_node *node, in index_mm_searchwild_node() argument
1015 while(node) { in index_mm_searchwild_node()
1016 for (j = 0; node->prefix[j]; j++) { in index_mm_searchwild_node()
1017 ch = node->prefix[j]; in index_mm_searchwild_node()
1020 index_mm_searchwild_all(node, j, buf, in index_mm_searchwild_node()
1026 index_mm_free_node(node); in index_mm_searchwild_node()
1033 child = index_mm_readchild(node, '*'); in index_mm_searchwild_node()
1040 child = index_mm_readchild(node, '?'); in index_mm_searchwild_node()
1047 child = index_mm_readchild(node, '['); in index_mm_searchwild_node()
1055 index_mm_searchwild_allvalues(node, out); in index_mm_searchwild_node()
1060 child = index_mm_readchild(node, key[i]); in index_mm_searchwild_node()
1061 index_mm_free_node(node); in index_mm_searchwild_node()
1062 node = child; in index_mm_searchwild_node()