Lines Matching defs:node
55 /* prefix, common part for all children of this node */
86 static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
90 child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));
94 node->children = child;
96 node->children[node->children_count].c = c;
97 node->children[node->children_count].child = node_child;
98 node->children_count++;
99 qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
105 static struct trie_node *node_lookup(const struct trie_node *node, uint8_t c) {
110 child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
116 static void trie_node_cleanup(struct trie_node *node) {
119 for (i = 0; i < node->children_count; i++)
120 trie_node_cleanup(node->children[i].child);
121 free(node->children);
122 free(node->values);
123 free(node);
141 static int trie_node_add_value(struct trie *trie, struct trie_node *node,
153 if (node->values_count) {
159 val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp_r, trie);
168 val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));
172 node->values = val;
173 node->values[node->values_count].key_off = k;
174 node->values[node->values_count].value_off = v;
175 node->values_count++;
177 qsort(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp);
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++) {
199 /* split node */
205 new_child->prefix_off = node->prefix_off + p+1;
206 new_child->children = node->children;
207 new_child->children_count = node->children_count;
208 new_child->values = node->values;
209 new_child->values_count = node->values_count;
212 s = strndup(trie->strings->buf + node->prefix_off, p);
220 node->prefix_off = off;
221 node->children = NULL;
222 node->children_count = 0;
223 node->values = NULL;
224 node->values_count = 0;
225 err = node_add_child(trie, node, new_child, c);
236 return trie_node_add_value(trie, node, key, value);
238 child = node_lookup(node, c);
254 err = node_add_child(trie, node, child, c);
263 node = child;
279 static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
282 for (i = 0; i < node->children_count; i++)
283 trie_store_nodes_size(trie, node->children[i].child);
286 for (i = 0; i < node->children_count; i++)
288 for (i = 0; i < node->values_count; i++)
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),
296 .children_count = node->children_count,
297 .values_count = htole64(node->values_count),
302 if (node->children_count) {
303 children = new0(struct trie_child_entry_f, node->children_count);
309 for (i = 0; i < node->children_count; i++) {
312 child_off = trie_store_nodes(trie, node->children[i].child);
317 children[i].c = node->children[i].c;
321 /* write node */
327 if (node->children_count) {
328 fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
329 trie->children_count += node->children_count;
334 for (i = 0; i < node->values_count; i++) {
336 .key_off = htole64(trie->strings_off + node->values[i].key_off),
337 .value_off = htole64(trie->strings_off + node->values[i].value_off),