Lines Matching defs:trie
38 * Uses a Patricia/radix trie to index all matches for efficient lookup.
47 /* in-memory trie objects */
48 struct trie {
89 static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
98 trie->children_count++;
103 trie->nodes_count++;
132 struct trie *trie = arg;
134 return strcmp(trie->strings->buf + val1->key_off,
135 trie->strings->buf + val2->key_off);
138 static int trie_node_add_value(struct trie *trie, struct trie_node *node,
143 k = strbuf_add_string(trie->strings, key, strlen(key));
146 v = strbuf_add_string(trie->strings, value, strlen(value));
156 val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
168 trie->values_count++;
173 qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
177 static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
187 for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
208 s = strndup(trie->strings->buf + node->prefix_off, p);
212 off = strbuf_add_string(trie->strings, s, p);
221 err = node_add_child(trie, node, new_child, c);
232 return trie_node_add_value(trie, node, key, value);
243 off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
250 err = node_add_child(trie, node, child, c);
256 return trie_node_add_value(trie, child, key, value);
266 struct trie *trie;
275 static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
279 trie_store_nodes_size(trie, node->children[i].child);
281 trie->strings_off += sizeof(struct trie_node_f);
283 trie->strings_off += sizeof(struct trie_child_entry_f);
285 trie->strings_off += sizeof(struct trie_value_entry_f);
288 static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
291 .prefix_off = htole64(trie->strings_off + node->prefix_off),
308 child_off = trie_store_nodes(trie, node->children[i].child);
318 node_off = ftello(trie->f);
319 fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
320 trie->nodes_count++;
324 fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
325 trie->children_count += node->children_count;
332 .key_off = htole64(trie->strings_off + node->values[i].key_off),
333 .value_off = htole64(trie->strings_off + node->values[i].value_off),
336 fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);
337 trie->values_count++;
343 static int trie_store(struct trie *trie, const char *filename) {
345 .trie = trie,
363 trie_store_nodes_size(&t, trie->root);
377 root_off = trie_store_nodes(&t, trie->root);
383 fwrite(trie->strings->buf, trie->strings->len, 1, t.f);
384 h.strings_len = htole64(trie->strings->len);
405 log_debug("=== trie on-disk ===");
414 log_debug("string store: %8zu bytes", trie->strings->len);
420 static int insert_data(struct trie *trie, struct udev_list *match_list,
444 trie_insert(trie, trie->root, udev_list_entry_get_name(entry), line, value);
449 static int import_file(struct udev *udev, struct trie *trie, const char *filename) {
515 insert_data(trie, &match_list, line, filename);
533 insert_data(trie, &match_list, line, filename);
569 struct trie *trie = NULL;
605 trie = new0(struct trie, 1);
606 if (!trie) {
612 trie->strings = strbuf_new();
613 if (!trie->strings) {
619 trie->root = new0(struct trie_node, 1);
620 if (!trie->root) {
624 trie->nodes_count++;
634 import_file(udev, trie, *f);
638 strbuf_complete(trie->strings);
640 log_debug("=== trie in-memory ===");
642 trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
644 trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
646 trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
648 trie->strings->len);
650 trie->strings->in_len, trie->strings->in_count);
652 trie->strings->dedup_len, trie->strings->dedup_count);
660 err = trie_store(trie, hwdb_bin);
680 if (trie) {
681 if (trie->root)
682 trie_node_cleanup(trie->root);
683 strbuf_cleanup(trie->strings);
684 free(trie);