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