Lines Matching defs:trie
35 * Uses a Patricia/radix trie to index all matches for efficient lookup.
44 /* in-memory trie objects */
45 struct trie {
86 static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
95 trie->children_count++;
100 trie->nodes_count++;
131 struct trie *trie = trie_values_cmp_param;
133 return strcmp(trie->strings->buf + val1->key_off,
134 trie->strings->buf + val2->key_off);
141 static int trie_node_add_value(struct trie *trie, struct trie_node *node,
146 k = strbuf_add_string(trie->strings, key, strlen(key));
149 v = strbuf_add_string(trie->strings, value, strlen(value));
159 val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp_r, trie);
171 trie->values_count++;
176 trie_values_cmp_param = trie;
181 static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
191 for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
212 s = strndup(trie->strings->buf + node->prefix_off, p);
216 off = strbuf_add_string(trie->strings, s, p);
225 err = node_add_child(trie, node, new_child, c);
236 return trie_node_add_value(trie, node, key, value);
247 off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
254 err = node_add_child(trie, node, child, c);
260 return trie_node_add_value(trie, child, key, value);
270 struct trie *trie;
279 static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
283 trie_store_nodes_size(trie, node->children[i].child);
285 trie->strings_off += sizeof(struct trie_node_f);
287 trie->strings_off += sizeof(struct trie_child_entry_f);
289 trie->strings_off += sizeof(struct trie_value_entry_f);
292 static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
295 .prefix_off = htole64(trie->strings_off + node->prefix_off),
312 child_off = trie_store_nodes(trie, node->children[i].child);
322 node_off = ftello(trie->f);
323 fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
324 trie->nodes_count++;
328 fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
329 trie->children_count += node->children_count;
336 .key_off = htole64(trie->strings_off + node->values[i].key_off),
337 .value_off = htole64(trie->strings_off + node->values[i].value_off),
340 fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);
341 trie->values_count++;
347 static int trie_store(struct trie *trie, const char *filename) {
349 .trie = trie,
367 trie_store_nodes_size(&t, trie->root);
381 root_off = trie_store_nodes(&t, trie->root);
387 fwrite(trie->strings->buf, trie->strings->len, 1, t.f);
388 h.strings_len = htole64(trie->strings->len);
409 log_debug("=== trie on-disk ===");
418 log_debug("string store: %8zu bytes", trie->strings->len);
424 static int insert_data(struct trie *trie, struct udev_list *match_list,
451 trie_insert(trie, trie->root, udev_list_entry_get_name(entry), line, value);
456 static int import_file(struct udev *udev, struct trie *trie, const char *filename) {
528 err = insert_data(trie, &match_list, line, filename);
549 err = insert_data(trie, &match_list, line, filename);
583 struct trie *trie = NULL;
616 trie = new0(struct trie, 1);
617 if (!trie) {
623 trie->strings = strbuf_new();
624 if (!trie->strings) {
630 trie->root = new0(struct trie_node, 1);
631 if (!trie->root) {
635 trie->nodes_count++;
645 import_file(udev, trie, *f);
649 strbuf_complete(trie->strings);
651 log_debug("=== trie in-memory ===");
653 trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
655 trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
657 trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
659 trie->strings->len);
661 trie->strings->in_len, trie->strings->in_count);
663 trie->strings->dedup_len, trie->strings->dedup_count);
670 err = trie_store(trie, hwdb_bin);
689 if (trie) {
690 if (trie->root)
691 trie_node_cleanup(trie->root);
692 strbuf_cleanup(trie->strings);
693 free(trie);