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