Lines Matching full:array
56 static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
61 static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
104 node->array = NULL; in ldns_radix_new_node()
202 /** Find some space in the array for the first byte */ in ldns_radix_insert()
205 LDNS_FREE(prefix->array); in ldns_radix_insert()
212 prefix->array[0].edge = add; in ldns_radix_insert()
216 len, &prefix->array[0].str, in ldns_radix_insert()
217 &prefix->array[0].len)) { in ldns_radix_insert()
219 LDNS_FREE(prefix->array); in ldns_radix_insert()
242 /** Find some space in the array for the byte. */ in ldns_radix_insert()
259 &prefix->array[byte], key, pos+1, in ldns_radix_insert()
268 prefix->array[byte].edge = add; in ldns_radix_insert()
269 } else if (prefix->array[byte-prefix->offset].edge == NULL) { in ldns_radix_insert()
282 &prefix->array[byte], key, pos+1, in ldns_radix_insert()
291 prefix->array[byte].edge = add; in ldns_radix_insert()
297 if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)], in ldns_radix_insert()
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()
408 * last of this array, or something before this node. in ldns_radix_find_less_equal()
417 if (!node->array[byte].edge) { in ldns_radix_find_less_equal()
419 * No exact match. Find the previous in the array 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()
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()
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()
748 ldns_radix_traverse_postorder(node->array[i].edge, in ldns_radix_traverse_postorder()
765 * otherwise an array entry.
804 if (n->array[byte].len != 0) { in ldns_radix_find_prefix()
806 if (pos + n->array[byte].len > len) { in ldns_radix_find_prefix()
809 if (memcmp(&key[pos], n->array[byte].str, in ldns_radix_find_prefix()
810 n->array[byte].len) != 0) { in ldns_radix_find_prefix()
813 pos += n->array[byte].len; in ldns_radix_find_prefix()
816 n = n->array[byte].edge; in ldns_radix_find_prefix()
830 * Make space in the node's array for another byte.
839 /** Is there an array? */ in ldns_radix_array_space()
840 if (!node->array) { in ldns_radix_array_space()
842 /** No array, create new array */ 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()
853 /** Array exist */ in ldns_radix_array_space()
854 assert(node->array != NULL); in ldns_radix_array_space()
858 /** Unused array */ in ldns_radix_array_space()
867 /** Not enough capacity, grow array */ in ldns_radix_array_space()
870 return 0; /* failed to grow array */ in ldns_radix_array_space()
874 memmove(&node->array[need], &node->array[0], 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()
888 /** Byte does not fit in array */ in ldns_radix_array_space()
892 /** Not enough capacity, grow array */ in ldns_radix_array_space()
895 return 0; /* failed to grow array */ in ldns_radix_array_space()
899 memset(&node->array[node->len], 0, in ldns_radix_array_space()
908 * Grow the array.
910 * @param need: number of elements the array at least need to 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()
941 * Create a prefix in the array string.
942 * @param array: array.
950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key, in ldns_radix_str_create() argument
953 array->str = LDNS_XMALLOC(uint8_t, (len-pos)); in ldns_radix_str_create()
954 if (!array->str) { in ldns_radix_str_create()
957 memmove(array->str, key+pos, len-pos); in ldns_radix_str_create()
958 array->len = (len-pos); in ldns_radix_str_create()
990 * @param array: array.
999 ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key, in ldns_radix_array_split() argument
1006 array->str, array->len)) { in ldns_radix_array_split()
1018 assert(strlen_to_add < array->len); in ldns_radix_array_split()
1020 if (array->len - strlen_to_add > 1) { in ldns_radix_array_split()
1022 array->str, array->len, &split_str, in ldns_radix_array_split()
1036 /** Make space in array for the new node */ in ldns_radix_array_split()
1038 array->str[strlen_to_add])) { in ldns_radix_array_split()
1047 add->parent = array->edge->parent; in ldns_radix_array_split()
1048 add->parent_index = array->edge->parent_index; in ldns_radix_array_split()
1049 add->array[0].edge = array->edge; in ldns_radix_array_split()
1050 add->array[0].str = split_str; in ldns_radix_array_split()
1051 add->array[0].len = split_len; in ldns_radix_array_split()
1052 array->edge->parent = add; in ldns_radix_array_split()
1053 array->edge->parent_index = 0; in ldns_radix_array_split()
1054 LDNS_FREE(array->str); in ldns_radix_array_split()
1055 array->edge = add; in ldns_radix_array_split()
1056 array->str = dup_str; in ldns_radix_array_split()
1057 array->len = strlen_to_add; in ldns_radix_array_split()
1058 } else if (ldns_radix_str_is_prefix(array->str, array->len, in ldns_radix_array_split()
1072 assert(array->len < strlen_to_add); in ldns_radix_array_split()
1073 if (strlen_to_add - array->len > 1) { in ldns_radix_array_split()
1074 if (!ldns_radix_prefix_remainder(array->len+1, in ldns_radix_array_split()
1080 /** Make space in array for the new node */ in ldns_radix_array_split()
1081 if (!ldns_radix_array_space(array->edge, in ldns_radix_array_split()
1082 str_to_add[array->len])) { in ldns_radix_array_split()
1089 add->parent = array->edge; in ldns_radix_array_split()
1090 add->parent_index = str_to_add[array->len] - in ldns_radix_array_split()
1091 array->edge->offset; in ldns_radix_array_split()
1092 array->edge->array[add->parent_index].edge = add; in ldns_radix_array_split()
1093 array->edge->array[add->parent_index].str = split_str; in ldns_radix_array_split()
1094 array->edge->array[add->parent_index].len = split_len; in ldns_radix_array_split()
1111 common_len = ldns_radix_str_common(array->str, array->len, in ldns_radix_array_split()
1113 assert(common_len < array->len); in ldns_radix_array_split()
1120 if (array->len - common_len > 1) { in ldns_radix_array_split()
1122 array->str, array->len, &s1, &l1)) { in ldns_radix_array_split()
1146 /** Make space in the common node array. */ in ldns_radix_array_split()
1147 if (!ldns_radix_array_space(common, array->str[common_len]) || in ldns_radix_array_split()
1149 LDNS_FREE(common->array); in ldns_radix_array_split()
1160 common->parent = array->edge->parent; in ldns_radix_array_split()
1161 common->parent_index = array->edge->parent_index; in ldns_radix_array_split()
1162 array->edge->parent = common; in ldns_radix_array_split()
1163 array->edge->parent_index = array->str[common_len] - in ldns_radix_array_split()
1167 common->array[array->edge->parent_index].edge = array->edge; in ldns_radix_array_split()
1168 common->array[array->edge->parent_index].str = s1; in ldns_radix_array_split()
1169 common->array[array->edge->parent_index].len = l1; in ldns_radix_array_split()
1170 common->array[add->parent_index].edge = add; in ldns_radix_array_split()
1171 common->array[add->parent_index].str = s2; in ldns_radix_array_split()
1172 common->array[add->parent_index].len = l2; in ldns_radix_array_split()
1173 LDNS_FREE(array->str); in ldns_radix_array_split()
1174 array->edge = common; in ldns_radix_array_split()
1175 array->str = common_str; in ldns_radix_array_split()
1176 array->len = common_len; in ldns_radix_array_split()
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()
1258 * Find the previous element in the array of this node, from index.
1270 if (node->array[i].edge) { in ldns_radix_prev_from_index()
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()
1386 ldns_radix_node_t* child = node->array[0].edge; in ldns_radix_cleanup_onechild()
1391 join_len = parent->array[parent_index].len + node->array[0].len + 1; in ldns_radix_cleanup_onechild()
1403 memcpy(join_str, parent->array[parent_index].str, in ldns_radix_cleanup_onechild()
1404 parent->array[parent_index].len); in ldns_radix_cleanup_onechild()
1405 join_str[parent->array[parent_index].len] = child->parent_index + in ldns_radix_cleanup_onechild()
1407 memmove(join_str + parent->array[parent_index].len+1, in ldns_radix_cleanup_onechild()
1408 node->array[0].str, node->array[0].len); in ldns_radix_cleanup_onechild()
1410 LDNS_FREE(parent->array[parent_index].str); in ldns_radix_cleanup_onechild()
1411 parent->array[parent_index].str = join_str; in ldns_radix_cleanup_onechild()
1412 parent->array[parent_index].len = join_len; in ldns_radix_cleanup_onechild()
1413 parent->array[parent_index].edge = child; in ldns_radix_cleanup_onechild()
1431 /** Delete lead node and fix parent array. */ in ldns_radix_cleanup_leaf()
1434 LDNS_FREE(parent->array[parent_index].str); in ldns_radix_cleanup_leaf()
1435 parent->array[parent_index].str = NULL; in ldns_radix_cleanup_leaf()
1436 parent->array[parent_index].len = 0; in ldns_radix_cleanup_leaf()
1437 parent->array[parent_index].edge = NULL; in ldns_radix_cleanup_leaf()
1438 /** Fix array in parent. */ in ldns_radix_cleanup_leaf()
1465 LDNS_FREE(node->array[i].str); in ldns_radix_node_free()
1469 LDNS_FREE(node->array); in ldns_radix_node_free()
1476 * Free select edge array.
1485 LDNS_FREE(node->array); in ldns_radix_node_array_free()
1486 node->array = NULL; in ldns_radix_node_array_free()
1493 * Free front of select edge array.
1502 while (n < node->len && node->array[n].edge == NULL) { in ldns_radix_node_array_free_front()
1514 memmove(&node->array[0], &node->array[n], 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()
1529 * Free front of select edge array.
1537 /** Shorten array. */ in ldns_radix_node_array_free_end()
1538 while (n < node->len && node->array[node->len-1-n].edge == NULL) { in ldns_radix_node_array_free_end()
1556 * Reduce the capacity of the array if needed.
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()