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,
92 	ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);  in ldns_radix_new_node()  local
93 	if (!node) {  in ldns_radix_new_node()
96 	node->data = data;  in ldns_radix_new_node()
97 	node->key = key;  in ldns_radix_new_node()
98 	node->klen = len;  in ldns_radix_new_node()
99 	node->parent = NULL;  in ldns_radix_new_node()
100 	node->parent_index = 0;  in ldns_radix_new_node()
101 	node->len = 0;  in ldns_radix_new_node()
102 	node->offset = 0;  in ldns_radix_new_node()
103 	node->capacity = 0;  in ldns_radix_new_node()
104 	node->array = NULL;  in ldns_radix_new_node()
105 	return node;  in ldns_radix_new_node()
336 	ldns_radix_node_t* node = NULL;  in ldns_radix_search()  local
343 	node = tree->root;  in ldns_radix_search()
344 	while (node) {  in ldns_radix_search()
346 			return node->data?node:NULL;  in ldns_radix_search()
349 		if (byte < node->offset) {  in ldns_radix_search()
352 		byte -= node->offset;  in ldns_radix_search()
353 		if (byte >= node->len) {  in ldns_radix_search()
357 		if (node->array[byte].len > 0) {  in ldns_radix_search()
359 			if (pos + node->array[byte].len > len) {  in ldns_radix_search()
362 			if (memcmp(&key[pos], node->array[byte].str,  in ldns_radix_search()
363 				node->array[byte].len) != 0) {  in ldns_radix_search()
366 			pos += node->array[byte].len;  in ldns_radix_search()
368 		node = node->array[byte].edge;  in ldns_radix_search()
383 	ldns_radix_node_t* node = NULL;  in ldns_radix_find_less_equal()  local
393 	node = tree->root;  in ldns_radix_find_less_equal()
396 		if (byte < node->offset) {  in ldns_radix_find_less_equal()
401 			ldns_radix_self_or_prev(node, result);  in ldns_radix_find_less_equal()
404 		byte -= node->offset;  in ldns_radix_find_less_equal()
405 		if (byte >= node->len) {  in ldns_radix_find_less_equal()
410 			*result = ldns_radix_last_in_subtree_incl_self(node);  in ldns_radix_find_less_equal()
412 				*result = ldns_radix_prev(node);  in ldns_radix_find_less_equal()
417 		if (!node->array[byte].edge) {  in ldns_radix_find_less_equal()
422 			*result = ldns_radix_prev_from_index(node, byte);  in ldns_radix_find_less_equal()
424 				ldns_radix_self_or_prev(node, result);  in ldns_radix_find_less_equal()
428 		if (node->array[byte].len != 0) {  in ldns_radix_find_less_equal()
430 			if (pos + node->array[byte].len > len) {  in ldns_radix_find_less_equal()
432 				if (memcmp(&key[pos], node->array[byte].str,  in ldns_radix_find_less_equal()
436 						node->array[byte].edge);  in ldns_radix_find_less_equal()
439 					*result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);  in ldns_radix_find_less_equal()
441 						 *result = ldns_radix_prev(node->array[byte].edge);  in ldns_radix_find_less_equal()
446 			memcmp_res = memcmp(&key[pos], node->array[byte].str,  in ldns_radix_find_less_equal()
447 				node->array[byte].len);  in ldns_radix_find_less_equal()
450 					node->array[byte].edge);  in ldns_radix_find_less_equal()
453 				*result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);  in ldns_radix_find_less_equal()
455 					 *result = ldns_radix_prev(node->array[byte].edge);  in ldns_radix_find_less_equal()
460 			pos += node->array[byte].len;  in ldns_radix_find_less_equal()
462 		node = node->array[byte].edge;  in ldns_radix_find_less_equal()
464 	if (node->data) {  in ldns_radix_find_less_equal()
466 		*result = node;  in ldns_radix_find_less_equal()
470 	*result = ldns_radix_prev(node);  in ldns_radix_find_less_equal()
513 ldns_radix_next(ldns_radix_node_t* node)  in ldns_radix_next()  argument
515 	if (!node) {  in ldns_radix_next()
518 	if (node->len) {  in ldns_radix_next()
520 		ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);  in ldns_radix_next()
526 	while (node->parent) {  in ldns_radix_next()
527 		uint8_t index = node->parent_index;  in ldns_radix_next()
528 		node = node->parent;  in ldns_radix_next()
530 		for (; index < node->len; index++) {  in ldns_radix_next()
531 			if (node->array[index].edge) {  in ldns_radix_next()
534 				if (node->array[index].edge->data) {  in ldns_radix_next()
535 					return node->array[index].edge;  in ldns_radix_next()
538 				next = ldns_radix_next_in_subtree(node);  in ldns_radix_next()
554 ldns_radix_prev(ldns_radix_node_t* node)  in ldns_radix_prev()  argument
556 	if (!node) {  in ldns_radix_prev()
561 	while (node->parent) {  in ldns_radix_prev()
562 		uint8_t index = node->parent_index;  in ldns_radix_prev()
564 		node = node->parent;  in ldns_radix_prev()
565 		assert(node->len > 0);  in ldns_radix_prev()
566 		prev = ldns_radix_prev_from_index(node, index);  in ldns_radix_prev()
570 		if (node->data) {  in ldns_radix_prev()
571 			return node;  in ldns_radix_prev()
583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,  in ldns_radix_node_print()  argument
587 	if (!node) {  in ldns_radix_node_print()
604 	if (node->data) {  in ldns_radix_node_print()
605 		fprintf(fd, " %s", (char*) node->data);  in ldns_radix_node_print()
609 	for (j = 0; j < node->len; j++) {  in ldns_radix_node_print()
610 		if (node->array[j].edge) {  in ldns_radix_node_print()
611 			ldns_radix_node_print(fd, node->array[j].edge, j,  in ldns_radix_node_print()
612 				node->array[j].str, node->array[j].len, d+1);  in ldns_radix_node_print()
740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,  in ldns_radix_traverse_postorder()  argument
744 	if (!node) {  in ldns_radix_traverse_postorder()
747 	for (i=0; i < node->len; i++) {  in ldns_radix_traverse_postorder()
748 		ldns_radix_traverse_postorder(node->array[i].edge,  in ldns_radix_traverse_postorder()
752 	(*func)(node, arg);  in ldns_radix_traverse_postorder()
837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)  in ldns_radix_array_space()  argument
840 	if (!node->array) {  in ldns_radix_array_space()
841 		assert(node->capacity == 0);  in ldns_radix_array_space()
843 		node->array = LDNS_MALLOC(ldns_radix_array_t);  in ldns_radix_array_space()
844 		if (!node->array) {  in ldns_radix_array_space()
847 		memset(&node->array[0], 0, sizeof(ldns_radix_array_t));  in ldns_radix_array_space()
848 		node->len = 1;  in ldns_radix_array_space()
849 		node->capacity = 1;  in ldns_radix_array_space()
850 		node->offset = byte;  in ldns_radix_array_space()
854 	assert(node->array != NULL);  in ldns_radix_array_space()
855 	assert(node->capacity > 0);  in ldns_radix_array_space()
857 	if (node->len == 0) {  in ldns_radix_array_space()
859 		node->len = 1;  in ldns_radix_array_space()
860 		node->offset = byte;  in ldns_radix_array_space()
861 	} else if (byte < node->offset) {  in ldns_radix_array_space()
864 		uint16_t need = node->offset - byte;  in ldns_radix_array_space()
866 		if (node->len + need > node->capacity) {  in ldns_radix_array_space()
868 			if (!ldns_radix_array_grow(node,  in ldns_radix_array_space()
869 				(unsigned) (node->len + need))) {  in ldns_radix_array_space()
874 		memmove(&node->array[need], &node->array[0],  in ldns_radix_array_space()
875 			node->len*sizeof(ldns_radix_array_t));  in ldns_radix_array_space()
877 		for (index = 0; index < node->len; index++) {  in ldns_radix_array_space()
878 			if (node->array[index+need].edge) {  in ldns_radix_array_space()
879 				node->array[index+need].edge->parent_index =  in ldns_radix_array_space()
884 		memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));  in ldns_radix_array_space()
885 		node->len += need;  in ldns_radix_array_space()
886 		node->offset = byte;  in ldns_radix_array_space()
887 	} else if (byte - node->offset >= node->len) {  in ldns_radix_array_space()
889 		uint16_t need = (byte - node->offset) - node->len + 1;  in ldns_radix_array_space()
891 		if (node->len + need > node->capacity) {  in ldns_radix_array_space()
893 			if (!ldns_radix_array_grow(node,  in ldns_radix_array_space()
894 				(unsigned) (node->len + need))) {  in ldns_radix_array_space()
899 		memset(&node->array[node->len], 0,  in ldns_radix_array_space()
901 		node->len += need;  in ldns_radix_array_space()
916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)  in ldns_radix_array_grow()  argument
918 	unsigned size = ((unsigned)node->capacity)*2;  in ldns_radix_array_grow()
930 	assert(node->len <= node->capacity);  in ldns_radix_array_grow()
931 	assert(node->capacity < size);  in ldns_radix_array_grow()
932 	memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));  in ldns_radix_array_grow()
933 	LDNS_FREE(node->array);  in ldns_radix_array_grow()
934 	node->array = a;  in ldns_radix_array_grow()
935 	node->capacity = size;  in ldns_radix_array_grow()
1235 ldns_radix_next_in_subtree(ldns_radix_node_t* node)  in ldns_radix_next_in_subtree()  argument
1240 	for (i = 0; i < node->len; i++) {  in ldns_radix_next_in_subtree()
1241 		if (node->array[i].edge) {  in ldns_radix_next_in_subtree()
1243 			if (node->array[i].edge->data) {  in ldns_radix_next_in_subtree()
1244 				return node->array[i].edge;  in ldns_radix_next_in_subtree()
1247 			next = ldns_radix_next_in_subtree(node->array[i].edge);  in ldns_radix_next_in_subtree()
1265 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)  in ldns_radix_prev_from_index()  argument
1270 		if (node->array[i].edge) {  in ldns_radix_prev_from_index()
1272 				ldns_radix_last_in_subtree_incl_self(node);  in ldns_radix_prev_from_index()
1289 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)  in ldns_radix_last_in_subtree_incl_self()  argument
1291 	ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);  in ldns_radix_last_in_subtree_incl_self()
1294 	} else if (node->data) {  in ldns_radix_last_in_subtree_incl_self()
1295 		return node;  in ldns_radix_last_in_subtree_incl_self()
1308 ldns_radix_last_in_subtree(ldns_radix_node_t* node)  in ldns_radix_last_in_subtree()  argument
1312 	for (i=(int)(node->len)-1; i >= 0; i--) {  in ldns_radix_last_in_subtree()
1313 		if (node->array[i].edge) {  in ldns_radix_last_in_subtree()
1315 			if (node->array[i].edge->len > 0) {  in ldns_radix_last_in_subtree()
1318 					node->array[i].edge);  in ldns_radix_last_in_subtree()
1324 			if (node->array[i].edge->data) {  in ldns_radix_last_in_subtree()
1325 				return node->array[i].edge;  in ldns_radix_last_in_subtree()
1340 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)  in ldns_radix_del_fix()  argument
1342 	while (node) {  in ldns_radix_del_fix()
1343 		if (node->data) {  in ldns_radix_del_fix()
1346 		} else if (node->len == 1 && node->parent) {  in ldns_radix_del_fix()
1348 			ldns_radix_cleanup_onechild(node);  in ldns_radix_del_fix()
1350 		} else if (node->len == 0) {  in ldns_radix_del_fix()
1352 			ldns_radix_node_t* parent = node->parent;  in ldns_radix_del_fix()
1355 				ldns_radix_node_free(node, NULL);  in ldns_radix_del_fix()
1360 			ldns_radix_cleanup_leaf(node);  in ldns_radix_del_fix()
1361 			node = parent;  in ldns_radix_del_fix()
1381 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)  in ldns_radix_cleanup_onechild()  argument
1385 	uint8_t parent_index = node->parent_index;  in ldns_radix_cleanup_onechild()
1386 	ldns_radix_node_t* child = node->array[0].edge;  in ldns_radix_cleanup_onechild()
1387 	ldns_radix_node_t* parent = node->parent;  in ldns_radix_cleanup_onechild()
1391 	join_len = parent->array[parent_index].len + node->array[0].len + 1;  in ldns_radix_cleanup_onechild()
1406 		node->offset;  in ldns_radix_cleanup_onechild()
1408 		node->array[0].str, node->array[0].len);  in ldns_radix_cleanup_onechild()
1416 	ldns_radix_node_free(node, NULL);  in ldns_radix_cleanup_onechild()
1427 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)  in ldns_radix_cleanup_leaf()  argument
1429 	uint8_t parent_index = node->parent_index;  in ldns_radix_cleanup_leaf()
1430 	ldns_radix_node_t* parent = node->parent;  in ldns_radix_cleanup_leaf()
1433 	ldns_radix_node_free(node, NULL);  in ldns_radix_cleanup_leaf()
1457 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)  in ldns_radix_node_free()  argument
1461 	if (!node) {  in ldns_radix_node_free()
1464 	for (i=0; i < node->len; i++) {  in ldns_radix_node_free()
1465 		LDNS_FREE(node->array[i].str);  in ldns_radix_node_free()
1467 	node->key = NULL;  in ldns_radix_node_free()
1468 	node->klen = 0;  in ldns_radix_node_free()
1469 	LDNS_FREE(node->array);  in ldns_radix_node_free()
1470 	LDNS_FREE(node);  in ldns_radix_node_free()
1481 ldns_radix_node_array_free(ldns_radix_node_t* node)  in ldns_radix_node_array_free()  argument
1483 	node->offset = 0;  in ldns_radix_node_array_free()
1484 	node->len = 0;  in ldns_radix_node_array_free()
1485 	LDNS_FREE(node->array);  in ldns_radix_node_array_free()
1486 	node->array = NULL;  in ldns_radix_node_array_free()
1487 	node->capacity = 0;  in ldns_radix_node_array_free()
1498 ldns_radix_node_array_free_front(ldns_radix_node_t* node)  in ldns_radix_node_array_free_front()  argument
1502    	while (n < node->len && node->array[n].edge == NULL) {  in ldns_radix_node_array_free_front()
1508 	if (n == node->len) {  in ldns_radix_node_array_free_front()
1509 		ldns_radix_node_array_free(node);  in ldns_radix_node_array_free_front()
1512 	assert(n < node->len);  in ldns_radix_node_array_free_front()
1513 	assert((int) n <= (255 - (int) node->offset));  in ldns_radix_node_array_free_front()
1514 	memmove(&node->array[0], &node->array[n],  in ldns_radix_node_array_free_front()
1515 		(node->len - n)*sizeof(ldns_radix_array_t));  in ldns_radix_node_array_free_front()
1516 	node->offset += n;  in ldns_radix_node_array_free_front()
1517 	node->len -= n;  in ldns_radix_node_array_free_front()
1518 	for (i=0; i < node->len; i++) {  in ldns_radix_node_array_free_front()
1519 		if (node->array[i].edge) {  in ldns_radix_node_array_free_front()
1520 			node->array[i].edge->parent_index = i;  in ldns_radix_node_array_free_front()
1523 	ldns_radix_array_reduce(node);  in ldns_radix_node_array_free_front()
1534 ldns_radix_node_array_free_end(ldns_radix_node_t* node)  in ldns_radix_node_array_free_end()  argument
1538 	while (n < node->len && node->array[node->len-1-n].edge == NULL) {  in ldns_radix_node_array_free_end()
1544 	if (n == node->len) {  in ldns_radix_node_array_free_end()
1545 		ldns_radix_node_array_free(node);  in ldns_radix_node_array_free_end()
1548 	assert(n < node->len);  in ldns_radix_node_array_free_end()
1549 	node->len -= n;  in ldns_radix_node_array_free_end()
1550 	ldns_radix_array_reduce(node);  in ldns_radix_node_array_free_end()
1561 ldns_radix_array_reduce(ldns_radix_node_t* node)  in ldns_radix_array_reduce()  argument
1563 	if (node->len <= node->capacity/2 && node->len != node->capacity) {  in ldns_radix_array_reduce()
1565 								node->len);  in ldns_radix_array_reduce()
1569 		memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);  in ldns_radix_array_reduce()
1570 		LDNS_FREE(node->array);  in ldns_radix_array_reduce()
1571 		node->array = a;  in ldns_radix_array_reduce()
1572 		node->capacity = node->len;  in ldns_radix_array_reduce()
1585 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)  in ldns_radix_self_or_prev()  argument
1587 	if (node->data) {  in ldns_radix_self_or_prev()
1588 		*result = node;  in ldns_radix_self_or_prev()
1590 		*result = ldns_radix_prev(node);  in ldns_radix_self_or_prev()