Lines Matching defs:node
54 static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
55 static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
67 static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
68 static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
71 ldns_radix_node_t* node);
72 static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
73 static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
74 static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
75 static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
76 static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
77 static void ldns_radix_node_array_free(ldns_radix_node_t* node);
78 static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
79 static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
80 static void ldns_radix_array_reduce(ldns_radix_node_t* node);
81 static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
86 * Create a new radix node.
92 ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
93 if (!node) {
96 node->data = data;
97 node->key = key;
98 node->klen = len;
99 node->parent = NULL;
100 node->parent_index = 0;
101 node->len = 0;
102 node->offset = 0;
103 node->capacity = 0;
104 node->array = NULL;
105 return node;
265 /** Add new node. */
288 /** Add new node. */
336 ldns_radix_node_t* node = NULL;
343 node = tree->root;
344 while (node) {
346 return node->data?node:NULL;
349 if (byte < node->offset) {
352 byte -= node->offset;
353 if (byte >= node->len) {
357 if (node->array[byte].len > 0) {
359 if (pos + node->array[byte].len > len) {
362 if (memcmp(&key[pos], node->array[byte].str,
363 node->array[byte].len) != 0) {
366 pos += node->array[byte].len;
368 node = node->array[byte].edge;
383 ldns_radix_node_t* node = NULL;
393 node = tree->root;
396 if (byte < node->offset) {
399 * previous node.
401 ldns_radix_self_or_prev(node, result);
404 byte -= node->offset;
405 if (byte >= node->len) {
407 * No exact match. The lesser is in this node or the
408 * last of this array, or something before this node.
410 *result = ldns_radix_last_in_subtree_incl_self(node);
412 *result = ldns_radix_prev(node);
417 if (!node->array[byte].edge) {
422 *result = ldns_radix_prev_from_index(node, byte);
424 ldns_radix_self_or_prev(node, result);
428 if (node->array[byte].len != 0) {
430 if (pos + node->array[byte].len > len) {
432 if (memcmp(&key[pos], node->array[byte].str,
434 /** Key is before this node. */
436 node->array[byte].edge);
439 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
441 *result = ldns_radix_prev(node->array[byte].edge);
446 memcmp_res = memcmp(&key[pos], node->array[byte].str,
447 node->array[byte].len);
450 node->array[byte].edge);
453 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
455 *result = ldns_radix_prev(node->array[byte].edge);
460 pos += node->array[byte].len;
462 node = node->array[byte].edge;
464 if (node->data) {
466 *result = node;
469 /** There is a node which is an exact match, but has no element. */
470 *result = ldns_radix_prev(node);
513 ldns_radix_next(ldns_radix_node_t* node)
515 if (!node) {
518 if (node->len) {
520 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
526 while (node->parent) {
527 uint8_t index = node->parent_index;
528 node = node->parent;
530 for (; index < node->len; index++) {
531 if (node->array[index].edge) {
534 if (node->array[index].edge->data) {
535 return node->array[index].edge;
538 next = ldns_radix_next_in_subtree(node);
554 ldns_radix_prev(ldns_radix_node_t* node)
556 if (!node) {
561 while (node->parent) {
562 uint8_t index = node->parent_index;
564 node = node->parent;
565 assert(node->len > 0);
566 prev = ldns_radix_prev_from_index(node, index);
570 if (node->data) {
571 return node;
579 * Print node.
583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,
587 if (!node) {
604 if (node->data) {
605 fprintf(fd, " %s", (char*) node->data);
609 for (j = 0; j < node->len; j++) {
610 if (node->array[j].edge) {
611 ldns_radix_node_print(fd, node->array[j].edge, j,
612 node->array[j].str, node->array[j].len, d+1);
655 /** Insert current node into tree1 */
702 /** Delete current node from tree1. */
707 /** Insert current node into tree2/ */
740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,
744 if (!node) {
747 for (i=0; i < node->len; i++) {
748 ldns_radix_traverse_postorder(node->array[i].edge,
752 (*func)(node, arg);
776 /** Start searching at the root node */
786 /** For each node, look if we can make further progress */
794 /** key < node */
799 /** key > node */
807 return 1; /* no match at child node */
811 return 1; /* no match at child node */
815 /** Continue searching prefix at this child node */
820 /** Update the prefix node */
830 * Make space in the node's array for another byte.
831 * @param node: node.
837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
840 if (!node->array) {
841 assert(node->capacity == 0);
843 node->array = LDNS_MALLOC(ldns_radix_array_t);
844 if (!node->array) {
847 memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
848 node->len = 1;
849 node->capacity = 1;
850 node->offset = byte;
854 assert(node->array != NULL);
855 assert(node->capacity > 0);
857 if (node->len == 0) {
859 node->len = 1;
860 node->offset = byte;
861 } else if (byte < node->offset) {
864 uint16_t need = node->offset - byte;
866 if (node->len + need > node->capacity) {
868 if (!ldns_radix_array_grow(node,
869 (unsigned) (node->len + need))) {
874 memmove(&node->array[need], &node->array[0],
875 node->len*sizeof(ldns_radix_array_t));
877 for (index = 0; index < node->len; index++) {
878 if (node->array[index+need].edge) {
879 node->array[index+need].edge->parent_index =
884 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
885 node->len += need;
886 node->offset = byte;
887 } else if (byte - node->offset >= node->len) {
889 uint16_t need = (byte - node->offset) - node->len + 1;
891 if (node->len + need > node->capacity) {
893 if (!ldns_radix_array_grow(node,
894 (unsigned) (node->len + need))) {
899 memset(&node->array[node->len], 0,
901 node->len += need;
909 * @param node: node.
916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
918 unsigned size = ((unsigned)node->capacity)*2;
930 assert(node->len <= node->capacity);
931 assert(node->capacity < size);
932 memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
933 LDNS_FREE(node->array);
934 node->array = a;
935 node->capacity = size;
994 * @param add: node to be added.
1036 /** Make space in array for the new node */
1044 * The added node should go direct under the existing parent.
1045 * The existing node should go under the added node.
1080 /** Make space in array for the new node */
1087 * The added node should go direct under the existing node.
1096 /** Create a new split node. */
1115 /** Create the new common node. */
1143 /** Make space in the common node array. */
1154 * The common node should go direct under the parent node.
1155 * The added and existing nodes go under the common node.
1226 * Find the next element in the subtree of this node.
1227 * @param node: node.
1228 * @return: node with next element.
1232 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1237 for (i = 0; i < node->len; i++) {
1238 if (node->array[i].edge) {
1240 if (node->array[i].edge->data) {
1241 return node->array[i].edge;
1244 next = ldns_radix_next_in_subtree(node->array[i].edge);
1255 * Find the previous element in the array of this node, from index.
1256 * @param node: node.
1258 * @return previous node from index.
1262 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1267 if (node->array[i].edge) {
1269 ldns_radix_last_in_subtree_incl_self(node);
1280 * Find last node in subtree, or this node (if have data).
1281 * @param node: node.
1282 * @return last node in subtree, or this node, or NULL.
1286 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1288 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1291 } else if (node->data) {
1292 return node;
1299 * Find last node in subtree.
1300 * @param node: node.
1301 * @return last node in subtree.
1305 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
1308 /** Look for the most right leaf node. */
1309 for (i=(int)(node->len)-1; i >= 0; i--) {
1310 if (node->array[i].edge) {
1311 /** Keep looking for the most right leaf node. */
1312 if (node->array[i].edge->len > 0) {
1315 node->array[i].edge);
1320 /** Could this be the most right leaf node? */
1321 if (node->array[i].edge->data) {
1322 return node->array[i].edge;
1333 * @param node: node with deleted element.
1337 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1339 while (node) {
1340 if (node->data) {
1343 } else if (node->len == 1 && node->parent) {
1345 ldns_radix_cleanup_onechild(node);
1347 } else if (node->len == 0) {
1348 /** Leaf node. */
1349 ldns_radix_node_t* parent = node->parent;
1351 /** The root is a leaf node. */
1352 ldns_radix_node_free(node, NULL);
1356 /** Cleanup leaf node and continue with parent. */
1357 ldns_radix_cleanup_leaf(node);
1358 node = parent;
1373 * Clean up a node with one child.
1374 * @param node: node with one child.
1378 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
1382 uint8_t parent_index = node->parent_index;
1383 ldns_radix_node_t* child = node->array[0].edge;
1384 ldns_radix_node_t* parent = node->parent;
1386 /** Node has one child, merge the child node into the parent node. */
1388 join_len = parent->array[parent_index].len + node->array[0].len + 1;
1394 * This tree is now inefficient, with the empty node still
1403 node->offset;
1405 node->array[0].str, node->array[0].len);
1413 ldns_radix_node_free(node, NULL);
1419 * Clean up a leaf node.
1420 * @param node: leaf node.
1424 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
1426 uint8_t parent_index = node->parent_index;
1427 ldns_radix_node_t* parent = node->parent;
1428 /** Delete lead node and fix parent array. */
1430 ldns_radix_node_free(node, NULL);
1448 * Free a radix node.
1449 * @param node: node.
1454 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1458 if (!node) {
1461 for (i=0; i < node->len; i++) {
1462 LDNS_FREE(node->array[i].str);
1464 node->key = NULL;
1465 node->klen = 0;
1466 LDNS_FREE(node->array);
1467 LDNS_FREE(node);
1474 * @param node: node.
1478 ldns_radix_node_array_free(ldns_radix_node_t* node)
1480 node->offset = 0;
1481 node->len = 0;
1482 LDNS_FREE(node->array);
1483 node->array = NULL;
1484 node->capacity = 0;
1491 * @param node: node.
1495 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1499 while (n < node->len && node->array[n].edge == NULL) {
1505 if (n == node->len) {
1506 ldns_radix_node_array_free(node);
1509 assert(n < node->len);
1510 assert((int) n <= (255 - (int) node->offset));
1511 memmove(&node->array[0], &node->array[n],
1512 (node->len - n)*sizeof(ldns_radix_array_t));
1513 node->offset += n;
1514 node->len -= n;
1515 for (i=0; i < node->len; i++) {
1516 if (node->array[i].edge) {
1517 node->array[i].edge->parent_index = i;
1520 ldns_radix_array_reduce(node);
1527 * @param node: node.
1531 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1535 while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1541 if (n == node->len) {
1542 ldns_radix_node_array_free(node);
1545 assert(n < node->len);
1546 node->len -= n;
1547 ldns_radix_array_reduce(node);
1554 * @param node: node.
1558 ldns_radix_array_reduce(ldns_radix_node_t* node)
1560 if (node->len <= node->capacity/2 && node->len != node->capacity) {
1562 node->len);
1566 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1567 LDNS_FREE(node->array);
1568 node->array = a;
1569 node->capacity = node->len;
1577 * @param node: from this node.
1578 * @param result: result node.
1582 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1584 if (node->data) {
1585 *result = node;
1587 *result = ldns_radix_prev(node);