suricata
util-radix-tree.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2022 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Anoop Saldanha <anoopsaldanha@gmail.com>
22  *
23  * Implementation of radix trees
24  */
25 
26 #include "suricata-common.h"
27 #include "util-radix-tree.h"
28 #include "util-debug.h"
29 #include "util-error.h"
30 #include "util-ip.h"
31 #include "util-unittest.h"
32 #include "util-memcmp.h"
33 #include "util-byte.h"
34 #include "util-cidr.h"
35 #include "util-print.h"
36 #include "util-validate.h"
37 
38 /**
39  * \brief Allocates and returns a new instance of SCRadixUserData.
40  *
41  * \param netmask The netmask entry (cidr) that has to be made in the new
42  * SCRadixUserData instance
43  * \param user The user data that has to be set for the above
44  * netmask in the newly created SCRadixUserData instance.
45  *
46  * \retval user_data Pointer to a new instance of SCRadixUserData.
47  */
48 static SCRadixUserData *SCRadixAllocSCRadixUserData(uint8_t netmask, void *user)
49 {
50  SCRadixUserData *user_data = SCCalloc(1, sizeof(SCRadixUserData));
51  if (unlikely(user_data == NULL)) {
52  SCLogError("Error allocating memory");
53  return NULL;
54  }
55 
56  user_data->netmask = netmask;
57  user_data->user = user;
58 
59  return user_data;
60 }
61 
62 /**
63  * \brief Deallocates an instance of SCRadixUserData.
64  *
65  * \param user_data Pointer to the instance of SCRadixUserData that has to be
66  * freed.
67  */
68 static void SCRadixDeAllocSCRadixUserData(SCRadixUserData *user_data)
69 {
70  SCFree(user_data);
71 
72  return;
73 }
74 
75 /**
76  * \brief Appends a user_data instance(SCRadixUserData) to a
77  * user_data(SCRadixUserData) list. We add the new entry in descending
78  * order with respect to the netmask contained in the SCRadixUserData.
79  *
80  * \param new Pointer to the SCRadixUserData to be added to the list.
81  * \param list Pointer to the SCRadixUserData list head, to which "new" has to
82  * be appended.
83  */
84 static void SCRadixAppendToSCRadixUserDataList(SCRadixUserData *new,
85  SCRadixUserData **list)
86 {
87  SCRadixUserData *temp = NULL;
88  SCRadixUserData *prev = NULL;
89 
90  if (new == NULL || list == NULL) {
91  FatalError("new or list supplied as NULL");
92  }
93 
94  /* add to the list in descending order. The reason we do this is for
95  * optimizing key retrieval for a ip key under a netblock */
96  prev = temp = *list;
97  while (temp != NULL) {
98  if (new->netmask > temp->netmask)
99  break;
100  prev = temp;
101  temp = temp->next;
102  }
103 
104  if (temp == *list) {
105  new->next = *list;
106  *list = new;
107  } else {
108  new->next = prev->next;
109  prev->next = new;
110  }
111 
112  return;
113 }
114 
115 /**
116  * \brief Creates a new Prefix for a key. Used internally by the API.
117  *
118  * \param key_stream Data that has to be wrapped in a SCRadixPrefix instance to
119  * be processed for insertion/lookup/removal of a node by the
120  * radix tree
121  * \param key_bitlen The bitlen of the above stream. For example if the
122  * stream holds the ipv4 address(4 bytes), bitlen would be 32
123  * \param user Pointer to the user data that has to be associated with
124  * this key
125  *
126  * \retval prefix The newly created prefix instance on success; NULL on failure
127  */
128 static SCRadixPrefix *SCRadixCreatePrefix(uint8_t *key_stream,
129  uint16_t key_bitlen, void *user,
130  uint8_t netmask)
131 {
132  SCRadixPrefix *prefix = NULL;
133 
134  if (key_bitlen == 0 || (key_bitlen % 8 != 0)) {
135  SCLogError("Invalid argument bitlen - %d", key_bitlen);
136  return NULL;
137  }
138 
139  if (key_stream == NULL) {
140  SCLogError("Argument \"stream\" NULL");
141  return NULL;
142  }
143 
144  if ((prefix = SCCalloc(1, sizeof(SCRadixPrefix))) == NULL)
145  goto error;
146 
147  if ((prefix->stream = SCCalloc(1, key_bitlen / 8)) == NULL)
148  goto error;
149 
150  memcpy(prefix->stream, key_stream, key_bitlen / 8);
151  prefix->bitlen = key_bitlen;
152 
153  prefix->user_data = SCRadixAllocSCRadixUserData(netmask, user);
154  if (prefix->user_data == NULL) {
155  goto error;
156  }
157 
158  return prefix;
159 
160 error:
161  if (prefix != NULL) {
162  if (prefix->stream != NULL) {
163  SCFree(prefix->stream);
164  }
165  SCFree(prefix);
166  }
167 
168  return NULL;
169 }
170 
171 /**
172  * \brief Adds a netmask and its user_data for a particular prefix stream.
173  *
174  * \param prefix The prefix stream to which the netmask and its corresponding
175  * user data has to be added.
176  * \param netmask The netmask value (cidr) that has to be added to the prefix.
177  * \param user The pointer to the user data corresponding to the above
178  * netmask.
179  */
180 static void SCRadixAddNetmaskUserDataToPrefix(SCRadixPrefix *prefix,
181  uint8_t netmask,
182  void *user)
183 {
184  if (prefix == NULL || user == NULL) {
185  FatalError("prefix or user NULL");
186  }
187 
188  SCRadixAppendToSCRadixUserDataList(SCRadixAllocSCRadixUserData(netmask, user),
189  &prefix->user_data);
190 
191  return;
192 }
193 
194 /**
195  * \brief Removes a particular user_data corresponding to a particular netmask
196  * entry, from a prefix.
197  *
198  * \param prefix Pointer to the prefix from which the user_data/netmask entry
199  * has to be removed.
200  * \param netmask The netmask value (cidr) whose user_data has to be deleted.
201  */
202 static void SCRadixRemoveNetmaskUserDataFromPrefix(SCRadixPrefix *prefix,
203  uint8_t netmask)
204 {
205  SCRadixUserData *temp = NULL, *prev = NULL;
206 
207  if (prefix == NULL) {
208  FatalError("prefix NULL");
209  }
210 
211  prev = temp = prefix->user_data;
212  while (temp != NULL) {
213  if (temp->netmask == netmask) {
214  if (temp == prefix->user_data)
215  prefix->user_data = temp->next;
216  else
217  prev->next = temp->next;
218 
219  SCRadixDeAllocSCRadixUserData(temp);
220  break;
221  }
222  prev = temp;
223  temp = temp->next;
224  }
225 
226  return;
227 }
228 
229 /**
230  * \brief Indicates if prefix contains an entry for an ip with a specific netmask.
231  *
232  * \param prefix Pointer to the ip prefix that is being checked.
233  * \param netmask The netmask value (cidr) that has to be checked for
234  * presence in the prefix.
235  *
236  * \retval 1 On match.
237  * \retval 0 On no match.
238  */
239 static int SCRadixPrefixContainNetmask(SCRadixPrefix *prefix, uint8_t netmask)
240 {
241  SCRadixUserData *user_data = NULL;
242 
243  if (prefix == NULL) {
244  SCLogError("prefix is NULL");
245  goto no_match;
246  }
247 
248  user_data = prefix->user_data;
249  while (user_data != NULL) {
250  if (user_data->netmask == netmask)
251  return 1;
252  user_data = user_data->next;
253  }
254 
255  no_match:
256  return 0;
257 }
258 
259 /**
260  * \brief Returns the total netmask count for this prefix.
261  *
262  * \param prefix Pointer to the prefix
263  *
264  * \retval count The total netmask count for this prefix.
265  */
266 static int SCRadixPrefixNetmaskCount(SCRadixPrefix *prefix)
267 {
268  SCRadixUserData *user_data = NULL;
269  uint32_t count = 0;
270 
271  if (prefix == NULL) {
272  SCLogError("prefix is NULL");
273  return 0;
274  }
275 
276  user_data = prefix->user_data;
277  while (user_data != NULL) {
278  count++;
279  user_data = user_data->next;
280  }
281 
282  return count;
283 }
284 
285 /**
286  * \brief Indicates if prefix contains an entry for an ip with a specific netmask
287  * and if it does, it sets the user data field
288  * SCRadixPrefix->user_data_result to the netmask user_data entry.
289  *
290  * \param prefix Pointer to the ip prefix that is being checked.
291  * \param netmask The netmask value for which we will have to return the user_data
292  * \param exact_match flag which indicates if we should check if the prefix
293  * holds proper netblock(< 32 for ipv4 and < 128 for ipv6) or not.
294  *
295  * \retval 1 On match.
296  * \retval 0 On no match.
297  */
298 static int SCRadixPrefixContainNetmaskAndSetUserData(
299  SCRadixPrefix *prefix, uint16_t netmask, bool exact_match, void **user_data_result)
300 {
301  SCRadixUserData *user_data = NULL;
302 
303  if (prefix == NULL) {
304  SCLogError("prefix is NULL");
305  goto no_match;
306  }
307 
308  user_data = prefix->user_data;
309  /* Check if we have a match for an exact ip. An exact ip as in not a proper
310  * netblock, i.e. an ip with a netmask of 32(ipv4) or 128(ipv6) */
311  if (exact_match) {
312  if (user_data->netmask == netmask) {
313  if (user_data_result)
314  *user_data_result = user_data->user;
315  return 1;
316  } else {
317  goto no_match;
318  }
319  }
320 
321  /* Check for the user_data entry for this netmask_value */
322  while (user_data != NULL) {
323  if (user_data->netmask == netmask) {
324  if (user_data_result)
325  *user_data_result = user_data->user;
326  return 1;
327  }
328  user_data = user_data->next;
329  }
330 
331 no_match:
332  if (user_data_result != NULL)
333  *user_data_result = NULL;
334  return 0;
335 }
336 
337 /**
338  * \brief Frees a SCRadixPrefix instance
339  *
340  * \param prefix Pointer to a prefix instance
341  * \param tree Pointer to the Radix tree to which this prefix belongs
342  */
343 static void SCRadixReleasePrefix(SCRadixPrefix *prefix, SCRadixTree *tree)
344 {
345  SCRadixUserData *user_data_temp1 = NULL;
346  SCRadixUserData *user_data_temp2 = NULL;
347 
348  if (prefix != NULL) {
349  if (prefix->stream != NULL)
350  SCFree(prefix->stream);
351 
352  user_data_temp1 = prefix->user_data;
353  if (tree->Free != NULL) {
354  while (user_data_temp1 != NULL) {
355  user_data_temp2 = user_data_temp1;
356  user_data_temp1 = user_data_temp1->next;
357  tree->Free(user_data_temp2->user);
358  SCRadixDeAllocSCRadixUserData(user_data_temp2);
359  }
360  } else if (user_data_temp1 != NULL) {
361  SCFree(user_data_temp1);
362  }
363 
364  SCFree(prefix);
365  }
366 
367  return;
368 }
369 
370 /**
371  * \brief Creates a new node for the Radix tree
372  *
373  * \retval node The newly created node for the radix tree
374  */
375 static inline SCRadixNode *SCRadixCreateNode(void)
376 {
377  SCRadixNode *node = NULL;
378 
379  if ((node = SCCalloc(1, sizeof(SCRadixNode))) == NULL) {
380  SCLogError("Fatal error encountered in SCRadixCreateNode. Mem not allocated...");
381  return NULL;
382  }
383 
384  return node;
385 }
386 
387 /**
388  * \brief Frees a Radix tree node
389  *
390  * \param node Pointer to a Radix tree node
391  * \param tree Pointer to the Radix tree to which this node belongs
392  */
393 static void SCRadixReleaseNode(SCRadixNode *node, SCRadixTree *tree)
394 {
395  if (node != NULL) {
396  SCRadixReleasePrefix(node->prefix, tree);
397 
398  if (node->netmasks != NULL)
399  SCFree(node->netmasks);
400 
401  SCFree(node);
402  }
403 
404  return;
405 }
406 
407 /**
408  * \brief Creates a new Radix tree
409  *
410  * \param Free Function pointer supplied by the user to be used by the Radix
411  * cleanup API to free the user supplied data
412  *
413  * \retval tree The newly created radix tree on success
414  *
415  * \initonly (all radix trees should be created at init)
416  */
417 SCRadixTree *SCRadixCreateRadixTree(void (*Free)(void*), void (*PrintData)(void*))
418 {
419  SCRadixTree *tree = NULL;
420 
421  if ((tree = SCCalloc(1, sizeof(SCRadixTree))) == NULL) {
422  FatalError("Fatal error encountered in SCRadixCreateRadixTree. Exiting...");
423  }
424 
425  tree->Free = Free;
426  tree->PrintData = PrintData;
427 
428  return tree;
429 }
430 
431 /**
432  * \brief Internal helper function used by SCRadixReleaseRadixTree to free a
433  * subtree
434  *
435  * \param node Pointer to the root of the subtree that has to be freed
436  * \param tree Pointer to the Radix tree to which this subtree belongs
437  */
438 static void SCRadixReleaseRadixSubtree(SCRadixNode *node, SCRadixTree *tree)
439 {
440  if (node != NULL) {
441  SCRadixReleaseRadixSubtree(node->left, tree);
442  SCRadixReleaseRadixSubtree(node->right, tree);
443  SCRadixReleaseNode(node, tree);
444  }
445 
446  return;
447 }
448 
449 /**
450  * \brief Frees a Radix tree and all its nodes
451  *
452  * \param tree Pointer to the Radix tree that has to be freed
453  */
455 {
456  if (tree == NULL)
457  return;
458 
459  SCRadixReleaseRadixSubtree(tree->head, tree);
460  tree->head = NULL;
461  SCFree(tree);
462  return;
463 }
464 
465 /**
466  * \brief Adds a key to the Radix tree. Used internally by the API.
467  *
468  * \param key_stream Data that has to added to the Radix tree
469  * \param key_bitlen The bitlen of the above stream. For example if the
470  * stream is the string "abcd", the bitlen would be 32. If
471  * the stream is an IPV6 address bitlen would be 128
472  * \param tree Pointer to the Radix tree
473  * \param user Pointer to the user data that has to be associated with
474  * this key
475  * \param netmask The netmask (cidr) if we are adding an IP netblock; 255
476  * if we are not adding an IP netblock
477  * \param exclusive True if the node should be added iff it doesn't exist.
478  *
479  * \retval node Pointer to the newly created node
480  */
481 static SCRadixNode *SCRadixAddKeyInternal(uint8_t *key_stream, uint8_t key_bitlen,
482  SCRadixTree *tree, void *user, uint8_t netmask, bool exclusive)
483 {
484  SCRadixNode *node = NULL;
485  SCRadixNode *new_node = NULL;
486  SCRadixNode *parent = NULL;
487  SCRadixNode *inter_node = NULL;
488  SCRadixNode *bottom_node = NULL;
489  void *ptmp;
490 
491  uint8_t *stream = NULL;
492  uint8_t bitlen = 0;
493 
494  uint16_t check_bit = 0;
495  uint16_t differ_bit = 0;
496 
497  uint16_t i = 0;
498  uint16_t j = 0;
499 
500  if (tree == NULL) {
501  SCLogError("Argument \"tree\" NULL");
503  return NULL;
504  }
505 
506  /* chop the ip address against a netmask */
507  MaskIPNetblock(key_stream, netmask, key_bitlen);
508 
509  /* the very first element in the radix tree */
510  if (tree->head == NULL) {
511  SCRadixPrefix *prefix = NULL;
512  if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, user,
513  netmask)) == NULL) {
514  SCLogError("Error creating prefix");
516  return NULL;
517  }
518  node = SCRadixCreateNode();
519  if (node == NULL) {
520  SCRadixReleasePrefix(prefix, tree);
522  return NULL;
523  }
524  node->prefix = prefix;
525  node->bit = prefix->bitlen;
526  tree->head = node;
527  if (netmask == 255 || (netmask == 32 && key_bitlen == 32) ||
528  (netmask == 128 && key_bitlen == 128)) {
530  return node;
531  }
532 
533  /* if we have reached here, we are actually having a proper netblock in
534  * our hand(i.e. < 32 for ipv4 and < 128 for ipv6). Add the netmask for
535  * this node. The reason we add netmasks other than 32 and 128, is
536  * because we need those netmasks in case of searches for ips contained
537  * in netblocks. If the netmask is 32 or 128, either ways we will be
538  * having an exact match for that ip value. If it is not, we start
539  * chopping the incoming search ip key using the netmask values added
540  * into the tree and then verify for a match */
541  node->netmask_cnt++;
542  if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt *
543  sizeof(uint8_t)))) == NULL) {
544  SCFree(node->netmasks);
545  node->netmasks = NULL;
546  SCLogError("Fatal error encountered in SCRadixAddKey. Mem not allocated");
548  return NULL;
549  }
550  node->netmasks = ptmp;
551  node->netmasks[0] = netmask;
552  return node;
553  }
554 
555  node = tree->head;
556  stream = key_stream;
557  bitlen = key_bitlen;
558 
559  /* we walk down the tree only when we satisfy 2 conditions. The first one
560  * being the incoming prefix is shorter than the differ bit of the current
561  * node. In case we fail in this aspect, we walk down to the tree, till we
562  * arrive at a node that ends in a prefix */
563  while (node->bit < bitlen || node->prefix == NULL) {
564  /* if the bitlen isn't long enough to handle the bit test, we just walk
565  * down along one of the paths, since either paths should end up with a
566  * node that has a common prefix whose differ bit is greater than the
567  * bitlen of the incoming prefix */
568  if (bitlen <= node->bit) {
569  if (node->right == NULL)
570  break;
571  node = node->right;
572  } else {
573  if (SC_RADIX_BITTEST(stream[node->bit >> 3],
574  (0x80 >> (node->bit % 8))) ) {
575  if (node->right == NULL)
576  break;
577  node = node->right;
578  } else {
579  if (node->left == NULL)
580  break;
581  node = node->left;
582  }
583  }
584  }
585 
586  /* we need to keep a reference to the bottom-most node, that actually holds
587  * the prefix */
588  bottom_node = node;
589 
590  DEBUG_VALIDATE_BUG_ON(bottom_node == NULL);
591  DEBUG_VALIDATE_BUG_ON(bottom_node->prefix == NULL);
592 
593  /* get the first bit position where the ips differ */
594  check_bit = (node->bit < bitlen)? node->bit: bitlen;
595  for (i = 0; (i * 8) < check_bit; i++) {
596  int temp;
597  if ((temp = (stream[i] ^ bottom_node->prefix->stream[i])) == 0) {
598  differ_bit = (i + 1) * 8;
599  continue;
600  }
601 
602  /* find out the position where the first bit differs. This method is
603  * faster, but at the cost of being larger. But with larger caches
604  * these days we don't have to worry about cache misses */
605  temp = temp * 2;
606  if (temp >= 256)
607  j = 0;
608  else if (temp >= 128)
609  j = 1;
610  else if (temp >= 64)
611  j = 2;
612  else if (temp >= 32)
613  j = 3;
614  else if (temp >= 16)
615  j = 4;
616  else if (temp >= 8)
617  j = 5;
618  else if (temp >= 4)
619  j = 6;
620  else if (temp >= 2)
621  j = 7;
622 
623  differ_bit = i * 8 + j;
624  break;
625  }
626  if (check_bit < differ_bit)
627  differ_bit = check_bit;
628 
629  /* walk up the tree till we find the position, to fit our new node in */
630  parent = node->parent;
631  while (parent && differ_bit <= parent->bit) {
632  node = parent;
633  parent = node->parent;
634  }
635 
636  /* We already have the node in the tree with the same differing bit pstn */
637  if (differ_bit == bitlen && node->bit == bitlen) {
638  if (node->prefix != NULL) {
639  /* Check if we already have this netmask entry covered by this prefix */
640  if (SCRadixPrefixContainNetmask(node->prefix, netmask)) {
641  /* Basically we already have this stream prefix, as well as the
642  * netblock entry for this. A perfect duplicate. */
643  if (exclusive) {
644  SCLogDebug("not inserting since it already exists");
646  return NULL;
647  }
648  SCLogDebug("Duplicate entry for this ip address/netblock");
649  } else {
650  /* Basically we already have this stream prefix, but we don't
651  * have an entry for this particular netmask value for this
652  * prefix. For example, we have an entry for 192.168.0.0 and
653  * 192.168.0.0/16 and now we are trying to enter 192.168.0.0/20 */
654  SCRadixAddNetmaskUserDataToPrefix(node->prefix, netmask, user);
655 
656  /* if we are adding a netmask of 32(for ipv4) or 128(for ipv6)
657  * it indicates we are adding an exact host ip into the radix
658  * tree, in which case we don't need to add the netmask value
659  * into the tree */
660  if (netmask == 255 || (netmask == 32 && bitlen == 32) || (netmask == 128 && bitlen == 128))
661  return node;
662 
663  /* looks like we have a netmask which is != 32 or 128, in which
664  * case we walk up the tree to insert this netmask value in the
665  * correct node */
666  parent = node->parent;
667  while (parent != NULL && netmask < (parent->bit + 1)) {
668  node = parent;
669  parent = parent->parent;
670  }
671 
672  node->netmask_cnt++;
673  new_node = node;
674 
675  if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt *
676  sizeof(uint8_t)))) == NULL) {
677  SCFree(node->netmasks);
678  node->netmasks = NULL;
679  SCLogError("Fatal error encountered in SCRadixAddKey. Mem not allocated...");
681  return NULL;
682  }
683  node->netmasks = ptmp;
684 
685  if (node->netmask_cnt == 1) {
686  node->netmasks[0] = netmask;
687  return new_node;
688  }
689 
690  node->netmasks[node->netmask_cnt - 1] = netmask;
691 
692  for (i = node->netmask_cnt - 1; i > 0; i--) {
693  if (netmask < node->netmasks[i - 1]) {
694  node->netmasks[i] = netmask;
695  break;
696  }
697 
698  node->netmasks[i] = node->netmasks[i - 1];
699  node->netmasks[i - 1] = netmask;
700  }
701  }
702  } else {
703  node->prefix = SCRadixCreatePrefix(key_stream, key_bitlen,
704  user, 255);
705  }
706  return node;
707  }
708 
709  /* create the leaf node for the new key */
710  SCRadixPrefix *prefix = NULL;
711  if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, user,
712  netmask)) == NULL) {
713  SCLogError("Error creating prefix");
715  return NULL;
716  }
717  new_node = SCRadixCreateNode();
718  new_node->prefix = prefix;
719  new_node->bit = prefix->bitlen;
720 
721  /* indicates that we have got a key that has length that is already covered
722  * by a prefix of some other key in the tree. We create a new intermediate
723  * node with a single child and stick it in. We need the if only in the
724  * case of variable length keys */
725  if (differ_bit == bitlen) {
726  if (SC_RADIX_BITTEST(bottom_node->prefix->stream[differ_bit >> 3],
727  (0x80 >> (differ_bit % 8))) ) {
728  new_node->right = node;
729  } else {
730  new_node->left = node;
731  }
732  new_node->parent = node->parent;
733 
734  if (node->parent == NULL)
735  tree->head = new_node;
736  else if (node->parent->right == node)
737  node->parent->right = new_node;
738  else
739  node->parent->left = new_node;
740 
741  node->parent = new_node;
742  /* stick our new_node into the tree. Create a node that holds the
743  * differing bit position and break the branch. Also handle the
744  * transfer of netmasks between node and inter_node(explained in more
745  * detail below) */
746  } else {
747  inter_node = SCRadixCreateNode();
748  inter_node->prefix = NULL;
749  inter_node->bit = differ_bit;
750  inter_node->parent = node->parent;
751 
752  if (node->netmasks != NULL) {
753  for (i = 0; i < node->netmask_cnt; i++) {
754  if (node->netmasks[i] < differ_bit + 1)
755  break;
756  }
757 
758  if (i < node->netmask_cnt) {
759  if ( (inter_node->netmasks = SCMalloc((node->netmask_cnt - i) *
760  sizeof(uint8_t))) == NULL) {
761  SCLogError("Fatal error encountered in SCRadixAddKey. Mem not allocated...");
762  SCRadixReleaseNode(inter_node, tree);
763  SCRadixReleaseNode(new_node, tree);
765  return NULL;
766  }
767 
768  for (j = 0; j < (node->netmask_cnt - i); j++)
769  inter_node->netmasks[j] = node->netmasks[i + j];
770 
771  inter_node->netmask_cnt = (node->netmask_cnt - i);
772  node->netmask_cnt = i;
773  }
774  }
775 
776  if (SC_RADIX_BITTEST(stream[differ_bit >> 3],
777  (0x80 >> (differ_bit % 8))) ) {
778  inter_node->left = node;
779  inter_node->right = new_node;
780  } else {
781  inter_node->left = new_node;
782  inter_node->right = node;
783  }
784  new_node->parent = inter_node;
785 
786  if (node->parent == NULL)
787  tree->head = inter_node;
788  else if (node->parent->right == node)
789  node->parent->right = inter_node;
790  else
791  node->parent->left = inter_node;
792 
793  node->parent = inter_node;
794  }
795 
796  /* insert the netmask into the tree */
797  if (netmask != 255 && (netmask != 32 || (netmask == 32 && bitlen != 32)) && netmask != 128) {
798  node = new_node;
799  parent = new_node->parent;
800  while (parent != NULL && netmask < (parent->bit + 1)) {
801  node = parent;
802  parent = parent->parent;
803  }
804 
805  node->netmask_cnt++;
806  if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt *
807  sizeof(uint8_t)))) == NULL) {
808  SCFree(node->netmasks);
809  node->netmasks = NULL;
810  FatalError("Fatal error encountered in SCRadixAddKey. Exiting...");
811  }
812  node->netmasks = ptmp;
813 
814  if (node->netmask_cnt == 1) {
815  node->netmasks[0] = netmask;
816  return new_node;
817  }
818 
819  node->netmasks[node->netmask_cnt - 1] = netmask;
820 
821  for (i = node->netmask_cnt - 1; i > 0; i--) {
822  if (netmask < node->netmasks[i - 1]) {
823  node->netmasks[i] = netmask;
824  break;
825  }
826 
827  node->netmasks[i] = node->netmasks[i - 1];
828  node->netmasks[i - 1] = netmask;
829  }
830  }
831 
832  return new_node;
833 }
834 
835 static SCRadixNode *SCRadixAddKeyExclusive(
836  uint8_t *key_stream, uint8_t key_bitlen, SCRadixTree *tree, void *user, uint8_t netmask)
837 {
838  return SCRadixAddKeyInternal(key_stream, key_bitlen, tree, user, netmask, true);
839 }
840 
841 static SCRadixNode *SCRadixAddKey(
842  uint8_t *key_stream, uint8_t key_bitlen, SCRadixTree *tree, void *user, uint8_t netmask)
843 {
844  return SCRadixAddKeyInternal(key_stream, key_bitlen, tree, user, netmask, false);
845 }
846 
847 /**
848  * \brief Adds a new IPV4 address to the Radix tree
849  *
850  * \param key_stream Data that has to be added to the Radix tree. In this case
851  * a pointer to an IPV4 address
852  * \param tree Pointer to the Radix tree
853  * \param user Pointer to the user data that has to be associated with the
854  * key
855  *
856  * \retval node Pointer to the newly created node
857  */
858 SCRadixNode *SCRadixAddKeyIPV4(uint8_t *key_stream, SCRadixTree *tree,
859  void *user)
860 {
861  SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, 32);
862 
863  return node;
864 }
865 
866 /**
867  * \brief Adds a new IPV6 address to the Radix tree
868  *
869  * \param key_stream Data that has to be added to the Radix tree. In this case
870  * the pointer to an IPV6 address
871  * \param tree Pointer to the Radix tree
872  * \param user Pointer to the user data that has to be associated with the
873  * key
874  *
875  * \retval node Pointer to the newly created node
876  */
877 SCRadixNode *SCRadixAddKeyIPV6(uint8_t *key_stream, SCRadixTree *tree,
878  void *user)
879 {
880  SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, 128);
881 
882  return node;
883 }
884 
885 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
886 static void SCRadixValidateIPv4Key(uint8_t *key, const uint8_t netmask)
887 {
888  uint32_t address;
889  memcpy(&address, key, sizeof(address));
890  uint32_t mask = CIDRGet(netmask);
891  if (address != (address & mask)) {
892  uint32_t masked = address & mask;
893  char ostr[16], nstr[16];
894  PrintInet(AF_INET, (void *)&address, ostr, sizeof(ostr));
895  PrintInet(AF_INET, (void *)&masked, nstr, sizeof(nstr));
896  SCLogNotice("input %s/%u != expected %s/%u", ostr, netmask, nstr, netmask);
897  abort();
898  }
899 }
900 
901 static void SCRadixValidateIPv6Key(uint8_t *key, const uint8_t netmask)
902 {
903  uint32_t address[4];
904  memcpy(&address, key, sizeof(address));
905 
906  uint32_t mask[4];
907  memset(&mask, 0, sizeof(mask));
908  struct in6_addr mask6;
909  CIDRGetIPv6(netmask, &mask6);
910  memcpy(&mask, &mask6.s6_addr, sizeof(mask));
911 
912  uint32_t masked[4];
913  masked[0] = address[0] & mask[0];
914  masked[1] = address[1] & mask[1];
915  masked[2] = address[2] & mask[2];
916  masked[3] = address[3] & mask[3];
917 
918  if (memcmp(masked, address, sizeof(masked)) != 0) {
919  char ostr[64], nstr[64];
920  PrintInet(AF_INET6, (void *)&address, ostr, sizeof(ostr));
921  PrintInet(AF_INET6, (void *)&masked, nstr, sizeof(nstr));
922  SCLogNotice("input %s/%u != expected %s/%u", ostr, netmask, nstr, netmask);
923  abort();
924  }
925 }
926 #endif
927 
928 /**
929  * \brief Adds a new IPV4 netblock to the Radix tree
930  *
931  * \param key_stream Data that has to be added to the Radix tree. In this case
932  * a pointer to an IPV4 netblock
933  * \param tree Pointer to the Radix tree
934  * \param user Pointer to the user data that has to be associated with the
935  * key
936  * \param netmask The netmask (cidr) if we are adding a netblock
937  *
938  * \retval node Pointer to the newly created node
939  */
941  void *user, uint8_t netmask)
942 {
943 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
944  SCRadixValidateIPv4Key(key_stream, netmask);
945 #endif
946  SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, netmask);
947 
948  return node;
949 }
950 
951 /**
952  * \brief Adds a new IPV6 netblock to the Radix tree
953  *
954  * \param key_stream Data that has to be added to the Radix tree. In this case
955  * a pointer to an IPV6 netblock
956  * \param tree Pointer to the Radix tree
957  * \param user Pointer to the user data that has to be associated with the
958  * key
959  * \param netmask The netmask (cidr) if we are adding a netblock
960  *
961  * \retval node Pointer to the newly created node
962  */
964  void *user, uint8_t netmask)
965 {
966 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
967  SCRadixValidateIPv6Key(key_stream, netmask);
968 #endif
969  SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, netmask);
970 
971  return node;
972 }
973 
974 /**
975  * \brief Adds a new IPV4/netblock to the Radix tree from a string
976  *
977  * \param str IPV4 string with optional /cidr netmask
978  * \param tree Pointer to the Radix tree
979  * \param user Pointer to the user data that has to be associated with
980  * the key
981  *
982  * \retval bool true (false) if the node was (wasn't) added.
983  *
984  * sc_errno is set:
985  * - SC_OK: Node added
986  * - SC_EEXIST: Node already exists
987  * - SC_EINVAL: Parameter value error
988  */
989 bool SCRadixAddKeyIPV4String(const char *str, SCRadixTree *tree, void *user)
990 {
991  uint32_t ip;
992  uint8_t netmask = 32;
993  char ip_str[32]; /* Max length for full ipv4/mask string with NUL */
994  char *mask_str = NULL;
995  struct in_addr addr;
996 
997  /* Make a copy of the string so it can be modified */
998  strlcpy(ip_str, str, sizeof(ip_str) - 2);
999  *(ip_str + (sizeof(ip_str) - 1)) = '\0';
1000 
1001  /* Does it have a mask? */
1002  if (NULL != (mask_str = strchr(ip_str, '/'))) {
1003  uint8_t cidr;
1004  *(mask_str++) = '\0';
1005 
1006  /* Dotted type netmask not supported (yet) */
1007  if (strchr(mask_str, '.') != NULL) {
1008  sc_errno = SC_EINVAL;
1009  return false;
1010  }
1011 
1012  /* Get binary values for cidr mask */
1013  if (StringParseU8RangeCheck(&cidr, 10, 0, (const char *)mask_str, 0, 32) < 0) {
1014  sc_errno = SC_EINVAL;
1015  return false;
1016  }
1017 
1018  netmask = (uint8_t)cidr;
1019  }
1020 
1021  /* Validate the IP */
1022  if (inet_pton(AF_INET, ip_str, &addr) <= 0) {
1023  sc_errno = SC_EINVAL;
1024  return false;
1025  }
1026  ip = addr.s_addr;
1027  if (netmask != 32) {
1028  uint32_t mask = CIDRGet(netmask);
1029  uint32_t masked = ip & mask;
1030  if (masked != ip) {
1031  char nstr[16];
1032  PrintInet(AF_INET, (void *)&masked, nstr, sizeof(nstr));
1033  SCLogWarning("adding '%s' as '%s/%u'", str, nstr, netmask);
1034  ip = masked;
1035  }
1036 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1037  SCRadixValidateIPv4Key((uint8_t *)&ip, netmask);
1038 #endif
1039  }
1040 
1041  SCLogDebug("trying to add %s, but only if it doesn't exist", ip_str);
1042  /* Add, but only if not there */
1043  if (SCRadixAddKeyExclusive((uint8_t *)&ip, 32, tree, user, netmask) == NULL) {
1044  return false;
1045  }
1046 
1047  return true;
1048 }
1049 
1050 /**
1051  * \brief Adds a new IPV6/netblock to the Radix tree from a string
1052  *
1053  * \param str IPV6 string with optional /cidr netmask
1054  * \param tree Pointer to the Radix tree
1055  * \param user Pointer to the user data that has to be associated with
1056  * the key
1057  *
1058  * \retval bool true (false) if the node was (wasn't) added.
1059  * sc_errno is set:
1060  * - SC_OK: Node added
1061  * - SC_EEXIST: Node already exists
1062  * - SC_EINVAL: Parameter value error
1063  */
1064 bool SCRadixAddKeyIPV6String(const char *str, SCRadixTree *tree, void *user)
1065 {
1066  uint8_t netmask = 128;
1067  char ip_str[80]; /* Max length for full ipv6/mask string with NUL */
1068  char *mask_str = NULL;
1069  struct in6_addr addr;
1070 
1071  /* Make a copy of the string so it can be modified */
1072  strlcpy(ip_str, str, sizeof(ip_str) - 2);
1073  *(ip_str + sizeof(ip_str) - 1) = '\0';
1074 
1075  /* Does it have a mask? */
1076  if (NULL != (mask_str = strchr(ip_str, '/'))) {
1077  uint8_t cidr;
1078  *(mask_str++) = '\0';
1079 
1080  /* Dotted type netmask not supported (yet) */
1081  if (strchr(mask_str, '.') != NULL) {
1082  sc_errno = SC_EINVAL;
1083  return false;
1084  }
1085 
1086  /* Get binary values for cidr mask */
1087  if (StringParseU8RangeCheck(&cidr, 10, 0, (const char *)mask_str, 0, 128) < 0) {
1088  sc_errno = SC_EINVAL;
1089  return false;
1090  }
1091 
1092  netmask = (uint8_t)cidr;
1093  }
1094 
1095  /* Validate the IP */
1096  if (inet_pton(AF_INET6, ip_str, &addr) <= 0) {
1097  sc_errno = SC_EINVAL;
1098  return false;
1099  }
1100 
1101  if (netmask != 128) {
1102  struct in6_addr mask6, check;
1103  CIDRGetIPv6(netmask, &mask6);
1104  memcpy(&check, &addr, sizeof(check));
1105  bool diff = false;
1106  for (int i = 0; i < 16; i++) {
1107  addr.s6_addr[i] &= mask6.s6_addr[i];
1108  diff |= (addr.s6_addr[i] != check.s6_addr[i]);
1109  }
1110  if (diff) {
1111  char nstr[64];
1112  PrintInet(AF_INET6, (void *)&addr.s6_addr, nstr, sizeof(nstr));
1113  SCLogWarning("adding '%s' as '%s/%u'", str, nstr, netmask);
1114  }
1115 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1116  SCRadixValidateIPv6Key((uint8_t *)&addr.s6_addr, netmask);
1117 #endif
1118  }
1119 
1120  SCLogDebug("trying to add %s, but only if it doesn't exist", str);
1121  /* Add, but only if not there */
1122  if (SCRadixAddKeyExclusive(addr.s6_addr, 128, tree, user, netmask) == NULL) {
1123  return false;
1124  }
1125 
1126  sc_errno = SC_OK;
1127  return true;
1128 }
1129 
1130 static void SCRadixTransferNetmasksBWNodes(SCRadixNode *dest, SCRadixNode *src)
1131 {
1132  int i = 0, j = 0;
1133  void *ptmp = NULL;
1134 
1135  if (src == NULL || dest == NULL) {
1136  SCLogError("src or dest NULL");
1137  return;
1138  }
1139 
1140  /* no netmasks in the source node, to transfer to the destination node */
1141  if (src->netmasks == NULL)
1142  return;
1143 
1144  if ( (ptmp = SCRealloc(dest->netmasks,
1145  (src->netmask_cnt + dest->netmask_cnt) *
1146  sizeof(uint8_t))) == NULL) {
1147  SCFree(dest->netmasks);
1148  dest->netmasks = NULL;
1149  return;
1150  }
1151  dest->netmasks = ptmp;
1152 
1153  for (i = dest->netmask_cnt, j = 0; j < src->netmask_cnt; i++, j++)
1154  dest->netmasks[i] = src->netmasks[j];
1155 
1156  return;
1157 }
1158 
1159 /**
1160  * \brief Removes a netblock entry from an ip node. The function first
1161  * deletes the netblock/user_data entry for the prefix and then
1162  * removes the netmask entry that has been made in the tree, by
1163  * walking up the tree and deleting the entry from the specific node.
1164  *
1165  * \param node The node from which the netblock entry has to be removed.
1166  * \param netmask The netmask entry (cidr) that has to be removed.
1167  */
1168 static void SCRadixRemoveNetblockEntry(SCRadixNode *node, uint8_t netmask)
1169 {
1170  void *ptmp;
1171  SCRadixNode *parent = NULL;
1172  int i = 0;
1173 
1174  if (node == NULL) {
1175  SCLogError("Invalid argument. Node is NULL");
1176  return;
1177  }
1178 
1179  SCRadixRemoveNetmaskUserDataFromPrefix(node->prefix, netmask);
1180 
1181  if (netmask == 32 || netmask == 128)
1182  return;
1183 
1184  parent = node->parent;
1185  while (parent != NULL && netmask < (parent->bit + 1)) {
1186  parent = parent->parent;
1187  }
1188 
1189  for (i = 0; i < node->netmask_cnt; i++) {
1190  if (node->netmasks[i] == netmask)
1191  break;
1192  }
1193 
1194  if (i == node->netmask_cnt) {
1195  SCLogDebug("Something's wrong with the tree. We are unable to find the "
1196  "netmask entry");
1197  return;
1198  }
1199 
1200  for ( ; i < node->netmask_cnt - 1; i++)
1201  node->netmasks[i] = node->netmasks[i + 1];
1202 
1203  node->netmask_cnt--;
1204  if (node->netmask_cnt == 0) {
1205  SCFree(node->netmasks);
1206  node->netmasks = NULL;
1207  return;
1208  }
1209 
1210  ptmp = SCRealloc(node->netmasks, node->netmask_cnt * sizeof(uint8_t));
1211  if (ptmp == NULL) {
1212  SCFree(node->netmasks);
1213  node->netmasks = NULL;
1214  return;
1215  }
1216  node->netmasks = ptmp;
1217 
1218  return;
1219 }
1220 
1221 /**
1222  * \brief Removes a key from the Radix tree
1223  *
1224  * \param key_stream Data that has to be removed from the Radix tree
1225  * \param key_bitlen The bitlen of the above stream. For example if the
1226  * stream holds an IPV4 address(4 bytes), bitlen would be 32
1227  * \param tree Pointer to the Radix tree from which the key has to be
1228  * removed
1229  */
1230 static void SCRadixRemoveKey(uint8_t *key_stream, uint16_t key_bitlen,
1231  SCRadixTree *tree, uint8_t netmask)
1232 {
1233  SCRadixNode *node = tree->head;
1234  SCRadixNode *parent = NULL;
1235  SCRadixNode *temp_dest = NULL;
1236 
1237  SCRadixPrefix *prefix = NULL;
1238 
1239  uint32_t mask = 0;
1240  int i = 0;
1241 
1242  if (node == NULL)
1243  return;
1244 
1245  if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, NULL, 255)) == NULL)
1246  return;
1247 
1248  while (node->bit < prefix->bitlen) {
1249  if (SC_RADIX_BITTEST(prefix->stream[node->bit >> 3],
1250  (0x80 >> (node->bit % 8))) ) {
1251  node = node->right;
1252  } else {
1253  node = node->left;
1254  }
1255 
1256  if (node == NULL) {
1257  SCRadixReleasePrefix(prefix, tree);
1258  return;
1259  }
1260  }
1261 
1262  if (node->bit != prefix->bitlen || node->prefix == NULL) {
1263  SCRadixReleasePrefix(prefix, tree);
1264  return;
1265  }
1266 
1267  i = prefix->bitlen / 8;
1268  if (SCMemcmp(node->prefix->stream, prefix->stream, i) == 0) {
1269  mask = UINT_MAX << (8 - prefix->bitlen % 8);
1270 
1271  if (prefix->bitlen % 8 == 0 ||
1272  (node->prefix->stream[i] & mask) == (prefix->stream[i] & mask)) {
1273  if (!SCRadixPrefixContainNetmask(node->prefix, netmask)) {
1274  SCLogDebug("The ip key exists in the Radix Tree, but this(%d) "
1275  "netblock entry doesn't exist", netmask);
1276  SCRadixReleasePrefix(prefix, tree);
1277  return;
1278  }
1279  } else {
1280  SCLogDebug("You are trying to remove a key that doesn't exist in "
1281  "the Radix Tree");
1282  SCRadixReleasePrefix(prefix, tree);
1283  return;
1284  }
1285  } else {
1286  SCLogDebug("You are trying to remove a key that doesn't exist in the "
1287  "Radix Tree");
1288  SCRadixReleasePrefix(prefix, tree);
1289  return;
1290  }
1291 
1292  /* The ip node does exist, and the netblock entry does exist in this node, if
1293  * we have reached this point. If we have more than one netblock entry, it
1294  * indicates we have multiple entries for this key. So we delete that
1295  * particular netblock entry, and make our way out of this function */
1296  if (SCRadixPrefixNetmaskCount(node->prefix) > 1) {
1297  SCRadixRemoveNetblockEntry(node, netmask);
1298  SCRadixReleasePrefix(prefix, tree);
1299  return;
1300  }
1301 
1302  /* we are deleting the root of the tree. This would be the only node left
1303  * in the tree */
1304  if (tree->head == node) {
1305  SCRadixReleaseNode(node, tree);
1306  tree->head = NULL;
1307  SCRadixReleasePrefix(prefix, tree);
1308  return;
1309  }
1310 
1311  parent = node->parent;
1312  /* parent->parent is not the root of the tree */
1313  if (parent->parent != NULL) {
1314  if (parent->parent->left == parent) {
1315  if (node->parent->left == node) {
1316  temp_dest = parent->right;
1317  parent->parent->left = parent->right;
1318  parent->right->parent = parent->parent;
1319  } else {
1320  temp_dest = parent->left;
1321  parent->parent->left = parent->left;
1322  parent->left->parent = parent->parent;
1323  }
1324  } else {
1325  if (node->parent->left == node) {
1326  temp_dest = parent->right;
1327  parent->parent->right = parent->right;
1328  parent->right->parent = parent->parent;
1329  } else {
1330  temp_dest = parent->left;
1331  parent->parent->right = parent->left;
1332  parent->left->parent = parent->parent;
1333  }
1334  }
1335  /* parent is the root of the tree */
1336  } else {
1337  if (parent->left == node) {
1338  temp_dest = tree->head->right;
1339  tree->head->right->parent = NULL;
1340  tree->head = tree->head->right;
1341  } else {
1342  temp_dest = tree->head->left;
1343  tree->head->left->parent = NULL;
1344  tree->head = tree->head->left;
1345  }
1346  }
1347  /* We need to shift the netmask entries from the node that would be
1348  * deleted to its immediate descendant */
1349  SCRadixTransferNetmasksBWNodes(temp_dest, parent);
1350  /* release the nodes */
1351  SCRadixReleaseNode(parent, tree);
1352  SCRadixReleaseNode(node, tree);
1353  SCRadixReleasePrefix(prefix, tree);
1354 
1355  return;
1356 }
1357 
1358 /**
1359  * \brief Removes a key from the Radix tree
1360  *
1361  * \param key_stream Data that has to be removed from the Radix tree
1362  * \param key_bitlen The bitlen of the above stream.
1363  * \param tree Pointer to the Radix tree from which the key has to be
1364  * removed
1365  */
1366 void SCRadixRemoveKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen,
1367  SCRadixTree *tree)
1368 {
1369  SCRadixRemoveKey(key_stream, key_bitlen, tree, 255);
1370  return;
1371 }
1372 
1373 /**
1374  * \brief Removes an IPV4 address netblock key from the Radix tree.
1375  *
1376  * \param key_stream Data that has to be removed from the Radix tree. In this
1377  * case an IPV4 address
1378  * \param tree Pointer to the Radix tree from which the key has to be
1379  * removed
1380  */
1381 void SCRadixRemoveKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree,
1382  uint8_t netmask)
1383 {
1384 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1385  SCRadixValidateIPv4Key(key_stream, netmask);
1386 #endif
1387  SCRadixRemoveKey(key_stream, 32, tree, netmask);
1388  return;
1389 }
1390 
1391 /**
1392  * \brief Removes an IPV4 address key(not a netblock) from the Radix tree.
1393  * Instead of using this function, we can also used
1394  * SCRadixRemoveKeyIPV4Netblock(), by supplying a netmask value of 32.
1395  *
1396  * \param key_stream Data that has to be removed from the Radix tree. In this
1397  * case an IPV4 address
1398  * \param tree Pointer to the Radix tree from which the key has to be
1399  * removed
1400  */
1401 void SCRadixRemoveKeyIPV4(uint8_t *key_stream, SCRadixTree *tree)
1402 {
1403  SCRadixRemoveKey(key_stream, 32, tree, 32);
1404  return;
1405 }
1406 
1407 /**
1408  * \brief Removes an IPV6 netblock address key from the Radix tree.
1409  *
1410  * \param key_stream Data that has to be removed from the Radix tree. In this
1411  * case an IPV6 address
1412  * \param tree Pointer to the Radix tree from which the key has to be
1413  * removed
1414  */
1415 void SCRadixRemoveKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree,
1416  uint8_t netmask)
1417 {
1418 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1419  SCRadixValidateIPv6Key(key_stream, netmask);
1420 #endif
1421  SCRadixRemoveKey(key_stream, 128, tree, netmask);
1422  return;
1423 }
1424 
1425 /**
1426  * \brief Removes an IPV6 address key(not a netblock) from the Radix tree.
1427  * Instead of using this function, we can also used
1428  * SCRadixRemoveKeyIPV6Netblock(), by supplying a netmask value of 128.
1429  *
1430  * \param key_stream Data that has to be removed from the Radix tree. In this
1431  * case an IPV6 address
1432  * \param tree Pointer to the Radix tree from which the key has to be
1433  * removed
1434  */
1435 void SCRadixRemoveKeyIPV6(uint8_t *key_stream, SCRadixTree *tree)
1436 {
1437  SCRadixRemoveKey(key_stream, 128, tree, 128);
1438  return;
1439 }
1440 
1441 /**
1442  * \brief Checks if an IP prefix falls under a netblock, in the path to the root
1443  * of the tree, from the node. Used internally by SCRadixFindKey()
1444  *
1445  * \param prefix Pointer to the prefix that contains the ip address
1446  * \param node Pointer to the node from where we have to climb the tree
1447  */
1448 static inline SCRadixNode *SCRadixFindKeyIPNetblock(
1449  uint8_t *key_stream, uint8_t key_bitlen, SCRadixNode *node, void **user_data_result)
1450 {
1451  SCRadixNode *netmask_node = NULL;
1452  uint32_t mask = 0;
1453  int bytes = 0;
1454  int i = 0;
1455  int j = 0;
1456 
1457  while (node != NULL && node->netmasks == NULL)
1458  node = node->parent;
1459 
1460  if (node == NULL)
1461  return NULL;
1462  /* hold the node found containing a netmask. We will need it when we call
1463  * this function recursively */
1464  netmask_node = node;
1465 
1466  for (j = 0; j < netmask_node->netmask_cnt; j++) {
1467  bytes = key_bitlen / 8;
1468  for (i = 0; i < bytes; i++) {
1469  mask = UINT_MAX;
1470  if ( ((i + 1) * 8) > netmask_node->netmasks[j]) {
1471  if ( ((i + 1) * 8 - netmask_node->netmasks[j]) < 8)
1472  mask = UINT_MAX << ((i + 1) * 8 - netmask_node->netmasks[j]);
1473  else
1474  mask = 0;
1475  }
1476  key_stream[i] &= mask;
1477  }
1478 
1479  while (node->bit < key_bitlen) {
1480  if (SC_RADIX_BITTEST(key_stream[node->bit >> 3],
1481  (0x80 >> (node->bit % 8))) ) {
1482  node = node->right;
1483  } else {
1484  node = node->left;
1485  }
1486 
1487  if (node == NULL)
1488  return NULL;
1489  }
1490 
1491  if (node->bit != key_bitlen || node->prefix == NULL)
1492  return NULL;
1493 
1494  if (SCMemcmp(node->prefix->stream, key_stream, bytes) == 0) {
1495  mask = UINT_MAX << (8 - key_bitlen % 8);
1496 
1497  if (key_bitlen % 8 == 0 ||
1498  (node->prefix->stream[bytes] & mask) == (key_stream[bytes] & mask)) {
1499  if (SCRadixPrefixContainNetmaskAndSetUserData(
1500  node->prefix, netmask_node->netmasks[j], false, user_data_result))
1501  return node;
1502  }
1503  }
1504  }
1505 
1506  return SCRadixFindKeyIPNetblock(key_stream, key_bitlen, netmask_node->parent, user_data_result);
1507 }
1508 
1509 /**
1510  * \brief Checks if an IP address key is present in the tree. The function
1511  * apart from handling any normal data, also handles ipv4/ipv6 netblocks
1512  *
1513  * \param key_stream Data that has to be found in the Radix tree
1514  * \param key_bitlen The bitlen of the above stream.
1515  * \param tree Pointer to the Radix tree
1516  * \param exact_match The key to be searched is an ip address
1517  * \param netmask Netmask used during exact match
1518  */
1519 static SCRadixNode *SCRadixFindKey(uint8_t *key_stream, uint8_t key_bitlen, uint8_t netmask,
1520  SCRadixTree *tree, bool exact_match, void **user_data_result)
1521 {
1522  if (tree == NULL || tree->head == NULL)
1523  return NULL;
1524 
1525  SCRadixNode *node = tree->head;
1526  uint32_t mask = 0;
1527  int bytes = 0;
1528  uint8_t tmp_stream[255];
1529 
1530  memset(tmp_stream, 0, 255);
1531  memcpy(tmp_stream, key_stream, key_bitlen / 8);
1532 
1533  while (node->bit < key_bitlen) {
1534  if (SC_RADIX_BITTEST(tmp_stream[node->bit >> 3],
1535  (0x80 >> (node->bit % 8))) ) {
1536  node = node->right;
1537  } else {
1538  node = node->left;
1539  }
1540 
1541  if (node == NULL) {
1542  return NULL;
1543  }
1544  }
1545 
1546  if (node->bit != key_bitlen || node->prefix == NULL) {
1547  return NULL;
1548  }
1549 
1550  bytes = key_bitlen / 8;
1551  if (SCMemcmp(node->prefix->stream, tmp_stream, bytes) == 0) {
1552  mask = UINT_MAX << (8 - key_bitlen % 8);
1553 
1554  if (key_bitlen % 8 == 0 ||
1555  (node->prefix->stream[bytes] & mask) == (tmp_stream[bytes] & mask)) {
1556  if (SCRadixPrefixContainNetmaskAndSetUserData(
1557  node->prefix, netmask, true, user_data_result)) {
1558  return node;
1559  }
1560  }
1561  }
1562 
1563  /* if you are not an ip key, get out of here */
1564  if (exact_match) {
1565  return NULL;
1566  }
1567 
1568  SCRadixNode *ret = SCRadixFindKeyIPNetblock(tmp_stream, key_bitlen, node, user_data_result);
1569  return ret;
1570 }
1571 
1572 /**
1573  * \brief Checks if an IPV4 address is present in the tree
1574  *
1575  * \param key_stream Data that has to be found in the Radix tree. In this case
1576  * an IPV4 address
1577  * \param tree Pointer to the Radix tree instance
1578  */
1579 SCRadixNode *SCRadixFindKeyIPV4ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1580 {
1581  return SCRadixFindKey(key_stream, 32, 32, tree, true, user_data_result);
1582 }
1583 
1584 /**
1585  * \brief Checks if an IPV4 address is present in the tree under a netblock
1586  *
1587  * \param key_stream Data that has to be found in the Radix tree. In this case
1588  * an IPV4 address
1589  * \param tree Pointer to the Radix tree instance
1590  */
1591 SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1592 {
1593  return SCRadixFindKey(key_stream, 32, 32, tree, false, user_data_result);
1594 }
1595 
1596 /**
1597  * \brief Checks if an IPV4 Netblock address is present in the tree
1598  *
1599  * \param key_stream Data that has to be found in the Radix tree. In this case
1600  * an IPV4 netblock address
1601  * \param tree Pointer to the Radix tree instance
1602  */
1604  uint8_t netmask, void **user_data_result)
1605 {
1606 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1607  SCRadixValidateIPv4Key(key_stream, netmask);
1608 #endif
1609  SCRadixNode *node = SCRadixFindKey(key_stream, 32, netmask, tree, true, user_data_result);
1610  return node;
1611 }
1612 
1613 /**
1614  * \brief Checks if an IPV6 Netblock address is present in the tree
1615  *
1616  * \param key_stream Data that has to be found in the Radix tree. In this case
1617  * an IPV6 netblock address
1618  * \param tree Pointer to the Radix tree instance
1619  */
1621  uint8_t netmask, void **user_data_result)
1622 {
1623 #if defined(DEBUG_VALIDATION) || defined(UNITTESTS)
1624  SCRadixValidateIPv6Key(key_stream, netmask);
1625 #endif
1626  SCRadixNode *node = SCRadixFindKey(key_stream, 128, netmask, tree, true, user_data_result);
1627  return node;
1628 }
1629 
1630 /**
1631  * \brief Checks if an IPV6 address is present in the tree
1632  *
1633  * \param key_stream Data that has to be found in the Radix tree. In this case
1634  * an IPV6 address
1635  * \param tree Pointer to the Radix tree instance
1636  */
1637 SCRadixNode *SCRadixFindKeyIPV6ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1638 {
1639  return SCRadixFindKey(key_stream, 128, 128, tree, true, user_data_result);
1640 }
1641 
1642 /**
1643  * \brief Checks if an IPV6 address is present in the tree under a netblock
1644  *
1645  * \param key_stream Data that has to be found in the Radix tree. In this case
1646  * an IPV6 address
1647  * \param tree Pointer to the Radix tree instance
1648  */
1649 SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1650 {
1651  return SCRadixFindKey(key_stream, 128, 128, tree, false, user_data_result);
1652 }
1653 
1654 /**
1655  * \brief Prints the node information from a Radix tree
1656  *
1657  * \param node Pointer to the Radix node whose information has to be printed
1658  * \param level Used for indentation purposes
1659  */
1660 void SCRadixPrintNodeInfo(SCRadixNode *node, int level, void (*PrintData)(void*))
1661 {
1662  int i = 0;
1663 
1664  if (node == NULL)
1665  return;
1666 
1667  for (i = 0; i < level; i++)
1668  printf(" ");
1669 
1670  printf("%d [", node->bit);
1671 
1672  if (node->netmasks == NULL) {
1673  printf("%d, ", -1);
1674  } else {
1675  for (i = 0; i < node->netmask_cnt; i++)
1676  printf("%s%d", (0 == i ? "" : ", "), node->netmasks[i]);
1677  }
1678 
1679  printf("] (");
1680  if (node->prefix != NULL) {
1681  for (i = 0; i * 8 < node->prefix->bitlen; i++)
1682  printf("%s%d", (0 == i ? "" : "."), node->prefix->stream[i]);
1683  printf(") user_data %p\n", node->prefix->user_data);
1684 
1685  SCRadixUserData *ud = node->prefix->user_data;
1686  do {
1687  for (int x = 0; x <= level; x++)
1688  printf(" ");
1689  printf("[%d] (%p): ", ud->netmask, ud->user);
1690  if (PrintData != NULL) {
1691  PrintData(ud->user);
1692  } else {
1693  printf("NULL");
1694  }
1695  printf("\n");
1696  ud = ud->next;
1697  } while (ud != NULL);
1698  } else {
1699  printf("inter_node)\n");
1700  }
1701 
1702  return;
1703 }
1704 
1705 /**
1706  * \brief Helper function used by SCRadixPrintTree. Prints the subtree with
1707  * node as the root of the subtree
1708  *
1709  * \param node Pointer to the node that is the root of the subtree to be printed
1710  * \param level Used for indentation purposes
1711  */
1712 static void SCRadixPrintRadixSubtree(SCRadixNode *node, int level, void (*PrintData)(void*))
1713 {
1714  if (node != NULL) {
1715  SCRadixPrintNodeInfo(node, level, PrintData);
1716  SCRadixPrintRadixSubtree(node->left, level + 1, PrintData);
1717  SCRadixPrintRadixSubtree(node->right, level + 1, PrintData);
1718  }
1719 
1720  return;
1721 }
1722 
1723 /**
1724  * \brief Prints the Radix Tree. While printing the radix tree we use the
1725  * following format
1726  *
1727  * Parent_0
1728  * Left_Child_1
1729  * Left_Child_2
1730  * Right_Child_2
1731  * Right_Child_1
1732  * Left_Child_2
1733  * Right_Child_2 and so on
1734  *
1735  * Each node printed out holds details on the next bit that differs
1736  * amongst its children, and if the node holds a prefix, the perfix is
1737  * printed as well.
1738  *
1739  * \param tree Pointer to the Radix tree that has to be printed
1740  */
1742 {
1743  printf("Printing the Radix Tree: \n");
1744 
1745  SCRadixPrintRadixSubtree(tree->head, 0, tree->PrintData);
1746 
1747  return;
1748 }
1749 
1750 /*------------------------------------Unit_Tests------------------------------*/
1751 
1752 #ifdef UNITTESTS
1753 
1754 static int SCRadixTestIPV4Insertion03(void)
1755 {
1756  SCRadixTree *tree = NULL;
1757  struct sockaddr_in servaddr;
1758  int result = 1;
1759 
1760  tree = SCRadixCreateRadixTree(free, NULL);
1761 
1762  /* add the keys */
1763  memset(&servaddr, 0, sizeof(servaddr));
1764  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1765  return 0;
1766  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1767 
1768  memset(&servaddr, 0, sizeof(servaddr));
1769  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1770  return 0;
1771  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1772 
1773  memset(&servaddr, 0, sizeof(servaddr));
1774  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1775  return 0;
1776  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1777 
1778  memset(&servaddr, 0, sizeof(servaddr));
1779  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1780  return 0;
1781  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1782 
1783  /* add a key that already exists in the tree */
1784  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1785 
1786  /* test for the existence of a key */
1787  memset(&servaddr, 0, sizeof(servaddr));
1788  if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0)
1789  return 0;
1790  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1791 
1792  /* test for the existence of a key */
1793  memset(&servaddr, 0, sizeof(servaddr));
1794  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1795  return 0;
1796  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1797 
1798  /* continue adding keys */
1799  memset(&servaddr, 0, sizeof(servaddr));
1800  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1801  return 0;
1802  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1803 
1804  memset(&servaddr, 0, sizeof(servaddr));
1805  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1806  return 0;
1807  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1808 
1809  memset(&servaddr, 0, sizeof(servaddr));
1810  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1811  return 0;
1812  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1813 
1814  /* test the existence of keys */
1815  memset(&servaddr, 0, sizeof(servaddr));
1816  if (inet_pton(AF_INET, "192.168.1.3", &servaddr.sin_addr) <= 0)
1817  return 0;
1818  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1819 
1820  memset(&servaddr, 0, sizeof(servaddr));
1821  if (inet_pton(AF_INET, "127.234.2.62", &servaddr.sin_addr) <= 0)
1822  return 0;
1823  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1824 
1825  memset(&servaddr, 0, sizeof(servaddr));
1826  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1827  return 0;
1828  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1829 
1830  memset(&servaddr, 0, sizeof(servaddr));
1831  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1832  return 0;
1833  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1834 
1835  memset(&servaddr, 0, sizeof(servaddr));
1836  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1837  return 0;
1838  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1839 
1840  memset(&servaddr, 0, sizeof(servaddr));
1841  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1842  return 0;
1843  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1844 
1845  memset(&servaddr, 0, sizeof(servaddr));
1846  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1847  return 0;
1848  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1849 
1850  memset(&servaddr, 0, sizeof(servaddr));
1851  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1852  return 0;
1853  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1854 
1855  memset(&servaddr, 0, sizeof(servaddr));
1856  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1857  return 0;
1858  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1859 
1861 
1862  return result;
1863 }
1864 
1865 static int SCRadixTestIPV4Removal04(void)
1866 {
1867  SCRadixTree *tree = NULL;
1868  struct sockaddr_in servaddr;
1869  int result = 1;
1870 
1871  tree = SCRadixCreateRadixTree(free, NULL);
1872 
1873  /* add the keys */
1874  memset(&servaddr, 0, sizeof(servaddr));
1875  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1876  return 0;
1877  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1878 
1879  memset(&servaddr, 0, sizeof(servaddr));
1880  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1881  return 0;
1882  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1883 
1884  memset(&servaddr, 0, sizeof(servaddr));
1885  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1886  return 0;
1887  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1888 
1889  memset(&servaddr, 0, sizeof(servaddr));
1890  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1891  return 0;
1892  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1893 
1894  memset(&servaddr, 0, sizeof(servaddr));
1895  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1896  return 0;
1897  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1898 
1899  memset(&servaddr, 0, sizeof(servaddr));
1900  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1901  return 0;
1902  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1903 
1904  memset(&servaddr, 0, sizeof(servaddr));
1905  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1906  return 0;
1907  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1908 
1909  /* remove the keys from the tree */
1910  memset(&servaddr, 0, sizeof(servaddr));
1911  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1912  return 0;
1913  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1914 
1915  memset(&servaddr, 0, sizeof(servaddr));
1916  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1917  return 0;
1918  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1919 
1920  memset(&servaddr, 0, sizeof(servaddr));
1921  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1922  return 0;
1923  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1924 
1925  memset(&servaddr, 0, sizeof(servaddr));
1926  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1927  return 0;
1928  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1929 
1930  memset(&servaddr, 0, sizeof(servaddr));
1931  if (inet_pton(AF_INET, "192.167.1.1", &servaddr.sin_addr) <= 0)
1932  return 0;
1933  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1934 
1935  memset(&servaddr, 0, sizeof(servaddr));
1936  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1937  return 0;
1938  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1939 
1940  memset(&servaddr, 0, sizeof(servaddr));
1941  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1942  return 0;
1943  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1944 
1945  memset(&servaddr, 0, sizeof(servaddr));
1946  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1947  return 0;
1948  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1949 
1950  memset(&servaddr, 0, sizeof(servaddr));
1951  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1952  return 0;
1953  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1954 
1955  memset(&servaddr, 0, sizeof(servaddr));
1956  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1957  return 0;
1958  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1959 
1960  memset(&servaddr, 0, sizeof(servaddr));
1961  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1962  return 0;
1963  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1964 
1965  memset(&servaddr, 0, sizeof(servaddr));
1966  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1967  return 0;
1968  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1969 
1970  result &= (tree->head == NULL);
1971 
1973 
1974  return result;
1975 }
1976 
1977 static int SCRadixTestIPV6Insertion07(void)
1978 {
1979  SCRadixTree *tree = NULL;
1980  struct sockaddr_in6 servaddr;
1981  int result = 1;
1982 
1983  tree = SCRadixCreateRadixTree(free, NULL);
1984 
1985  /* add the keys */
1986  memset(&servaddr, 0, sizeof(servaddr));
1987  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
1988  &servaddr.sin6_addr) <= 0)
1989  return 0;
1990  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1991 
1992  memset(&servaddr, 0, sizeof(servaddr));
1993  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
1994  &servaddr.sin6_addr) <= 0)
1995  return 0;
1996  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1997 
1998  memset(&servaddr, 0, sizeof(servaddr));
1999  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2000  &servaddr.sin6_addr) <= 0)
2001  return 0;
2002  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2003 
2004  memset(&servaddr, 0, sizeof(servaddr));
2005  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2006  &servaddr.sin6_addr) <= 0)
2007  return 0;
2008  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2009 
2010  /* Try to add the prefix that already exists in the tree */
2011  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2012 
2013  memset(&servaddr, 0, sizeof(servaddr));
2014  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2015  &servaddr.sin6_addr) <= 0)
2016  return 0;
2017  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2018 
2019  memset(&servaddr, 0, sizeof(servaddr));
2020  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2021  &servaddr.sin6_addr) <= 0)
2022  return 0;
2023  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2024 
2025  memset(&servaddr, 0, sizeof(servaddr));
2026  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2027  &servaddr.sin6_addr) <= 0)
2028  return 0;
2029  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2030 
2031  /* test the existence of keys */
2032  memset(&servaddr, 0, sizeof(servaddr));
2033  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2034  &servaddr.sin6_addr) <= 0)
2035  return 0;
2036  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2037 
2038  memset(&servaddr, 0, sizeof(servaddr));
2039  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2040  &servaddr.sin6_addr) <= 0)
2041  return 0;
2042  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2043 
2044  memset(&servaddr, 0, sizeof(servaddr));
2045  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2046  &servaddr.sin6_addr) <= 0)
2047  return 0;
2048  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2049 
2050  memset(&servaddr, 0, sizeof(servaddr));
2051  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2052  &servaddr.sin6_addr) <= 0)
2053  return 0;
2054  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2055 
2056  memset(&servaddr, 0, sizeof(servaddr));
2057  if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212",
2058  &servaddr.sin6_addr) <= 0)
2059  return 0;
2060  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2061 
2062  memset(&servaddr, 0, sizeof(servaddr));
2063  if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315",
2064  &servaddr.sin6_addr) <= 0)
2065  return 0;
2066  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2067 
2068  memset(&servaddr, 0, sizeof(servaddr));
2069  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2070  &servaddr.sin6_addr) <= 0)
2071  return 0;
2072  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2073 
2074  memset(&servaddr, 0, sizeof(servaddr));
2075  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2076  &servaddr.sin6_addr) <= 0)
2077  return 0;
2078  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2079 
2080  memset(&servaddr, 0, sizeof(servaddr));
2081  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2082  &servaddr.sin6_addr) <= 0)
2083  return 0;
2084  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2085 
2087 
2088  return result;
2089 }
2090 
2091 static int SCRadixTestIPV6Removal08(void)
2092 {
2093  SCRadixTree *tree = NULL;
2094  struct sockaddr_in6 servaddr;
2095  int result = 1;
2096 
2097  tree = SCRadixCreateRadixTree(free, NULL);
2098 
2099  /* add the keys */
2100  memset(&servaddr, 0, sizeof(servaddr));
2101  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2102  &servaddr.sin6_addr) <= 0)
2103  return 0;
2104  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2105 
2106  memset(&servaddr, 0, sizeof(servaddr));
2107  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2108  &servaddr.sin6_addr) <= 0)
2109  return 0;
2110  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2111 
2112  memset(&servaddr, 0, sizeof(servaddr));
2113  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2114  &servaddr.sin6_addr) <= 0)
2115  return 0;
2116  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2117 
2118  memset(&servaddr, 0, sizeof(servaddr));
2119  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2120  &servaddr.sin6_addr) <= 0)
2121  return 0;
2122  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2123 
2124  /* Try to add the prefix that already exists in the tree */
2125  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2126 
2127  memset(&servaddr, 0, sizeof(servaddr));
2128  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2129  &servaddr.sin6_addr) <= 0)
2130  return 0;
2131  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2132 
2133  memset(&servaddr, 0, sizeof(servaddr));
2134  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2135  &servaddr.sin6_addr) <= 0)
2136  return 0;
2137  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2138 
2139  memset(&servaddr, 0, sizeof(servaddr));
2140  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2141  &servaddr.sin6_addr) <= 0)
2142  return 0;
2143  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2144 
2145  /* test the existence of keys */
2146  memset(&servaddr, 0, sizeof(servaddr));
2147  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2148  &servaddr.sin6_addr) <= 0)
2149  return 0;
2150  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2151 
2152  memset(&servaddr, 0, sizeof(servaddr));
2153  if (inet_pton(AF_INET6, "8888:0BF1:5346:BDEA:6422:8713:9124:2315",
2154  &servaddr.sin6_addr) <= 0)
2155  return 0;
2156  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2157 
2158  memset(&servaddr, 0, sizeof(servaddr));
2159  if (inet_pton(AF_INET6, "2006:0BF1:5346:BDEA:7422:8713:9124:2315",
2160  &servaddr.sin6_addr) <= 0)
2161  return 0;
2162  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2163 
2164  memset(&servaddr, 0, sizeof(servaddr));
2165  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2166  &servaddr.sin6_addr) <= 0)
2167  return 0;
2168  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2169 
2170  memset(&servaddr, 0, sizeof(servaddr));
2171  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2172  &servaddr.sin6_addr) <= 0)
2173  return 0;
2174  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2175 
2176  /* test for existence */
2177  memset(&servaddr, 0, sizeof(servaddr));
2178  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2179  &servaddr.sin6_addr) <= 0)
2180  return 0;
2181  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2182 
2183  memset(&servaddr, 0, sizeof(servaddr));
2184  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2185  &servaddr.sin6_addr) <= 0)
2186  return 0;
2187  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2188 
2189  memset(&servaddr, 0, sizeof(servaddr));
2190  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2191  &servaddr.sin6_addr) <= 0)
2192  return 0;
2193  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2194 
2195  memset(&servaddr, 0, sizeof(servaddr));
2196  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2197  &servaddr.sin6_addr) <= 0)
2198  return 0;
2199  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2200 
2201  memset(&servaddr, 0, sizeof(servaddr));
2202  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2203  &servaddr.sin6_addr) <= 0)
2204  return 0;
2205  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2206 
2207  memset(&servaddr, 0, sizeof(servaddr));
2208  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:DDDD:2315",
2209  &servaddr.sin6_addr) <= 0)
2210  return 0;
2211  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2212 
2213  /* remove keys */
2214  memset(&servaddr, 0, sizeof(servaddr));
2215  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2216  &servaddr.sin6_addr) <= 0)
2217  return 0;
2218  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2219 
2220  memset(&servaddr, 0, sizeof(servaddr));
2221  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2222  &servaddr.sin6_addr) <= 0)
2223  return 0;
2224  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2225 
2226  /* test for existence */
2227  memset(&servaddr, 0, sizeof(servaddr));
2228  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2229  &servaddr.sin6_addr) <= 0)
2230  return 0;
2231  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2232 
2233  memset(&servaddr, 0, sizeof(servaddr));
2234  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2235  &servaddr.sin6_addr) <= 0)
2236  return 0;
2237  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2238 
2239  memset(&servaddr, 0, sizeof(servaddr));
2240  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2241  &servaddr.sin6_addr) <= 0)
2242  return 0;
2243  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2244 
2245  memset(&servaddr, 0, sizeof(servaddr));
2246  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2247  &servaddr.sin6_addr) <= 0)
2248  return 0;
2249  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2250 
2251  memset(&servaddr, 0, sizeof(servaddr));
2252  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2253  &servaddr.sin6_addr) <= 0)
2254  return 0;
2255  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2256 
2257  memset(&servaddr, 0, sizeof(servaddr));
2258  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2259  &servaddr.sin6_addr) <= 0)
2260  return 0;
2261  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2262 
2263  /* remove keys */
2264  memset(&servaddr, 0, sizeof(servaddr));
2265  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2266  &servaddr.sin6_addr) <= 0)
2267  return 0;
2268  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2269 
2270  memset(&servaddr, 0, sizeof(servaddr));
2271  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2272  &servaddr.sin6_addr) <= 0)
2273  return 0;
2274  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2275 
2276  memset(&servaddr, 0, sizeof(servaddr));
2277  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2278  &servaddr.sin6_addr) <= 0)
2279  return 0;
2280  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2281 
2282  memset(&servaddr, 0, sizeof(servaddr));
2283  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2284  &servaddr.sin6_addr) <= 0)
2285  return 0;
2286  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2287 
2288  /* test for existence */
2289  memset(&servaddr, 0, sizeof(servaddr));
2290  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2291  &servaddr.sin6_addr) <= 0)
2292  return 0;
2293  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2294 
2295  memset(&servaddr, 0, sizeof(servaddr));
2296  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2297  &servaddr.sin6_addr) <= 0)
2298  return 0;
2299  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2300 
2301  memset(&servaddr, 0, sizeof(servaddr));
2302  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2303  &servaddr.sin6_addr) <= 0)
2304  return 0;
2305  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2306 
2307  memset(&servaddr, 0, sizeof(servaddr));
2308  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2309  &servaddr.sin6_addr) <= 0)
2310  return 0;
2311  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2312 
2313  memset(&servaddr, 0, sizeof(servaddr));
2314  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2315  &servaddr.sin6_addr) <= 0)
2316  return 0;
2317  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2318 
2319  memset(&servaddr, 0, sizeof(servaddr));
2320  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2321  &servaddr.sin6_addr) <= 0)
2322  return 0;
2323  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2324 
2326 
2327  return result;
2328 }
2329 
2330 /** Bug #5066
2331  *
2332  * insert:
2333  * - 100.117.241.0/25: 100.117.241.0 - 100.117.241.127
2334  * - 100.117.241.0/26: 100.117.241.0 - 100.117.241.63
2335  *
2336  * check:
2337  * - 100.117.241.64/26: 100.117.241.64 - 100.117.241.127
2338  */
2339 
2340 static int SCRadixTestIPV4Bug5066(void)
2341 {
2342  struct sockaddr_in servaddr;
2343  SCRadixNode *node = NULL;
2344 
2345  SCLogDebug("setup tree");
2346  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
2347 
2348  memset(&servaddr, 0, sizeof(servaddr));
2349  FAIL_IF(inet_pton(AF_INET, "100.117.241.0", &servaddr.sin_addr) <= 0);
2350  SCLogDebug("add 100.117.241.0/25");
2351  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1"), 25);
2352  SCRadixPrintTree(tree);
2353  SCLogDebug("find 100.117.241.0/25");
2354  char *r = NULL;
2355  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 25, (void **)&r);
2356  FAIL_IF_NULL(node);
2357  SCRadixPrintNodeInfo(node, 0, NULL);
2358 
2359  SCLogDebug("add 100.117.241.0/26");
2360  FAIL_IF(inet_pton(AF_INET, "100.117.241.0", &servaddr.sin_addr) <= 0);
2361  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("2"), 26);
2362  SCRadixPrintTree(tree);
2363  SCLogDebug("find 100.117.241.0/26");
2364  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 26, NULL);
2365  FAIL_IF_NULL(node);
2366  SCRadixPrintNodeInfo(node, 0, NULL);
2367 
2368  SCLogDebug("find 100.117.241.64/26 (should fail)");
2369  FAIL_IF(inet_pton(AF_INET, "100.117.241.64", &servaddr.sin_addr) <= 0);
2370  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 26, NULL);
2371  FAIL_IF_NOT_NULL(node);
2372  SCRadixPrintNodeInfo(node, 0, NULL);
2373 
2374  SCLogDebug("add 100.117.241.64/26");
2375  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("3"), 26);
2376  SCLogDebug("find 100.117.241.64/26 (should succeed)");
2377  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 26, NULL);
2378  FAIL_IF_NULL(node);
2379  SCRadixPrintNodeInfo(node, 0, NULL);
2380 
2381  SCRadixPrintTree(tree);
2382 
2384  PASS;
2385 }
2386 
2387 static void SCRadixTestIPV4Bug5066v2PrintData(void *d)
2388 {
2389  const char *s = d;
2390  printf("%s", s);
2391 }
2392 
2393 static int SCRadixTestIPV4Bug5066v2(void)
2394 {
2395  struct sockaddr_in servaddr;
2396  SCRadixNode *node = NULL;
2397 
2398  SCLogDebug("setup tree");
2399  SCRadixTree *tree = SCRadixCreateRadixTree(free, SCRadixTestIPV4Bug5066v2PrintData);
2400 
2401  memset(&servaddr, 0, sizeof(servaddr));
2402  FAIL_IF(inet_pton(AF_INET, "1.2.3.0", &servaddr.sin_addr) <= 0);
2403  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.0/24"), 24);
2404  SCRadixPrintTree(tree);
2405  char *r = NULL;
2406  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 24, (void **)&r);
2407  SCRadixPrintTree(tree);
2408  FAIL_IF_NULL(node);
2409  SCRadixPrintNodeInfo(node, 0, NULL);
2410  FAIL_IF_NOT(strcmp(r, "1.2.3.0/24") == 0);
2411 
2412  memset(&servaddr, 0, sizeof(servaddr));
2413  FAIL_IF(inet_pton(AF_INET, "1.2.3.0", &servaddr.sin_addr) <= 0);
2414  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.0/25"), 25);
2415  SCRadixPrintTree(tree);
2416  r = NULL;
2417  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 25, (void **)&r);
2418  SCRadixPrintTree(tree);
2419  FAIL_IF_NULL(node);
2420  SCRadixPrintNodeInfo(node, 0, NULL);
2421  FAIL_IF_NOT(strcmp(r, "1.2.3.0/25") == 0);
2422 
2423  memset(&servaddr, 0, sizeof(servaddr));
2424  FAIL_IF(inet_pton(AF_INET, "1.2.3.0", &servaddr.sin_addr) <= 0);
2425  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.0/26"), 26);
2426  SCRadixPrintTree(tree);
2427  r = NULL;
2428  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 26, (void **)&r);
2429  SCRadixPrintTree(tree);
2430  FAIL_IF_NULL(node);
2431  SCRadixPrintNodeInfo(node, 0, NULL);
2432  FAIL_IF_NOT(strcmp(r, "1.2.3.0/26") == 0);
2433 
2434  memset(&servaddr, 0, sizeof(servaddr));
2435  FAIL_IF(inet_pton(AF_INET, "1.2.3.64", &servaddr.sin_addr) <= 0);
2436  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.64/26"), 26);
2437  SCRadixPrintTree(tree);
2438  r = NULL;
2439  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 26, (void **)&r);
2440  SCRadixPrintTree(tree);
2441  FAIL_IF_NULL(node);
2442  SCRadixPrintNodeInfo(node, 0, NULL);
2443  FAIL_IF_NOT(strcmp(r, "1.2.3.64/26") == 0);
2444 
2445  memset(&servaddr, 0, sizeof(servaddr));
2446  FAIL_IF(inet_pton(AF_INET, "1.2.3.64", &servaddr.sin_addr) <= 0);
2447  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.64/27"), 27);
2448  SCRadixPrintTree(tree);
2449  r = NULL;
2450  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 27, (void **)&r);
2451  SCRadixPrintTree(tree);
2452  FAIL_IF_NULL(node);
2453  SCRadixPrintNodeInfo(node, 0, NULL);
2454  FAIL_IF_NOT(strcmp(r, "1.2.3.64/27") == 0);
2455 
2456  memset(&servaddr, 0, sizeof(servaddr));
2457  FAIL_IF(inet_pton(AF_INET, "1.2.3.96", &servaddr.sin_addr) <= 0);
2458  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, strdup("1.2.3.96/27"), 27);
2459  SCRadixPrintTree(tree);
2460  r = NULL;
2461  node = SCRadixFindKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 27, (void **)&r);
2462  SCRadixPrintTree(tree);
2463  FAIL_IF_NULL(node);
2464  SCLogNotice("node:");
2465  SCRadixPrintNodeInfo(node, 0, NULL);
2466  FAIL_IF_NOT(strcmp(r, "1.2.3.96/27") == 0);
2467 
2469  PASS;
2470 }
2471 
2472 /** Bug #5066
2473  */
2474 static int SCRadixTestIPV6Bug5066(void)
2475 {
2476  struct sockaddr_in6 servaddr;
2477  SCRadixNode *node = NULL;
2478 
2479  SCLogDebug("setup tree");
2480  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
2481 
2482  memset(&servaddr, 0, sizeof(servaddr));
2483  FAIL_IF(inet_pton(AF_INET6, "2000::1:0", &servaddr.sin6_addr) <= 0);
2484  SCLogDebug("add 2000::1:0/121");
2485  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, strdup("1"), 121);
2486  SCRadixPrintTree(tree);
2487  SCLogDebug("find 2000::1:0/121");
2488  char *r = NULL;
2489  node = SCRadixFindKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, 121, (void **)&r);
2490  FAIL_IF_NULL(node);
2491  SCRadixPrintNodeInfo(node, 0, NULL);
2492 
2493  SCLogDebug("add 2000::1:0/122");
2494  FAIL_IF(inet_pton(AF_INET6, "2000::1:0", &servaddr.sin6_addr) <= 0);
2495  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, strdup("2"), 122);
2496  SCRadixPrintTree(tree);
2497  SCLogDebug("find 2000::1:0/122");
2498  node = SCRadixFindKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, 122, NULL);
2499  FAIL_IF_NULL(node);
2500  SCRadixPrintNodeInfo(node, 0, NULL);
2501 
2502  SCLogDebug("find 2000::1:40/122 (should fail)");
2503  FAIL_IF(inet_pton(AF_INET6, "2000::1:40", &servaddr.sin6_addr) <= 0);
2504  node = SCRadixFindKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, 122, NULL);
2505  FAIL_IF_NOT_NULL(node);
2506  SCRadixPrintNodeInfo(node, 0, NULL);
2507 
2508  SCLogDebug("add 2000::1:40/122");
2509  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, strdup("3"), 122);
2510  SCLogDebug("find 2000::1:40/122 (should succeed)");
2511  node = SCRadixFindKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, 122, NULL);
2512  FAIL_IF_NULL(node);
2513  SCRadixPrintNodeInfo(node, 0, NULL);
2514 
2515  SCRadixPrintTree(tree);
2516 
2518  PASS;
2519 }
2520 
2521 static int SCRadixTestIPV4NetblockInsertion09(void)
2522 {
2523  SCRadixTree *tree = NULL;
2524  struct sockaddr_in servaddr;
2525  int result = 1;
2526 
2527  tree = SCRadixCreateRadixTree(free, NULL);
2528 
2529  /* add the keys */
2530  memset(&servaddr, 0, sizeof(servaddr));
2531  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
2532  return 0;
2533  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2534 
2535  memset(&servaddr, 0, sizeof(servaddr));
2536  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
2537  return 0;
2538  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2539 
2540  memset(&servaddr, 0, sizeof(servaddr));
2541  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
2542  return 0;
2543  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2544 
2545  memset(&servaddr, 0, sizeof(servaddr));
2546  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2547  return 0;
2548  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2549 
2550  memset(&servaddr, 0, sizeof(servaddr));
2551  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
2552  return 0;
2553  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2554 
2555  memset(&servaddr, 0, sizeof(servaddr));
2556  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
2557  return 0;
2558  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2559 
2560  memset(&servaddr, 0, sizeof(servaddr));
2561  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
2562  return 0;
2563  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2564 
2565  memset(&servaddr, 0, sizeof(servaddr));
2566  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2567  return 0;
2568  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2569 
2570  memset(&servaddr, 0, sizeof(servaddr));
2571  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2572  return 0;
2573  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2574 
2575  memset(&servaddr, 0, sizeof(servaddr));
2576  if (inet_pton(AF_INET, "192.171.192.0", &servaddr.sin_addr) <= 0)
2577  return 0;
2578  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2579 
2580  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2581  return 0;
2582  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2583 
2584  /* test for the existence of a key */
2585  memset(&servaddr, 0, sizeof(servaddr));
2586  if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0)
2587  return 0;
2588  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2589 
2590  memset(&servaddr, 0, sizeof(servaddr));
2591  if (inet_pton(AF_INET, "192.170.1.6", &servaddr.sin_addr) <= 0)
2592  return 0;
2593  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2594 
2595  memset(&servaddr, 0, sizeof(servaddr));
2596  if (inet_pton(AF_INET, "192.171.128.145", &servaddr.sin_addr) <= 0)
2597  return 0;
2598  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2599 
2600  memset(&servaddr, 0, sizeof(servaddr));
2601  if (inet_pton(AF_INET, "192.171.64.6", &servaddr.sin_addr) <= 0)
2602  return 0;
2603  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2604 
2605  memset(&servaddr, 0, sizeof(servaddr));
2606  if (inet_pton(AF_INET, "192.171.191.6", &servaddr.sin_addr) <= 0)
2607  return 0;
2608  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2609 
2610  memset(&servaddr, 0, sizeof(servaddr));
2611  if (inet_pton(AF_INET, "192.171.224.6", &servaddr.sin_addr) <= 0)
2612  return 0;
2613  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2614 
2615  memset(&servaddr, 0, sizeof(servaddr));
2616  if (inet_pton(AF_INET, "192.174.224.6", &servaddr.sin_addr) <= 0)
2617  return 0;
2618  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2619 
2620  memset(&servaddr, 0, sizeof(servaddr));
2621  if (inet_pton(AF_INET, "192.175.224.6", &servaddr.sin_addr) <= 0)
2622  return 0;
2623  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2624 
2626 
2627  return result;
2628 }
2629 
2630 static int SCRadixTestIPV4NetblockInsertion10(void)
2631 {
2632  SCRadixTree *tree = NULL;
2633  SCRadixNode *node[2];
2634  struct sockaddr_in servaddr;
2635 
2636  tree = SCRadixCreateRadixTree(free, NULL);
2637 
2638  /* add the keys */
2639  memset(&servaddr, 0, sizeof(servaddr));
2640  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2641  return 0;
2642  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2643 
2644  memset(&servaddr, 0, sizeof(servaddr));
2645  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2646  return 0;
2647  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2648 
2649  memset(&servaddr, 0, sizeof(servaddr));
2650  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2651  return 0;
2652  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2653 
2654  memset(&servaddr, 0, sizeof(servaddr));
2655  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2656  return 0;
2657  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2658 
2659  memset(&servaddr, 0, sizeof(servaddr));
2660  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2661  return 0;
2662  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2663 
2664  memset(&servaddr, 0, sizeof(servaddr));
2665  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2666  return 0;
2667  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2668 
2669  memset(&servaddr, 0, sizeof(servaddr));
2670  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2671  return 0;
2672  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2673 
2674  memset(&servaddr, 0, sizeof(servaddr));
2675  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2676  return 0;
2677  node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2678 
2679  memset(&servaddr, 0, sizeof(servaddr));
2680  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2681  return 0;
2682  node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2683 
2684  memset(&servaddr, 0, sizeof(servaddr));
2685  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2686  return 0;
2687  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2688 
2689  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2690  return 0;
2691  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2692 
2693  SCRadixPrintTree(tree);
2694 
2695  /* test for the existence of a key */
2696  memset(&servaddr, 0, sizeof(servaddr));
2697  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2698  return 0;
2699  SCRadixNode *found = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2700  FAIL_IF_NOT(found == node[0]);
2701 
2702  SCLogDebug("search \"exact\" match for 192.171.128.45");
2703  memset(&servaddr, 0, sizeof(servaddr));
2704  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2705  return 0;
2706  found = SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2707  FAIL_IF_NOT(found == node[1]);
2708 
2709  SCLogDebug("search \"best\" match for 192.171.128.45");
2710  memset(&servaddr, 0, sizeof(servaddr));
2711  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2712  return 0;
2713  found = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2714  FAIL_IF_NOT(found == node[1]);
2715 
2716  memset(&servaddr, 0, sizeof(servaddr));
2717  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2718  return 0;
2719  found = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2720  FAIL_IF_NOT(found == node[0]);
2721 
2722  /* let us remove a netblock */
2723  memset(&servaddr, 0, sizeof(servaddr));
2724  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2725  return 0;
2726  SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 24);
2727 
2728  memset(&servaddr, 0, sizeof(servaddr));
2729  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2730  return 0;
2731  found = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2732  FAIL_IF_NOT_NULL(found);
2733 
2734  memset(&servaddr, 0, sizeof(servaddr));
2735  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2736  return 0;
2737  found = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL);
2738  FAIL_IF_NOT_NULL(found);
2739 
2741  PASS;
2742 }
2743 
2744 static int SCRadixTestIPV4NetblockInsertion11(void)
2745 {
2746  SCRadixTree *tree = NULL;
2747  SCRadixNode *node = NULL;
2748  struct sockaddr_in servaddr;
2749  int result = 1;
2750 
2751  tree = SCRadixCreateRadixTree(free, NULL);
2752 
2753  /* add the keys */
2754  memset(&servaddr, 0, sizeof(servaddr));
2755  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2756  return 0;
2757  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2758 
2759  memset(&servaddr, 0, sizeof(servaddr));
2760  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2761  return 0;
2762  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2763 
2764  memset(&servaddr, 0, sizeof(servaddr));
2765  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2766  return 0;
2767  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2768 
2769  memset(&servaddr, 0, sizeof(servaddr));
2770  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2771  return 0;
2772  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2773 
2774  memset(&servaddr, 0, sizeof(servaddr));
2775  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2776  return 0;
2777  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2778 
2779  memset(&servaddr, 0, sizeof(servaddr));
2780  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2781  return 0;
2782  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2783 
2784  memset(&servaddr, 0, sizeof(servaddr));
2785  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2786  return 0;
2787  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2788 
2789  memset(&servaddr, 0, sizeof(servaddr));
2790  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2791  return 0;
2792  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2793 
2794  memset(&servaddr, 0, sizeof(servaddr));
2795  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2796  return 0;
2797  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2798 
2799  memset(&servaddr, 0, sizeof(servaddr));
2800  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2801  return 0;
2802  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2803 
2804  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2805  return 0;
2806  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2807 
2808  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2809  return 0;
2810  node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 0);
2811 
2812  /* test for the existence of a key */
2813  memset(&servaddr, 0, sizeof(servaddr));
2814  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2815  return 0;
2816  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2817 
2818  memset(&servaddr, 0, sizeof(servaddr));
2819  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2820  return 0;
2821  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2822 
2823  memset(&servaddr, 0, sizeof(servaddr));
2824  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2825  return 0;
2826  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2827 
2828  memset(&servaddr, 0, sizeof(servaddr));
2829  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2830  return 0;
2831  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2832 
2833  memset(&servaddr, 0, sizeof(servaddr));
2834  if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0)
2835  return 0;
2836  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2837 
2838  memset(&servaddr, 0, sizeof(servaddr));
2839  if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0)
2840  return 0;
2841  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2842 
2843  memset(&servaddr, 0, sizeof(servaddr));
2844  if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0)
2845  return 0;
2846  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2847 
2848  memset(&servaddr, 0, sizeof(servaddr));
2849  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2850  return 0;
2851  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2852 
2853  memset(&servaddr, 0, sizeof(servaddr));
2854  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2855  return 0;
2856  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2857  SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != node);
2858 
2859  memset(&servaddr, 0, sizeof(servaddr));
2860  if (inet_pton(AF_INET, "245.63.62.121", &servaddr.sin_addr) <= 0)
2861  return 0;
2862  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2863  SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2864 
2865  memset(&servaddr, 0, sizeof(servaddr));
2866  if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0)
2867  return 0;
2868  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2869  SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2870 
2871  /* remove node 0.0.0.0 */
2872  memset(&servaddr, 0, sizeof(servaddr));
2873  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2874  return 0;
2875  SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 0);
2876 
2877  memset(&servaddr, 0, sizeof(servaddr));
2878  if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0)
2879  return 0;
2880  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2881 
2882  memset(&servaddr, 0, sizeof(servaddr));
2883  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2884  return 0;
2885  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2886 
2887  memset(&servaddr, 0, sizeof(servaddr));
2888  if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0)
2889  return 0;
2890  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2891 
2892  memset(&servaddr, 0, sizeof(servaddr));
2893  if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0)
2894  return 0;
2895  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2896 
2897  memset(&servaddr, 0, sizeof(servaddr));
2898  if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0)
2899  return 0;
2900  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2901 
2902  memset(&servaddr, 0, sizeof(servaddr));
2903  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2904  return 0;
2905  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2906 
2908 
2909  return result;
2910 }
2911 
2912 static int SCRadixTestIPV4NetblockInsertion12(void)
2913 {
2914  SCRadixTree *tree = NULL;
2915  SCRadixNode *node[2];
2916  struct sockaddr_in servaddr;
2917  int result = 1;
2918 
2919  tree = SCRadixCreateRadixTree(free, NULL);
2920 
2921  /* add the keys */
2922  memset(&servaddr, 0, sizeof(servaddr));
2923  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2924  return 0;
2925  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2926 
2927  memset(&servaddr, 0, sizeof(servaddr));
2928  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2929  return 0;
2930  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2931 
2932  memset(&servaddr, 0, sizeof(servaddr));
2933  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2934  return 0;
2935  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2936 
2937  memset(&servaddr, 0, sizeof(servaddr));
2938  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2939  return 0;
2940  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2941 
2942  memset(&servaddr, 0, sizeof(servaddr));
2943  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2944  return 0;
2945  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2946 
2947  memset(&servaddr, 0, sizeof(servaddr));
2948  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2949  return 0;
2950  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2951 
2952  memset(&servaddr, 0, sizeof(servaddr));
2953  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2954  return 0;
2955  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2956 
2957  memset(&servaddr, 0, sizeof(servaddr));
2958  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2959  return 0;
2960  node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2961 
2962  memset(&servaddr, 0, sizeof(servaddr));
2963  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2964  return 0;
2965  node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2966 
2967  memset(&servaddr, 0, sizeof(servaddr));
2968  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2969  return 0;
2970  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2971 
2972  if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0)
2973  return 0;
2974  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 32);
2975 
2976  /* test for the existence of a key */
2977  memset(&servaddr, 0, sizeof(servaddr));
2978  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2979  return 0;
2980  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
2981 
2982  memset(&servaddr, 0, sizeof(servaddr));
2983  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2984  return 0;
2985  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2986 
2987  memset(&servaddr, 0, sizeof(servaddr));
2988  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2989  return 0;
2990  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2991 
2992  memset(&servaddr, 0, sizeof(servaddr));
2993  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2994  return 0;
2995  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2996 
2997  memset(&servaddr, 0, sizeof(servaddr));
2998  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2999  return 0;
3000  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
3001 
3002  memset(&servaddr, 0, sizeof(servaddr));
3003  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
3004  return 0;
3005  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
3006 
3007  memset(&servaddr, 0, sizeof(servaddr));
3008  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
3009  return 0;
3010  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
3011 
3012  memset(&servaddr, 0, sizeof(servaddr));
3013  if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0)
3014  return 0;
3015  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
3016 
3017  memset(&servaddr, 0, sizeof(servaddr));
3018  if (inet_pton(AF_INET, "225.175.21.224", &servaddr.sin_addr) <= 0)
3019  return 0;
3020  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
3021 
3022  memset(&servaddr, 0, sizeof(servaddr));
3023  if (inet_pton(AF_INET, "225.175.21.229", &servaddr.sin_addr) <= 0)
3024  return 0;
3025  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
3026 
3027  memset(&servaddr, 0, sizeof(servaddr));
3028  if (inet_pton(AF_INET, "225.175.21.230", &servaddr.sin_addr) <= 0)
3029  return 0;
3030  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
3031 
3033 
3034  return result;
3035 }
3036 
3037 static int SCRadixTestIPV6NetblockInsertion13(void)
3038 {
3039  SCRadixTree *tree = NULL;
3040  struct sockaddr_in6 servaddr;
3041  int result = 1;
3042 
3043  tree = SCRadixCreateRadixTree(free, NULL);
3044 
3045  /* add the keys */
3046  memset(&servaddr, 0, sizeof(servaddr));
3047  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
3048  &servaddr.sin6_addr) <= 0)
3049  return 0;
3050  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3051 
3052  memset(&servaddr, 0, sizeof(servaddr));
3053  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
3054  &servaddr.sin6_addr) <= 0)
3055  return 0;
3056  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3057 
3058  memset(&servaddr, 0, sizeof(servaddr));
3059  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
3060  &servaddr.sin6_addr) <= 0)
3061  return 0;
3062  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3063 
3064  memset(&servaddr, 0, sizeof(servaddr));
3065  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
3066  &servaddr.sin6_addr) <= 0)
3067  return 0;
3068  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3069 
3070  memset(&servaddr, 0, sizeof(servaddr));
3071  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
3072  &servaddr.sin6_addr) <= 0)
3073  return 0;
3074  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3075 
3076  memset(&servaddr, 0, sizeof(servaddr));
3077  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000",
3078  &servaddr.sin6_addr) <= 0)
3079  return 0;
3080  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56);
3081 
3082  memset(&servaddr, 0, sizeof(servaddr));
3083  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
3084  &servaddr.sin6_addr) <= 0)
3085  return 0;
3086  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3087 
3088  /* test the existence of keys */
3089  memset(&servaddr, 0, sizeof(servaddr));
3090  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
3091  &servaddr.sin6_addr) <= 0)
3092  return 0;
3093  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3094 
3095  memset(&servaddr, 0, sizeof(servaddr));
3096  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
3097  &servaddr.sin6_addr) <= 0)
3098  return 0;
3099  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3100 
3101  memset(&servaddr, 0, sizeof(servaddr));
3102  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
3103  &servaddr.sin6_addr) <= 0)
3104  return 0;
3105  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3106 
3107  memset(&servaddr, 0, sizeof(servaddr));
3108  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
3109  &servaddr.sin6_addr) <= 0)
3110  return 0;
3111  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3112 
3113  memset(&servaddr, 0, sizeof(servaddr));
3114  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
3115  &servaddr.sin6_addr) <= 0)
3116  return 0;
3117  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3118 
3119  memset(&servaddr, 0, sizeof(servaddr));
3120  if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212",
3121  &servaddr.sin6_addr) <= 0)
3122  return 0;
3123  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
3124 
3125  memset(&servaddr, 0, sizeof(servaddr));
3126  if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315",
3127  &servaddr.sin6_addr) <= 0)
3128  return 0;
3129  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
3130 
3131  memset(&servaddr, 0, sizeof(servaddr));
3132  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
3133  &servaddr.sin6_addr) <= 0)
3134  return 0;
3135  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3136 
3137  memset(&servaddr, 0, sizeof(servaddr));
3138  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
3139  &servaddr.sin6_addr) <= 0)
3140  return 0;
3141  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3142 
3143  memset(&servaddr, 0, sizeof(servaddr));
3144  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1146:6241",
3145  &servaddr.sin6_addr) <= 0)
3146  return 0;
3147  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3148 
3149  memset(&servaddr, 0, sizeof(servaddr));
3150  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1356:1241",
3151  &servaddr.sin6_addr) <= 0)
3152  return 0;
3153  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
3154 
3155  memset(&servaddr, 0, sizeof(servaddr));
3156  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DAAA:1245:2342:1146:6241",
3157  &servaddr.sin6_addr) <= 0)
3158  return 0;
3159  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
3160 
3161 
3163 
3164  return result;
3165 }
3166 
3167 static int SCRadixTestIPV6NetblockInsertion14(void)
3168 {
3169  SCRadixTree *tree = NULL;
3170  SCRadixNode *node = NULL;
3171  struct sockaddr_in6 servaddr;
3172  int result = 1;
3173 
3174  tree = SCRadixCreateRadixTree(free, NULL);
3175 
3176  /* add the keys */
3177  memset(&servaddr, 0, sizeof(servaddr));
3178  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
3179  &servaddr.sin6_addr) <= 0)
3180  return 0;
3181  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3182 
3183  memset(&servaddr, 0, sizeof(servaddr));
3184  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
3185  &servaddr.sin6_addr) <= 0)
3186  return 0;
3187  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3188 
3189  memset(&servaddr, 0, sizeof(servaddr));
3190  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
3191  &servaddr.sin6_addr) <= 0)
3192  return 0;
3193  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3194 
3195  memset(&servaddr, 0, sizeof(servaddr));
3196  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
3197  &servaddr.sin6_addr) <= 0)
3198  return 0;
3199  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3200 
3201  memset(&servaddr, 0, sizeof(servaddr));
3202  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
3203  &servaddr.sin6_addr) <= 0)
3204  return 0;
3205  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3206 
3207  memset(&servaddr, 0, sizeof(servaddr));
3208  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000",
3209  &servaddr.sin6_addr) <= 0)
3210  return 0;
3211  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56);
3212 
3213  memset(&servaddr, 0, sizeof(servaddr));
3214  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
3215  &servaddr.sin6_addr) <= 0)
3216  return 0;
3217  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
3218 
3219  memset(&servaddr, 0, sizeof(servaddr));
3220  if (inet_pton(AF_INET6, "::", &servaddr.sin6_addr) <= 0)
3221  return 0;
3222  node = SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL,
3223  0);
3224 
3225  /* test the existence of keys */
3226  memset(&servaddr, 0, sizeof(servaddr));
3227  if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315",
3228  &servaddr.sin6_addr) <= 0)
3229  return 0;
3230  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
3231 
3232  memset(&servaddr, 0, sizeof(servaddr));
3233  if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315",
3234  &servaddr.sin6_addr) <= 0)
3235  return 0;
3236  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
3237 
3238  memset(&servaddr, 0, sizeof(servaddr));
3239  if (inet_pton(AF_INET6, "2004:0BF1:5346:B116:2362:8713:9124:2315",
3240  &servaddr.sin6_addr) <= 0)
3241  return 0;
3242  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
3243 
3244  memset(&servaddr, 0, sizeof(servaddr));
3245  if (inet_pton(AF_INET6, "2004:0B23:3252:BDEA:7422:8713:9124:2341",
3246  &servaddr.sin6_addr) <= 0)
3247  return 0;
3248  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
3249 
3250  memset(&servaddr, 0, sizeof(servaddr));
3251  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
3252  &servaddr.sin6_addr) <= 0)
3253  return 0;
3254  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL &&
3255  SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node);
3256 
3257  memset(&servaddr, 0, sizeof(servaddr));
3258  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
3259  &servaddr.sin6_addr) <= 0)
3260  return 0;
3261  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL &&
3262  SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node);
3263 
3265 
3266  return result;
3267 }
3268 
3269 /**
3270  * \test Check that the best match search works for all the
3271  * possible netblocks of a fixed address
3272  */
3273 static int SCRadixTestIPV4NetBlocksAndBestSearch15(void)
3274 {
3275 
3276  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3277  FAIL_IF_NULL(tree);
3278 
3279  struct sockaddr_in servaddr;
3280  memset(&servaddr, 0, sizeof(servaddr));
3281  FAIL_IF(inet_pton(AF_INET, "192.168.0.1", &servaddr.sin_addr) <= 0);
3282 
3283  for (uint32_t i = 0; i <= 32; i++) {
3284  uint32_t *user = SCMalloc(sizeof(uint32_t));
3285  FAIL_IF_NULL(user);
3286  *user = i;
3287 
3288  char str[32];
3289  snprintf(str, sizeof(str), "192.168.0.1/%u", i);
3290  SCRadixAddKeyIPV4String(str, tree, user);
3291 
3292  void *user_data = NULL;
3293  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3294  FAIL_IF_NULL(node);
3295  FAIL_IF_NULL(user_data);
3296  FAIL_IF(*((uint32_t *)user_data) != i);
3297  }
3298 
3300  PASS;
3301 }
3302 
3303 /**
3304  * \test Check that the best match search works for all the
3305  * possible netblocks of a fixed address
3306  */
3307 static int SCRadixTestIPV4NetBlocksAndBestSearch16(void)
3308 {
3309 
3310  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3311  FAIL_IF_NULL(tree);
3312 
3313  struct sockaddr_in servaddr;
3314  memset(&servaddr, 0, sizeof(servaddr));
3315  FAIL_IF(inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0);
3316 
3317  for (uint32_t i = 0; i <= 32; i++) {
3318  uint32_t *user = SCMalloc(sizeof(uint32_t));
3319  FAIL_IF_NULL(user);
3320  *user = i;
3321 
3322  char str[32];
3323  snprintf(str, sizeof(str), "192.168.1.1/%u", i);
3324  SCRadixAddKeyIPV4String(str, tree, user);
3325 
3326  void *user_data = NULL;
3327  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3328  FAIL_IF_NULL(node);
3329  FAIL_IF_NULL(user_data);
3330  FAIL_IF(*((uint32_t *)user_data) != i);
3331  }
3332 
3334  PASS;
3335 }
3336 
3337 /**
3338  * \test Check that the best match search works for all the
3339  * possible netblocks of a fixed address
3340  */
3341 static int SCRadixTestIPV4NetBlocksAndBestSearch17(void)
3342 {
3343  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3344  FAIL_IF_NULL(tree);
3345 
3346  struct sockaddr_in servaddr;
3347  memset(&servaddr, 0, sizeof(servaddr));
3348  FAIL_IF(inet_pton(AF_INET, "10.0.0.1", &servaddr.sin_addr) <= 0);
3349 
3350  for (uint32_t i = 0; i <= 32; i++) {
3351  uint32_t *user = SCMalloc(sizeof(uint32_t));
3352  FAIL_IF_NULL(user);
3353  *user = i;
3354 
3355  char str[32];
3356  snprintf(str, sizeof(str), "10.0.0.1/%u", i);
3357  SCRadixAddKeyIPV4String(str, tree, user);
3358 
3359  void *user_data = NULL;
3360  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3361  FAIL_IF_NULL(node);
3362  FAIL_IF_NULL(user_data);
3363  FAIL_IF(*((uint32_t *)user_data) != i);
3364  }
3365 
3367  PASS;
3368 }
3369 
3370 /**
3371  * \test Check that the best match search works for all the
3372  * possible netblocks of a fixed address
3373  */
3374 static int SCRadixTestIPV4NetBlocksAndBestSearch18(void)
3375 {
3376  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3377  FAIL_IF_NULL(tree);
3378 
3379  struct sockaddr_in servaddr;
3380  memset(&servaddr, 0, sizeof(servaddr));
3381  FAIL_IF(inet_pton(AF_INET, "172.26.0.1", &servaddr.sin_addr) <= 0);
3382 
3383  for (uint32_t i = 0; i <= 32; i++) {
3384  uint32_t *user = SCMalloc(sizeof(uint32_t));
3385  FAIL_IF_NULL(user);
3386  *user = i;
3387 
3388  char str[32];
3389  snprintf(str, sizeof(str), "172.26.0.1/%u", i);
3390  SCRadixAddKeyIPV4String(str, tree, user);
3391 
3392  void *user_data = NULL;
3393  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3394  FAIL_IF_NULL(node);
3395  FAIL_IF_NULL(user_data);
3396  FAIL_IF(*((uint32_t *)user_data) != i);
3397  }
3398 
3400  PASS;
3401 }
3402 
3403 /**
3404  * \test Check special combinations of netblocks and addresses
3405  * on best search checking the returned userdata
3406  */
3407 static int SCRadixTestIPV4NetBlocksAndBestSearch19(void)
3408 {
3409  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3410  FAIL_IF_NULL(tree);
3411 
3412  struct sockaddr_in servaddr;
3413  memset(&servaddr, 0, sizeof(servaddr));
3414  FAIL_IF(inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0);
3415 
3416  uint32_t *user = SCMalloc(sizeof(uint32_t));
3417  FAIL_IF_NULL(user);
3418  *user = 100;
3419 
3420  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 0);
3421 
3422  memset(&servaddr, 0, sizeof(servaddr));
3423  FAIL_IF(inet_pton(AF_INET, "192.168.1.15", &servaddr.sin_addr) <= 0);
3424  void *user_data = NULL;
3425  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3426  FAIL_IF_NULL(node);
3427  FAIL_IF_NULL(user_data);
3428  FAIL_IF(*((uint32_t *)user_data) != 100);
3429 
3430  user_data = NULL;
3431  memset(&servaddr, 0, sizeof(servaddr));
3432  FAIL_IF(inet_pton(AF_INET, "177.0.0.0", &servaddr.sin_addr) <= 0);
3433  user = SCMalloc(sizeof(uint32_t));
3434  FAIL_IF_NULL(user);
3435  *user = 200;
3436 
3437  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 8);
3438 
3439  memset(&servaddr, 0, sizeof(servaddr));
3440  FAIL_IF(inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0);
3441 
3442  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3443  FAIL_IF_NULL(node);
3444  FAIL_IF_NULL(user_data);
3445  FAIL_IF(*((uint32_t *)user_data) != 200);
3446 
3447  user_data = NULL;
3448  memset(&servaddr, 0, sizeof(servaddr));
3449  FAIL_IF(inet_pton(AF_INET, "178.168.1.15", &servaddr.sin_addr) <= 0);
3450 
3451  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3452  FAIL_IF_NULL(node);
3453  FAIL_IF_NULL(user_data);
3454  FAIL_IF(*((uint32_t *)user_data) != 100);
3455 
3456  user_data = NULL;
3457  memset(&servaddr, 0, sizeof(servaddr));
3458  FAIL_IF(inet_pton(AF_INET, "177.160.0.0", &servaddr.sin_addr) <= 0);
3459  user = SCMalloc(sizeof(uint32_t));
3460  FAIL_IF_NULL(user);
3461  *user = 300;
3462 
3463  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 12);
3464 
3465  memset(&servaddr, 0, sizeof(servaddr));
3466  FAIL_IF(inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0);
3467 
3468  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3469  FAIL_IF_NULL(node);
3470  FAIL_IF_NULL(user_data);
3471  FAIL_IF(*((uint32_t *)user_data) != 300);
3472 
3473  user_data = NULL;
3474  memset(&servaddr, 0, sizeof(servaddr));
3475  FAIL_IF(inet_pton(AF_INET, "177.167.1.15", &servaddr.sin_addr) <= 0);
3476 
3477  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3478  FAIL_IF_NULL(node);
3479  FAIL_IF_NULL(user_data);
3480  FAIL_IF(*((uint32_t *)user_data) != 300);
3481 
3482  user_data = NULL;
3483  memset(&servaddr, 0, sizeof(servaddr));
3484  FAIL_IF(inet_pton(AF_INET, "177.178.1.15", &servaddr.sin_addr) <= 0);
3485 
3486  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3487  FAIL_IF_NULL(node);
3488  FAIL_IF_NULL(user_data);
3489  FAIL_IF(*((uint32_t *)user_data) != 200);
3490 
3491  user_data = NULL;
3492  memset(&servaddr, 0, sizeof(servaddr));
3493  FAIL_IF(inet_pton(AF_INET, "197.178.1.15", &servaddr.sin_addr) <= 0);
3494 
3495  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3496  FAIL_IF_NULL(node);
3497  FAIL_IF_NULL(user_data);
3498  FAIL_IF(*((uint32_t *)user_data) != 100);
3499 
3501  PASS;
3502 }
3503 
3504 /**
3505  * \test Check that the best match search works for all the
3506  * possible netblocks of a fixed address
3507  */
3508 static int SCRadixTestIPV6NetBlocksAndBestSearch20(void)
3509 {
3510  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3511  FAIL_IF_NULL(tree);
3512 
3513  struct sockaddr_in6 servaddr;
3514  memset(&servaddr, 0, sizeof(servaddr));
3515  FAIL_IF(inet_pton(AF_INET6, "ABAB:CDCD:ABAB:CDCD:1234:4321:1234:4321", &servaddr.sin6_addr) <=
3516  0);
3517 
3518  for (uint32_t i = 0; i <= 128; i++) {
3519  uint32_t *user = SCMalloc(sizeof(uint32_t));
3520  FAIL_IF_NULL(user);
3521  *user = i;
3522 
3523  char str[64];
3524  snprintf(str, sizeof(str), "ABAB:CDCD:ABAB:CDCD:1234:4321:1234:4321/%u", i);
3525  SCRadixAddKeyIPV6String(str, tree, user);
3526 
3527  void *user_data = NULL;
3528  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3529  FAIL_IF_NULL(node);
3530  FAIL_IF_NULL(user_data);
3531  FAIL_IF(*((uint32_t *)user_data) != i);
3532  }
3533 
3535  PASS;
3536 }
3537 
3538 /**
3539  * \test Check that the best match search works for all the
3540  * possible netblocks of a fixed address
3541  */
3542 static int SCRadixTestIPV6NetBlocksAndBestSearch21(void)
3543 {
3544  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3545  FAIL_IF_NULL(tree);
3546 
3547  struct sockaddr_in6 servaddr;
3548  memset(&servaddr, 0, sizeof(servaddr));
3549  FAIL_IF(inet_pton(AF_INET6, "ff00::1", &servaddr.sin6_addr) <= 0);
3550 
3551  for (uint32_t i = 0; i <= 128; i++) {
3552  uint32_t *user = SCMalloc(sizeof(uint32_t));
3553  FAIL_IF_NULL(user);
3554  *user = i;
3555 
3556  char str[64];
3557  snprintf(str, sizeof(str), "ff00::1/%u", i);
3558  SCRadixAddKeyIPV6String(str, tree, user);
3559 
3560  void *user_data = NULL;
3561  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3562  FAIL_IF_NULL(node);
3563  FAIL_IF_NULL(user_data);
3564  FAIL_IF(*((uint32_t *)user_data) != i);
3565  }
3566 
3568  PASS;
3569 }
3570 
3571 /**
3572  * \test Check that the best match search works for all the
3573  * possible netblocks of a fixed address
3574  */
3575 static int SCRadixTestIPV6NetBlocksAndBestSearch22(void)
3576 {
3577  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3578  FAIL_IF_NULL(tree);
3579 
3580  struct sockaddr_in6 servaddr;
3581  memset(&servaddr, 0, sizeof(servaddr));
3582  FAIL_IF(inet_pton(AF_INET6, "ff00::192:168:1:1", &servaddr.sin6_addr) <= 0);
3583 
3584  for (uint32_t i = 0; i <= 128; i++) {
3585  uint32_t *user = SCMalloc(sizeof(uint32_t));
3586  FAIL_IF_NULL(user);
3587  *user = i;
3588 
3589  char str[64];
3590  snprintf(str, sizeof(str), "ff00::192:168:1:1/%u", i);
3591  SCRadixAddKeyIPV6String(str, tree, user);
3592 
3593  void *user_data = NULL;
3594  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3595  FAIL_IF_NULL(node);
3596  FAIL_IF_NULL(user_data);
3597  FAIL_IF(*((uint32_t *)user_data) != i);
3598  }
3599 
3601  PASS;
3602 }
3603 
3604 /**
3605  * \test Check that the best match search works for all the
3606  * possible netblocks of a fixed address
3607  */
3608 static int SCRadixTestIPV6NetBlocksAndBestSearch23(void)
3609 {
3610  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3611  FAIL_IF_NULL(tree);
3612 
3613  struct sockaddr_in6 servaddr;
3614  memset(&servaddr, 0, sizeof(servaddr));
3615  FAIL_IF(inet_pton(AF_INET6, "FF00:ABCD:BCDA::ABCD", &servaddr.sin6_addr) <= 0);
3616 
3617  for (uint32_t i = 0; i <= 128; i++) {
3618  uint32_t *user = SCMalloc(sizeof(uint32_t));
3619  FAIL_IF_NULL(user);
3620  *user = i;
3621 
3622  char str[64];
3623  snprintf(str, sizeof(str), "FF00:ABCD:BCDA::ABCD/%u", i);
3624  SCRadixAddKeyIPV6String(str, tree, user);
3625 
3626  void *user_data = NULL;
3627  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3628  FAIL_IF_NULL(node);
3629  FAIL_IF_NULL(user_data);
3630  FAIL_IF(*((uint32_t *)user_data) != i);
3631  }
3632 
3634  PASS;
3635 }
3636 
3637 /**
3638  * \test Check special combinations of netblocks and addresses
3639  * on best search checking the returned userdata
3640  */
3641 static int SCRadixTestIPV6NetBlocksAndBestSearch24(void)
3642 {
3643  struct sockaddr_in6 servaddr;
3644  void *user_data = NULL;
3645 
3646  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3647  FAIL_IF_NULL(tree);
3648 
3649  uint32_t *user = SCMalloc(sizeof(uint32_t));
3650  FAIL_IF_NULL(user);
3651  *user = 100;
3652  SCRadixAddKeyIPV6String("::/0", tree, user);
3653 
3654  memset(&servaddr, 0, sizeof(servaddr));
3655  FAIL_IF(inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0);
3656  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3657  FAIL_IF_NULL(node);
3658  FAIL_IF_NULL(user_data);
3659  FAIL_IF(*((uint32_t *)user_data) != 100);
3660 
3661  user_data = NULL;
3662  user = SCMalloc(sizeof(uint32_t));
3663  FAIL_IF_NULL(user);
3664  *user = 200;
3665  SCRadixAddKeyIPV6String("ABCD::0/8", tree, user);
3666 
3667  memset(&servaddr, 0, sizeof(servaddr));
3668  FAIL_IF(inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0);
3669  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3670  FAIL_IF_NULL(node);
3671  FAIL_IF_NULL(user_data);
3672  FAIL_IF(*((uint32_t *)user_data) != 200);
3673 
3674  user_data = NULL;
3675  memset(&servaddr, 0, sizeof(servaddr));
3676  FAIL_IF(inet_pton(AF_INET6, "DCBA::1", &servaddr.sin6_addr) <= 0);
3677 
3678  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3679  FAIL_IF_NULL(node);
3680  FAIL_IF_NULL(user_data);
3681  FAIL_IF(*((uint32_t *)user_data) != 100);
3682 
3683  user_data = NULL;
3684  user = SCMalloc(sizeof(uint32_t));
3685  FAIL_IF_NULL(user);
3686  *user = 300;
3687  SCRadixAddKeyIPV6String("ABCD:ABCD::0/12", tree, user);
3688 
3689  memset(&servaddr, 0, sizeof(servaddr));
3690  FAIL_IF(inet_pton(AF_INET6, "ABCD:ABCD::1", &servaddr.sin6_addr) <= 0);
3691  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3692  FAIL_IF_NULL(node);
3693  FAIL_IF_NULL(user_data);
3694  FAIL_IF(*((uint32_t *)user_data) != 300);
3695 
3696  user_data = NULL;
3697  memset(&servaddr, 0, sizeof(servaddr));
3698  FAIL_IF(inet_pton(AF_INET6, "ABCD:AAAA::1", &servaddr.sin6_addr) <= 0);
3699  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3700  FAIL_IF_NULL(node);
3701  FAIL_IF_NULL(user_data);
3702  FAIL_IF(*((uint32_t *)user_data) != 300);
3703 
3704  user_data = NULL;
3705  memset(&servaddr, 0, sizeof(servaddr));
3706  FAIL_IF(inet_pton(AF_INET6, "ABAB::1", &servaddr.sin6_addr) <= 0);
3707  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3708  FAIL_IF_NULL(node);
3709  FAIL_IF_NULL(user_data);
3710  FAIL_IF(*((uint32_t *)user_data) != 200);
3711 
3712  user_data = NULL;
3713  memset(&servaddr, 0, sizeof(servaddr));
3714  FAIL_IF(inet_pton(AF_INET6, "CABD::1", &servaddr.sin6_addr) <= 0);
3715  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3716  FAIL_IF_NULL(node);
3717  FAIL_IF_NULL(user_data);
3718  FAIL_IF(*((uint32_t *)user_data) != 100);
3719 
3721  PASS;
3722 }
3723 
3724 /**
3725  * \test SCRadixTestIPV4NetblockInsertion15 insert a node searching on it.
3726  * Should always return true but the purpose of the test is to monitor
3727  * the memory usage to detect memleaks (there was one on searching)
3728  */
3729 static int SCRadixTestIPV4NetblockInsertion25(void)
3730 {
3731  SCRadixTree *tree = NULL;
3732  struct sockaddr_in servaddr;
3733  int result = 1;
3734 
3735  tree = SCRadixCreateRadixTree(free, NULL);
3736 
3737  memset(&servaddr, 0, sizeof(servaddr));
3738  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
3739  return 0;
3740  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
3741 
3742  /* test for the existence of a key */
3743  memset(&servaddr, 0, sizeof(servaddr));
3744  if (inet_pton(AF_INET, "192.168.128.53", &servaddr.sin_addr) <= 0)
3745  return 0;
3746 
3747  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
3748 
3750 
3751  return result;
3752 }
3753 
3754 /**
3755  * \test SCRadixTestIPV4NetblockInsertion26 insert a node searching on it.
3756  * Should always return true but the purpose of the test is to monitor
3757  * the memory usage to detect memleaks (there was one on searching)
3758  */
3759 static int SCRadixTestIPV4NetblockInsertion26(void)
3760 {
3761  struct sockaddr_in servaddr;
3762 
3763  SCRadixTree *tree = SCRadixCreateRadixTree(free, NULL);
3764  FAIL_IF_NULL(tree);
3765 
3766  memset(&servaddr, 0, sizeof(servaddr));
3767  FAIL_IF(inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0);
3768 
3769  char *str = SCStrdup("Hello1");
3770  FAIL_IF_NULL(str);
3771  SCRadixNode *node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 0);
3772  FAIL_IF_NULL(node);
3773 
3774  str = SCStrdup("Hello1");
3775  FAIL_IF_NULL(str);
3776 
3777  memset(&servaddr, 0, sizeof(servaddr));
3778  FAIL_IF(inet_pton(AF_INET, "176.0.0.0", &servaddr.sin_addr) <= 0);
3779 
3780  node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 5);
3781  FAIL_IF_NULL(node);
3782 
3783  str = SCStrdup("Hello1");
3784  FAIL_IF_NULL(str);
3785 
3786  memset(&servaddr, 0, sizeof(servaddr));
3787  FAIL_IF(inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0);
3788 
3789  node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 7);
3790  FAIL_IF_NULL(node);
3791 
3792  /* test for the existence of a key */
3793  // result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree) != NULL);
3794 
3796 
3797  PASS;
3798 }
3799 
3800 #endif
3801 
3803 {
3804 
3805 #ifdef UNITTESTS
3806  UtRegisterTest("SCRadixTestIPV4Insertion03", SCRadixTestIPV4Insertion03);
3807  UtRegisterTest("SCRadixTestIPV4Removal04", SCRadixTestIPV4Removal04);
3808  UtRegisterTest("SCRadixTestIPV6Insertion07", SCRadixTestIPV6Insertion07);
3809  UtRegisterTest("SCRadixTestIPV6Removal08", SCRadixTestIPV6Removal08);
3810  UtRegisterTest("SCRadixTestIPV4NetblockInsertion09",
3811  SCRadixTestIPV4NetblockInsertion09);
3812  UtRegisterTest("SCRadixTestIPV4Bug5066", SCRadixTestIPV4Bug5066);
3813  UtRegisterTest("SCRadixTestIPV4Bug5066v2", SCRadixTestIPV4Bug5066v2);
3814  UtRegisterTest("SCRadixTestIPV6Bug5066", SCRadixTestIPV6Bug5066);
3815  UtRegisterTest("SCRadixTestIPV4NetblockInsertion10",
3816  SCRadixTestIPV4NetblockInsertion10);
3817  UtRegisterTest("SCRadixTestIPV4NetblockInsertion11",
3818  SCRadixTestIPV4NetblockInsertion11);
3819  UtRegisterTest("SCRadixTestIPV4NetblockInsertion12",
3820  SCRadixTestIPV4NetblockInsertion12);
3821  UtRegisterTest("SCRadixTestIPV6NetblockInsertion13",
3822  SCRadixTestIPV6NetblockInsertion13);
3823  UtRegisterTest("SCRadixTestIPV6NetblockInsertion14",
3824  SCRadixTestIPV6NetblockInsertion14);
3825  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch15",
3826  SCRadixTestIPV4NetBlocksAndBestSearch15);
3827  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch16",
3828  SCRadixTestIPV4NetBlocksAndBestSearch16);
3829  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch17",
3830  SCRadixTestIPV4NetBlocksAndBestSearch17);
3831  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch18",
3832  SCRadixTestIPV4NetBlocksAndBestSearch18);
3833  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch19",
3834  SCRadixTestIPV4NetBlocksAndBestSearch19);
3835  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch20",
3836  SCRadixTestIPV6NetBlocksAndBestSearch20);
3837  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch21",
3838  SCRadixTestIPV6NetBlocksAndBestSearch21);
3839  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch22",
3840  SCRadixTestIPV6NetBlocksAndBestSearch22);
3841  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch23",
3842  SCRadixTestIPV6NetBlocksAndBestSearch23);
3843  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch24",
3844  SCRadixTestIPV6NetBlocksAndBestSearch24);
3845  UtRegisterTest("SCRadixTestIPV4NetblockInsertion25",
3846  SCRadixTestIPV4NetblockInsertion25);
3847  UtRegisterTest("SCRadixTestIPV4NetblockInsertion26",
3848  SCRadixTestIPV4NetblockInsertion26);
3849 #endif
3850 
3851  return;
3852 }
SCRadixPrefix_::user_data
SCRadixUserData * user_data
Definition: util-radix-tree.h:55
util-byte.h
SCRadixRemoveKeyIPV4Netblock
void SCRadixRemoveKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask)
Removes an IPV4 address netblock key from the Radix tree.
Definition: util-radix-tree.c:1381
SCRadixRemoveKeyIPV6Netblock
void SCRadixRemoveKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask)
Removes an IPV6 netblock address key from the Radix tree.
Definition: util-radix-tree.c:1415
FAIL_IF_NULL
#define FAIL_IF_NULL(expr)
Fail a test if expression evaluates to NULL.
Definition: util-unittest.h:89
MaskIPNetblock
void MaskIPNetblock(uint8_t *stream, int netmask, int key_bitlen)
Culls the non-netmask portion of the IP address. For example an IP address 192.168....
Definition: util-ip.c:187
SCRadixAddKeyIPV6String
bool SCRadixAddKeyIPV6String(const char *str, SCRadixTree *tree, void *user)
Adds a new IPV6/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:1064
SCRadixFindKeyIPV6Netblock
SCRadixNode * SCRadixFindKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask, void **user_data_result)
Checks if an IPV6 Netblock address is present in the tree.
Definition: util-radix-tree.c:1620
SCRadixNode_::prefix
SCRadixPrefix * prefix
Definition: util-radix-tree.h:74
unlikely
#define unlikely(expr)
Definition: util-optimize.h:35
UtRegisterTest
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
Definition: util-unittest.c:103
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:269
SCRadixNode_::bit
uint16_t bit
Definition: util-radix-tree.h:64
SCRadixRemoveKeyIPV6
void SCRadixRemoveKeyIPV6(uint8_t *key_stream, SCRadixTree *tree)
Removes an IPV6 address key(not a netblock) from the Radix tree. Instead of using this function,...
Definition: util-radix-tree.c:1435
CIDRGet
uint32_t CIDRGet(int cidr)
Definition: util-cidr.c:57
SC_EINVAL
@ SC_EINVAL
Definition: util-error.h:30
SCRadixPrefix_
Structure for the prefix/key in the radix tree.
Definition: util-radix-tree.h:44
SCRadixTree_
Structure for the radix tree.
Definition: util-radix-tree.h:86
SCRadixAddKeyIPV6
SCRadixNode * SCRadixAddKeyIPV6(uint8_t *key_stream, SCRadixTree *tree, void *user)
Adds a new IPV6 address to the Radix tree.
Definition: util-radix-tree.c:877
SCRadixUserData_::next
struct SCRadixUserData_ * next
Definition: util-radix-tree.h:36
SCRadixFindKeyIPV4BestMatch
SCRadixNode * SCRadixFindKeyIPV4BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV4 address is present in the tree under a netblock.
Definition: util-radix-tree.c:1591
SCRadixPrefix_::stream
uint8_t * stream
Definition: util-radix-tree.h:49
SCRadixFindKeyIPV6BestMatch
SCRadixNode * SCRadixFindKeyIPV6BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV6 address is present in the tree under a netblock.
Definition: util-radix-tree.c:1649
SCRadixNode_::right
struct SCRadixNode_ * right
Definition: util-radix-tree.h:77
SCRadixAddKeyIPV4String
bool SCRadixAddKeyIPV4String(const char *str, SCRadixTree *tree, void *user)
Adds a new IPV4/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:989
util-unittest.h
FAIL_IF_NOT
#define FAIL_IF_NOT(expr)
Fail a test if expression evaluates to false.
Definition: util-unittest.h:82
SC_ENOMEM
@ SC_ENOMEM
Definition: util-error.h:29
SCRadixAddKeyIPV4Netblock
SCRadixNode * SCRadixAddKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, void *user, uint8_t netmask)
Adds a new IPV4 netblock to the Radix tree.
Definition: util-radix-tree.c:940
strlcpy
size_t strlcpy(char *dst, const char *src, size_t siz)
Definition: util-strlcpyu.c:43
util-memcmp.h
util-cidr.h
SCRadixRegisterTests
void SCRadixRegisterTests(void)
Definition: util-radix-tree.c:3802
FAIL_IF_NOT_NULL
#define FAIL_IF_NOT_NULL(expr)
Fail a test if expression evaluates to non-NULL.
Definition: util-unittest.h:96
util-debug.h
PASS
#define PASS
Pass the test.
Definition: util-unittest.h:105
util-error.h
SCRadixReleaseRadixTree
void SCRadixReleaseRadixTree(SCRadixTree *tree)
Frees a Radix tree and all its nodes.
Definition: util-radix-tree.c:454
SCRadixTree_::Free
void(* Free)(void *)
Definition: util-radix-tree.h:93
SCRadixUserData_
Structure that hold the user data and the netmask associated with it.
Definition: util-radix-tree.h:32
util-print.h
util-ip.h
PrintInet
const char * PrintInet(int af, const void *src, char *dst, socklen_t size)
Definition: util-print.c:262
SC_RADIX_BITTEST
#define SC_RADIX_BITTEST(x, y)
Definition: util-radix-tree.h:27
SCLogWarning
#define SCLogWarning(...)
Macro used to log WARNING messages.
Definition: util-debug.h:249
SCRadixCreateRadixTree
SCRadixTree * SCRadixCreateRadixTree(void(*Free)(void *), void(*PrintData)(void *))
Creates a new Radix tree.
Definition: util-radix-tree.c:417
SCRadixRemoveKeyIPV4
void SCRadixRemoveKeyIPV4(uint8_t *key_stream, SCRadixTree *tree)
Removes an IPV4 address key(not a netblock) from the Radix tree. Instead of using this function,...
Definition: util-radix-tree.c:1401
util-radix-tree.h
SC_OK
@ SC_OK
Definition: util-error.h:27
SCRadixFindKeyIPV6ExactMatch
SCRadixNode * SCRadixFindKeyIPV6ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV6 address is present in the tree.
Definition: util-radix-tree.c:1637
SCRadixUserData_::netmask
uint8_t netmask
Definition: util-radix-tree.h:38
StringParseU8RangeCheck
int StringParseU8RangeCheck(uint8_t *res, int base, size_t len, const char *str, uint8_t min, uint8_t max)
Definition: util-byte.c:462
SCRadixTree_::head
SCRadixNode * head
Definition: util-radix-tree.h:88
SCRealloc
#define SCRealloc(ptr, sz)
Definition: util-mem.h:50
SCRadixTree_::PrintData
void(* PrintData)(void *)
Definition: util-radix-tree.h:92
CIDRGetIPv6
void CIDRGetIPv6(int cidr, struct in6_addr *in6)
Creates a cidr ipv6 netblock, based on the cidr netblock value.
Definition: util-cidr.c:82
FAIL_IF
#define FAIL_IF(expr)
Fail a test if expression evaluates to true.
Definition: util-unittest.h:71
suricata-common.h
SCRadixFindKeyIPV4Netblock
SCRadixNode * SCRadixFindKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask, void **user_data_result)
Checks if an IPV4 Netblock address is present in the tree.
Definition: util-radix-tree.c:1603
SCRadixPrintTree
void SCRadixPrintTree(SCRadixTree *tree)
Prints the Radix Tree. While printing the radix tree we use the following format.
Definition: util-radix-tree.c:1741
SCRadixUserData_::user
void * user
Definition: util-radix-tree.h:34
SCRadixAddKeyIPV6Netblock
SCRadixNode * SCRadixAddKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, void *user, uint8_t netmask)
Adds a new IPV6 netblock to the Radix tree.
Definition: util-radix-tree.c:963
SCStrdup
#define SCStrdup(s)
Definition: util-mem.h:56
FatalError
#define FatalError(...)
Definition: util-debug.h:502
util-validate.h
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
SC_EEXIST
@ SC_EEXIST
Definition: util-error.h:32
str
#define str(s)
Definition: suricata-common.h:291
SCRadixNode_
Structure for the node in the radix tree.
Definition: util-radix-tree.h:61
SCLogError
#define SCLogError(...)
Macro used to log ERROR messages.
Definition: util-debug.h:261
SCFree
#define SCFree(p)
Definition: util-mem.h:61
src
uint16_t src
Definition: app-layer-dnp3.h:5
SCRadixNode_::netmask_cnt
uint16_t netmask_cnt
Definition: util-radix-tree.h:69
sc_errno
thread_local SCError sc_errno
Definition: util-error.c:31
address
uint8_t address
Definition: decode-ppp.h:0
SCRadixFindKeyIPV4ExactMatch
SCRadixNode * SCRadixFindKeyIPV4ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV4 address is present in the tree.
Definition: util-radix-tree.c:1579
SCRadixAddKeyIPV4
SCRadixNode * SCRadixAddKeyIPV4(uint8_t *key_stream, SCRadixTree *tree, void *user)
Adds a new IPV4 address to the Radix tree.
Definition: util-radix-tree.c:858
SCRadixNode_::netmasks
uint8_t * netmasks
Definition: util-radix-tree.h:71
SCRadixNode_::parent
struct SCRadixNode_ * parent
Definition: util-radix-tree.h:80
SCRadixPrintNodeInfo
void SCRadixPrintNodeInfo(SCRadixNode *node, int level, void(*PrintData)(void *))
Prints the node information from a Radix tree.
Definition: util-radix-tree.c:1660
SCRadixNode_::left
struct SCRadixNode_ * left
Definition: util-radix-tree.h:77
SCLogNotice
#define SCLogNotice(...)
Macro used to log NOTICE messages.
Definition: util-debug.h:237
SCCalloc
#define SCCalloc(nm, sz)
Definition: util-mem.h:53
SCRadixRemoveKeyGeneric
void SCRadixRemoveKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, SCRadixTree *tree)
Removes a key from the Radix tree.
Definition: util-radix-tree.c:1366
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:104
SCRadixPrefix_::bitlen
uint16_t bitlen
Definition: util-radix-tree.h:46