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