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