contrib/ldns/radix.c

51 	radix_strlen_t len);
53 	radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
57 	radix_strlen_t pos, radix_strlen_t len);
62 	radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
98 	node->klen = len;
101 	node->len = 0;
168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
178 	add = ldns_radix_new_node(data, key, len);
183 	if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
186 		if (len == 0) {
213 			if (len > 1) {
216 					len, &prefix->array[0].str,
217 					&prefix->array[0].len)) {
226 	} else if (pos == len) {
235 		prefix->klen = len; /* redundant */
239 		assert(pos < len);
241 			(byte - prefix->offset) >= prefix->len) {
254 			assert((byte - prefix->offset) <= prefix->len);
256 			if (pos+1 < len) {
260 					len)) {
279 			if (pos+1 < len) {
283 					len)) {
298 				key, pos+1, len, add)) {
314 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
316     ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
334 ldns_radix_search(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
345 		if (pos == len) {
353 		if (byte >= node->len) {
357 		if (node->array[byte].len > 0) {
359 			if (pos + node->array[byte].len > len) {
363 				node->array[byte].len) != 0) {
366 			pos += node->array[byte].len;
381 	radix_strlen_t len, ldns_radix_node_t** result)
394 	while (pos < len) {
405 		if (byte >= node->len) {
428 		if (node->array[byte].len != 0) {
430 			if (pos + node->array[byte].len > len) {
433 					len-pos) <= 0) {
447 				node->array[byte].len);
460 			pos += node->array[byte].len;
518 	if (node->len) {
530 		for (; index < node->len; index++) {
565 		assert(node->len > 0);
584 	uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d)
596 		for (l=0; l < len; l++) {
599 		fprintf(fd, "]%u", (unsigned) len);
609 	for (j = 0; j < node->len; j++) {
612 				node->array[j].str, node->array[j].len, d+1);
747 	for (i=0; i < node->len; i++) {
763  * @param len:    length of key.
764  * @param result: the longest prefix, the entry itself if *pos==len,
767  *                If *pos==len, an exact match is found.
774 	radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos)
788 		if (pos == len) {
798 		if (byte >= n->len) {
804 		if (n->array[byte].len != 0) {
806 			if (pos + n->array[byte].len > len) {
810 				n->array[byte].len) != 0) {
813 			pos += n->array[byte].len;
848 		node->len = 1;
857 	if (node->len == 0) {
859 		node->len = 1;
866 		if (node->len + need > node->capacity) {
869 				(unsigned) (node->len + need))) {
875 			node->len*sizeof(ldns_radix_array_t));
877 		for (index = 0; index < node->len; index++) {
885 		node->len += need;
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) {
894 				(unsigned) (node->len + need))) {
899 		memset(&node->array[node->len], 0,
901 		node->len += need;
930 	assert(node->len <= node->capacity);
932 	memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
945  * @param len:   length of key.
951 	radix_strlen_t pos, radix_strlen_t len)
953 	array->str = LDNS_XMALLOC(uint8_t, (len-pos));
957 	memmove(array->str, key+pos, len-pos);
958 	array->len = (len-pos);
993  * @param len:   length of the key.
1000 	radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add)
1003 	radix_strlen_t strlen_to_add = len - pos;
1006 		array->str, array->len)) {
1018 		assert(strlen_to_add < array->len);
1020 		if (array->len - strlen_to_add > 1) {
1022 				array->str, array->len, &split_str,
1051 		add->array[0].len = split_len;
1057 		array->len = strlen_to_add;
1058 	} else if (ldns_radix_str_is_prefix(array->str, array->len,
1072 		assert(array->len < strlen_to_add);
1073 		if (strlen_to_add - array->len > 1) {
1074 			if (!ldns_radix_prefix_remainder(array->len+1,
1082 			str_to_add[array->len])) {
1090 		add->parent_index = str_to_add[array->len] -
1094 		array->edge->array[add->parent_index].len = split_len;
1111 		common_len = ldns_radix_str_common(array->str, array->len,
1113 		assert(common_len < array->len);
1120 		if (array->len - common_len > 1) {
1122 				array->str, array->len, &s1, &l1)) {
1166 		common->array[array->edge->parent_index].len = l1;
1169 		common->array[add->parent_index].len = l2;
1173 		array->len = common_len;
1237 	for (i = 0; i < node->len; i++) {
1309 	for (i=(int)(node->len)-1; i >= 0; i--) {
1312 			if (node->array[i].edge->len > 0) {
1343 		} else if (node->len == 1 && node->parent) {
1347 		} else if (node->len == 0) {
1387 	assert(parent_index < parent->len);
1388 	join_len = parent->array[parent_index].len + node->array[0].len + 1;
1401 		parent->array[parent_index].len);
1402 	join_str[parent->array[parent_index].len] = child->parent_index +
1404 	memmove(join_str + parent->array[parent_index].len+1,
1405 		node->array[0].str, node->array[0].len);
1409 	parent->array[parent_index].len = join_len;
1429 	assert(parent_index < parent->len);
1433 	parent->array[parent_index].len = 0;
1436 	if (parent->len == 1) {
1461 	for (i=0; i < node->len; i++) {
1481 	node->len = 0;
1499    	while (n < node->len && node->array[n].edge == NULL) {
1505 	if (n == node->len) {
1509 	assert(n < node->len);
1512 		(node->len - n)*sizeof(ldns_radix_array_t));
1514 	node->len -= n;
1515 	for (i=0; i < node->len; i++) {
1535 	while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1541 	if (n == node->len) {
1545 	assert(n < node->len);
1546 	node->len -= n;
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);
1569 		node->capacity = node->len;