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  */
SCRadixAllocSCRadixUserData(uint8_t netmask,void * user)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  */
SCRadixDeAllocSCRadixUserData(SCRadixUserData * user_data)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  */
SCRadixAppendToSCRadixUserDataList(SCRadixUserData * new,SCRadixUserData ** list)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  */
SCRadixCreatePrefix(uint8_t * key_stream,uint16_t key_bitlen,void * user,uint8_t netmask)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  */
SCRadixAddNetmaskUserDataToPrefix(SCRadixPrefix * prefix,uint8_t netmask,void * user)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  */
SCRadixRemoveNetmaskUserDataFromPrefix(SCRadixPrefix * prefix,uint8_t netmask)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  */
SCRadixPrefixContainNetmask(SCRadixPrefix * prefix,uint8_t netmask)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  */
SCRadixPrefixNetmaskCount(SCRadixPrefix * prefix)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  */
SCRadixPrefixContainNetmaskAndSetUserData(SCRadixPrefix * prefix,uint16_t netmask,int exact_match,void ** user_data_result)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  */
SCRadixReleasePrefix(SCRadixPrefix * prefix,SCRadixTree * tree)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  */
SCRadixCreateNode(void)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  */
SCRadixReleaseNode(SCRadixNode * node,SCRadixTree * tree)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  */
SCRadixCreateRadixTree(void (* Free)(void *),void (* PrintData)(void *))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  */
SCRadixReleaseRadixSubtree(SCRadixNode * node,SCRadixTree * tree)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  */
SCRadixReleaseRadixTree(SCRadixTree * tree)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  */
SCRadixAddKey(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree,void * user,uint8_t netmask)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  */
SCRadixAddKeyGeneric(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree,void * user)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  */
SCRadixAddKeyIPV4(uint8_t * key_stream,SCRadixTree * tree,void * user)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  */
SCRadixAddKeyIPV6(uint8_t * key_stream,SCRadixTree * tree,void * user)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  */
SCRadixAddKeyIPV4Netblock(uint8_t * key_stream,SCRadixTree * tree,void * user,uint8_t netmask)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  */
SCRadixAddKeyIPV6Netblock(uint8_t * key_stream,SCRadixTree * tree,void * user,uint8_t netmask)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  */
SCRadixAddKeyIPV4String(const char * str,SCRadixTree * tree,void * user)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  */
SCRadixAddKeyIPV6String(const char * str,SCRadixTree * tree,void * user)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 
SCRadixTransferNetmasksBWNodes(SCRadixNode * dest,SCRadixNode * src)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  */
SCRadixRemoveNetblockEntry(SCRadixNode * node,uint8_t netmask)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  */
SCRadixRemoveKey(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree,uint8_t netmask)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  */
SCRadixRemoveKeyGeneric(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree)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  */
SCRadixRemoveKeyIPV4Netblock(uint8_t * key_stream,SCRadixTree * tree,uint8_t netmask)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  */
SCRadixRemoveKeyIPV4(uint8_t * key_stream,SCRadixTree * tree)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  */
SCRadixRemoveKeyIPV6Netblock(uint8_t * key_stream,SCRadixTree * tree,uint8_t netmask)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  */
SCRadixRemoveKeyIPV6(uint8_t * key_stream,SCRadixTree * tree)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  */
SCRadixFindKeyIPNetblock(uint8_t * key_stream,uint8_t key_bitlen,SCRadixNode * node,void ** user_data_result)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  */
SCRadixFindKey(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree,int exact_match,void ** user_data_result)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  */
SCRadixFindKeyGeneric(uint8_t * key_stream,uint16_t key_bitlen,SCRadixTree * tree,void ** user_data_result)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  */
SCRadixFindKeyIPV4ExactMatch(uint8_t * key_stream,SCRadixTree * tree,void ** user_data_result)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  */
SCRadixFindKeyIPV4BestMatch(uint8_t * key_stream,SCRadixTree * tree,void ** user_data_result)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  */
SCRadixFindKeyIPV4Netblock(uint8_t * key_stream,SCRadixTree * tree,uint8_t netmask,void ** user_data_result)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  */
SCRadixFindKeyIPV6Netblock(uint8_t * key_stream,SCRadixTree * tree,uint8_t netmask,void ** user_data_result)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  */
SCRadixFindKeyIPV6ExactMatch(uint8_t * key_stream,SCRadixTree * tree,void ** user_data_result)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  */
SCRadixFindKeyIPV6BestMatch(uint8_t * key_stream,SCRadixTree * tree,void ** user_data_result)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  */
SCRadixPrintNodeInfo(SCRadixNode * node,int level,void (* PrintData)(void *))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  */
SCRadixPrintRadixSubtree(SCRadixNode * node,int level,void (* PrintData)(void *))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  */
SCRadixPrintTree(SCRadixTree * tree)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 
SCRadixTestIPV4Insertion03(void)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 
SCRadixTestIPV4Removal04(void)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 
SCRadixTestIPV6Insertion07(void)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 
SCRadixTestIPV6Removal08(void)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 
SCRadixTestIPV4NetblockInsertion09(void)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 
SCRadixTestIPV4NetblockInsertion10(void)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 
SCRadixTestIPV4NetblockInsertion11(void)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 
SCRadixTestIPV4NetblockInsertion12(void)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 
SCRadixTestIPV6NetblockInsertion13(void)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 
SCRadixTestIPV6NetblockInsertion14(void)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  */
SCRadixTestIPV4NetBlocksAndBestSearch15(void)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  */
SCRadixTestIPV4NetBlocksAndBestSearch16(void)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  */
SCRadixTestIPV4NetBlocksAndBestSearch17(void)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  */
SCRadixTestIPV4NetBlocksAndBestSearch18(void)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  */
SCRadixTestIPV4NetBlocksAndBestSearch19(void)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  */
SCRadixTestIPV6NetBlocksAndBestSearch20(void)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  */
SCRadixTestIPV6NetBlocksAndBestSearch21(void)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  */
SCRadixTestIPV6NetBlocksAndBestSearch22(void)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  */
SCRadixTestIPV6NetBlocksAndBestSearch23(void)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  */
SCRadixTestIPV6NetBlocksAndBestSearch24(void)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  */
SCRadixTestIPV4NetblockInsertion25(void)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  */
SCRadixTestIPV4NetblockInsertion26(void)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 
SCRadixRegisterTests(void)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 }
4092