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