suricata
util-radix-tree.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2010 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 
34 /**
35  * \brief Allocates and returns a new instance of SCRadixUserData.
36  *
37  * \param netmask The netmask entry (cidr) that has to be made in the new
38  * SCRadixUserData instance
39  * \param user The user data that has to be set for the above
40  * netmask in the newly created SCRadixUserData instance.
41  *
42  * \retval user_data Pointer to a new instance of SCRadixUserData.
43  */
44 static SCRadixUserData *SCRadixAllocSCRadixUserData(uint8_t netmask, void *user)
45 {
46  SCRadixUserData *user_data = SCMalloc(sizeof(SCRadixUserData));
47  if (unlikely(user_data == NULL)) {
48  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
49  return NULL;
50  }
51 
52  memset(user_data, 0, sizeof(SCRadixUserData));
53 
54  user_data->netmask = netmask;
55  user_data->user = user;
56 
57  return user_data;
58 }
59 
60 /**
61  * \brief Deallocates an instance of SCRadixUserData.
62  *
63  * \param user_data Pointer to the instance of SCRadixUserData that has to be
64  * freed.
65  */
66 static void SCRadixDeAllocSCRadixUserData(SCRadixUserData *user_data)
67 {
68  SCFree(user_data);
69 
70  return;
71 }
72 
73 /**
74  * \brief Appends a user_data instance(SCRadixUserData) to a
75  * user_data(SCRadixUserData) list. We add the new entry in descending
76  * order with respect to the netmask contained in the SCRadixUserData.
77  *
78  * \param new Pointer to the SCRadixUserData to be added to the list.
79  * \param list Pointer to the SCRadixUserData list head, to which "new" has to
80  * be appended.
81  */
82 static void SCRadixAppendToSCRadixUserDataList(SCRadixUserData *new,
83  SCRadixUserData **list)
84 {
85  SCRadixUserData *temp = NULL;
86  SCRadixUserData *prev = NULL;
87 
88  if (new == NULL || list == NULL) {
89  SCLogError(SC_ERR_INVALID_ARGUMENTS, "new or list supplied as NULL");
90  exit(EXIT_FAILURE);
91  }
92 
93  /* add to the list in descending order. The reason we do this is for
94  * optimizing key retrieval for a ip key under a netblock */
95  prev = temp = *list;
96  while (temp != NULL) {
97  if (new->netmask > temp->netmask)
98  break;
99  prev = temp;
100  temp = temp->next;
101  }
102 
103  if (temp == *list) {
104  new->next = *list;
105  *list = new;
106  } else {
107  new->next = prev->next;
108  prev->next = new;
109  }
110 
111  return;
112 }
113 
114 /**
115  * \brief Creates a new Prefix for a key. Used internally by the API.
116  *
117  * \param key_stream Data that has to be wrapped in a SCRadixPrefix instance to
118  * be processed for insertion/lookup/removal of a node by the
119  * radix tree
120  * \param key_bitlen The bitlen of the the above stream. For example if the
121  * stream holds the ipv4 address(4 bytes), bitlen would be 32
122  * \param user Pointer to the user data that has to be associated with
123  * this key
124  *
125  * \retval prefix The newly created prefix instance on success; NULL on failure
126  */
127 static SCRadixPrefix *SCRadixCreatePrefix(uint8_t *key_stream,
128  uint16_t key_bitlen, void *user,
129  uint8_t netmask)
130 {
131  SCRadixPrefix *prefix = NULL;
132 
133  if ((key_bitlen % 8 != 0)) {
134  SCLogError(SC_ERR_INVALID_ARGUMENT, "Invalid argument bitlen - %d",
135  key_bitlen);
136  return NULL;
137  }
138 
139  if (key_stream == NULL) {
140  SCLogError(SC_ERR_INVALID_ARGUMENT, "Argument \"stream\" NULL");
141  return NULL;
142  }
143 
144  if ( (prefix = SCMalloc(sizeof(SCRadixPrefix))) == NULL)
145  goto error;
146 
147  memset(prefix, 0, sizeof(SCRadixPrefix));
148 
149  if ( (prefix->stream = SCMalloc(key_bitlen / 8)) == NULL)
150  goto error;
151 
152  memset(prefix->stream, 0, key_bitlen / 8);
153 
154  memcpy(prefix->stream, key_stream, key_bitlen / 8);
155  prefix->bitlen = key_bitlen;
156 
157  prefix->user_data = SCRadixAllocSCRadixUserData(netmask, user);
158  if (prefix->user_data == NULL) {
159  goto error;
160  }
161 
162  return prefix;
163 
164 error:
165  if (prefix != NULL) {
166  if (prefix->stream != NULL) {
167  SCFree(prefix->stream);
168  }
169  SCFree(prefix);
170  }
171 
172  return NULL;
173 }
174 
175 /**
176  * \brief Adds a netmask and its user_data for a particular prefix stream.
177  *
178  * \param prefix The prefix stream to which the netmask and its corresponding
179  * user data has to be added.
180  * \param netmask The netmask value (cidr) that has to be added to the prefix.
181  * \param user The pointer to the user data corresponding to the above
182  * netmask.
183  */
184 static void SCRadixAddNetmaskUserDataToPrefix(SCRadixPrefix *prefix,
185  uint8_t netmask,
186  void *user)
187 {
188  if (prefix == NULL || user == NULL) {
189  SCLogError(SC_ERR_INVALID_ARGUMENTS, "prefix or user NULL");
190  exit(EXIT_FAILURE);
191  }
192 
193  SCRadixAppendToSCRadixUserDataList(SCRadixAllocSCRadixUserData(netmask, user),
194  &prefix->user_data);
195 
196  return;
197 }
198 
199 /**
200  * \brief Removes a particular user_data corresponding to a particular netmask
201  * entry, from a prefix.
202  *
203  * \param prefix Pointer to the prefix from which the user_data/netmask entry
204  * has to be removed.
205  * \param netmask The netmask value (cidr) whose user_data has to be deleted.
206  */
207 static void SCRadixRemoveNetmaskUserDataFromPrefix(SCRadixPrefix *prefix,
208  uint8_t netmask)
209 {
210  SCRadixUserData *temp = NULL, *prev = NULL;
211 
212  if (prefix == NULL) {
213  SCLogError(SC_ERR_INVALID_ARGUMENTS, "prefix NULL");
214  exit(EXIT_FAILURE);
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) {
431  SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixCreateRadixTree. Exiting...");
432  exit(EXIT_FAILURE);
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(uint8_t *key_stream, uint16_t key_bitlen,
492  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  int check_bit = 0;
505  int differ_bit = 0;
506 
507  int i = 0;
508  int j = 0;
509  int temp = 0;
510 
511  if (tree == NULL) {
512  SCLogError(SC_ERR_INVALID_ARGUMENT, "Argument \"tree\" NULL");
513  return NULL;
514  }
515 
516  /* chop the ip address against a netmask */
517  MaskIPNetblock(key_stream, netmask, key_bitlen);
518 
519  /* the very first element in the radix tree */
520  if (tree->head == NULL) {
521  SCRadixPrefix *prefix = NULL;
522  if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, user,
523  netmask)) == NULL) {
524  SCLogError(SC_ERR_RADIX_TREE_GENERIC, "Error creating prefix");
525  return NULL;
526  }
527  node = SCRadixCreateNode();
528  if (node == NULL) {
529  SCRadixReleasePrefix(prefix, tree);
530  return NULL;
531  }
532  node->prefix = prefix;
533  node->bit = prefix->bitlen;
534  tree->head = node;
535  if (netmask == 255 || (netmask == 32 && key_bitlen == 32) || (netmask == 128 && key_bitlen == 128))
536  return node;
537 
538  /* if we have reached here, we are actually having a proper netblock in
539  * our hand(i.e. < 32 for ipv4 and < 128 for ipv6). Add the netmask for
540  * this node. The reason we add netmasks other than 32 and 128, is
541  * because we need those netmasks in case of searches for ips contained
542  * in netblocks. If the netmask is 32 or 128, either ways we will be
543  * having an exact match for that ip value. If it is not, we start
544  * chopping the incoming search ip key using the netmask values added
545  * into the tree and then verify for a match */
546  node->netmask_cnt++;
547  if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt *
548  sizeof(uint8_t)))) == NULL) {
549  SCFree(node->netmasks);
550  node->netmasks = NULL;
551  SCLogError(SC_ERR_MEM_ALLOC, "Fatal error encountered in SCRadixAddKey. Mem not allocated");
552  return NULL;
553  }
554  node->netmasks = ptmp;
555  node->netmasks[0] = netmask;
556  return node;
557  }
558 
559  node = tree->head;
560  stream = key_stream;
561  bitlen = key_bitlen;
562 
563  /* we walk down the tree only when we satisfy 2 conditions. The first one
564  * being the incoming prefix is shorter than the differ bit of the current
565  * node. In case we fail in this aspect, we walk down to the tree, till we
566  * arrive at a node that ends in a prefix */
567  while (node->bit < bitlen || node->prefix == NULL) {
568  /* if the bitlen isn't long enough to handle the bit test, we just walk
569  * down along one of the paths, since either paths should end up with a
570  * node that has a common prefix whose differ bit is greater than the
571  * bitlen of the incoming prefix */
572  if (bitlen <= node->bit) {
573  if (node->right == NULL)
574  break;
575  node = node->right;
576  } else {
577  if (SC_RADIX_BITTEST(stream[node->bit >> 3],
578  (0x80 >> (node->bit % 8))) ) {
579  if (node->right == NULL)
580  break;
581  node = node->right;
582  } else {
583  if (node->left == NULL)
584  break;
585  node = node->left;
586  }
587  }
588  }
589 
590  /* we need to keep a reference to the bottom-most node, that actually holds
591  * the prefix */
592  bottom_node = node;
593 
594  /* get the first bit position where the ips differ */
595  check_bit = (node->bit < bitlen)? node->bit: bitlen;
596  for (i = 0; (i * 8) < check_bit; i++) {
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 - 2; i >= 0; i--) {
687  if (netmask < node->netmasks[i]) {
688  node->netmasks[i + 1] = netmask;
689  break;
690  }
691 
692  node->netmasks[i + 1] = node->netmasks[i];
693  node->netmasks[i] = 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;
802  SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixAddKey. Exiting...");
803  exit(EXIT_FAILURE);
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 - 2; i >= 0; i--) {
815  if (netmask < node->netmasks[i]) {
816  node->netmasks[i + 1] = netmask;
817  break;
818  }
819 
820  node->netmasks[i + 1] = node->netmasks[i];
821  node->netmasks[i] = netmask;
822  }
823  }
824 
825  return new_node;
826 }
827 
828 /**
829  * \brief Adds a new generic key to the Radix tree
830  *
831  * \param key_stream Data that has to be added to the Radix tree
832  * \param key_bitlen The bitlen of the the above stream. For example if the
833  * stream is the string "abcd", the bitlen would be 32
834  * \param tree Pointer to the Radix tree
835  * \param user Pointer to the user data that has to be associated with the
836  * key
837  *
838  * \retval node Pointer to the newly created node
839  */
840 SCRadixNode *SCRadixAddKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen,
841  SCRadixTree *tree, void *user)
842 {
843  SCRadixNode *node = SCRadixAddKey(key_stream, key_bitlen, tree, user, 255);
844 
845  return node;
846 }
847 
848 /**
849  * \brief Adds a new IPV4 address to the Radix tree
850  *
851  * \param key_stream Data that has to be added to the Radix tree. In this case
852  * a pointer to an IPV4 address
853  * \param tree Pointer to the Radix tree
854  * \param user Pointer to the user data that has to be associated with the
855  * key
856  *
857  * \retval node Pointer to the newly created node
858  */
859 SCRadixNode *SCRadixAddKeyIPV4(uint8_t *key_stream, SCRadixTree *tree,
860  void *user)
861 {
862  SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, 32);
863 
864  return node;
865 }
866 
867 /**
868  * \brief Adds a new IPV6 address to the Radix tree
869  *
870  * \param key_stream Data that has to be added to the Radix tree. In this case
871  * the pointer to an IPV6 address
872  * \param tree Pointer to the Radix tree
873  * \param user Pointer to the user data that has to be associated with the
874  * key
875  *
876  * \retval node Pointer to the newly created node
877  */
878 SCRadixNode *SCRadixAddKeyIPV6(uint8_t *key_stream, SCRadixTree *tree,
879  void *user)
880 {
881  SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, 128);
882 
883  return node;
884 }
885 
886 /**
887  * \brief Adds a new IPV4 netblock to the Radix tree
888  *
889  * \param key_stream Data that has to be added to the Radix tree. In this case
890  * a pointer to an IPV4 netblock
891  * \param tree Pointer to the Radix tree
892  * \param user Pointer to the user data that has to be associated with the
893  * key
894  * \param netmask The netmask (cidr) if we are adding a netblock
895  *
896  * \retval node Pointer to the newly created node
897  */
899  void *user, uint8_t netmask)
900 {
901  SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, netmask);
902 
903  return node;
904 }
905 
906 /**
907  * \brief Adds a new IPV6 netblock to the Radix tree
908  *
909  * \param key_stream Data that has to be added to the Radix tree. In this case
910  * a pointer to an IPV6 netblock
911  * \param tree Pointer to the Radix tree
912  * \param user Pointer to the user data that has to be associated with the
913  * key
914  * \param netmask The netmask (cidr) if we are adding a netblock
915  *
916  * \retval node Pointer to the newly created node
917  */
919  void *user, uint8_t netmask)
920 {
921  SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, netmask);
922 
923  return node;
924 }
925 
926 /**
927  * \brief Adds a new IPV4/netblock to the Radix tree from a string
928  *
929  * \param str IPV4 string with optional /cidr netmask
930  * \param tree Pointer to the Radix tree
931  * \param user Pointer to the user data that has to be associated with
932  * the key
933  *
934  * \retval node Pointer to the newly created node
935  */
936 SCRadixNode *SCRadixAddKeyIPV4String(const char *str, SCRadixTree *tree, void *user)
937 {
938  uint32_t ip;
939  uint8_t netmask = 32;
940  char ip_str[32]; /* Max length for full ipv4/mask string with NUL */
941  char *mask_str = NULL;
942  struct in_addr addr;
943 
944  /* Make a copy of the string so it can be modified */
945  strlcpy(ip_str, str, sizeof(ip_str) - 2);
946  *(ip_str + (sizeof(ip_str) - 1)) = '\0';
947 
948  /* Does it have a mask? */
949  if (NULL != (mask_str = strchr(ip_str, '/'))) {
950  int cidr;
951  *(mask_str++) = '\0';
952 
953  /* Dotted type netmask not supported (yet) */
954  if (strchr(mask_str, '.') != NULL) {
955  return NULL;
956  }
957 
958  /* Get binary values for cidr mask */
959  cidr = atoi(mask_str);
960  if ((cidr < 0) || (cidr > 32)) {
961  return NULL;
962  }
963  netmask = (uint8_t)cidr;
964  }
965 
966  /* Validate the IP */
967  if (inet_pton(AF_INET, ip_str, &addr) <= 0) {
968  return NULL;
969  }
970  ip = addr.s_addr;
971 
972  return SCRadixAddKey((uint8_t *)&ip, 32, tree, user, netmask);
973 }
974 
975 /**
976  * \brief Adds a new IPV6/netblock to the Radix tree from a string
977  *
978  * \param str IPV6 string with optional /cidr netmask
979  * \param tree Pointer to the Radix tree
980  * \param user Pointer to the user data that has to be associated with
981  * the key
982  *
983  * \retval node Pointer to the newly created node
984  */
985 SCRadixNode *SCRadixAddKeyIPV6String(const char *str, SCRadixTree *tree, void *user)
986 {
987  uint8_t netmask = 128;
988  char ip_str[80]; /* Max length for full ipv6/mask string with NUL */
989  char *mask_str = NULL;
990  struct in6_addr addr;
991 
992  /* Make a copy of the string so it can be modified */
993  strlcpy(ip_str, str, sizeof(ip_str) - 2);
994  *(ip_str + sizeof(ip_str) - 1) = '\0';
995 
996  /* Does it have a mask? */
997  if (NULL != (mask_str = strchr(ip_str, '/'))) {
998  int cidr;
999  *(mask_str++) = '\0';
1000 
1001  /* Dotted type netmask not supported (yet) */
1002  if (strchr(mask_str, '.') != NULL) {
1003  return NULL;
1004  }
1005 
1006  /* Get binary values for cidr mask */
1007  cidr = atoi(mask_str);
1008  if ((cidr < 0) || (cidr > 128)) {
1009  return NULL;
1010  }
1011  netmask = (uint8_t)cidr;
1012  }
1013 
1014  /* Validate the IP */
1015  if (inet_pton(AF_INET6, ip_str, &addr) <= 0) {
1016  return NULL;
1017  }
1018 
1019  return SCRadixAddKey(addr.s6_addr, 128, tree, user, netmask);
1020 }
1021 
1022 static void SCRadixTransferNetmasksBWNodes(SCRadixNode *dest, SCRadixNode *src)
1023 {
1024  int i = 0, j = 0;
1025  void *ptmp = NULL;
1026 
1027  if (src == NULL || dest == NULL) {
1028  SCLogError(SC_ERR_INVALID_ARGUMENTS, "src or dest NULL");
1029  return;
1030  }
1031 
1032  /* no netmasks in the source node, to transfer to the destination node */
1033  if (src->netmasks == NULL)
1034  return;
1035 
1036  if ( (ptmp = SCRealloc(dest->netmasks,
1037  (src->netmask_cnt + dest->netmask_cnt) *
1038  sizeof(uint8_t))) == NULL) {
1039  SCFree(dest->netmasks);
1040  dest->netmasks = NULL;
1041  return;
1042  }
1043  dest->netmasks = ptmp;
1044 
1045  for (i = dest->netmask_cnt, j = 0; j < src->netmask_cnt; i++, j++)
1046  dest->netmasks[i] = src->netmasks[j];
1047 
1048  return;
1049 }
1050 
1051 /**
1052  * \brief Removes a netblock entry from an ip node. The function first
1053  * deletes the netblock/user_data entry for the prefix and then
1054  * removes the netmask entry that has been made in the tree, by
1055  * walking up the tree and deleting the entry from the specific node.
1056  *
1057  * \param node The node from which the netblock entry has to be removed.
1058  * \param netmask The netmask entry (cidr) that has to be removed.
1059  */
1060 static void SCRadixRemoveNetblockEntry(SCRadixNode *node, uint8_t netmask)
1061 {
1062  void *ptmp;
1063  SCRadixNode *parent = NULL;
1064  int i = 0;
1065 
1066  if (node == NULL) {
1067  SCLogError(SC_ERR_INVALID_ARGUMENTS, "Invalid argument. Node is NULL");
1068  return;
1069  }
1070 
1071  SCRadixRemoveNetmaskUserDataFromPrefix(node->prefix, netmask);
1072 
1073  if (netmask == 32 || netmask == 128)
1074  return;
1075 
1076  parent = node->parent;
1077  while (parent != NULL && netmask < (parent->bit + 1)) {
1078  parent = parent->parent;
1079  }
1080 
1081  for (i = 0; i < node->netmask_cnt; i++) {
1082  if (node->netmasks[i] == netmask)
1083  break;
1084  }
1085 
1086  if (i == node->netmask_cnt) {
1087  SCLogDebug("Something's wrong with the tree. We are unable to find the "
1088  "netmask entry");
1089  return;
1090  }
1091 
1092  for ( ; i < node->netmask_cnt - 1; i++)
1093  node->netmasks[i] = node->netmasks[i + 1];
1094 
1095  node->netmask_cnt--;
1096  if (node->netmask_cnt == 0) {
1097  SCFree(node->netmasks);
1098  node->netmasks = NULL;
1099  return;
1100  }
1101 
1102  ptmp = SCRealloc(node->netmasks, node->netmask_cnt * sizeof(uint8_t));
1103  if (ptmp == NULL) {
1104  SCFree(node->netmasks);
1105  node->netmasks = NULL;
1106  return;
1107  }
1108  node->netmasks = ptmp;
1109 
1110  return;
1111 }
1112 
1113 /**
1114  * \brief Removes a key from the Radix tree
1115  *
1116  * \param key_stream Data that has to be removed from the Radix tree
1117  * \param key_bitlen The bitlen of the the above stream. For example if the
1118  * stream holds an IPV4 address(4 bytes), bitlen would be 32
1119  * \param tree Pointer to the Radix tree from which the key has to be
1120  * removed
1121  */
1122 static void SCRadixRemoveKey(uint8_t *key_stream, uint16_t key_bitlen,
1123  SCRadixTree *tree, uint8_t netmask)
1124 {
1125  SCRadixNode *node = tree->head;
1126  SCRadixNode *parent = NULL;
1127  SCRadixNode *temp_dest = NULL;
1128 
1129  SCRadixPrefix *prefix = NULL;
1130 
1131  uint32_t mask = 0;
1132  int i = 0;
1133 
1134  if (node == NULL)
1135  return;
1136 
1137  if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, NULL, 255)) == NULL)
1138  return;
1139 
1140  while (node->bit < prefix->bitlen) {
1141  if (SC_RADIX_BITTEST(prefix->stream[node->bit >> 3],
1142  (0x80 >> (node->bit % 8))) ) {
1143  node = node->right;
1144  } else {
1145  node = node->left;
1146  }
1147 
1148  if (node == NULL) {
1149  SCRadixReleasePrefix(prefix, tree);
1150  return;
1151  }
1152  }
1153 
1154  if (node->bit != prefix->bitlen || node->prefix == NULL) {
1155  SCRadixReleasePrefix(prefix, tree);
1156  return;
1157  }
1158 
1159  i = prefix->bitlen / 8;
1160  if (SCMemcmp(node->prefix->stream, prefix->stream, i) == 0) {
1161  mask = UINT_MAX << (8 - prefix->bitlen % 8);
1162 
1163  if (prefix->bitlen % 8 == 0 ||
1164  (node->prefix->stream[i] & mask) == (prefix->stream[i] & mask)) {
1165  if (!SCRadixPrefixContainNetmask(node->prefix, netmask)) {
1166  SCLogDebug("The ip key exists in the Radix Tree, but this(%d) "
1167  "netblock entry doesn't exist", netmask);
1168  SCRadixReleasePrefix(prefix, tree);
1169  return;
1170  }
1171  } else {
1172  SCLogDebug("You are trying to remove a key that doesn't exist in "
1173  "the Radix Tree");
1174  SCRadixReleasePrefix(prefix, tree);
1175  return;
1176  }
1177  } else {
1178  SCLogDebug("You are trying to remove a key that doesn't exist in the "
1179  "Radix Tree");
1180  SCRadixReleasePrefix(prefix, tree);
1181  return;
1182  }
1183 
1184  /* The ip node does exist, and the netblock entry does exist in this node, if
1185  * we have reached this point. If we have more than one netblock entry, it
1186  * indicates we have multiple entries for this key. So we delete that
1187  * particular netblock entry, and make our way out of this function */
1188  if (SCRadixPrefixNetmaskCount(node->prefix) > 1) {
1189  SCRadixRemoveNetblockEntry(node, netmask);
1190  SCRadixReleasePrefix(prefix, tree);
1191  return;
1192  }
1193 
1194  /* we are deleting the root of the tree. This would be the only node left
1195  * in the tree */
1196  if (tree->head == node) {
1197  SCRadixReleaseNode(node, tree);
1198  tree->head = NULL;
1199  SCRadixReleasePrefix(prefix, tree);
1200  return;
1201  }
1202 
1203  parent = node->parent;
1204  /* parent->parent is not the root of the tree */
1205  if (parent->parent != NULL) {
1206  if (parent->parent->left == parent) {
1207  if (node->parent->left == node) {
1208  temp_dest = parent->right;
1209  parent->parent->left = parent->right;
1210  parent->right->parent = parent->parent;
1211  } else {
1212  temp_dest = parent->left;
1213  parent->parent->left = parent->left;
1214  parent->left->parent = parent->parent;
1215  }
1216  } else {
1217  if (node->parent->left == node) {
1218  temp_dest = parent->right;
1219  parent->parent->right = parent->right;
1220  parent->right->parent = parent->parent;
1221  } else {
1222  temp_dest = parent->left;
1223  parent->parent->right = parent->left;
1224  parent->left->parent = parent->parent;
1225  }
1226  }
1227  /* parent is the root of the tree */
1228  } else {
1229  if (parent->left == node) {
1230  temp_dest = tree->head->right;
1231  tree->head->right->parent = NULL;
1232  tree->head = tree->head->right;
1233  } else {
1234  temp_dest = tree->head->left;
1235  tree->head->left->parent = NULL;
1236  tree->head = tree->head->left;
1237  }
1238  }
1239  /* We need to shift the netmask entries from the node that would be
1240  * deleted to its immediate descendant */
1241  SCRadixTransferNetmasksBWNodes(temp_dest, parent);
1242  /* release the nodes */
1243  SCRadixReleaseNode(parent, tree);
1244  SCRadixReleaseNode(node, tree);
1245  SCRadixReleasePrefix(prefix, tree);
1246 
1247  return;
1248 }
1249 
1250 /**
1251  * \brief Removes a key from the Radix tree
1252  *
1253  * \param key_stream Data that has to be removed from the Radix tree
1254  * \param key_bitlen The bitlen of the the above stream.
1255  * \param tree Pointer to the Radix tree from which the key has to be
1256  * removed
1257  */
1258 void SCRadixRemoveKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen,
1259  SCRadixTree *tree)
1260 {
1261  SCRadixRemoveKey(key_stream, key_bitlen, tree, 255);
1262  return;
1263 }
1264 
1265 /**
1266  * \brief Removes an IPV4 address netblock key from the Radix tree.
1267  *
1268  * \param key_stream Data that has to be removed from the Radix tree. In this
1269  * case an IPV4 address
1270  * \param tree Pointer to the Radix tree from which the key has to be
1271  * removed
1272  */
1273 void SCRadixRemoveKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree,
1274  uint8_t netmask)
1275 {
1276  SCRadixRemoveKey(key_stream, 32, tree, netmask);
1277  return;
1278 }
1279 
1280 /**
1281  * \brief Removes an IPV4 address key(not a netblock) from the Radix tree.
1282  * Instead of using this function, we can also used
1283  * SCRadixRemoveKeyIPV4Netblock(), by supplying a netmask value of 32.
1284  *
1285  * \param key_stream Data that has to be removed from the Radix tree. In this
1286  * case an IPV4 address
1287  * \param tree Pointer to the Radix tree from which the key has to be
1288  * removed
1289  */
1290 void SCRadixRemoveKeyIPV4(uint8_t *key_stream, SCRadixTree *tree)
1291 {
1292  SCRadixRemoveKey(key_stream, 32, tree, 32);
1293  return;
1294 }
1295 
1296 /**
1297  * \brief Removes an IPV6 netblock address key from the Radix tree.
1298  *
1299  * \param key_stream Data that has to be removed from the Radix tree. In this
1300  * case an IPV6 address
1301  * \param tree Pointer to the Radix tree from which the key has to be
1302  * removed
1303  */
1304 void SCRadixRemoveKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree,
1305  uint8_t netmask)
1306 {
1307  SCRadixRemoveKey(key_stream, 128, tree, netmask);
1308  return;
1309 }
1310 
1311 /**
1312  * \brief Removes an IPV6 address key(not a netblock) from the Radix tree.
1313  * Instead of using this function, we can also used
1314  * SCRadixRemoveKeyIPV6Netblock(), by supplying a netmask value of 128.
1315  *
1316  * \param key_stream Data that has to be removed from the Radix tree. In this
1317  * case an IPV6 address
1318  * \param tree Pointer to the Radix tree from which the key has to be
1319  * removed
1320  */
1321 void SCRadixRemoveKeyIPV6(uint8_t *key_stream, SCRadixTree *tree)
1322 {
1323  SCRadixRemoveKey(key_stream, 128, tree, 128);
1324  return;
1325 }
1326 
1327 /**
1328  * \brief Checks if an IP prefix falls under a netblock, in the path to the root
1329  * of the tree, from the node. Used internally by SCRadixFindKey()
1330  *
1331  * \param prefix Pointer to the prefix that contains the ip address
1332  * \param node Pointer to the node from where we have to climb the tree
1333  */
1334 static inline SCRadixNode *SCRadixFindKeyIPNetblock(uint8_t *key_stream, uint8_t key_bitlen,
1335  SCRadixNode *node, void **user_data_result)
1336 {
1337  SCRadixNode *netmask_node = NULL;
1338  uint32_t mask = 0;
1339  int bytes = 0;
1340  int i = 0;
1341  int j = 0;
1342 
1343  while (node != NULL && node->netmasks == NULL)
1344  node = node->parent;
1345 
1346  if (node == NULL)
1347  return NULL;
1348  /* hold the node found containing a netmask. We will need it when we call
1349  * this function recursively */
1350  netmask_node = node;
1351 
1352  for (j = 0; j < netmask_node->netmask_cnt; j++) {
1353  bytes = key_bitlen / 8;
1354  for (i = 0; i < bytes; i++) {
1355  mask = UINT_MAX;
1356  if ( ((i + 1) * 8) > netmask_node->netmasks[j]) {
1357  if ( ((i + 1) * 8 - netmask_node->netmasks[j]) < 8)
1358  mask = UINT_MAX << ((i + 1) * 8 - netmask_node->netmasks[j]);
1359  else
1360  mask = 0;
1361  }
1362  key_stream[i] &= mask;
1363  }
1364 
1365  while (node->bit < key_bitlen) {
1366  if (SC_RADIX_BITTEST(key_stream[node->bit >> 3],
1367  (0x80 >> (node->bit % 8))) ) {
1368  node = node->right;
1369  } else {
1370  node = node->left;
1371  }
1372 
1373  if (node == NULL)
1374  return NULL;
1375  }
1376 
1377  if (node->bit != key_bitlen || node->prefix == NULL)
1378  return NULL;
1379 
1380  if (SCMemcmp(node->prefix->stream, key_stream, bytes) == 0) {
1381  mask = UINT_MAX << (8 - key_bitlen % 8);
1382 
1383  if (key_bitlen % 8 == 0 ||
1384  (node->prefix->stream[bytes] & mask) == (key_stream[bytes] & mask)) {
1385  if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, netmask_node->netmasks[j], 0, user_data_result))
1386  return node;
1387  }
1388  }
1389  }
1390 
1391  return SCRadixFindKeyIPNetblock(key_stream, key_bitlen, netmask_node->parent, user_data_result);
1392 }
1393 
1394 /**
1395  * \brief Checks if an IP address key is present in the tree. The function
1396  * apart from handling any normal data, also handles ipv4/ipv6 netblocks
1397  *
1398  * \param key_stream Data that has to be found in the Radix tree
1399  * \param key_bitlen The bitlen of the above stream.
1400  * \param tree Pointer to the Radix tree
1401  * \param exact_match The key to be searched is an ip address
1402  */
1403 static SCRadixNode *SCRadixFindKey(uint8_t *key_stream, uint16_t key_bitlen,
1404  SCRadixTree *tree, int exact_match, void **user_data_result)
1405 {
1406  if (tree == NULL || tree->head == NULL)
1407  return NULL;
1408 
1409  SCRadixNode *node = tree->head;
1410  uint32_t mask = 0;
1411  int bytes = 0;
1412  uint8_t tmp_stream[255];
1413 
1414  if (key_bitlen > 255)
1415  return NULL;
1416 
1417  memset(tmp_stream, 0, 255);
1418  memcpy(tmp_stream, key_stream, key_bitlen / 8);
1419 
1420  while (node->bit < key_bitlen) {
1421  if (SC_RADIX_BITTEST(tmp_stream[node->bit >> 3],
1422  (0x80 >> (node->bit % 8))) ) {
1423  node = node->right;
1424  } else {
1425  node = node->left;
1426  }
1427 
1428  if (node == NULL) {
1429  return NULL;
1430  }
1431  }
1432 
1433  if (node->bit != key_bitlen || node->prefix == NULL) {
1434  return NULL;
1435  }
1436 
1437  bytes = key_bitlen / 8;
1438  if (SCMemcmp(node->prefix->stream, tmp_stream, bytes) == 0) {
1439  mask = UINT_MAX << (8 - key_bitlen % 8);
1440 
1441  if (key_bitlen % 8 == 0 ||
1442  (node->prefix->stream[bytes] & mask) == (tmp_stream[bytes] & mask)) {
1443  if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, key_bitlen, 1, user_data_result)) {
1444  return node;
1445  }
1446  }
1447  }
1448 
1449  /* if you are not an ip key, get out of here */
1450  if (exact_match) {
1451  return NULL;
1452  }
1453 
1454  SCRadixNode *ret = SCRadixFindKeyIPNetblock(tmp_stream, key_bitlen, node, user_data_result);
1455  return ret;
1456 }
1457 
1458 /**
1459  * \brief Checks if a key is present in the tree
1460  *
1461  * \param key_stream Data that has to be found in the Radix tree
1462  * \param key_bitlen The bitlen of the the above stream.
1463  * \param tree Pointer to the Radix tree instance
1464  */
1465 SCRadixNode *SCRadixFindKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen,
1466  SCRadixTree *tree, void **user_data_result)
1467 {
1468  return SCRadixFindKey(key_stream, key_bitlen, tree, 1, user_data_result);
1469 }
1470 
1471 /**
1472  * \brief Checks if an IPV4 address is present in the tree
1473  *
1474  * \param key_stream Data that has to be found in the Radix tree. In this case
1475  * an IPV4 address
1476  * \param tree Pointer to the Radix tree instance
1477  */
1478 SCRadixNode *SCRadixFindKeyIPV4ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1479 {
1480  return SCRadixFindKey(key_stream, 32, tree, 1, user_data_result);
1481 }
1482 
1483 /**
1484  * \brief Checks if an IPV4 address is present in the tree under a netblock
1485  *
1486  * \param key_stream Data that has to be found in the Radix tree. In this case
1487  * an IPV4 address
1488  * \param tree Pointer to the Radix tree instance
1489  */
1490 SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1491 {
1492  return SCRadixFindKey(key_stream, 32, tree, 0, user_data_result);
1493 }
1494 
1495 /**
1496  * \brief Checks if an IPV4 Netblock address is present in the tree
1497  *
1498  * \param key_stream Data that has to be found in the Radix tree. In this case
1499  * an IPV4 netblock address
1500  * \param tree Pointer to the Radix tree instance
1501  */
1503  uint8_t netmask, void **user_data_result)
1504 {
1505  SCRadixNode *node = NULL;
1506  node = SCRadixFindKey(key_stream, 32, tree, 0, user_data_result);
1507  if (node == NULL)
1508  return node;
1509 
1510  if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, netmask, 1, user_data_result))
1511  return node;
1512  else
1513  return NULL;
1514 }
1515 
1516 /**
1517  * \brief Checks if an IPV6 Netblock address is present in the tree
1518  *
1519  * \param key_stream Data that has to be found in the Radix tree. In this case
1520  * an IPV6 netblock address
1521  * \param tree Pointer to the Radix tree instance
1522  */
1524  uint8_t netmask, void **user_data_result)
1525 {
1526  SCRadixNode *node = NULL;
1527  node = SCRadixFindKey(key_stream, 128, tree, 0, user_data_result);
1528  if (node == NULL)
1529  return node;
1530 
1531  if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, (uint16_t)netmask, 1, user_data_result))
1532  return node;
1533  else
1534  return NULL;
1535 }
1536 
1537 /**
1538  * \brief Checks if an IPV6 address is present in the tree
1539  *
1540  * \param key_stream Data that has to be found in the Radix tree. In this case
1541  * an IPV6 address
1542  * \param tree Pointer to the Radix tree instance
1543  */
1544 SCRadixNode *SCRadixFindKeyIPV6ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1545 {
1546  return SCRadixFindKey(key_stream, 128, tree, 1, user_data_result);
1547 }
1548 
1549 /**
1550  * \brief Checks if an IPV6 address is present in the tree under a netblock
1551  *
1552  * \param key_stream Data that has to be found in the Radix tree. In this case
1553  * an IPV6 address
1554  * \param tree Pointer to the Radix tree instance
1555  */
1556 SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
1557 {
1558  return SCRadixFindKey(key_stream, 128, tree, 0, user_data_result);
1559 }
1560 
1561 /**
1562  * \brief Prints the node information from a Radix tree
1563  *
1564  * \param node Pointer to the Radix node whose information has to be printed
1565  * \param level Used for indentation purposes
1566  */
1567 void SCRadixPrintNodeInfo(SCRadixNode *node, int level, void (*PrintData)(void*))
1568 {
1569  int i = 0;
1570 
1571  if (node == NULL)
1572  return;
1573 
1574  for (i = 0; i < level; i++)
1575  printf(" ");
1576 
1577  printf("%d [", node->bit);
1578 
1579  if (node->netmasks == NULL) {
1580  printf("%d, ", -1);
1581  } else {
1582  for (i = 0; i < node->netmask_cnt; i++)
1583  printf("%s%d", (0 == i ? "" : ", "), node->netmasks[i]);
1584  }
1585 
1586  printf("] (");
1587  if (node->prefix != NULL) {
1588  for (i = 0; i * 8 < node->prefix->bitlen; i++)
1589  printf("%s%d", (0 == i ? "" : "."), node->prefix->stream[i]);
1590  printf(")\n");
1591 
1592  SCRadixUserData *ud = NULL;
1593  if (PrintData != NULL) {
1594  do {
1595  ud = node->prefix->user_data;
1596  printf(" [%d], ", ud->netmask);
1597  PrintData(ud->user);
1598  ud = ud->next;
1599  } while (ud != NULL);
1600  } else {
1601  //ud = node->prefix->user_data;
1602  //while (ud != NULL) {
1603  // printf(" [nm %d with data], ", ud->netmask);
1604  // ud = ud->next;
1605  //}
1606  printf("No print function provided");
1607  }
1608  printf("\n");
1609  } else {
1610  printf("NULL)\n");
1611  }
1612 
1613  return;
1614 }
1615 
1616 /**
1617  * \brief Helper function used by SCRadixPrintTree. Prints the subtree with
1618  * node as the root of the subtree
1619  *
1620  * \param node Pointer to the node that is the root of the subtree to be printed
1621  * \param level Used for indentation purposes
1622  */
1623 static void SCRadixPrintRadixSubtree(SCRadixNode *node, int level, void (*PrintData)(void*))
1624 {
1625  if (node != NULL) {
1626  SCRadixPrintNodeInfo(node, level, PrintData);
1627  SCRadixPrintRadixSubtree(node->left, level + 1, PrintData);
1628  SCRadixPrintRadixSubtree(node->right, level + 1, PrintData);
1629  }
1630 
1631  return;
1632 }
1633 
1634 /**
1635  * \brief Prints the Radix Tree. While printing the radix tree we use the
1636  * following format
1637  *
1638  * Parent_0
1639  * Left_Child_1
1640  * Left_Child_2
1641  * Right_Child_2
1642  * Right_Child_1
1643  * Left_Child_2
1644  * Right_Child_2 and so on
1645  *
1646  * Each node printed out holds details on the next bit that differs
1647  * amongst its children, and if the node holds a prefix, the perfix is
1648  * printed as well.
1649  *
1650  * \param tree Pointer to the Radix tree that has to be printed
1651  */
1653 {
1654  printf("Printing the Radix Tree: \n");
1655 
1656  SCRadixPrintRadixSubtree(tree->head, 0, tree->PrintData);
1657 
1658  return;
1659 }
1660 
1661 /*------------------------------------Unit_Tests------------------------------*/
1662 
1663 #ifdef UNITTESTS
1664 
1665 static int SCRadixTestIPV4Insertion03(void)
1666 {
1667  SCRadixTree *tree = NULL;
1668  struct sockaddr_in servaddr;
1669  int result = 1;
1670 
1671  tree = SCRadixCreateRadixTree(free, NULL);
1672 
1673  /* add the keys */
1674  bzero(&servaddr, sizeof(servaddr));
1675  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1676  return 0;
1677  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1678 
1679  bzero(&servaddr, sizeof(servaddr));
1680  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1681  return 0;
1682  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1683 
1684  bzero(&servaddr, sizeof(servaddr));
1685  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1686  return 0;
1687  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1688 
1689  bzero(&servaddr, sizeof(servaddr));
1690  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1691  return 0;
1692  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1693 
1694  /* add a key that already exists in the tree */
1695  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1696 
1697  /* test for the existance of a key */
1698  bzero(&servaddr, sizeof(servaddr));
1699  if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0)
1700  return 0;
1701  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1702 
1703  /* test for the existance of a key */
1704  bzero(&servaddr, sizeof(servaddr));
1705  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1706  return 0;
1707  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1708 
1709  /* continue adding keys */
1710  bzero(&servaddr, sizeof(servaddr));
1711  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1712  return 0;
1713  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1714 
1715  bzero(&servaddr, sizeof(servaddr));
1716  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1717  return 0;
1718  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1719 
1720  bzero(&servaddr, sizeof(servaddr));
1721  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1722  return 0;
1723  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1724 
1725  /* test the existence of keys */
1726  bzero(&servaddr, sizeof(servaddr));
1727  if (inet_pton(AF_INET, "192.168.1.3", &servaddr.sin_addr) <= 0)
1728  return 0;
1729  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1730 
1731  bzero(&servaddr, sizeof(servaddr));
1732  if (inet_pton(AF_INET, "127.234.2.62", &servaddr.sin_addr) <= 0)
1733  return 0;
1734  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1735 
1736  bzero(&servaddr, sizeof(servaddr));
1737  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1738  return 0;
1739  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1740 
1741  bzero(&servaddr, sizeof(servaddr));
1742  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1743  return 0;
1744  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1745 
1746  bzero(&servaddr, sizeof(servaddr));
1747  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1748  return 0;
1749  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1750 
1751  bzero(&servaddr, sizeof(servaddr));
1752  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1753  return 0;
1754  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1755 
1756  bzero(&servaddr, sizeof(servaddr));
1757  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1758  return 0;
1759  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1760 
1761  bzero(&servaddr, sizeof(servaddr));
1762  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1763  return 0;
1764  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1765 
1766  bzero(&servaddr, sizeof(servaddr));
1767  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1768  return 0;
1769  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1770 
1772 
1773  return result;
1774 }
1775 
1776 static int SCRadixTestIPV4Removal04(void)
1777 {
1778  SCRadixTree *tree = NULL;
1779  struct sockaddr_in servaddr;
1780  int result = 1;
1781 
1782  tree = SCRadixCreateRadixTree(free, NULL);
1783 
1784  /* add the keys */
1785  bzero(&servaddr, sizeof(servaddr));
1786  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1787  return 0;
1788  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1789 
1790  bzero(&servaddr, sizeof(servaddr));
1791  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1792  return 0;
1793  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1794 
1795  bzero(&servaddr, sizeof(servaddr));
1796  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1797  return 0;
1798  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1799 
1800  bzero(&servaddr, sizeof(servaddr));
1801  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1802  return 0;
1803  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1804 
1805  bzero(&servaddr, sizeof(servaddr));
1806  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1807  return 0;
1808  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1809 
1810  bzero(&servaddr, sizeof(servaddr));
1811  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1812  return 0;
1813  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1814 
1815  bzero(&servaddr, sizeof(servaddr));
1816  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1817  return 0;
1818  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
1819 
1820  /* remove the keys from the tree */
1821  bzero(&servaddr, sizeof(servaddr));
1822  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
1823  return 0;
1824  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1825 
1826  bzero(&servaddr, sizeof(servaddr));
1827  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1828  return 0;
1829  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1830 
1831  bzero(&servaddr, sizeof(servaddr));
1832  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
1833  return 0;
1834  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1835 
1836  bzero(&servaddr, sizeof(servaddr));
1837  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
1838  return 0;
1839  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1840 
1841  bzero(&servaddr, sizeof(servaddr));
1842  if (inet_pton(AF_INET, "192.167.1.1", &servaddr.sin_addr) <= 0)
1843  return 0;
1844  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
1845 
1846  bzero(&servaddr, sizeof(servaddr));
1847  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1848  return 0;
1849  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1850 
1851  bzero(&servaddr, sizeof(servaddr));
1852  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
1853  return 0;
1854  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1855 
1856  bzero(&servaddr, sizeof(servaddr));
1857  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
1858  return 0;
1859  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1860 
1861  bzero(&servaddr, sizeof(servaddr));
1862  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1863  return 0;
1864  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1865 
1866  bzero(&servaddr, sizeof(servaddr));
1867  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1868  return 0;
1869  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
1870 
1871  bzero(&servaddr, sizeof(servaddr));
1872  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
1873  return 0;
1874  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1875 
1876  bzero(&servaddr, sizeof(servaddr));
1877  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
1878  return 0;
1879  SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree);
1880 
1881  result &= (tree->head == NULL);
1882 
1884 
1885  return result;
1886 }
1887 
1888 static int SCRadixTestIPV6Insertion07(void)
1889 {
1890  SCRadixTree *tree = NULL;
1891  struct sockaddr_in6 servaddr;
1892  int result = 1;
1893 
1894  tree = SCRadixCreateRadixTree(free, NULL);
1895 
1896  /* add the keys */
1897  bzero(&servaddr, sizeof(servaddr));
1898  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
1899  &servaddr.sin6_addr) <= 0)
1900  return 0;
1901  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1902 
1903  bzero(&servaddr, sizeof(servaddr));
1904  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
1905  &servaddr.sin6_addr) <= 0)
1906  return 0;
1907  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1908 
1909  bzero(&servaddr, sizeof(servaddr));
1910  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
1911  &servaddr.sin6_addr) <= 0)
1912  return 0;
1913  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1914 
1915  bzero(&servaddr, sizeof(servaddr));
1916  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
1917  &servaddr.sin6_addr) <= 0)
1918  return 0;
1919  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1920 
1921  /* Try to add the prefix that already exists in the tree */
1922  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1923 
1924  bzero(&servaddr, sizeof(servaddr));
1925  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
1926  &servaddr.sin6_addr) <= 0)
1927  return 0;
1928  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1929 
1930  bzero(&servaddr, sizeof(servaddr));
1931  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
1932  &servaddr.sin6_addr) <= 0)
1933  return 0;
1934  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1935 
1936  bzero(&servaddr, sizeof(servaddr));
1937  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
1938  &servaddr.sin6_addr) <= 0)
1939  return 0;
1940  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
1941 
1942  /* test the existence of keys */
1943  bzero(&servaddr, sizeof(servaddr));
1944  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
1945  &servaddr.sin6_addr) <= 0)
1946  return 0;
1947  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1948 
1949  bzero(&servaddr, sizeof(servaddr));
1950  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
1951  &servaddr.sin6_addr) <= 0)
1952  return 0;
1953  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1954 
1955  bzero(&servaddr, sizeof(servaddr));
1956  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
1957  &servaddr.sin6_addr) <= 0)
1958  return 0;
1959  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1960 
1961  bzero(&servaddr, sizeof(servaddr));
1962  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
1963  &servaddr.sin6_addr) <= 0)
1964  return 0;
1965  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1966 
1967  bzero(&servaddr, sizeof(servaddr));
1968  if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212",
1969  &servaddr.sin6_addr) <= 0)
1970  return 0;
1971  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
1972 
1973  bzero(&servaddr, sizeof(servaddr));
1974  if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315",
1975  &servaddr.sin6_addr) <= 0)
1976  return 0;
1977  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
1978 
1979  bzero(&servaddr, sizeof(servaddr));
1980  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
1981  &servaddr.sin6_addr) <= 0)
1982  return 0;
1983  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1984 
1985  bzero(&servaddr, sizeof(servaddr));
1986  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
1987  &servaddr.sin6_addr) <= 0)
1988  return 0;
1989  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1990 
1991  bzero(&servaddr, sizeof(servaddr));
1992  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
1993  &servaddr.sin6_addr) <= 0)
1994  return 0;
1995  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
1996 
1998 
1999  return result;
2000 }
2001 
2002 static int SCRadixTestIPV6Removal08(void)
2003 {
2004  SCRadixTree *tree = NULL;
2005  struct sockaddr_in6 servaddr;
2006  int result = 1;
2007 
2008  tree = SCRadixCreateRadixTree(free, NULL);
2009 
2010  /* add the keys */
2011  bzero(&servaddr, sizeof(servaddr));
2012  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2013  &servaddr.sin6_addr) <= 0)
2014  return 0;
2015  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2016 
2017  bzero(&servaddr, sizeof(servaddr));
2018  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2019  &servaddr.sin6_addr) <= 0)
2020  return 0;
2021  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2022 
2023  bzero(&servaddr, sizeof(servaddr));
2024  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2025  &servaddr.sin6_addr) <= 0)
2026  return 0;
2027  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2028 
2029  bzero(&servaddr, sizeof(servaddr));
2030  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2031  &servaddr.sin6_addr) <= 0)
2032  return 0;
2033  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2034 
2035  /* Try to add the prefix that already exists in the tree */
2036  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2037 
2038  bzero(&servaddr, sizeof(servaddr));
2039  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2040  &servaddr.sin6_addr) <= 0)
2041  return 0;
2042  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2043 
2044  bzero(&servaddr, sizeof(servaddr));
2045  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2046  &servaddr.sin6_addr) <= 0)
2047  return 0;
2048  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2049 
2050  bzero(&servaddr, sizeof(servaddr));
2051  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2052  &servaddr.sin6_addr) <= 0)
2053  return 0;
2054  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2055 
2056  /* test the existence of keys */
2057  bzero(&servaddr, sizeof(servaddr));
2058  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2059  &servaddr.sin6_addr) <= 0)
2060  return 0;
2061  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2062 
2063  bzero(&servaddr, sizeof(servaddr));
2064  if (inet_pton(AF_INET6, "8888:0BF1:5346:BDEA:6422:8713:9124:2315",
2065  &servaddr.sin6_addr) <= 0)
2066  return 0;
2067  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2068 
2069  bzero(&servaddr, sizeof(servaddr));
2070  if (inet_pton(AF_INET6, "2006:0BF1:5346:BDEA:7422:8713:9124:2315",
2071  &servaddr.sin6_addr) <= 0)
2072  return 0;
2073  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2074 
2075  bzero(&servaddr, sizeof(servaddr));
2076  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2077  &servaddr.sin6_addr) <= 0)
2078  return 0;
2079  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2080 
2081  bzero(&servaddr, sizeof(servaddr));
2082  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2083  &servaddr.sin6_addr) <= 0)
2084  return 0;
2085  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2086 
2087  /* test for existance */
2088  bzero(&servaddr, sizeof(servaddr));
2089  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2090  &servaddr.sin6_addr) <= 0)
2091  return 0;
2092  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2093 
2094  bzero(&servaddr, sizeof(servaddr));
2095  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2096  &servaddr.sin6_addr) <= 0)
2097  return 0;
2098  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2099 
2100  bzero(&servaddr, sizeof(servaddr));
2101  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2102  &servaddr.sin6_addr) <= 0)
2103  return 0;
2104  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2105 
2106  bzero(&servaddr, sizeof(servaddr));
2107  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2108  &servaddr.sin6_addr) <= 0)
2109  return 0;
2110  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2111 
2112  bzero(&servaddr, sizeof(servaddr));
2113  if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315",
2114  &servaddr.sin6_addr) <= 0)
2115  return 0;
2116  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2117 
2118  bzero(&servaddr, sizeof(servaddr));
2119  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:DDDD:2315",
2120  &servaddr.sin6_addr) <= 0)
2121  return 0;
2122  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2123 
2124  /* remove keys */
2125  bzero(&servaddr, sizeof(servaddr));
2126  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2127  &servaddr.sin6_addr) <= 0)
2128  return 0;
2129  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2130 
2131  bzero(&servaddr, sizeof(servaddr));
2132  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2133  &servaddr.sin6_addr) <= 0)
2134  return 0;
2135  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2136 
2137  /* test for existance */
2138  bzero(&servaddr, sizeof(servaddr));
2139  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2140  &servaddr.sin6_addr) <= 0)
2141  return 0;
2142  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2143 
2144  bzero(&servaddr, sizeof(servaddr));
2145  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2146  &servaddr.sin6_addr) <= 0)
2147  return 0;
2148  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2149 
2150  bzero(&servaddr, sizeof(servaddr));
2151  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2152  &servaddr.sin6_addr) <= 0)
2153  return 0;
2154  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2155 
2156  bzero(&servaddr, sizeof(servaddr));
2157  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2158  &servaddr.sin6_addr) <= 0)
2159  return 0;
2160  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2161 
2162  bzero(&servaddr, sizeof(servaddr));
2163  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2164  &servaddr.sin6_addr) <= 0)
2165  return 0;
2166  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2167 
2168  bzero(&servaddr, sizeof(servaddr));
2169  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2170  &servaddr.sin6_addr) <= 0)
2171  return 0;
2172  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2173 
2174  /* remove keys */
2175  bzero(&servaddr, sizeof(servaddr));
2176  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2177  &servaddr.sin6_addr) <= 0)
2178  return 0;
2179  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2180 
2181  bzero(&servaddr, sizeof(servaddr));
2182  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2183  &servaddr.sin6_addr) <= 0)
2184  return 0;
2185  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2186 
2187  bzero(&servaddr, sizeof(servaddr));
2188  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2189  &servaddr.sin6_addr) <= 0)
2190  return 0;
2191  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2192 
2193  bzero(&servaddr, sizeof(servaddr));
2194  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2195  &servaddr.sin6_addr) <= 0)
2196  return 0;
2197  SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree);
2198 
2199  /* test for existance */
2200  bzero(&servaddr, sizeof(servaddr));
2201  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2202  &servaddr.sin6_addr) <= 0)
2203  return 0;
2204  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2205 
2206  bzero(&servaddr, sizeof(servaddr));
2207  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2208  &servaddr.sin6_addr) <= 0)
2209  return 0;
2210  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2211 
2212  bzero(&servaddr, sizeof(servaddr));
2213  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2214  &servaddr.sin6_addr) <= 0)
2215  return 0;
2216  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2217 
2218  bzero(&servaddr, sizeof(servaddr));
2219  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2220  &servaddr.sin6_addr) <= 0)
2221  return 0;
2222  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2223 
2224  bzero(&servaddr, sizeof(servaddr));
2225  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2226  &servaddr.sin6_addr) <= 0)
2227  return 0;
2228  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2229 
2230  bzero(&servaddr, sizeof(servaddr));
2231  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2232  &servaddr.sin6_addr) <= 0)
2233  return 0;
2234  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2235 
2237 
2238  return result;
2239 }
2240 
2241 static int SCRadixTestIPV4NetblockInsertion09(void)
2242 {
2243  SCRadixTree *tree = NULL;
2244  struct sockaddr_in servaddr;
2245  int result = 1;
2246 
2247  tree = SCRadixCreateRadixTree(free, NULL);
2248 
2249  /* add the keys */
2250  bzero(&servaddr, sizeof(servaddr));
2251  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0)
2252  return 0;
2253  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2254 
2255  bzero(&servaddr, sizeof(servaddr));
2256  if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0)
2257  return 0;
2258  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2259 
2260  bzero(&servaddr, sizeof(servaddr));
2261  if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0)
2262  return 0;
2263  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2264 
2265  bzero(&servaddr, sizeof(servaddr));
2266  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2267  return 0;
2268  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2269 
2270  bzero(&servaddr, sizeof(servaddr));
2271  if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0)
2272  return 0;
2273  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2274 
2275  bzero(&servaddr, sizeof(servaddr));
2276  if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0)
2277  return 0;
2278  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2279 
2280  bzero(&servaddr, sizeof(servaddr));
2281  if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0)
2282  return 0;
2283  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2284 
2285  bzero(&servaddr, sizeof(servaddr));
2286  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2287  return 0;
2288  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2289 
2290  bzero(&servaddr, sizeof(servaddr));
2291  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2292  return 0;
2293  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2294 
2295  bzero(&servaddr, sizeof(servaddr));
2296  if (inet_pton(AF_INET, "192.171.192.0", &servaddr.sin_addr) <= 0)
2297  return 0;
2298  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2299 
2300  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2301  return 0;
2302  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2303 
2304  /* test for the existance of a key */
2305  bzero(&servaddr, sizeof(servaddr));
2306  if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0)
2307  return 0;
2308  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2309 
2310  bzero(&servaddr, sizeof(servaddr));
2311  if (inet_pton(AF_INET, "192.170.1.6", &servaddr.sin_addr) <= 0)
2312  return 0;
2313  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2314 
2315  bzero(&servaddr, sizeof(servaddr));
2316  if (inet_pton(AF_INET, "192.171.128.145", &servaddr.sin_addr) <= 0)
2317  return 0;
2318  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2319 
2320  bzero(&servaddr, sizeof(servaddr));
2321  if (inet_pton(AF_INET, "192.171.64.6", &servaddr.sin_addr) <= 0)
2322  return 0;
2323  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2324 
2325  bzero(&servaddr, sizeof(servaddr));
2326  if (inet_pton(AF_INET, "192.171.191.6", &servaddr.sin_addr) <= 0)
2327  return 0;
2328  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2329 
2330  bzero(&servaddr, sizeof(servaddr));
2331  if (inet_pton(AF_INET, "192.171.224.6", &servaddr.sin_addr) <= 0)
2332  return 0;
2333  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2334 
2335  bzero(&servaddr, sizeof(servaddr));
2336  if (inet_pton(AF_INET, "192.174.224.6", &servaddr.sin_addr) <= 0)
2337  return 0;
2338  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2339 
2340  bzero(&servaddr, sizeof(servaddr));
2341  if (inet_pton(AF_INET, "192.175.224.6", &servaddr.sin_addr) <= 0)
2342  return 0;
2343  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2344 
2346 
2347  return result;
2348 }
2349 
2350 static int SCRadixTestIPV4NetblockInsertion10(void)
2351 {
2352  SCRadixTree *tree = NULL;
2353  SCRadixNode *node[2];
2354  struct sockaddr_in servaddr;
2355  int result = 1;
2356 
2357  tree = SCRadixCreateRadixTree(free, NULL);
2358 
2359  /* add the keys */
2360  bzero(&servaddr, sizeof(servaddr));
2361  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2362  return 0;
2363  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2364 
2365  bzero(&servaddr, sizeof(servaddr));
2366  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2367  return 0;
2368  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2369 
2370  bzero(&servaddr, sizeof(servaddr));
2371  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2372  return 0;
2373  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2374 
2375  bzero(&servaddr, sizeof(servaddr));
2376  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2377  return 0;
2378  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2379 
2380  bzero(&servaddr, sizeof(servaddr));
2381  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2382  return 0;
2383  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2384 
2385  bzero(&servaddr, sizeof(servaddr));
2386  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2387  return 0;
2388  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2389 
2390  bzero(&servaddr, sizeof(servaddr));
2391  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2392  return 0;
2393  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2394 
2395  bzero(&servaddr, sizeof(servaddr));
2396  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2397  return 0;
2398  node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL,
2399  24);
2400 
2401  bzero(&servaddr, sizeof(servaddr));
2402  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2403  return 0;
2404  node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2405 
2406  bzero(&servaddr, sizeof(servaddr));
2407  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2408  return 0;
2409  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2410 
2411  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2412  return 0;
2413  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2414 
2415  /* test for the existance of a key */
2416  bzero(&servaddr, sizeof(servaddr));
2417  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2418  return 0;
2419  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
2420 
2421  bzero(&servaddr, sizeof(servaddr));
2422  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2423  return 0;
2424  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2425 
2426  bzero(&servaddr, sizeof(servaddr));
2427  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2428  return 0;
2429  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2430 
2431  bzero(&servaddr, sizeof(servaddr));
2432  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2433  return 0;
2434  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
2435 
2436  /* let us remove a netblock */
2437  bzero(&servaddr, sizeof(servaddr));
2438  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2439  return 0;
2440  SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 24);
2441 
2442  bzero(&servaddr, sizeof(servaddr));
2443  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2444  return 0;
2445  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2446 
2447  bzero(&servaddr, sizeof(servaddr));
2448  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2449  return 0;
2450  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2451 
2453 
2454  return result;
2455 }
2456 
2457 static int SCRadixTestIPV4NetblockInsertion11(void)
2458 {
2459  SCRadixTree *tree = NULL;
2460  SCRadixNode *node = NULL;
2461  struct sockaddr_in servaddr;
2462  int result = 1;
2463 
2464  tree = SCRadixCreateRadixTree(free, NULL);
2465 
2466  /* add the keys */
2467  bzero(&servaddr, sizeof(servaddr));
2468  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2469  return 0;
2470  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2471 
2472  bzero(&servaddr, sizeof(servaddr));
2473  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2474  return 0;
2475  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2476 
2477  bzero(&servaddr, sizeof(servaddr));
2478  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2479  return 0;
2480  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2481 
2482  bzero(&servaddr, sizeof(servaddr));
2483  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2484  return 0;
2485  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2486 
2487  bzero(&servaddr, sizeof(servaddr));
2488  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2489  return 0;
2490  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2491 
2492  bzero(&servaddr, sizeof(servaddr));
2493  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2494  return 0;
2495  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2496 
2497  bzero(&servaddr, sizeof(servaddr));
2498  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2499  return 0;
2500  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2501 
2502  bzero(&servaddr, sizeof(servaddr));
2503  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2504  return 0;
2505  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2506 
2507  bzero(&servaddr, sizeof(servaddr));
2508  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2509  return 0;
2510  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2511 
2512  bzero(&servaddr, sizeof(servaddr));
2513  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2514  return 0;
2515  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2516 
2517  if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0)
2518  return 0;
2519  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2520 
2521  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2522  return 0;
2523  node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 0);
2524 
2525  /* test for the existance of a key */
2526  bzero(&servaddr, sizeof(servaddr));
2527  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2528  return 0;
2529  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2530 
2531  bzero(&servaddr, sizeof(servaddr));
2532  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2533  return 0;
2534  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2535 
2536  bzero(&servaddr, sizeof(servaddr));
2537  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2538  return 0;
2539  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2540 
2541  bzero(&servaddr, sizeof(servaddr));
2542  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2543  return 0;
2544  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2545 
2546  bzero(&servaddr, sizeof(servaddr));
2547  if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0)
2548  return 0;
2549  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2550 
2551  bzero(&servaddr, sizeof(servaddr));
2552  if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0)
2553  return 0;
2554  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2555 
2556  bzero(&servaddr, sizeof(servaddr));
2557  if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0)
2558  return 0;
2559  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2560 
2561  bzero(&servaddr, sizeof(servaddr));
2562  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2563  return 0;
2564  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2565 
2566  bzero(&servaddr, sizeof(servaddr));
2567  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2568  return 0;
2569  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2570  SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != node);
2571 
2572  bzero(&servaddr, sizeof(servaddr));
2573  if (inet_pton(AF_INET, "245.63.62.121", &servaddr.sin_addr) <= 0)
2574  return 0;
2575  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2576  SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2577 
2578  bzero(&servaddr, sizeof(servaddr));
2579  if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0)
2580  return 0;
2581  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL &&
2582  SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node);
2583 
2584  /* remove node 0.0.0.0 */
2585  bzero(&servaddr, sizeof(servaddr));
2586  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2587  return 0;
2588  SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 0);
2589 
2590  bzero(&servaddr, sizeof(servaddr));
2591  if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0)
2592  return 0;
2593  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2594 
2595  bzero(&servaddr, sizeof(servaddr));
2596  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2597  return 0;
2598  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2599 
2600  bzero(&servaddr, sizeof(servaddr));
2601  if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0)
2602  return 0;
2603  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2604 
2605  bzero(&servaddr, sizeof(servaddr));
2606  if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0)
2607  return 0;
2608  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2609 
2610  bzero(&servaddr, sizeof(servaddr));
2611  if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0)
2612  return 0;
2613  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2614 
2615  bzero(&servaddr, sizeof(servaddr));
2616  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
2617  return 0;
2618  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2619 
2621 
2622  return result;
2623 }
2624 
2625 static int SCRadixTestIPV4NetblockInsertion12(void)
2626 {
2627  SCRadixTree *tree = NULL;
2628  SCRadixNode *node[2];
2629  struct sockaddr_in servaddr;
2630  int result = 1;
2631 
2632  tree = SCRadixCreateRadixTree(free, NULL);
2633 
2634  /* add the keys */
2635  bzero(&servaddr, sizeof(servaddr));
2636  if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0)
2637  return 0;
2638  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2639 
2640  bzero(&servaddr, sizeof(servaddr));
2641  if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0)
2642  return 0;
2643  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2644 
2645  bzero(&servaddr, sizeof(servaddr));
2646  if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0)
2647  return 0;
2648  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2649 
2650  bzero(&servaddr, sizeof(servaddr));
2651  if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0)
2652  return 0;
2653  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2654 
2655  bzero(&servaddr, sizeof(servaddr));
2656  if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0)
2657  return 0;
2658  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2659 
2660  bzero(&servaddr, sizeof(servaddr));
2661  if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0)
2662  return 0;
2663  SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2664 
2665  bzero(&servaddr, sizeof(servaddr));
2666  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
2667  return 0;
2668  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
2669 
2670  bzero(&servaddr, sizeof(servaddr));
2671  if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0)
2672  return 0;
2673  node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24);
2674 
2675  bzero(&servaddr, sizeof(servaddr));
2676  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2677  return 0;
2678  node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL);
2679 
2680  bzero(&servaddr, sizeof(servaddr));
2681  if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0)
2682  return 0;
2683  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18);
2684 
2685  if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0)
2686  return 0;
2687  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 32);
2688 
2689  /* test for the existance of a key */
2690  bzero(&servaddr, sizeof(servaddr));
2691  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2692  return 0;
2693  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
2694 
2695  bzero(&servaddr, sizeof(servaddr));
2696  if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0)
2697  return 0;
2698  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2699 
2700  bzero(&servaddr, sizeof(servaddr));
2701  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2702  return 0;
2703  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2704 
2705  bzero(&servaddr, sizeof(servaddr));
2706  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2707  return 0;
2708  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2709 
2710  bzero(&servaddr, sizeof(servaddr));
2711  if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0)
2712  return 0;
2713  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]);
2714 
2715  bzero(&servaddr, sizeof(servaddr));
2716  if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0)
2717  return 0;
2718  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]);
2719 
2720  bzero(&servaddr, sizeof(servaddr));
2721  if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0)
2722  return 0;
2723  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2724 
2725  bzero(&servaddr, sizeof(servaddr));
2726  if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0)
2727  return 0;
2728  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
2729 
2730  bzero(&servaddr, sizeof(servaddr));
2731  if (inet_pton(AF_INET, "225.175.21.224", &servaddr.sin_addr) <= 0)
2732  return 0;
2733  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2734 
2735  bzero(&servaddr, sizeof(servaddr));
2736  if (inet_pton(AF_INET, "225.175.21.229", &servaddr.sin_addr) <= 0)
2737  return 0;
2738  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2739 
2740  bzero(&servaddr, sizeof(servaddr));
2741  if (inet_pton(AF_INET, "225.175.21.230", &servaddr.sin_addr) <= 0)
2742  return 0;
2743  result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL);
2744 
2746 
2747  return result;
2748 }
2749 
2750 static int SCRadixTestIPV6NetblockInsertion13(void)
2751 {
2752  SCRadixTree *tree = NULL;
2753  struct sockaddr_in6 servaddr;
2754  int result = 1;
2755 
2756  tree = SCRadixCreateRadixTree(free, NULL);
2757 
2758  /* add the keys */
2759  bzero(&servaddr, sizeof(servaddr));
2760  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2761  &servaddr.sin6_addr) <= 0)
2762  return 0;
2763  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2764 
2765  bzero(&servaddr, sizeof(servaddr));
2766  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2767  &servaddr.sin6_addr) <= 0)
2768  return 0;
2769  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2770 
2771  bzero(&servaddr, sizeof(servaddr));
2772  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2773  &servaddr.sin6_addr) <= 0)
2774  return 0;
2775  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2776 
2777  bzero(&servaddr, sizeof(servaddr));
2778  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2779  &servaddr.sin6_addr) <= 0)
2780  return 0;
2781  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2782 
2783  bzero(&servaddr, sizeof(servaddr));
2784  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2785  &servaddr.sin6_addr) <= 0)
2786  return 0;
2787  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2788 
2789  bzero(&servaddr, sizeof(servaddr));
2790  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000",
2791  &servaddr.sin6_addr) <= 0)
2792  return 0;
2793  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56);
2794 
2795  bzero(&servaddr, sizeof(servaddr));
2796  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
2797  &servaddr.sin6_addr) <= 0)
2798  return 0;
2799  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2800 
2801  /* test the existence of keys */
2802  bzero(&servaddr, sizeof(servaddr));
2803  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2804  &servaddr.sin6_addr) <= 0)
2805  return 0;
2806  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2807 
2808  bzero(&servaddr, sizeof(servaddr));
2809  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2810  &servaddr.sin6_addr) <= 0)
2811  return 0;
2812  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2813 
2814  bzero(&servaddr, sizeof(servaddr));
2815  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2816  &servaddr.sin6_addr) <= 0)
2817  return 0;
2818  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2819 
2820  bzero(&servaddr, sizeof(servaddr));
2821  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2822  &servaddr.sin6_addr) <= 0)
2823  return 0;
2824  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2825 
2826  bzero(&servaddr, sizeof(servaddr));
2827  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2828  &servaddr.sin6_addr) <= 0)
2829  return 0;
2830  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2831 
2832  bzero(&servaddr, sizeof(servaddr));
2833  if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212",
2834  &servaddr.sin6_addr) <= 0)
2835  return 0;
2836  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2837 
2838  bzero(&servaddr, sizeof(servaddr));
2839  if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315",
2840  &servaddr.sin6_addr) <= 0)
2841  return 0;
2842  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2843 
2844  bzero(&servaddr, sizeof(servaddr));
2845  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2846  &servaddr.sin6_addr) <= 0)
2847  return 0;
2848  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2849 
2850  bzero(&servaddr, sizeof(servaddr));
2851  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212",
2852  &servaddr.sin6_addr) <= 0)
2853  return 0;
2854  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2855 
2856  bzero(&servaddr, sizeof(servaddr));
2857  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1146:6241",
2858  &servaddr.sin6_addr) <= 0)
2859  return 0;
2860  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2861 
2862  bzero(&servaddr, sizeof(servaddr));
2863  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1356:1241",
2864  &servaddr.sin6_addr) <= 0)
2865  return 0;
2866  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL);
2867 
2868  bzero(&servaddr, sizeof(servaddr));
2869  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DAAA:1245:2342:1146:6241",
2870  &servaddr.sin6_addr) <= 0)
2871  return 0;
2872  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2873 
2874 
2876 
2877  return result;
2878 }
2879 
2880 static int SCRadixTestIPV6NetblockInsertion14(void)
2881 {
2882  SCRadixTree *tree = NULL;
2883  SCRadixNode *node = NULL;
2884  struct sockaddr_in6 servaddr;
2885  int result = 1;
2886 
2887  tree = SCRadixCreateRadixTree(free, NULL);
2888 
2889  /* add the keys */
2890  bzero(&servaddr, sizeof(servaddr));
2891  if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315",
2892  &servaddr.sin6_addr) <= 0)
2893  return 0;
2894  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2895 
2896  bzero(&servaddr, sizeof(servaddr));
2897  if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432",
2898  &servaddr.sin6_addr) <= 0)
2899  return 0;
2900  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2901 
2902  bzero(&servaddr, sizeof(servaddr));
2903  if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861",
2904  &servaddr.sin6_addr) <= 0)
2905  return 0;
2906  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2907 
2908  bzero(&servaddr, sizeof(servaddr));
2909  if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315",
2910  &servaddr.sin6_addr) <= 0)
2911  return 0;
2912  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2913 
2914  bzero(&servaddr, sizeof(servaddr));
2915  if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375",
2916  &servaddr.sin6_addr) <= 0)
2917  return 0;
2918  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2919 
2920  bzero(&servaddr, sizeof(servaddr));
2921  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000",
2922  &servaddr.sin6_addr) <= 0)
2923  return 0;
2924  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56);
2925 
2926  bzero(&servaddr, sizeof(servaddr));
2927  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
2928  &servaddr.sin6_addr) <= 0)
2929  return 0;
2930  SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL);
2931 
2932  bzero(&servaddr, sizeof(servaddr));
2933  if (inet_pton(AF_INET6, "::", &servaddr.sin6_addr) <= 0)
2934  return 0;
2935  node = SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL,
2936  0);
2937 
2938  /* test the existence of keys */
2939  bzero(&servaddr, sizeof(servaddr));
2940  if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315",
2941  &servaddr.sin6_addr) <= 0)
2942  return 0;
2943  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL);
2944 
2945  bzero(&servaddr, sizeof(servaddr));
2946  if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315",
2947  &servaddr.sin6_addr) <= 0)
2948  return 0;
2949  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
2950 
2951  bzero(&servaddr, sizeof(servaddr));
2952  if (inet_pton(AF_INET6, "2004:0BF1:5346:B116:2362:8713:9124:2315",
2953  &servaddr.sin6_addr) <= 0)
2954  return 0;
2955  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
2956 
2957  bzero(&servaddr, sizeof(servaddr));
2958  if (inet_pton(AF_INET6, "2004:0B23:3252:BDEA:7422:8713:9124:2341",
2959  &servaddr.sin6_addr) <= 0)
2960  return 0;
2961  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node);
2962 
2963  bzero(&servaddr, sizeof(servaddr));
2964  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
2965  &servaddr.sin6_addr) <= 0)
2966  return 0;
2967  result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL &&
2968  SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node);
2969 
2970  bzero(&servaddr, sizeof(servaddr));
2971  if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241",
2972  &servaddr.sin6_addr) <= 0)
2973  return 0;
2974  result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL &&
2975  SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node);
2976 
2978 
2979  return result;
2980 }
2981 
2982 /**
2983  * \test Check that the best match search works for all the
2984  * possible netblocks of a fixed address
2985  */
2986 static int SCRadixTestIPV4NetBlocksAndBestSearch15(void)
2987 {
2988  SCRadixTree *tree = NULL;
2989  struct sockaddr_in servaddr;
2990  int result = 1;
2991 
2992  tree = SCRadixCreateRadixTree(free, NULL);
2993 
2994  uint32_t i = 0;
2995 
2996  uint32_t *user;
2997 
2998  bzero(&servaddr, sizeof(servaddr));
2999  if (inet_pton(AF_INET, "192.168.0.1", &servaddr.sin_addr) <= 0) {
3000  result = 0;
3001  goto end;
3002  }
3003 
3004  for (; i <= 32; i++) {
3005  user = SCMalloc(sizeof(uint32_t));
3006  if (unlikely(user == NULL)) {
3007  result = 0;
3008  goto end;
3009  }
3010 
3011  *user = i;
3012 
3013  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i);
3014 
3015  void *user_data = NULL;
3016  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3017  if (node == NULL) {
3018  printf("node == NULL: ");
3019  result = 0;
3020  goto end;
3021  }
3022 
3023  if (user_data == NULL) {
3024  printf("User data == NULL: ");
3025  result = 0;
3026  goto end;
3027  }
3028 
3029  if ( *( (uint32_t *)user_data) != i) {
3030  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3031  result = 0;
3032  goto end;
3033  }
3034  }
3035 
3036 end:
3038 
3039  return result;
3040 }
3041 
3042 /**
3043  * \test Check that the best match search works for all the
3044  * possible netblocks of a fixed address
3045  */
3046 static int SCRadixTestIPV4NetBlocksAndBestSearch16(void)
3047 {
3048  SCRadixTree *tree = NULL;
3049  struct sockaddr_in servaddr;
3050  int result = 1;
3051 
3052  tree = SCRadixCreateRadixTree(free, NULL);
3053 
3054  uint32_t i = 0;
3055 
3056  uint32_t *user;
3057 
3058  bzero(&servaddr, sizeof(servaddr));
3059  if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) {
3060  result = 0;
3061  goto end;
3062  }
3063 
3064  for (; i <= 32; i++) {
3065  user = SCMalloc(sizeof(uint32_t));
3066  if (unlikely(user == NULL)) {
3067  result = 0;
3068  goto end;
3069  }
3070 
3071  *user = i;
3072 
3073  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i);
3074 
3075  void *user_data = NULL;
3076  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3077  if (node == NULL) {
3078  printf("node == NULL: ");
3079  result = 0;
3080  goto end;
3081  }
3082 
3083  if (user_data == NULL) {
3084  printf("User data == NULL: ");
3085  result = 0;
3086  goto end;
3087  }
3088 
3089  if ( *( (uint32_t *)user_data) != i) {
3090  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3091  result = 0;
3092  goto end;
3093  }
3094  }
3095 
3096 end:
3098 
3099  return result;
3100 }
3101 
3102 /**
3103  * \test Check that the best match search works for all the
3104  * possible netblocks of a fixed address
3105  */
3106 static int SCRadixTestIPV4NetBlocksAndBestSearch17(void)
3107 {
3108  SCRadixTree *tree = NULL;
3109  struct sockaddr_in servaddr;
3110  int result = 1;
3111 
3112  tree = SCRadixCreateRadixTree(free, NULL);
3113 
3114  uint32_t i = 0;
3115 
3116  uint32_t *user;
3117 
3118  bzero(&servaddr, sizeof(servaddr));
3119  if (inet_pton(AF_INET, "10.0.0.1", &servaddr.sin_addr) <= 0) {
3120  result = 0;
3121  goto end;
3122  }
3123 
3124  for (; i <= 32; i++) {
3125  user = SCMalloc(sizeof(uint32_t));
3126  if (unlikely(user == NULL)) {
3127  result = 0;
3128  goto end;
3129  }
3130 
3131  *user = i;
3132 
3133  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i);
3134 
3135  void *user_data = NULL;
3136  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3137  if (node == NULL) {
3138  printf("node == NULL: ");
3139  result = 0;
3140  goto end;
3141  }
3142 
3143  if (user_data == NULL) {
3144  printf("User data == NULL: ");
3145  result = 0;
3146  goto end;
3147  }
3148 
3149  if ( *( (uint32_t *)user_data) != i) {
3150  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3151  result = 0;
3152  goto end;
3153  }
3154  }
3155 
3156 end:
3158 
3159  return result;
3160 }
3161 
3162 /**
3163  * \test Check that the best match search works for all the
3164  * possible netblocks of a fixed address
3165  */
3166 static int SCRadixTestIPV4NetBlocksAndBestSearch18(void)
3167 {
3168  SCRadixTree *tree = NULL;
3169  struct sockaddr_in servaddr;
3170  int result = 1;
3171 
3172  tree = SCRadixCreateRadixTree(free, NULL);
3173 
3174  uint32_t i = 0;
3175 
3176  uint32_t *user;
3177 
3178  bzero(&servaddr, sizeof(servaddr));
3179  if (inet_pton(AF_INET, "172.26.0.1", &servaddr.sin_addr) <= 0) {
3180  result = 0;
3181  goto end;
3182  }
3183 
3184  for (; i <= 32; i++) {
3185  user = SCMalloc(sizeof(uint32_t));
3186  if (unlikely(user == NULL)) {
3187  result = 0;
3188  goto end;
3189  }
3190 
3191  *user = i;
3192 
3193  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i);
3194 
3195  void *user_data = NULL;
3196  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3197  if (node == NULL) {
3198  printf("node == NULL: ");
3199  result = 0;
3200  goto end;
3201  }
3202 
3203  if (user_data == NULL) {
3204  printf("User data == NULL: ");
3205  result = 0;
3206  goto end;
3207  }
3208 
3209  if ( *( (uint32_t *)user_data) != i) {
3210  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3211  result = 0;
3212  goto end;
3213  }
3214  }
3215 
3216 end:
3218 
3219  return result;
3220 }
3221 
3222 /**
3223  * \test Check special combinations of netblocks and addresses
3224  * on best search checking the returned userdata
3225  */
3226 static int SCRadixTestIPV4NetBlocksAndBestSearch19(void)
3227 {
3228  SCRadixTree *tree = NULL;
3229  struct sockaddr_in servaddr;
3230  int result = 1;
3231  void *user_data = NULL;
3232 
3233  tree = SCRadixCreateRadixTree(free, NULL);
3234 
3235  uint32_t *user;
3236 
3237  bzero(&servaddr, sizeof(servaddr));
3238  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) {
3239  result = 0;
3240  goto end;
3241  }
3242 
3243  user = SCMalloc(sizeof(uint32_t));
3244  if (unlikely(user == NULL)) {
3245  result = 0;
3246  goto end;
3247  }
3248 
3249  *user = 100;
3250 
3251  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 0);
3252 
3253  bzero(&servaddr, sizeof(servaddr));
3254  if (inet_pton(AF_INET, "192.168.1.15", &servaddr.sin_addr) <= 0) {
3255  result = 0;
3256  goto end;
3257  }
3258 
3259  SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3260  if (node == NULL) {
3261  printf("node == NULL: ");
3262  result = 0;
3263  goto end;
3264  }
3265 
3266  if (user_data == NULL) {
3267  printf("User data == NULL: ");
3268  result = 0;
3269  goto end;
3270  }
3271 
3272  if ( *( (uint32_t *)user_data) != 100) {
3273  result = 0;
3274  goto end;
3275  }
3276 
3277  user_data = NULL;
3278 
3279  bzero(&servaddr, sizeof(servaddr));
3280  if (inet_pton(AF_INET, "177.0.0.0", &servaddr.sin_addr) <= 0) {
3281  result = 0;
3282  goto end;
3283  }
3284 
3285  user = SCMalloc(sizeof(uint32_t));
3286  if (unlikely(user == NULL)) {
3287  result = 0;
3288  goto end;
3289  }
3290 
3291  *user = 200;
3292 
3293  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 8);
3294 
3295  bzero(&servaddr, sizeof(servaddr));
3296  if (inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0) {
3297  result = 0;
3298  goto end;
3299  }
3300 
3301  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3302  if (node == NULL) {
3303  printf("node == NULL: ");
3304  result = 0;
3305  goto end;
3306  }
3307 
3308  if (user_data == NULL) {
3309  printf("User data == NULL: ");
3310  result = 0;
3311  goto end;
3312  }
3313 
3314  if ( *( (uint32_t *)user_data) != 200) {
3315  result = 0;
3316  goto end;
3317  }
3318 
3319  user_data = NULL;
3320 
3321  bzero(&servaddr, sizeof(servaddr));
3322  if (inet_pton(AF_INET, "178.168.1.15", &servaddr.sin_addr) <= 0) {
3323  result = 0;
3324  goto end;
3325  }
3326 
3327  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3328  if (node == NULL) {
3329  printf("node == NULL: ");
3330  result = 0;
3331  goto end;
3332  }
3333 
3334  if (user_data == NULL) {
3335  printf("User data == NULL: ");
3336  result = 0;
3337  goto end;
3338  }
3339 
3340  if ( *( (uint32_t*)user_data) != 100) {
3341  result = 0;
3342  goto end;
3343  }
3344 
3345  user_data = NULL;
3346  bzero(&servaddr, sizeof(servaddr));
3347  if (inet_pton(AF_INET, "177.168.0.0", &servaddr.sin_addr) <= 0) {
3348  result = 0;
3349  goto end;
3350  }
3351 
3352  user = SCMalloc(sizeof(uint32_t));
3353  if (unlikely(user == NULL)) {
3354  result = 0;
3355  goto end;
3356  }
3357 
3358  *user = 300;
3359 
3360  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 12);
3361 
3362  bzero(&servaddr, sizeof(servaddr));
3363  if (inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0) {
3364  result = 0;
3365  goto end;
3366  }
3367 
3368  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3369  if (node == NULL) {
3370  printf("node == NULL: ");
3371  result = 0;
3372  goto end;
3373  }
3374 
3375  if (user_data == NULL) {
3376  printf("User data == NULL: ");
3377  result = 0;
3378  goto end;
3379  }
3380 
3381  if ( *( (uint32_t*)user_data) != 300) {
3382  result = 0;
3383  goto end;
3384  }
3385 
3386  user_data = NULL;
3387  bzero(&servaddr, sizeof(servaddr));
3388  if (inet_pton(AF_INET, "177.167.1.15", &servaddr.sin_addr) <= 0) {
3389  result = 0;
3390  goto end;
3391  }
3392 
3393  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3394  if (node == NULL) {
3395  printf("node == NULL: ");
3396  result = 0;
3397  goto end;
3398  }
3399 
3400  if (user_data == NULL) {
3401  printf("User data == NULL: ");
3402  result = 0;
3403  goto end;
3404  }
3405 
3406  if ( *( (uint32_t *)user_data) != 300) {
3407  result = 0;
3408  goto end;
3409  }
3410 
3411  user_data = NULL;
3412  bzero(&servaddr, sizeof(servaddr));
3413  if (inet_pton(AF_INET, "177.178.1.15", &servaddr.sin_addr) <= 0) {
3414  result = 0;
3415  goto end;
3416  }
3417 
3418  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3419  if (node == NULL) {
3420  printf("node == NULL: ");
3421  result = 0;
3422  goto end;
3423  }
3424 
3425  if (user_data == NULL) {
3426  printf("User data == NULL: ");
3427  result = 0;
3428  goto end;
3429  }
3430 
3431  if ( *( (uint32_t *)user_data) != 200) {
3432  result = 0;
3433  goto end;
3434  }
3435 
3436  user_data = NULL;
3437  bzero(&servaddr, sizeof(servaddr));
3438  if (inet_pton(AF_INET, "197.178.1.15", &servaddr.sin_addr) <= 0) {
3439  result = 0;
3440  goto end;
3441  }
3442 
3443  node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data);
3444  if (node == NULL) {
3445  printf("node == NULL: ");
3446  result = 0;
3447  goto end;
3448  }
3449 
3450  if (user_data == NULL) {
3451  printf("User data == NULL: ");
3452  result = 0;
3453  goto end;
3454  }
3455 
3456  if ( *( (uint32_t *)user_data) != 100) {
3457  result = 0;
3458  goto end;
3459  }
3460 
3461 
3462 end:
3464 
3465  return result;
3466 }
3467 
3468 /**
3469  * \test Check that the best match search works for all the
3470  * possible netblocks of a fixed address
3471  */
3472 static int SCRadixTestIPV6NetBlocksAndBestSearch20(void)
3473 {
3474  SCRadixTree *tree = NULL;
3475  struct sockaddr_in6 servaddr;
3476  int result = 1;
3477 
3478  tree = SCRadixCreateRadixTree(free, NULL);
3479 
3480  uint32_t i = 0;
3481 
3482  uint32_t *user;
3483 
3484  bzero(&servaddr, sizeof(servaddr));
3485  if (inet_pton(AF_INET6, "ABAB:CDCD:ABAB:CDCD:1234:4321:1234:4321", &servaddr.sin6_addr) <= 0) {
3486  result = 0;
3487  goto end;
3488  }
3489 
3490  for (; i <= 128; i++) {
3491  user = SCMalloc(sizeof(uint32_t));
3492  if (unlikely(user == NULL)) {
3493  result = 0;
3494  goto end;
3495  }
3496 
3497  *user = i;
3498 
3499  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i);
3500 
3501  void *user_data = NULL;
3502  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3503  if (node == NULL) {
3504  printf("node == NULL: ");
3505  result = 0;
3506  goto end;
3507  }
3508 
3509  if (user_data == NULL) {
3510  printf("User data == NULL: ");
3511  result = 0;
3512  goto end;
3513  }
3514 
3515  if ( *( (uint32_t *)user_data) != i) {
3516  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3517  result = 0;
3518  goto end;
3519  }
3520  }
3521 
3522 end:
3524 
3525  return result;
3526 }
3527 
3528 /**
3529  * \test Check that the best match search works for all the
3530  * possible netblocks of a fixed address
3531  */
3532 static int SCRadixTestIPV6NetBlocksAndBestSearch21(void)
3533 {
3534  SCRadixTree *tree = NULL;
3535  struct sockaddr_in6 servaddr;
3536  int result = 1;
3537 
3538  tree = SCRadixCreateRadixTree(free, NULL);
3539 
3540  uint32_t i = 0;
3541 
3542  uint32_t *user;
3543 
3544  bzero(&servaddr, sizeof(servaddr));
3545  if (inet_pton(AF_INET6, "ff00::1", &servaddr.sin6_addr) <= 0) {
3546  result = 0;
3547  goto end;
3548  }
3549 
3550  for (; i <= 128; i++) {
3551  user = SCMalloc(sizeof(uint32_t));
3552  if (unlikely(user == NULL)) {
3553  result = 0;
3554  goto end;
3555  }
3556 
3557  *user = i;
3558 
3559  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i);
3560 
3561  void *user_data = NULL;
3562  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3563  if (node == NULL) {
3564  printf("node == NULL: ");
3565  result = 0;
3566  goto end;
3567  }
3568 
3569  if (user_data == NULL) {
3570  printf("User data == NULL: ");
3571  result = 0;
3572  goto end;
3573  }
3574 
3575  if ( *( (uint32_t *)user_data) != i) {
3576  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3577  result = 0;
3578  goto end;
3579  }
3580  }
3581 
3582 end:
3584 
3585  return result;
3586 }
3587 
3588 /**
3589  * \test Check that the best match search works for all the
3590  * possible netblocks of a fixed address
3591  */
3592 static int SCRadixTestIPV6NetBlocksAndBestSearch22(void)
3593 {
3594  SCRadixTree *tree = NULL;
3595  struct sockaddr_in6 servaddr;
3596  int result = 1;
3597 
3598  tree = SCRadixCreateRadixTree(free, NULL);
3599 
3600  uint32_t i = 0;
3601 
3602  uint32_t *user;
3603 
3604  bzero(&servaddr, sizeof(servaddr));
3605  if (inet_pton(AF_INET6, "ff00::192:168:1:1", &servaddr.sin6_addr) <= 0) {
3606  result = 0;
3607  goto end;
3608  }
3609 
3610  for (; i <= 128; i++) {
3611  user = SCMalloc(sizeof(uint32_t));
3612  if (unlikely(user == NULL)) {
3613  result = 0;
3614  goto end;
3615  }
3616 
3617  *user = i;
3618 
3619  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i);
3620 
3621  void *user_data = NULL;
3622  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3623  if (node == NULL) {
3624  printf("node == NULL: ");
3625  result = 0;
3626  goto end;
3627  }
3628 
3629  if (user_data == NULL) {
3630  printf("User data == NULL: ");
3631  result = 0;
3632  goto end;
3633  }
3634 
3635  if ( *( (uint32_t *)user_data) != i) {
3636  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3637  result = 0;
3638  goto end;
3639  }
3640  }
3641 
3642 end:
3644 
3645  return result;
3646 }
3647 
3648 /**
3649  * \test Check that the best match search works for all the
3650  * possible netblocks of a fixed address
3651  */
3652 static int SCRadixTestIPV6NetBlocksAndBestSearch23(void)
3653 {
3654  SCRadixTree *tree = NULL;
3655  struct sockaddr_in6 servaddr;
3656  int result = 1;
3657 
3658  tree = SCRadixCreateRadixTree(free, NULL);
3659 
3660  uint32_t i = 0;
3661 
3662  uint32_t *user;
3663 
3664  bzero(&servaddr, sizeof(servaddr));
3665  if (inet_pton(AF_INET6, "FF00:ABCD:BCDA::ABCD", &servaddr.sin6_addr) <= 0) {
3666  result = 0;
3667  goto end;
3668  }
3669 
3670  for (; i <= 128; i++) {
3671  user = SCMalloc(sizeof(uint32_t));
3672  if (unlikely(user == NULL)) {
3673  result = 0;
3674  goto end;
3675  }
3676 
3677  *user = i;
3678 
3679  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i);
3680 
3681  void *user_data = NULL;
3682  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3683  if (node == NULL) {
3684  printf("node == NULL: ");
3685  result = 0;
3686  goto end;
3687  }
3688 
3689  if (user_data == NULL) {
3690  printf("User data == NULL: ");
3691  result = 0;
3692  goto end;
3693  }
3694 
3695  if ( *( (uint32_t *)user_data) != i) {
3696  printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i);
3697  result = 0;
3698  goto end;
3699  }
3700  }
3701 
3702 end:
3704 
3705  return result;
3706 }
3707 
3708 /**
3709  * \test Check special combinations of netblocks and addresses
3710  * on best search checking the returned userdata
3711  */
3712 static int SCRadixTestIPV6NetBlocksAndBestSearch24(void)
3713 {
3714  SCRadixTree *tree = NULL;
3715  struct sockaddr_in6 servaddr;
3716  int result = 1;
3717  void *user_data = NULL;
3718 
3719  tree = SCRadixCreateRadixTree(free, NULL);
3720 
3721  uint32_t *user;
3722 
3723  bzero(&servaddr, sizeof(servaddr));
3724  if (inet_pton(AF_INET6, "::", &servaddr.sin6_addr) <= 0) {
3725  result = 0;
3726  goto end;
3727  }
3728 
3729  user = SCMalloc(sizeof(uint32_t));
3730  if (unlikely(user == NULL)) {
3731  result = 0;
3732  goto end;
3733  }
3734 
3735  *user = 100;
3736 
3737  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 0);
3738 
3739  bzero(&servaddr, sizeof(servaddr));
3740  if (inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0) {
3741  result = 0;
3742  goto end;
3743  }
3744 
3745  SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3746  if (node == NULL) {
3747  printf("node == NULL: ");
3748  result = 0;
3749  goto end;
3750  }
3751 
3752  if (user_data == NULL) {
3753  printf("User data == NULL: ");
3754  result = 0;
3755  goto end;
3756  }
3757 
3758  if ( *( (uint32_t*)user_data) != 100) {
3759  result = 0;
3760  goto end;
3761  }
3762 
3763  user_data = NULL;
3764  bzero(&servaddr, sizeof(servaddr));
3765  if (inet_pton(AF_INET6, "ABCD::0", &servaddr.sin6_addr) <= 0) {
3766  result = 0;
3767  goto end;
3768  }
3769 
3770  user = SCMalloc(sizeof(uint32_t));
3771  if (unlikely(user == NULL)) {
3772  result = 0;
3773  goto end;
3774  }
3775 
3776  *user = 200;
3777 
3778  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 8);
3779 
3780  bzero(&servaddr, sizeof(servaddr));
3781  if (inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0) {
3782  result = 0;
3783  goto end;
3784  }
3785 
3786  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3787  if (node == NULL) {
3788  printf("node == NULL: ");
3789  result = 0;
3790  goto end;
3791  }
3792 
3793  if (user_data == NULL) {
3794  printf("User data == NULL: ");
3795  result = 0;
3796  goto end;
3797  }
3798 
3799  if ( *( (uint32_t *)user_data) != 200) {
3800  printf("User data == %"PRIu32"; i != 200 ", *( (uint32_t *)user_data));
3801  result = 0;
3802  goto end;
3803  }
3804 
3805  user_data = NULL;
3806  bzero(&servaddr, sizeof(servaddr));
3807  if (inet_pton(AF_INET6, "DCBA::1", &servaddr.sin6_addr) <= 0) {
3808  result = 0;
3809  goto end;
3810  }
3811 
3812  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3813  if (node == NULL) {
3814  printf("node == NULL: ");
3815  result = 0;
3816  goto end;
3817  }
3818 
3819  if (user_data == NULL) {
3820  printf("User data == NULL: ");
3821  result = 0;
3822  goto end;
3823  }
3824 
3825  if ( *( (uint32_t *)user_data) != 100) {
3826  printf("User data == %"PRIu32"; != 100 ", *( (uint32_t *)user_data));
3827  result = 0;
3828  goto end;
3829  }
3830 
3831  user_data = NULL;
3832  bzero(&servaddr, sizeof(servaddr));
3833  if (inet_pton(AF_INET6, "ABCD:ABCD::0", &servaddr.sin6_addr) <= 0) {
3834  result = 0;
3835  goto end;
3836  }
3837 
3838  user = SCMalloc(sizeof(uint32_t));
3839  if (unlikely(user == NULL)) {
3840  result = 0;
3841  goto end;
3842  }
3843 
3844  *user = 300;
3845 
3846  SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 12);
3847 
3848  bzero(&servaddr, sizeof(servaddr));
3849  if (inet_pton(AF_INET6, "ABCD:ABCD::1", &servaddr.sin6_addr) <= 0) {
3850  result = 0;
3851  goto end;
3852  }
3853 
3854  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3855  if (node == NULL) {
3856  printf("node == NULL: ");
3857  result = 0;
3858  goto end;
3859  }
3860 
3861  if (user_data == NULL) {
3862  printf("User data == NULL: ");
3863  result = 0;
3864  goto end;
3865  }
3866 
3867  if ( *( (uint32_t *)user_data) != 300) {
3868  result = 0;
3869  goto end;
3870  }
3871 
3872  user_data = NULL;
3873  bzero(&servaddr, sizeof(servaddr));
3874  if (inet_pton(AF_INET6, "ABCD:AAAA::1", &servaddr.sin6_addr) <= 0) {
3875  result = 0;
3876  goto end;
3877  }
3878 
3879  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3880  if (node == NULL) {
3881  printf("node == NULL: ");
3882  result = 0;
3883  goto end;
3884  }
3885 
3886  if (user_data == NULL) {
3887  printf("User data == NULL: ");
3888  result = 0;
3889  goto end;
3890  }
3891 
3892  if ( *( (uint32_t *)user_data) != 300) {
3893  result = 0;
3894  goto end;
3895  }
3896 
3897  user_data = NULL;
3898  bzero(&servaddr, sizeof(servaddr));
3899  if (inet_pton(AF_INET6, "ABAB::1", &servaddr.sin6_addr) <= 0) {
3900  result = 0;
3901  goto end;
3902  }
3903 
3904  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3905  if (node == NULL) {
3906  printf("node == NULL: ");
3907  result = 0;
3908  goto end;
3909  }
3910 
3911  if (user_data == NULL) {
3912  printf("User data == NULL: ");
3913  result = 0;
3914  goto end;
3915  }
3916 
3917  if ( *( (uint32_t *)user_data) != 200) {
3918  result = 0;
3919  goto end;
3920  }
3921 
3922  user_data = NULL;
3923  bzero(&servaddr, sizeof(servaddr));
3924  if (inet_pton(AF_INET6, "CABD::1", &servaddr.sin6_addr) <= 0) {
3925  result = 0;
3926  goto end;
3927  }
3928 
3929  node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data);
3930  if (node == NULL) {
3931  printf("node == NULL: ");
3932  result = 0;
3933  goto end;
3934  }
3935 
3936  if (user_data == NULL) {
3937  printf("User data == NULL: ");
3938  result = 0;
3939  goto end;
3940  }
3941 
3942  if ( *( (uint32_t *)user_data) != 100) {
3943  result = 0;
3944  goto end;
3945  }
3946 
3947 
3948 end:
3950 
3951  return result;
3952 }
3953 
3954 
3955 /**
3956  * \test SCRadixTestIPV4NetblockInsertion15 insert a node searching on it.
3957  * Should always return true but the purposse of the test is to monitor
3958  * the memory usage to detect memleaks (there was one on searching)
3959  */
3960 static int SCRadixTestIPV4NetblockInsertion25(void)
3961 {
3962  SCRadixTree *tree = NULL;
3963  struct sockaddr_in servaddr;
3964  int result = 1;
3965 
3966  tree = SCRadixCreateRadixTree(free, NULL);
3967 
3968  bzero(&servaddr, sizeof(servaddr));
3969  if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0)
3970  return 0;
3971  SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16);
3972 
3973  /* test for the existance of a key */
3974  bzero(&servaddr, sizeof(servaddr));
3975  if (inet_pton(AF_INET, "192.168.128.53", &servaddr.sin_addr) <= 0)
3976  return 0;
3977 
3978  result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL);
3979 
3981 
3982  return result;
3983 }
3984 
3985 /**
3986  * \test SCRadixTestIPV4NetblockInsertion26 insert a node searching on it.
3987  * Should always return true but the purposse of the test is to monitor
3988  * the memory usage to detect memleaks (there was one on searching)
3989  */
3990 static int SCRadixTestIPV4NetblockInsertion26(void)
3991 {
3992  SCRadixNode *tmp = NULL;
3993  SCRadixTree *tree = NULL;
3994  struct sockaddr_in servaddr;
3995  int result = 1;
3996  char *str = SCStrdup("Hello1");
3997 
3998  tree = SCRadixCreateRadixTree(free, NULL);
3999 
4000  bzero(&servaddr, sizeof(servaddr));
4001  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0)
4002  return 0;
4003  tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 0);
4004  if (!tmp) {
4005  printf("Not inserted correctly 1:");
4006  result = 0;
4007  goto this_end;
4008  }
4009  str = SCStrdup("Hello1");
4010 
4011  bzero(&servaddr, sizeof(servaddr));
4012  if (inet_pton(AF_INET, "176.0.0.1", &servaddr.sin_addr) <= 0)
4013  return 0;
4014  tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 5);
4015  if (!tmp) {
4016  printf("Not inserted correctly 2:");
4017  result = 0;
4018  goto this_end;
4019  }
4020 
4021  str = SCStrdup("Hello1");
4022  bzero(&servaddr, sizeof(servaddr));
4023  if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) {
4024  SCFree(str);
4025  return 0;
4026  }
4027  tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 7);
4028  if (!tmp) {
4029  printf("Not inserted correctly 3:");
4030  result = 0;
4031  goto this_end;
4032  }
4033 
4034  /* test for the existance of a key */
4035  //result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree) != NULL);
4036 
4037 this_end:
4039 
4040  //SCFree(str);
4041  return result;
4042 }
4043 
4044 #endif
4045 
4047 {
4048 
4049 #ifdef UNITTESTS
4050  UtRegisterTest("SCRadixTestIPV4Insertion03", SCRadixTestIPV4Insertion03);
4051  UtRegisterTest("SCRadixTestIPV4Removal04", SCRadixTestIPV4Removal04);
4052  UtRegisterTest("SCRadixTestIPV6Insertion07", SCRadixTestIPV6Insertion07);
4053  UtRegisterTest("SCRadixTestIPV6Removal08", SCRadixTestIPV6Removal08);
4054  UtRegisterTest("SCRadixTestIPV4NetblockInsertion09",
4055  SCRadixTestIPV4NetblockInsertion09);
4056  UtRegisterTest("SCRadixTestIPV4NetblockInsertion10",
4057  SCRadixTestIPV4NetblockInsertion10);
4058  UtRegisterTest("SCRadixTestIPV4NetblockInsertion11",
4059  SCRadixTestIPV4NetblockInsertion11);
4060  UtRegisterTest("SCRadixTestIPV4NetblockInsertion12",
4061  SCRadixTestIPV4NetblockInsertion12);
4062  UtRegisterTest("SCRadixTestIPV6NetblockInsertion13",
4063  SCRadixTestIPV6NetblockInsertion13);
4064  UtRegisterTest("SCRadixTestIPV6NetblockInsertion14",
4065  SCRadixTestIPV6NetblockInsertion14);
4066  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch15",
4067  SCRadixTestIPV4NetBlocksAndBestSearch15);
4068  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch16",
4069  SCRadixTestIPV4NetBlocksAndBestSearch16);
4070  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch17",
4071  SCRadixTestIPV4NetBlocksAndBestSearch17);
4072  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch18",
4073  SCRadixTestIPV4NetBlocksAndBestSearch18);
4074  UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch19",
4075  SCRadixTestIPV4NetBlocksAndBestSearch19);
4076  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch20",
4077  SCRadixTestIPV6NetBlocksAndBestSearch20);
4078  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch21",
4079  SCRadixTestIPV6NetBlocksAndBestSearch21);
4080  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch22",
4081  SCRadixTestIPV6NetBlocksAndBestSearch22);
4082  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch23",
4083  SCRadixTestIPV6NetBlocksAndBestSearch23);
4084  UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch24",
4085  SCRadixTestIPV6NetBlocksAndBestSearch24);
4086  UtRegisterTest("SCRadixTestIPV4NetblockInsertion25",
4087  SCRadixTestIPV4NetblockInsertion25);
4088  UtRegisterTest("SCRadixTestIPV4NetblockInsertion26",
4089  SCRadixTestIPV4NetblockInsertion26);
4090 #endif
4091 
4092  return;
4093 }
struct SCRadixNode_ * parent
SCRadixPrefix * prefix
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:490
#define SCLogDebug(...)
Definition: util-debug.h:335
struct SCRadixUserData_ * next
struct SCRadixNode_ * left
#define bzero(s, n)
Definition: win32-misc.h:32
size_t strlcpy(char *dst, const char *src, size_t siz)
Definition: util-strlcpyu.c:43
uint8_t * stream
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.240.1 would be chopped to 192.168.224.0 against a netmask value of 19.
Definition: util-ip.c:187
#define unlikely(expr)
Definition: util-optimize.h:35
Structure for the prefix/key in the radix tree.
void(* Free)(void *)
SCRadixNode * SCRadixFindKeyIPV4ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV4 address is present in the tree.
uint16_t src
void(* PrintData)(void *)
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.
void SCRadixPrintTree(SCRadixTree *tree)
Prints the Radix Tree. While printing the radix tree we use the following format. ...
SCRadixTree * SCRadixCreateRadixTree(void(*Free)(void *), void(*PrintData)(void *))
Creates a new Radix tree.
#define SC_RADIX_BITTEST(x, y)
void SCRadixRegisterTests(void)
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...
SCRadixNode * SCRadixAddKeyIPV6String(const char *str, SCRadixTree *tree, void *user)
Adds a new IPV6/netblock to the Radix tree from a string.
SCRadixNode * SCRadixAddKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, void *user, uint8_t netmask)
Adds a new IPV4 netblock to the Radix tree.
void SCRadixReleaseRadixTree(SCRadixTree *tree)
Frees a Radix tree and all its nodes.
#define str(s)
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.
SCRadixNode * SCRadixAddKeyIPV4(uint8_t *key_stream, SCRadixTree *tree, void *user)
Adds a new IPV4 address to the Radix tree.
#define SCLogError(err_code,...)
Macro used to log ERROR messages.
Definition: util-debug.h:294
SCRadixNode * SCRadixFindKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, SCRadixTree *tree, void **user_data_result)
Checks if a key is present in the tree.
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
Structure for the node in the radix tree.
SCRadixNode * SCRadixAddKeyIPV4String(const char *str, SCRadixTree *tree, void *user)
Adds a new IPV4/netblock to the Radix tree from a string.
SCRadixNode * head
struct SCRadixNode_ * right
#define SCRealloc(x, a)
Definition: util-mem.h:190
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.
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.
#define SCMalloc(a)
Definition: util-mem.h:174
#define SCFree(a)
Definition: util-mem.h:236
SCRadixNode * SCRadixAddKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, SCRadixTree *tree, void *user)
Adds a new generic key to the Radix tree.
void SCRadixRemoveKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, SCRadixTree *tree)
Removes a key from the Radix tree.
Structure that hold the user data and the netmask associated with it.
void SCRadixPrintNodeInfo(SCRadixNode *node, int level, void(*PrintData)(void *))
Prints the node information from a Radix tree.
SCRadixNode * SCRadixFindKeyIPV6ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
Checks if an IPV6 address is present in the tree.
#define SCStrdup(a)
Definition: util-mem.h:220
SCRadixNode * SCRadixAddKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, void *user, uint8_t netmask)
Adds a new IPV6 netblock to the Radix tree.
void SCRadixRemoveKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask)
Removes an IPV6 netblock address key from the Radix tree.
SCRadixNode * SCRadixAddKeyIPV6(uint8_t *key_stream, SCRadixTree *tree, void *user)
Adds a new IPV6 address to the Radix tree.
void SCRadixRemoveKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, uint8_t netmask)
Removes an IPV4 address netblock key from the Radix tree.
Structure for the radix tree.
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...
SCRadixUserData * user_data
uint8_t * netmasks