radix.c
Go to the documentation of this file.
1 /*
2  * radix.c -- generic radix tree
3  *
4  * Taken from NSD4, modified for ldns
5  *
6  * Copyright (c) 2012, NLnet Labs. All rights reserved.
7  *
8  * This software is open source.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
14  * Redistributions of source code must retain the above copyright notice,
15  * this list of conditions and the following disclaimer.
16  *
17  * Redistributions in binary form must reproduce the above copyright notice,
18  * this list of conditions and the following disclaimer in the documentation
19  * and/or other materials provided with the distribution.
20  *
21  * Neither the name of the NLNET LABS nor the names of its contributors may
22  * be used to endorse or promote products derived from this software without
23  * specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
31  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  *
37  */
38 
44 #include <ldns/config.h>
45 #include <ldns/radix.h>
46 #include <ldns/util.h>
47 #include <stdlib.h>
48 
50 static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
51  radix_strlen_t len);
52 static int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
53  radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
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);
56 static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
57  radix_strlen_t pos, radix_strlen_t len);
58 static int ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
59  uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str,
60  radix_strlen_t* split_len);
61 static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
62  radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
63 static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
64  uint8_t* str2, radix_strlen_t len2);
65 static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
66  uint8_t* str2, radix_strlen_t len2);
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,
69  uint8_t index);
70 static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
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,
82  ldns_radix_node_t** result);
83 
84 
89 static ldns_radix_node_t*
90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
91 {
92  ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
93  if (!node) {
94  return NULL;
95  }
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;
106 }
107 
108 
113 ldns_radix_t *
114 ldns_radix_create(void)
115 {
116  ldns_radix_t* tree;
117 
119  tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
120  if (!tree) {
121  return NULL;
122  }
124  ldns_radix_init(tree);
125  return tree;
126 }
127 
128 
133 void
134 ldns_radix_init(ldns_radix_t* tree)
135 {
137  if (tree) {
138  tree->root = NULL;
139  tree->count = 0;
140  }
141  return;
142 }
143 
144 
149 void
150 ldns_radix_free(ldns_radix_t* tree)
151 {
152  if (tree) {
153  if (tree->root) {
154  ldns_radix_traverse_postorder(tree->root,
155  ldns_radix_node_free, NULL);
156  }
157  LDNS_FREE(tree);
158  }
159  return;
160 }
161 
162 
167 ldns_status
168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
169  void* data)
170 {
171  radix_strlen_t pos = 0;
172  ldns_radix_node_t* add = NULL;
173  ldns_radix_node_t* prefix = NULL;
174 
175  if (!tree || !key || !data) {
176  return LDNS_STATUS_NULL;
177  }
178  add = ldns_radix_new_node(data, key, len);
179  if (!add) {
180  return LDNS_STATUS_MEM_ERR;
181  }
183  if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
185  assert(tree->root == NULL);
186  if (len == 0) {
191  tree->root = add;
192  } else {
197  prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
198  if (!prefix) {
199  LDNS_FREE(add);
200  return LDNS_STATUS_MEM_ERR;
201  }
203  if (!ldns_radix_array_space(prefix, key[0])) {
204  LDNS_FREE(add);
205  LDNS_FREE(prefix->array);
206  LDNS_FREE(prefix);
207  return LDNS_STATUS_MEM_ERR;
208  }
210  add->parent = prefix;
211  add->parent_index = 0;
212  prefix->array[0].edge = add;
213  if (len > 1) {
215  if (!ldns_radix_prefix_remainder(1, key,
216  len, &prefix->array[0].str,
217  &prefix->array[0].len)) {
218  LDNS_FREE(add);
219  LDNS_FREE(prefix->array);
220  LDNS_FREE(prefix);
221  return LDNS_STATUS_MEM_ERR;
222  }
223  }
224  tree->root = prefix;
225  }
226  } else if (pos == len) {
228  LDNS_FREE(add);
229  if (prefix->data) {
230  /* Element already exists */
231  return LDNS_STATUS_EXISTS_ERR;
232  }
233  prefix->data = data;
234  prefix->key = key;
235  prefix->klen = len; /* redundant */
236  } else {
238  uint8_t byte = key[pos];
239  assert(pos < len);
240  if (byte < prefix->offset ||
241  (byte - prefix->offset) >= prefix->len) {
249  if (!ldns_radix_array_space(prefix, byte)) {
250  LDNS_FREE(add);
251  return LDNS_STATUS_MEM_ERR;
252  }
253  assert(byte >= prefix->offset);
254  assert((byte - prefix->offset) <= prefix->len);
255  byte -= prefix->offset;
256  if (pos+1 < len) {
258  if (!ldns_radix_str_create(
259  &prefix->array[byte], key, pos+1,
260  len)) {
261  LDNS_FREE(add);
262  return LDNS_STATUS_MEM_ERR;
263  }
264  }
266  add->parent = prefix;
267  add->parent_index = byte;
268  prefix->array[byte].edge = add;
269  } else if (prefix->array[byte-prefix->offset].edge == NULL) {
278  byte -= prefix->offset;
279  if (pos+1 < len) {
281  if (!ldns_radix_str_create(
282  &prefix->array[byte], key, pos+1,
283  len)) {
284  LDNS_FREE(add);
285  return LDNS_STATUS_MEM_ERR;
286  }
287  }
289  add->parent = prefix;
290  add->parent_index = byte;
291  prefix->array[byte].edge = add;
292  } else {
297  if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
298  key, pos+1, len, add)) {
299  LDNS_FREE(add);
300  return LDNS_STATUS_MEM_ERR;
301  }
302  }
303  }
304 
305  tree->count ++;
306  return LDNS_STATUS_OK;
307 }
308 
309 
314 void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
315 {
316  ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
317  void* data = NULL;
318  if (del) {
319  tree->count--;
320  data = del->data;
321  del->data = NULL;
322  ldns_radix_del_fix(tree, del);
323  return data;
324  }
325  return NULL;
326 }
327 
328 
333 ldns_radix_node_t*
334 ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
335 {
336  ldns_radix_node_t* node = NULL;
337  radix_strlen_t pos = 0;
338  uint8_t byte = 0;
339 
340  if (!tree || !key) {
341  return NULL;
342  }
343  node = tree->root;
344  while (node) {
345  if (pos == len) {
346  return node->data?node:NULL;
347  }
348  byte = key[pos];
349  if (byte < node->offset) {
350  return NULL;
351  }
352  byte -= node->offset;
353  if (byte >= node->len) {
354  return NULL;
355  }
356  pos++;
357  if (node->array[byte].len > 0) {
359  if (pos + node->array[byte].len > len) {
360  return NULL;
361  }
362  if (memcmp(&key[pos], node->array[byte].str,
363  node->array[byte].len) != 0) {
364  return NULL;
365  }
366  pos += node->array[byte].len;
367  }
368  node = node->array[byte].edge;
369  }
370  return NULL;
371 }
372 
373 
379 int
380 ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key,
381  radix_strlen_t len, ldns_radix_node_t** result)
382 {
383  ldns_radix_node_t* node = NULL;
384  radix_strlen_t pos = 0;
385  uint8_t byte;
386  int memcmp_res = 0;
387 
388  if (!tree || !tree->root || !key) {
389  *result = NULL;
390  return 0;
391  }
392 
393  node = tree->root;
394  while (pos < len) {
395  byte = key[pos];
396  if (byte < node->offset) {
401  ldns_radix_self_or_prev(node, result);
402  return 0;
403  }
404  byte -= node->offset;
405  if (byte >= node->len) {
410  *result = ldns_radix_last_in_subtree_incl_self(node);
411  if (*result == NULL) {
412  *result = ldns_radix_prev(node);
413  }
414  return 0;
415  }
416  pos++;
417  if (!node->array[byte].edge) {
422  *result = ldns_radix_prev_from_index(node, byte);
423  if (*result == NULL) {
424  ldns_radix_self_or_prev(node, result);
425  }
426  return 0;
427  }
428  if (node->array[byte].len != 0) {
430  if (pos + node->array[byte].len > len) {
432  if (memcmp(&key[pos], node->array[byte].str,
433  len-pos) <= 0) {
435  *result = ldns_radix_prev(
436  node->array[byte].edge);
437  } else {
439  *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
440  if (*result == NULL) {
441  *result = ldns_radix_prev(node->array[byte].edge);
442  }
443  }
444  return 0;
445  }
446  memcmp_res = memcmp(&key[pos], node->array[byte].str,
447  node->array[byte].len);
448  if (memcmp_res < 0) {
449  *result = ldns_radix_prev(
450  node->array[byte].edge);
451  return 0;
452  } else if (memcmp_res > 0) {
453  *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
454  if (*result == NULL) {
455  *result = ldns_radix_prev(node->array[byte].edge);
456  }
457  return 0;
458  }
459 
460  pos += node->array[byte].len;
461  }
462  node = node->array[byte].edge;
463  }
464  if (node->data) {
466  *result = node;
467  return 1;
468  }
470  *result = ldns_radix_prev(node);
471  return 0;
472 }
473 
474 
479 ldns_radix_node_t*
480 ldns_radix_first(const ldns_radix_t* tree)
481 {
482  ldns_radix_node_t* first = NULL;
483  if (!tree || !tree->root) {
484  return NULL;
485  }
486  first = tree->root;
487  if (first->data) {
488  return first;
489  }
490  return ldns_radix_next(first);
491 }
492 
493 
498 ldns_radix_node_t*
499 ldns_radix_last(const ldns_radix_t* tree)
500 {
501  if (!tree || !tree->root) {
502  return NULL;
503  }
504  return ldns_radix_last_in_subtree_incl_self(tree->root);
505 }
506 
507 
512 ldns_radix_node_t*
513 ldns_radix_next(ldns_radix_node_t* node)
514 {
515  if (!node) {
516  return NULL;
517  }
518  if (node->len) {
520  ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
521  if (next) {
522  return next;
523  }
524  }
526  while (node->parent) {
527  uint8_t index = node->parent_index;
528  node = node->parent;
529  index++;
530  for (; index < node->len; index++) {
531  if (node->array[index].edge) {
532  ldns_radix_node_t* next;
534  if (node->array[index].edge->data) {
535  return node->array[index].edge;
536  }
538  next = ldns_radix_next_in_subtree(node);
539  if (next) {
540  return next;
541  }
542  }
543  }
544  }
545  return NULL;
546 }
547 
548 
553 ldns_radix_node_t*
554 ldns_radix_prev(ldns_radix_node_t* node)
555 {
556  if (!node) {
557  return NULL;
558  }
559 
561  while (node->parent) {
562  uint8_t index = node->parent_index;
563  ldns_radix_node_t* prev;
564  node = node->parent;
565  assert(node->len > 0);
566  prev = ldns_radix_prev_from_index(node, index);
567  if (prev) {
568  return prev;
569  }
570  if (node->data) {
571  return node;
572  }
573  }
574  return NULL;
575 }
576 
577 
582 static void
583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,
584  uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d)
585 {
586  uint8_t j;
587  if (!node) {
588  return;
589  }
590  for (j = 0; j < d; j++) {
591  fprintf(fd, "--");
592  }
593  if (str) {
594  radix_strlen_t l;
595  fprintf(fd, "| [%u+", (unsigned) i);
596  for (l=0; l < len; l++) {
597  fprintf(fd, "%c", (char) str[l]);
598  }
599  fprintf(fd, "]%u", (unsigned) len);
600  } else {
601  fprintf(fd, "| [%u]", (unsigned) i);
602  }
603 
604  if (node->data) {
605  fprintf(fd, " %s", (char*) node->data);
606  }
607  fprintf(fd, "\n");
608 
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);
613  }
614  }
615  return;
616 }
617 
618 
623 void
624 ldns_radix_printf(FILE* fd, const ldns_radix_t* tree)
625 {
626  if (!fd || !tree) {
627  return;
628  }
629  if (!tree->root) {
630  fprintf(fd, "; empty radix tree\n");
631  return;
632  }
633  ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
634  return;
635 }
636 
637 
642 ldns_status
643 ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
644 {
645  ldns_radix_node_t* cur_node, *next_node;
646  ldns_status status;
647  if (!tree2 || !tree2->root) {
648  return LDNS_STATUS_OK;
649  }
652  cur_node = ldns_radix_first(tree2);
653  while (cur_node) {
654  status = LDNS_STATUS_NO_DATA;
656  if (cur_node->data) {
657  status = ldns_radix_insert(tree1, cur_node->key,
658  cur_node->klen, cur_node->data);
660  if (status != LDNS_STATUS_OK &&
661  status != LDNS_STATUS_EXISTS_ERR) {
662  return status;
663  }
664  }
665  next_node = ldns_radix_next(cur_node);
666  if (status == LDNS_STATUS_OK) {
667  (void) ldns_radix_delete(tree2, cur_node->key,
668  cur_node->klen);
669  }
670  cur_node = next_node;
671  }
672 
673  return LDNS_STATUS_OK;
674 }
675 
676 
681 ldns_status
682 ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
683 {
684  size_t count = 0;
685  ldns_radix_node_t* cur_node;
686  ldns_status status = LDNS_STATUS_OK;
687  if (!tree1 || !tree1->root || num == 0) {
688  return LDNS_STATUS_OK;
689  }
690  if (!tree2) {
691  return LDNS_STATUS_NULL;
692  }
693  if (!*tree2) {
694  *tree2 = ldns_radix_create();
695  if (!*tree2) {
696  return LDNS_STATUS_MEM_ERR;
697  }
698  }
699  cur_node = ldns_radix_first(tree1);
700  while (count < num && cur_node) {
701  if (cur_node->data) {
703  uint8_t* cur_key = cur_node->key;
704  radix_strlen_t cur_len = cur_node->klen;
705  void* cur_data = ldns_radix_delete(tree1, cur_key,
706  cur_len);
708  if (!cur_data) {
709  return LDNS_STATUS_NO_DATA;
710  }
711  status = ldns_radix_insert(*tree2, cur_key, cur_len,
712  cur_data);
713  if (status != LDNS_STATUS_OK &&
714  status != LDNS_STATUS_EXISTS_ERR) {
715  return status;
716  }
717 /*
718  if (status == LDNS_STATUS_OK) {
719  cur_node->key = NULL;
720  cur_node->klen = 0;
721  }
722 */
724  count++;
725  cur_node = ldns_radix_first(tree1);
726  } else {
727  cur_node = ldns_radix_next(cur_node);
728  }
729  }
730  return LDNS_STATUS_OK;
731 }
732 
733 
739 void
740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,
741  void (*func)(ldns_radix_node_t*, void*), void* arg)
742 {
743  uint8_t i;
744  if (!node) {
745  return;
746  }
747  for (i=0; i < node->len; i++) {
748  ldns_radix_traverse_postorder(node->array[i].edge,
749  func, arg);
750  }
752  (*func)(node, arg);
753  return;
754 }
755 
756 
772 static int
773 ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
774  radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos)
775 {
777  ldns_radix_node_t* n = tree->root;
778  radix_strlen_t pos = 0;
779  uint8_t byte;
780  *respos = 0;
781  *result = n;
782  if (!n) {
784  return 0;
785  }
787  while (n) {
788  if (pos == len) {
790  return 1;
791  }
792  byte = key[pos];
793  if (byte < n->offset) {
795  return 1;
796  }
797  byte -= n->offset;
798  if (byte >= n->len) {
800  return 1;
801  }
803  pos++;
804  if (n->array[byte].len != 0) {
806  if (pos + n->array[byte].len > len) {
807  return 1; /* no match at child node */
808  }
809  if (memcmp(&key[pos], n->array[byte].str,
810  n->array[byte].len) != 0) {
811  return 1; /* no match at child node */
812  }
813  pos += n->array[byte].len;
814  }
816  n = n->array[byte].edge;
817  if (!n) {
818  return 1;
819  }
821  *respos = pos;
822  *result = n;
823  }
825  return 1;
826 }
827 
828 
836 static int
837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
838 {
840  if (!node->array) {
841  assert(node->capacity == 0);
843  node->array = LDNS_MALLOC(ldns_radix_array_t);
844  if (!node->array) {
845  return 0;
846  }
847  memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
848  node->len = 1;
849  node->capacity = 1;
850  node->offset = byte;
851  return 1;
852  }
854  assert(node->array != NULL);
855  assert(node->capacity > 0);
856 
857  if (node->len == 0) {
859  node->len = 1;
860  node->offset = byte;
861  } else if (byte < node->offset) {
863  uint8_t index;
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))) {
870  return 0; /* failed to grow array */
871  }
872  }
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 =
880  index + need;
881  }
882  }
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))) {
895  return 0; /* failed to grow array */
896  }
897  }
899  memset(&node->array[node->len], 0,
900  need*sizeof(ldns_radix_array_t));
901  node->len += need;
902  }
903  return 1;
904 }
905 
906 
915 static int
916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
917 {
918  unsigned size = ((unsigned)node->capacity)*2;
919  ldns_radix_array_t* a = NULL;
920  if (need > size) {
921  size = need;
922  }
923  if (size > 256) {
924  size = 256;
925  }
926  a = LDNS_XMALLOC(ldns_radix_array_t, size);
927  if (!a) {
928  return 0;
929  }
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;
936  return 1;
937 }
938 
939 
949 static int
950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
951  radix_strlen_t pos, radix_strlen_t len)
952 {
953  array->str = LDNS_XMALLOC(uint8_t, (len-pos));
954  if (!array->str) {
955  return 0;
956  }
957  memmove(array->str, key+pos, len-pos);
958  array->len = (len-pos);
959  return 1;
960 }
961 
962 
973 static int
974 ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
975  uint8_t* longer_str, radix_strlen_t longer_len,
976  uint8_t** split_str, radix_strlen_t* split_len)
977 {
978  *split_len = longer_len - prefix_len;
979  *split_str = LDNS_XMALLOC(uint8_t, (*split_len));
980  if (!*split_str) {
981  return 0;
982  }
983  memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
984  return 1;
985 }
986 
987 
998 static int
999 ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
1000  radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add)
1001 {
1002  uint8_t* str_to_add = key + pos;
1003  radix_strlen_t strlen_to_add = len - pos;
1004 
1005  if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add,
1006  array->str, array->len)) {
1008  uint8_t* split_str = NULL, *dup_str = NULL;
1009  radix_strlen_t split_len = 0;
1018  assert(strlen_to_add < array->len);
1020  if (array->len - strlen_to_add > 1) {
1021  if (!ldns_radix_prefix_remainder(strlen_to_add+1,
1022  array->str, array->len, &split_str,
1023  &split_len)) {
1024  return 0;
1025  }
1026  }
1028  if (strlen_to_add != 0) {
1029  dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
1030  if (!dup_str) {
1031  LDNS_FREE(split_str);
1032  return 0;
1033  }
1034  memcpy(dup_str, str_to_add, strlen_to_add);
1035  }
1037  if (!ldns_radix_array_space(add,
1038  array->str[strlen_to_add])) {
1039  LDNS_FREE(split_str);
1040  LDNS_FREE(dup_str);
1041  return 0;
1042  }
1047  add->parent = array->edge->parent;
1048  add->parent_index = array->edge->parent_index;
1049  add->array[0].edge = array->edge;
1050  add->array[0].str = split_str;
1051  add->array[0].len = split_len;
1052  array->edge->parent = add;
1053  array->edge->parent_index = 0;
1054  LDNS_FREE(array->str);
1055  array->edge = add;
1056  array->str = dup_str;
1057  array->len = strlen_to_add;
1058  } else if (ldns_radix_str_is_prefix(array->str, array->len,
1059  str_to_add, strlen_to_add)) {
1070  uint8_t* split_str = NULL;
1071  radix_strlen_t split_len = 0;
1072  assert(array->len < strlen_to_add);
1073  if (strlen_to_add - array->len > 1) {
1074  if (!ldns_radix_prefix_remainder(array->len+1,
1075  str_to_add, strlen_to_add, &split_str,
1076  &split_len)) {
1077  return 0;
1078  }
1079  }
1081  if (!ldns_radix_array_space(array->edge,
1082  str_to_add[array->len])) {
1083  LDNS_FREE(split_str);
1084  return 0;
1085  }
1089  add->parent = array->edge;
1090  add->parent_index = str_to_add[array->len] -
1091  array->edge->offset;
1092  array->edge->array[add->parent_index].edge = add;
1093  array->edge->array[add->parent_index].str = split_str;
1094  array->edge->array[add->parent_index].len = split_len;
1095  } else {
1108  ldns_radix_node_t* common = NULL;
1109  uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL;
1110  radix_strlen_t common_len = 0, l1 = 0, l2 = 0;
1111  common_len = ldns_radix_str_common(array->str, array->len,
1112  str_to_add, strlen_to_add);
1113  assert(common_len < array->len);
1114  assert(common_len < strlen_to_add);
1116  common = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
1117  if (!common) {
1118  return 0;
1119  }
1120  if (array->len - common_len > 1) {
1121  if (!ldns_radix_prefix_remainder(common_len+1,
1122  array->str, array->len, &s1, &l1)) {
1123  LDNS_FREE(common);
1124  return 0;
1125  }
1126  }
1127  if (strlen_to_add - common_len > 1) {
1128  if (!ldns_radix_prefix_remainder(common_len+1,
1129  str_to_add, strlen_to_add, &s2, &l2)) {
1130  LDNS_FREE(common);
1131  LDNS_FREE(s1);
1132  return 0;
1133  }
1134  }
1136  if (common_len > 0) {
1137  common_str = LDNS_XMALLOC(uint8_t, common_len);
1138  if (!common_str) {
1139  LDNS_FREE(common);
1140  LDNS_FREE(s1);
1141  LDNS_FREE(s2);
1142  return 0;
1143  }
1144  memcpy(common_str, str_to_add, common_len);
1145  }
1147  if (!ldns_radix_array_space(common, array->str[common_len]) ||
1148  !ldns_radix_array_space(common, str_to_add[common_len])) {
1149  LDNS_FREE(common->array);
1150  LDNS_FREE(common);
1151  LDNS_FREE(common_str);
1152  LDNS_FREE(s1);
1153  LDNS_FREE(s2);
1154  return 0;
1155  }
1160  common->parent = array->edge->parent;
1161  common->parent_index = array->edge->parent_index;
1162  array->edge->parent = common;
1163  array->edge->parent_index = array->str[common_len] -
1164  common->offset;
1165  add->parent = common;
1166  add->parent_index = str_to_add[common_len] - common->offset;
1167  common->array[array->edge->parent_index].edge = array->edge;
1168  common->array[array->edge->parent_index].str = s1;
1169  common->array[array->edge->parent_index].len = l1;
1170  common->array[add->parent_index].edge = add;
1171  common->array[add->parent_index].str = s2;
1172  common->array[add->parent_index].len = l2;
1173  LDNS_FREE(array->str);
1174  array->edge = common;
1175  array->str = common_str;
1176  array->len = common_len;
1177  }
1178  return 1;
1179 }
1180 
1181 
1191 static int
1192 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
1193  uint8_t* str2, radix_strlen_t len2)
1194 {
1195  if (len1 == 0) {
1196  return 1; /* empty prefix is also a prefix */
1197  }
1198  if (len1 > len2) {
1199  return 0; /* len1 is longer so str1 cannot be a prefix */
1200  }
1201  return (memcmp(str1, str2, len1) == 0);
1202 }
1203 
1204 
1214 static radix_strlen_t
1215 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
1216  uint8_t* str2, radix_strlen_t len2)
1217 {
1218  radix_strlen_t i, max = (len1<len2)?len1:len2;
1219  for (i=0; i<max; i++) {
1220  if (str1[i] != str2[i]) {
1221  return i;
1222  }
1223  }
1224  return max;
1225 }
1226 
1227 
1234 static ldns_radix_node_t*
1235 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1236 {
1237  uint16_t i;
1238  ldns_radix_node_t* next;
1240  for (i = 0; i < node->len; i++) {
1241  if (node->array[i].edge) {
1243  if (node->array[i].edge->data) {
1244  return node->array[i].edge;
1245  }
1247  next = ldns_radix_next_in_subtree(node->array[i].edge);
1248  if (next) {
1249  return next;
1250  }
1251  }
1252  }
1253  return NULL;
1254 }
1255 
1256 
1264 static ldns_radix_node_t*
1265 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1266 {
1267  uint8_t i = index;
1268  while (i > 0) {
1269  i--;
1270  if (node->array[i].edge) {
1271  ldns_radix_node_t* prev =
1272  ldns_radix_last_in_subtree_incl_self(node);
1273  if (prev) {
1274  return prev;
1275  }
1276  }
1277  }
1278  return NULL;
1279 }
1280 
1281 
1288 static ldns_radix_node_t*
1289 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1290 {
1291  ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1292  if (last) {
1293  return last;
1294  } else if (node->data) {
1295  return node;
1296  }
1297  return NULL;
1298 }
1299 
1300 
1307 static ldns_radix_node_t*
1308 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
1309 {
1310  int i;
1312  for (i=(int)(node->len)-1; i >= 0; i--) {
1313  if (node->array[i].edge) {
1315  if (node->array[i].edge->len > 0) {
1316  ldns_radix_node_t* last =
1317  ldns_radix_last_in_subtree(
1318  node->array[i].edge);
1319  if (last) {
1320  return last;
1321  }
1322  }
1324  if (node->array[i].edge->data) {
1325  return node->array[i].edge;
1326  }
1327  }
1328  }
1329  return NULL;
1330 }
1331 
1332 
1339 static void
1340 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1341 {
1342  while (node) {
1343  if (node->data) {
1345  return;
1346  } else if (node->len == 1 && node->parent) {
1348  ldns_radix_cleanup_onechild(node);
1349  return;
1350  } else if (node->len == 0) {
1352  ldns_radix_node_t* parent = node->parent;
1353  if (!parent) {
1355  ldns_radix_node_free(node, NULL);
1356  tree->root = NULL;
1357  return;
1358  }
1360  ldns_radix_cleanup_leaf(node);
1361  node = parent;
1362  } else {
1367  return;
1368  }
1369  }
1371  return;
1372 }
1373 
1374 
1380 static void
1381 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
1382 {
1383  uint8_t* join_str;
1384  radix_strlen_t join_len;
1385  uint8_t parent_index = node->parent_index;
1386  ldns_radix_node_t* child = node->array[0].edge;
1387  ldns_radix_node_t* parent = node->parent;
1388 
1390  assert(parent_index < parent->len);
1391  join_len = parent->array[parent_index].len + node->array[0].len + 1;
1392 
1393  join_str = LDNS_XMALLOC(uint8_t, join_len);
1394  if (!join_str) {
1400  return;
1401  }
1402 
1403  memcpy(join_str, parent->array[parent_index].str,
1404  parent->array[parent_index].len);
1405  join_str[parent->array[parent_index].len] = child->parent_index +
1406  node->offset;
1407  memmove(join_str + parent->array[parent_index].len+1,
1408  node->array[0].str, node->array[0].len);
1409 
1410  LDNS_FREE(parent->array[parent_index].str);
1411  parent->array[parent_index].str = join_str;
1412  parent->array[parent_index].len = join_len;
1413  parent->array[parent_index].edge = child;
1414  child->parent = parent;
1415  child->parent_index = parent_index;
1416  ldns_radix_node_free(node, NULL);
1417  return;
1418 }
1419 
1420 
1426 static void
1427 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
1428 {
1429  uint8_t parent_index = node->parent_index;
1430  ldns_radix_node_t* parent = node->parent;
1432  assert(parent_index < parent->len);
1433  ldns_radix_node_free(node, NULL);
1434  LDNS_FREE(parent->array[parent_index].str);
1435  parent->array[parent_index].str = NULL;
1436  parent->array[parent_index].len = 0;
1437  parent->array[parent_index].edge = NULL;
1439  if (parent->len == 1) {
1440  ldns_radix_node_array_free(parent);
1441  } else if (parent_index == 0) {
1442  ldns_radix_node_array_free_front(parent);
1443  } else {
1444  ldns_radix_node_array_free_end(parent);
1445  }
1446  return;
1447 }
1448 
1449 
1456 static void
1457 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1458 {
1459  uint16_t i;
1460  (void) arg;
1461  if (!node) {
1462  return;
1463  }
1464  for (i=0; i < node->len; i++) {
1465  LDNS_FREE(node->array[i].str);
1466  }
1467  node->key = NULL;
1468  node->klen = 0;
1469  LDNS_FREE(node->array);
1470  LDNS_FREE(node);
1471  return;
1472 }
1473 
1474 
1480 static void
1481 ldns_radix_node_array_free(ldns_radix_node_t* node)
1482 {
1483  node->offset = 0;
1484  node->len = 0;
1485  LDNS_FREE(node->array);
1486  node->array = NULL;
1487  node->capacity = 0;
1488  return;
1489 }
1490 
1491 
1497 static void
1498 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1499 {
1500  uint16_t i, n = 0;
1502  while (n < node->len && node->array[n].edge == NULL) {
1503  n++;
1504  }
1505  if (n == 0) {
1506  return;
1507  }
1508  if (n == node->len) {
1509  ldns_radix_node_array_free(node);
1510  return;
1511  }
1512  assert(n < node->len);
1513  assert((int) n <= (255 - (int) node->offset));
1514  memmove(&node->array[0], &node->array[n],
1515  (node->len - n)*sizeof(ldns_radix_array_t));
1516  node->offset += n;
1517  node->len -= n;
1518  for (i=0; i < node->len; i++) {
1519  if (node->array[i].edge) {
1520  node->array[i].edge->parent_index = i;
1521  }
1522  }
1523  ldns_radix_array_reduce(node);
1524  return;
1525 }
1526 
1527 
1533 static void
1534 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1535 {
1536  uint16_t n = 0;
1538  while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1539  n++;
1540  }
1541  if (n == 0) {
1542  return;
1543  }
1544  if (n == node->len) {
1545  ldns_radix_node_array_free(node);
1546  return;
1547  }
1548  assert(n < node->len);
1549  node->len -= n;
1550  ldns_radix_array_reduce(node);
1551  return;
1552 }
1553 
1554 
1560 static void
1561 ldns_radix_array_reduce(ldns_radix_node_t* node)
1562 {
1563  if (node->len <= node->capacity/2 && node->len != node->capacity) {
1564  ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
1565  node->len);
1566  if (!a) {
1567  return;
1568  }
1569  memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1570  LDNS_FREE(node->array);
1571  node->array = a;
1572  node->capacity = node->len;
1573  }
1574  return;
1575 }
1576 
1577 
1584 static void
1585 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1586 {
1587  if (node->data) {
1588  *result = node;
1589  } else {
1590  *result = ldns_radix_prev(node);
1591  }
1592  return;
1593 }
LDNS_STATUS_EXISTS_ERR
@ LDNS_STATUS_EXISTS_ERR
Definition: error.h:121
LDNS_STATUS_NO_DATA
@ LDNS_STATUS_NO_DATA
Definition: error.h:77
LDNS_STATUS_NULL
@ LDNS_STATUS_NULL
Definition: error.h:51
LDNS_STATUS_MEM_ERR
@ LDNS_STATUS_MEM_ERR
Definition: error.h:34
LDNS_STATUS_OK
@ LDNS_STATUS_OK
Definition: error.h:26
ldns_status
enum ldns_enum_status ldns_status
Definition: error.h:148
ldns_radix_prev
ldns_radix_node_t * ldns_radix_prev(ldns_radix_node_t *node)
Previous element.
Definition: radix.c:554
ldns_radix_init
void ldns_radix_init(ldns_radix_t *tree)
Initialize radix tree.
Definition: radix.c:134
ldns_radix_traverse_postorder
void ldns_radix_traverse_postorder(ldns_radix_node_t *node, void(*func)(ldns_radix_node_t *, void *), void *arg)
Call function for all nodes in the tree, such that leaf nodes are called before parent nodes.
Definition: radix.c:740
ldns_radix_join
ldns_status ldns_radix_join(ldns_radix_t *tree1, ldns_radix_t *tree2)
Join two radix trees.
Definition: radix.c:643
ldns_radix_free
void ldns_radix_free(ldns_radix_t *tree)
Free radix tree.
Definition: radix.c:150
ldns_radix_split
ldns_status ldns_radix_split(ldns_radix_t *tree1, size_t num, ldns_radix_t **tree2)
Split a radix tree intwo.
Definition: radix.c:682
ldns_radix_last
ldns_radix_node_t * ldns_radix_last(const ldns_radix_t *tree)
Get the last element in the tree.
Definition: radix.c:499
ldns_radix_create
ldns_radix_t * ldns_radix_create(void)
Create a new radix tree.
Definition: radix.c:114
ldns_radix_search
ldns_radix_node_t * ldns_radix_search(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Search data in the tree.
Definition: radix.c:334
ldns_radix_next
ldns_radix_node_t * ldns_radix_next(ldns_radix_node_t *node)
Next element.
Definition: radix.c:513
ldns_radix_insert
ldns_status ldns_radix_insert(ldns_radix_t *tree, uint8_t *key, radix_strlen_t len, void *data)
Insert data into the tree.
Definition: radix.c:168
ldns_radix_first
ldns_radix_node_t * ldns_radix_first(const ldns_radix_t *tree)
Get the first element in the tree.
Definition: radix.c:480
ldns_radix_find_less_equal
int ldns_radix_find_less_equal(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len, ldns_radix_node_t **result)
Search data in the tree, and if not found, find the closest smaller element in the tree.
Definition: radix.c:380
ldns_radix_printf
void ldns_radix_printf(FILE *fd, const ldns_radix_t *tree)
Print radix tree.
Definition: radix.c:624
ldns_radix_delete
void * ldns_radix_delete(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Delete data from the tree.
Definition: radix.c:314
radix.h
Radix tree.
radix_strlen_t
uint16_t radix_strlen_t
Definition: radix.h:52
ldns_radix_array_t
Radix node select edge array.
Definition: radix.h:58
ldns_radix_array_t::edge
ldns_radix_node_t * edge
Node that deals with byte+str.
Definition: radix.h:64
ldns_radix_array_t::len
radix_strlen_t len
Length of additional string for this edge.
Definition: radix.h:62
ldns_radix_array_t::str
uint8_t * str
Additional string after the selection byte for this edge.
Definition: radix.h:60
ldns_radix_node_t
A node in a radix tree.
Definition: radix.h:68
ldns_radix_node_t::parent
ldns_radix_node_t * parent
Parent node.
Definition: radix.h:76
ldns_radix_node_t::offset
uint16_t offset
Offset of the array.
Definition: radix.h:82
ldns_radix_node_t::klen
radix_strlen_t klen
Key length corresponding to this node.
Definition: radix.h:72
ldns_radix_node_t::array
ldns_radix_array_t * array
Select edge array.
Definition: radix.h:86
ldns_radix_node_t::len
uint16_t len
Length of the array.
Definition: radix.h:80
ldns_radix_node_t::capacity
uint16_t capacity
Capacity of the array.
Definition: radix.h:84
ldns_radix_node_t::data
void * data
Data corresponding to this node.
Definition: radix.h:74
ldns_radix_node_t::parent_index
uint8_t parent_index
Index in the parent node select edge array.
Definition: radix.h:78
ldns_radix_node_t::key
uint8_t * key
Key corresponding to this node.
Definition: radix.h:70
ldns_radix_t
An entire radix tree.
Definition: radix.h:90
ldns_radix_t::root
ldns_radix_node_t * root
Root.
Definition: radix.h:92
ldns_radix_t::count
size_t count
Number of nodes in tree.
Definition: radix.h:94
LDNS_FREE
#define LDNS_FREE(ptr)
Definition: util.h:60
LDNS_MALLOC
#define LDNS_MALLOC(type)
Memory management macros.
Definition: util.h:49
LDNS_XMALLOC
#define LDNS_XMALLOC(type, count)
Definition: util.h:51