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