diff options
Diffstat (limited to 'framework/src/suricata/src/util-radix-tree.c')
| -rw-r--r-- | framework/src/suricata/src/util-radix-tree.c | 4228 |
1 files changed, 0 insertions, 4228 deletions
diff --git a/framework/src/suricata/src/util-radix-tree.c b/framework/src/suricata/src/util-radix-tree.c deleted file mode 100644 index cbf49c7d..00000000 --- a/framework/src/suricata/src/util-radix-tree.c +++ /dev/null @@ -1,4228 +0,0 @@ -/* Copyright (C) 2007-2010 Open Information Security Foundation - * - * You can copy, redistribute or modify this Program under the terms of - * the GNU General Public License version 2 as published by the Free - * Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * version 2 along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - * 02110-1301, USA. - */ - -/** - * \file - * - * \author Anoop Saldanha <anoopsaldanha@gmail.com> - * - * Implementation of radix trees - */ - -#include "suricata-common.h" -#include "util-radix-tree.h" -#include "util-debug.h" -#include "util-error.h" -#include "util-ip.h" -#include "util-unittest.h" -#include "util-memcmp.h" - -/** - * \brief Allocates and returns a new instance of SCRadixUserData. - * - * \param netmask The netmask entry (cidr) that has to be made in the new - * SCRadixUserData instance - * \param user The user data that has to be set for the above - * netmask in the newly created SCRadixUserData instance. - * - * \retval user_data Pointer to a new instance of SCRadixUserData. - */ -static SCRadixUserData *SCRadixAllocSCRadixUserData(uint8_t netmask, void *user) -{ - SCRadixUserData *user_data = SCMalloc(sizeof(SCRadixUserData)); - if (unlikely(user_data == NULL)) { - SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory"); - return NULL; - } - - memset(user_data, 0, sizeof(SCRadixUserData)); - - user_data->netmask = netmask; - user_data->user = user; - - return user_data; -} - -/** - * \brief Deallocates an instance of SCRadixUserData. - * - * \param user_data Pointer to the instance of SCRadixUserData that has to be - * freed. - */ -static void SCRadixDeAllocSCRadixUserData(SCRadixUserData *user_data) -{ - SCFree(user_data); - - return; -} - -/** - * \brief Appends a user_data instance(SCRadixUserData) to a - * user_data(SCRadixUserData) list. We add the new entry in descending - * order with respect to the netmask contained in the SCRadixUserData. - * - * \param new Pointer to the SCRadixUserData to be added to the list. - * \param list Pointer to the SCRadixUserData list head, to which "new" has to - * be appended. - */ -static void SCRadixAppendToSCRadixUserDataList(SCRadixUserData *new, - SCRadixUserData **list) -{ - SCRadixUserData *temp = NULL; - SCRadixUserData *prev = NULL; - - if (new == NULL || list == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENTS, "new or list supplied as NULL"); - exit(EXIT_FAILURE); - } - - /* add to the list in descending order. The reason we do this is for - * optimizing key retrieval for a ip key under a netblock */ - prev = temp = *list; - while (temp != NULL) { - if (new->netmask > temp->netmask) - break; - prev = temp; - temp = temp->next; - } - - if (temp == *list) { - new->next = *list; - *list = new; - } else { - new->next = prev->next; - prev->next = new; - } - - return; -} - -/** - * \brief Creates a new Prefix for a key. Used internally by the API. - * - * \param key_stream Data that has to be wrapped in a SCRadixPrefix instance to - * be processed for insertion/lookup/removal of a node by the - * radix tree - * \param key_bitlen The bitlen of the the above stream. For example if the - * stream holds the ipv4 address(4 bytes), bitlen would be 32 - * \param user Pointer to the user data that has to be associated with - * this key - * - * \retval prefix The newly created prefix instance on success; NULL on failure - */ -static SCRadixPrefix *SCRadixCreatePrefix(uint8_t *key_stream, - uint16_t key_bitlen, void *user, - uint8_t netmask) -{ - SCRadixPrefix *prefix = NULL; - - if ((key_bitlen % 8 != 0)) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "Invalid argument bitlen - %d", - key_bitlen); - return NULL; - } - - if (key_stream == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "Argument \"stream\" NULL"); - return NULL; - } - - if ( (prefix = SCMalloc(sizeof(SCRadixPrefix))) == NULL) - goto error; - - memset(prefix, 0, sizeof(SCRadixPrefix)); - - if ( (prefix->stream = SCMalloc(key_bitlen / 8)) == NULL) - goto error; - - memset(prefix->stream, 0, key_bitlen / 8); - - memcpy(prefix->stream, key_stream, key_bitlen / 8); - prefix->bitlen = key_bitlen; - - prefix->user_data = SCRadixAllocSCRadixUserData(netmask, user); - if (prefix->user_data == NULL) { - goto error; - } - - return prefix; - -error: - if (prefix != NULL) { - if (prefix->stream != NULL) { - SCFree(prefix->stream); - } - SCFree(prefix); - } - - return NULL; -} - -/** - * \brief Adds a netmask and its user_data for a particular prefix stream. - * - * \param prefix The prefix stream to which the netmask and its corresponding - * user data has to be added. - * \param netmask The netmask value (cidr) that has to be added to the prefix. - * \param user The pointer to the user data corresponding to the above - * netmask. - */ -static void SCRadixAddNetmaskUserDataToPrefix(SCRadixPrefix *prefix, - uint8_t netmask, - void *user) -{ - if (prefix == NULL || user == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENTS, "prefix or user NULL"); - exit(EXIT_FAILURE); - } - - SCRadixAppendToSCRadixUserDataList(SCRadixAllocSCRadixUserData(netmask, user), - &prefix->user_data); - - return; -} - -/** - * \brief Removes a particular user_data corresponding to a particular netmask - * entry, from a prefix. - * - * \param prefix Pointer to the prefix from which the user_data/netmask entry - * has to be removed. - * \param netmask The netmask value (cidr) whose user_data has to be deleted. - */ -static void SCRadixRemoveNetmaskUserDataFromPrefix(SCRadixPrefix *prefix, - uint8_t netmask) -{ - SCRadixUserData *temp = NULL, *prev = NULL; - - if (prefix == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENTS, "prefix NULL"); - exit(EXIT_FAILURE); - } - - prev = temp = prefix->user_data; - while (temp != NULL) { - if (temp->netmask == netmask) { - if (temp == prefix->user_data) - prefix->user_data = temp->next; - else - prev->next = temp->next; - - SCRadixDeAllocSCRadixUserData(temp); - break; - } - prev = temp; - temp = temp->next; - } - - return; -} - -/** - * \brief Indicates if prefix contains an entry for an ip with a specific netmask. - * - * \param prefix Pointer to the ip prefix that is being checked. - * \param netmask The netmask value (cidr) that has to be checked for - * presence in the prefix. - * - * \retval 1 On match. - * \retval 0 On no match. - */ -static int SCRadixPrefixContainNetmask(SCRadixPrefix *prefix, uint8_t netmask) -{ - SCRadixUserData *user_data = NULL; - - if (prefix == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "prefix is NULL"); - goto no_match; - } - - user_data = prefix->user_data; - while (user_data != NULL) { - if (user_data->netmask == netmask) - return 1; - user_data = user_data->next; - } - - no_match: - return 0; -} - -/** - * \brief Returns the total netmask count for this prefix. - * - * \param prefix Pointer to the prefix - * - * \retval count The total netmask count for this prefix. - */ -static int SCRadixPrefixNetmaskCount(SCRadixPrefix *prefix) -{ - SCRadixUserData *user_data = NULL; - uint32_t count = 0; - - if (prefix == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "prefix is NULL"); - return 0; - } - - user_data = prefix->user_data; - while (user_data != NULL) { - count++; - user_data = user_data->next; - } - - return count; -} - -/** - * \brief Indicates if prefix contains an entry for an ip with a specific netmask - * and if it does, it sets the user data field - * SCRadixPrefix->user_data_result to the netmask user_data entry. - * - * \param prefix Pointer to the ip prefix that is being checked. - * \param netmask The netmask value for which we will have to return the user_data - * \param exact_match Bool flag which indicates if we should check if the prefix - * holds proper netblock(< 32 for ipv4 and < 128 for ipv6) or not. - * - * \retval 1 On match. - * \retval 0 On no match. - */ -static int SCRadixPrefixContainNetmaskAndSetUserData(SCRadixPrefix *prefix, - uint16_t netmask, - int exact_match, - void **user_data_result) -{ - SCRadixUserData *user_data = NULL; - - if (prefix == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "prefix is NULL"); - goto no_match; - } - - user_data = prefix->user_data; - /* Check if we have a match for an exact ip. An exact ip as in not a proper - * netblock, i.e. an ip with a netmask of 32(ipv4) or 128(ipv6) */ - if (exact_match) { - if (user_data->netmask == netmask) { - if (user_data_result) - *user_data_result = user_data->user; - return 1; - } else { - goto no_match; - } - } - - /* Check for the user_data entry for this netmask_value */ - while (user_data != NULL) { - if (user_data->netmask == netmask) { - if (user_data_result) - *user_data_result = user_data->user; - return 1; - } - user_data = user_data->next; - } - -no_match: - if (user_data_result != NULL) - *user_data_result = NULL; - return 0; -} - -/** - * \brief Frees a SCRadixPrefix instance - * - * \param prefix Pointer to a prefix instance - * \param tree Pointer to the Radix tree to which this prefix belongs - */ -static void SCRadixReleasePrefix(SCRadixPrefix *prefix, SCRadixTree *tree) -{ - SCRadixUserData *user_data_temp1 = NULL; - SCRadixUserData *user_data_temp2 = NULL; - - if (prefix != NULL) { - if (prefix->stream != NULL) - SCFree(prefix->stream); - - user_data_temp1 = prefix->user_data; - if (tree->Free != NULL) { - while (user_data_temp1 != NULL) { - user_data_temp2 = user_data_temp1; - user_data_temp1 = user_data_temp1->next; - tree->Free(user_data_temp2->user); - SCRadixDeAllocSCRadixUserData(user_data_temp2); - } - } else if (user_data_temp1 != NULL) { - SCFree(user_data_temp1); - } - - SCFree(prefix); - } - - return; -} - -/** - * \brief Creates a new node for the Radix tree - * - * \retval node The newly created node for the radix tree - */ -static inline SCRadixNode *SCRadixCreateNode() -{ - SCRadixNode *node = NULL; - - if ( (node = SCMalloc(sizeof(SCRadixNode))) == NULL) { - SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixCreateNode. Mem not allocated..."); - return NULL; - } - memset(node, 0, sizeof(SCRadixNode)); - - return node; -} - -/** - * \brief Frees a Radix tree node - * - * \param node Pointer to a Radix tree node - * \param tree Pointer to the Radix tree to which this node belongs - */ -static void SCRadixReleaseNode(SCRadixNode *node, SCRadixTree *tree) -{ - if (node != NULL) { - SCRadixReleasePrefix(node->prefix, tree); - - if (node->netmasks != NULL) - SCFree(node->netmasks); - - SCFree(node); - } - - return; -} - -/** - * \brief Creates a new Radix tree - * - * \param Free Function pointer supplied by the user to be used by the Radix - * cleanup API to free the user suppplied data - * - * \retval tree The newly created radix tree on success - * - * \initonly (all radix trees should be created at init) - */ -SCRadixTree *SCRadixCreateRadixTree(void (*Free)(void*), void (*PrintData)(void*)) -{ - SCRadixTree *tree = NULL; - - if ( (tree = SCMalloc(sizeof(SCRadixTree))) == NULL) { - SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixCreateRadixTree. Exiting..."); - exit(EXIT_FAILURE); - } - memset(tree, 0, sizeof(SCRadixTree)); - - tree->Free = Free; - tree->PrintData = PrintData; - - return tree; -} - -/** - * \brief Internal helper function used by SCRadixReleaseRadixTree to free a - * subtree - * - * \param node Pointer to the root of the subtree that has to be freed - * \param tree Pointer to the Radix tree to which this subtree belongs - */ -static void SCRadixReleaseRadixSubtree(SCRadixNode *node, SCRadixTree *tree) -{ - if (node != NULL) { - SCRadixReleaseRadixSubtree(node->left, tree); - SCRadixReleaseRadixSubtree(node->right, tree); - SCRadixReleaseNode(node, tree); - } - - return; -} - -/** - * \brief Frees a Radix tree and all its nodes - * - * \param tree Pointer to the Radix tree that has to be freed - */ -void SCRadixReleaseRadixTree(SCRadixTree *tree) -{ - if (tree == NULL) - return; - - SCRadixReleaseRadixSubtree(tree->head, tree); - tree->head = NULL; - SCFree(tree); - return; -} - -/** - * \brief Adds a key to the Radix tree. Used internally by the API. - * - * \param key_stream Data that has to added to the Radix tree - * \param key_bitlen The bitlen of the the above stream. For example if the - * stream is the string "abcd", the bitlen would be 32. If - * the stream is an IPV6 address bitlen would be 128 - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with - * this key - * \param netmask The netmask (cidr) if we are adding an IP netblock; 255 - * if we are not adding an IP netblock - * - * \retval node Pointer to the newly created node - */ -static SCRadixNode *SCRadixAddKey(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree, void *user, uint8_t netmask) -{ - SCRadixNode *node = NULL; - SCRadixNode *new_node = NULL; - SCRadixNode *parent = NULL; - SCRadixNode *inter_node = NULL; - SCRadixNode *bottom_node = NULL; - - SCRadixPrefix *prefix = NULL; - - void *ptmp; - - uint8_t *stream = NULL; - uint8_t bitlen = 0; - - int check_bit = 0; - int differ_bit = 0; - - int i = 0; - int j = 0; - int temp = 0; - - if (tree == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENT, "Argument \"tree\" NULL"); - return NULL; - } - - /* chop the ip address against a netmask */ - MaskIPNetblock(key_stream, netmask, key_bitlen); - - if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, user, - netmask)) == NULL) { - SCLogError(SC_ERR_RADIX_TREE_GENERIC, "Error creating prefix"); - return NULL; - } - - /* the very first element in the radix tree */ - if (tree->head == NULL) { - node = SCRadixCreateNode(); - if (node == NULL) - return NULL; - node->prefix = prefix; - node->bit = prefix->bitlen; - tree->head = node; - if (netmask == 255 || (netmask == 32 && key_bitlen == 32) || (netmask == 128 && key_bitlen == 128)) - return node; - - /* if we have reached here, we are actually having a proper netblock in - * our hand(i.e. < 32 for ipv4 and < 128 for ipv6). Add the netmask for - * this node. The reason we add netmasks other than 32 and 128, is - * because we need those netmasks in case of searches for ips contained - * in netblocks. If the netmask is 32 or 128, either ways we will be - * having an exact match for that ip value. If it is not, we start - * chopping the incoming search ip key using the netmask values added - * into the tree and then verify for a match */ - node->netmask_cnt++; - if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt * - sizeof(uint8_t)))) == NULL) { - SCFree(node->netmasks); - node->netmasks = NULL; - SCLogError(SC_ERR_MEM_ALLOC, "Fatal error encountered in SCRadixAddKey. Mem not allocated"); - return NULL; - } - node->netmasks = ptmp; - node->netmasks[0] = netmask; - return node; - } - - node = tree->head; - stream = prefix->stream; - bitlen = prefix->bitlen; - - /* we walk down the tree only when we satisfy 2 conditions. The first one - * being the incoming prefix is shorter than the differ bit of the current - * node. In case we fail in this aspect, we walk down to the tree, till we - * arrive at a node that ends in a prefix */ - while (node->bit < bitlen || node->prefix == NULL) { - /* if the bitlen isn't long enough to handle the bit test, we just walk - * down along one of the paths, since either paths should end up with a - * node that has a common prefix whose differ bit is greater than the - * bitlen of the incoming prefix */ - if (bitlen <= node->bit) { - if (node->right == NULL) - break; - node = node->right; - } else { - if (SC_RADIX_BITTEST(stream[node->bit >> 3], - (0x80 >> (node->bit % 8))) ) { - if (node->right == NULL) - break; - node = node->right; - } else { - if (node->left == NULL) - break; - node = node->left; - } - } - } - - /* we need to keep a reference to the bottom-most node, that actually holds - * the prefix */ - bottom_node = node; - - /* get the first bit position where the ips differ */ - check_bit = (node->bit < bitlen)? node->bit: bitlen; - for (i = 0; (i * 8) < check_bit; i++) { - if ((temp = (stream[i] ^ bottom_node->prefix->stream[i])) == 0) { - differ_bit = (i + 1) * 8; - continue; - } - - /* find out the position where the first bit differs. This method is - * faster, but at the cost of being larger. But with larger caches - * these days we don't have to worry about cache misses */ - temp = temp * 2; - if (temp >= 256) - j = 0; - else if (temp >= 128) - j = 1; - else if (temp >= 64) - j = 2; - else if (temp >= 32) - j = 3; - else if (temp >= 16) - j = 4; - else if (temp >= 8) - j = 5; - else if (temp >= 4) - j = 6; - else if (temp >= 2) - j = 7; - - differ_bit = i * 8 + j; - break; - } - if (check_bit < differ_bit) - differ_bit = check_bit; - - /* walk up the tree till we find the position, to fit our new node in */ - parent = node->parent; - while (parent && differ_bit <= parent->bit) { - node = parent; - parent = node->parent; - } - - /* We already have the node in the tree with the same differing bit pstn */ - if (differ_bit == bitlen && node->bit == bitlen) { - if (node->prefix != NULL) { - /* Check if we already have this netmask entry covered by this prefix */ - if (SCRadixPrefixContainNetmask(node->prefix, netmask)) { - /* Basically we already have this stream prefix, as well as the - * netblock entry for this. A perfect duplicate. */ - SCLogDebug("Duplicate entry for this ip address/netblock"); - } else { - /* Basically we already have this stream prefix, but we don't - * have an entry for this particular netmask value for this - * prefix. For example, we have an entry for 192.168.0.0 and - * 192.168.0.0/16 and now we are trying to enter 192.168.0.0/20 */ - SCRadixAddNetmaskUserDataToPrefix(node->prefix, netmask, user); - - /* if we are adding a netmask of 32(for ipv4) or 128(for ipv6) - * it indicates we are adding an exact host ip into the radix - * tree, in which case we don't need to add the netmask value - * into the tree */ - if (netmask == 255 || (netmask == 32 && bitlen == 32) || (netmask == 128 && bitlen == 128)) - return node; - - /* looks like we have a netmask which is != 32 or 128, in which - * case we walk up the tree to insert this netmask value in the - * correct node */ - parent = node->parent; - while (parent != NULL && netmask < (parent->bit + 1)) { - node = parent; - parent = parent->parent; - } - - node->netmask_cnt++; - new_node = node; - - if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt * - sizeof(uint8_t)))) == NULL) { - SCFree(node->netmasks); - node->netmasks = NULL; - SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixAddKey. Mem not allocated..."); - return NULL; - } - node->netmasks = ptmp; - - if (node->netmask_cnt == 1) { - node->netmasks[0] = netmask; - return new_node; - } - - node->netmasks[node->netmask_cnt - 1] = netmask; - - for (i = node->netmask_cnt - 2; i >= 0; i--) { - if (netmask < node->netmasks[i]) { - node->netmasks[i + 1] = netmask; - break; - } - - node->netmasks[i + 1] = node->netmasks[i]; - node->netmasks[i] = netmask; - } - } - } else { - node->prefix = SCRadixCreatePrefix(prefix->stream, prefix->bitlen, - user, 255); - } - return node; - } - - /* create the leaf node for the new key */ - new_node = SCRadixCreateNode(); - new_node->prefix = prefix; - new_node->bit = prefix->bitlen; - - /* indicates that we have got a key that has length that is already covered - * by a prefix of some other key in the tree. We create a new intermediate - * node with a single child and stick it in. We need the if only in the - * case of variable length keys */ - if (differ_bit == bitlen) { - if (SC_RADIX_BITTEST(bottom_node->prefix->stream[differ_bit >> 3], - (0x80 >> (differ_bit % 8))) ) { - new_node->right = node; - } else { - new_node->left = node; - } - new_node->parent = node->parent; - - if (node->parent == NULL) - tree->head = new_node; - else if (node->parent->right == node) - node->parent->right = new_node; - else - node->parent->left = new_node; - - node->parent = new_node; - /* stick our new_node into the tree. Create a node that holds the - * differing bit position and break the branch. Also handle the - * tranfer of netmasks between node and inter_node(explained in more - * detail below) */ - } else { - inter_node = SCRadixCreateNode(); - inter_node->prefix = NULL; - inter_node->bit = differ_bit; - inter_node->parent = node->parent; - - if (node->netmasks != NULL) { - for (i = 0; i < node->netmask_cnt; i++) { - if (node->netmasks[i] < differ_bit + 1) - break; - } - - if ( (inter_node->netmasks = SCMalloc((node->netmask_cnt - i) * - sizeof(uint8_t))) == NULL) { - SCLogError(SC_ERR_MEM_ALLOC, "Fatal error encountered in SCRadixAddKey. Mem not allocated..."); - return NULL; - } - - for (j = 0; j < (node->netmask_cnt - i); j++) - inter_node->netmasks[j] = node->netmasks[i + j]; - - inter_node->netmask_cnt = (node->netmask_cnt - i); - node->netmask_cnt = i; - - if (node->netmask_cnt == 0) { - SCFree(node->netmasks); - node->netmasks = NULL; - } - } - - if (SC_RADIX_BITTEST(stream[differ_bit >> 3], - (0x80 >> (differ_bit % 8))) ) { - inter_node->left = node; - inter_node->right = new_node; - } else { - inter_node->left = new_node; - inter_node->right = node; - } - new_node->parent = inter_node; - - if (node->parent == NULL) - tree->head = inter_node; - else if (node->parent->right == node) - node->parent->right = inter_node; - else - node->parent->left = inter_node; - - node->parent = inter_node; - } - - /* insert the netmask into the tree */ - if (netmask != 255 && (netmask != 32 || (netmask == 32 && bitlen != 32)) && netmask != 128) { - node = new_node; - parent = new_node->parent; - while (parent != NULL && netmask < (parent->bit + 1)) { - node = parent; - parent = parent->parent; - } - - node->netmask_cnt++; - if ( (ptmp = SCRealloc(node->netmasks, (node->netmask_cnt * - sizeof(uint8_t)))) == NULL) { - SCFree(node->netmasks); - node->netmasks = NULL; - SCLogError(SC_ERR_FATAL, "Fatal error encountered in SCRadixAddKey. Exiting..."); - exit(EXIT_FAILURE); - } - node->netmasks = ptmp; - - if (node->netmask_cnt == 1) { - node->netmasks[0] = netmask; - return new_node; - } - - node->netmasks[node->netmask_cnt - 1] = netmask; - - for (i = node->netmask_cnt - 2; i >= 0; i--) { - if (netmask < node->netmasks[i]) { - node->netmasks[i + 1] = netmask; - break; - } - - node->netmasks[i + 1] = node->netmasks[i]; - node->netmasks[i] = netmask; - } - } - - return new_node; -} - -/** - * \brief Adds a new generic key to the Radix tree - * - * \param key_stream Data that has to be added to the Radix tree - * \param key_bitlen The bitlen of the the above stream. For example if the - * stream is the string "abcd", the bitlen would be 32 - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with the - * key - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree, void *user) -{ - SCRadixNode *node = SCRadixAddKey(key_stream, key_bitlen, tree, user, 255); - - return node; -} - -/** - * \brief Adds a new IPV4 address to the Radix tree - * - * \param key_stream Data that has to be added to the Radix tree. In this case - * a pointer to an IPV4 address - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with the - * key - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV4(uint8_t *key_stream, SCRadixTree *tree, - void *user) -{ - SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, 32); - - return node; -} - -/** - * \brief Adds a new IPV6 address to the Radix tree - * - * \param key_stream Data that has to be added to the Radix tree. In this case - * the pointer to an IPV6 address - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with the - * key - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV6(uint8_t *key_stream, SCRadixTree *tree, - void *user) -{ - SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, 128); - - return node; -} - -/** - * \brief Adds a new IPV4 netblock to the Radix tree - * - * \param key_stream Data that has to be added to the Radix tree. In this case - * a pointer to an IPV4 netblock - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with the - * key - * \param netmask The netmask (cidr) if we are adding a netblock - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, - void *user, uint8_t netmask) -{ - SCRadixNode *node = SCRadixAddKey(key_stream, 32, tree, user, netmask); - - return node; -} - -/** - * \brief Adds a new IPV6 netblock to the Radix tree - * - * \param key_stream Data that has to be added to the Radix tree. In this case - * a pointer to an IPV6 netblock - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with the - * key - * \param netmask The netmask (cidr) if we are adding a netblock - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, - void *user, uint8_t netmask) -{ - SCRadixNode *node = SCRadixAddKey(key_stream, 128, tree, user, netmask); - - return node; -} - -/** - * \brief Adds a new IPV4/netblock to the Radix tree from a string - * - * \param str IPV4 string with optional /cidr netmask - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with - * the key - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV4String(const char *str, SCRadixTree *tree, void *user) -{ - uint32_t ip; - uint8_t netmask = 32; - char ip_str[32]; /* Max length for full ipv4/mask string with NUL */ - char *mask_str = NULL; - struct in_addr addr; - - /* Make a copy of the string so it can be modified */ - strlcpy(ip_str, str, sizeof(ip_str) - 2); - *(ip_str + (sizeof(ip_str) - 1)) = '\0'; - - /* Does it have a mask? */ - if (NULL != (mask_str = strchr(ip_str, '/'))) { - int cidr; - *(mask_str++) = '\0'; - - /* Dotted type netmask not supported (yet) */ - if (strchr(mask_str, '.') != NULL) { - return NULL; - } - - /* Get binary values for cidr mask */ - cidr = atoi(mask_str); - if ((cidr < 0) || (cidr > 32)) { - return NULL; - } - netmask = (uint8_t)cidr; - } - - /* Validate the IP */ - if (inet_pton(AF_INET, ip_str, &addr) <= 0) { - return NULL; - } - ip = addr.s_addr; - - return SCRadixAddKey((uint8_t *)&ip, 32, tree, user, netmask); -} - -/** - * \brief Adds a new IPV6/netblock to the Radix tree from a string - * - * \param str IPV6 string with optional /cidr netmask - * \param tree Pointer to the Radix tree - * \param user Pointer to the user data that has to be associated with - * the key - * - * \retval node Pointer to the newly created node - */ -SCRadixNode *SCRadixAddKeyIPV6String(const char *str, SCRadixTree *tree, void *user) -{ - uint8_t netmask = 128; - char ip_str[80]; /* Max length for full ipv6/mask string with NUL */ - char *mask_str = NULL; - struct in6_addr addr; - - /* Make a copy of the string so it can be modified */ - strlcpy(ip_str, str, sizeof(ip_str) - 2); - *(ip_str + sizeof(ip_str) - 1) = '\0'; - - /* Does it have a mask? */ - if (NULL != (mask_str = strchr(ip_str, '/'))) { - int cidr; - *(mask_str++) = '\0'; - - /* Dotted type netmask not supported (yet) */ - if (strchr(mask_str, '.') != NULL) { - return NULL; - } - - /* Get binary values for cidr mask */ - cidr = atoi(mask_str); - if ((cidr < 0) || (cidr > 128)) { - return NULL; - } - netmask = (uint8_t)cidr; - } - - /* Validate the IP */ - if (inet_pton(AF_INET6, ip_str, &addr) <= 0) { - return NULL; - } - - return SCRadixAddKey(addr.s6_addr, 128, tree, user, netmask); -} - -static void SCRadixTransferNetmasksBWNodes(SCRadixNode *dest, SCRadixNode *src) -{ - int i = 0, j = 0; - void *ptmp = NULL; - - if (src == NULL || dest == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENTS, "src or dest NULL"); - return; - } - - /* no netmasks in the source node, to transfer to the destination node */ - if (src->netmasks == NULL) - return; - - if ( (ptmp = SCRealloc(dest->netmasks, - (src->netmask_cnt + dest->netmask_cnt) * - sizeof(uint8_t))) == NULL) { - SCFree(dest->netmasks); - dest->netmasks = NULL; - return; - } - dest->netmasks = ptmp; - - for (i = dest->netmask_cnt, j = 0; j < src->netmask_cnt; i++, j++) - dest->netmasks[i] = src->netmasks[j]; - - return; -} - -/** - * \brief Removes a netblock entry from an ip node. The function first - * deletes the netblock/user_data entry for the prefix and then - * removes the netmask entry that has been made in the tree, by - * walking up the tree and deleting the entry from the specific node. - * - * \param node The node from which the netblock entry has to be removed. - * \param netmask The netmask entry (cidr) that has to be removed. - */ -static void SCRadixRemoveNetblockEntry(SCRadixNode *node, uint8_t netmask) -{ - void *ptmp; - SCRadixNode *parent = NULL; - int i = 0; - - if (node == NULL) { - SCLogError(SC_ERR_INVALID_ARGUMENTS, "Invalid argument. Node is NULL"); - return; - } - - SCRadixRemoveNetmaskUserDataFromPrefix(node->prefix, netmask); - - if (netmask == 32 || netmask == 128) - return; - - parent = node->parent; - while (parent != NULL && netmask < (parent->bit + 1)) { - parent = parent->parent; - } - - for (i = 0; i < node->netmask_cnt; i++) { - if (node->netmasks[i] == netmask) - break; - } - - if (i == node->netmask_cnt) { - SCLogDebug("Something's wrong with the tree. We are unable to find the " - "netmask entry"); - return; - } - - for ( ; i < node->netmask_cnt - 1; i++) - node->netmasks[i] = node->netmasks[i + 1]; - - node->netmask_cnt--; - if (node->netmask_cnt == 0) { - SCFree(node->netmasks); - node->netmasks = NULL; - return; - } - - ptmp = SCRealloc(node->netmasks, node->netmask_cnt * sizeof(uint8_t)); - if (ptmp == NULL) { - SCFree(node->netmasks); - node->netmasks = NULL; - return; - } - node->netmasks = ptmp; - - return; -} - -/** - * \brief Removes a key from the Radix tree - * - * \param key_stream Data that has to be removed from the Radix tree - * \param key_bitlen The bitlen of the the above stream. For example if the - * stream holds an IPV4 address(4 bytes), bitlen would be 32 - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -static void SCRadixRemoveKey(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree, uint8_t netmask) -{ - SCRadixNode *node = tree->head; - SCRadixNode *parent = NULL; - SCRadixNode *temp_dest = NULL; - - SCRadixPrefix *prefix = NULL; - - int mask = 0; - int i = 0; - - if (node == NULL) - return; - - if ( (prefix = SCRadixCreatePrefix(key_stream, key_bitlen, NULL, 255)) == NULL) - return; - - while (node->bit < prefix->bitlen) { - if (SC_RADIX_BITTEST(prefix->stream[node->bit >> 3], - (0x80 >> (node->bit % 8))) ) { - node = node->right; - } else { - node = node->left; - } - - if (node == NULL) { - SCRadixReleasePrefix(prefix, tree); - return; - } - } - - if (node->bit != prefix->bitlen || node->prefix == NULL) { - SCRadixReleasePrefix(prefix, tree); - return; - } - - i = prefix->bitlen / 8; - if (SCMemcmp(node->prefix->stream, prefix->stream, i) == 0) { - mask = -1 << (8 - prefix->bitlen % 8); - - if (prefix->bitlen % 8 == 0 || - (node->prefix->stream[i] & mask) == (prefix->stream[i] & mask)) { - if (!SCRadixPrefixContainNetmask(node->prefix, netmask)) { - SCLogDebug("The ip key exists in the Radix Tree, but this(%d) " - "netblock entry doesn't exist", netmask); - SCRadixReleasePrefix(prefix, tree); - return; - } - } else { - SCLogDebug("You are trying to remove a key that doesn't exist in " - "the Radix Tree"); - SCRadixReleasePrefix(prefix, tree); - return; - } - } else { - SCLogDebug("You are trying to remove a key that doesn't exist in the " - "Radix Tree"); - SCRadixReleasePrefix(prefix, tree); - return; - } - - /* The ip node does exist, and the netblock entry does exist in this node, if - * we have reached this point. If we have more than one netblock entry, it - * indicates we have multiple entries for this key. So we delete that - * particular netblock entry, and make our way out of this function */ - if (SCRadixPrefixNetmaskCount(node->prefix) > 1) { - SCRadixRemoveNetblockEntry(node, netmask); - SCRadixReleasePrefix(prefix, tree); - return; - } - - /* we are deleting the root of the tree. This would be the only node left - * in the tree */ - if (tree->head == node) { - SCFree(node); - tree->head = NULL; - SCRadixReleasePrefix(prefix, tree); - return; - } - - parent = node->parent; - /* parent->parent is not the root of the tree */ - if (parent->parent != NULL) { - if (parent->parent->left == parent) { - if (node->parent->left == node) { - temp_dest = parent->right; - parent->parent->left = parent->right; - parent->right->parent = parent->parent; - } else { - temp_dest = parent->left; - parent->parent->left = parent->left; - parent->left->parent = parent->parent; - } - } else { - if (node->parent->left == node) { - temp_dest = parent->right; - parent->parent->right = parent->right; - parent->right->parent = parent->parent; - } else { - temp_dest = parent->left; - parent->parent->right = parent->left; - parent->left->parent = parent->parent; - } - } - /* parent is the root of the tree */ - } else { - if (parent->left == node) { - temp_dest = tree->head->right; - tree->head->right->parent = NULL; - tree->head = tree->head->right; - } else { - temp_dest = tree->head->left; - tree->head->left->parent = NULL; - tree->head = tree->head->left; - } - } - /* We need to shift the netmask entries from the node that would be - * deleted to its immediate descendant */ - SCRadixTransferNetmasksBWNodes(temp_dest, parent); - /* release the nodes */ - SCRadixReleaseNode(parent, tree); - SCRadixReleaseNode(node, tree); - SCRadixReleasePrefix(prefix, tree); - - return; -} - -/** - * \brief Removes a key from the Radix tree - * - * \param key_stream Data that has to be removed from the Radix tree - * \param key_bitlen The bitlen of the the above stream. - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -void SCRadixRemoveKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree) -{ - SCRadixRemoveKey(key_stream, key_bitlen, tree, 255); - return; -} - -/** - * \brief Removes an IPV4 address netblock key from the Radix tree. - * - * \param key_stream Data that has to be removed from the Radix tree. In this - * case an IPV4 address - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -void SCRadixRemoveKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, - uint8_t netmask) -{ - SCRadixRemoveKey(key_stream, 32, tree, netmask); - return; -} - -/** - * \brief Removes an IPV4 address key(not a netblock) from the Radix tree. - * Instead of using this function, we can also used - * SCRadixRemoveKeyIPV4Netblock(), by supplying a netmask value of 32. - * - * \param key_stream Data that has to be removed from the Radix tree. In this - * case an IPV4 address - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -void SCRadixRemoveKeyIPV4(uint8_t *key_stream, SCRadixTree *tree) -{ - SCRadixRemoveKey(key_stream, 32, tree, 32); - return; -} - -/** - * \brief Removes an IPV6 netblock address key from the Radix tree. - * - * \param key_stream Data that has to be removed from the Radix tree. In this - * case an IPV6 address - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -void SCRadixRemoveKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, - uint8_t netmask) -{ - SCRadixRemoveKey(key_stream, 128, tree, netmask); - return; -} - -/** - * \brief Removes an IPV6 address key(not a netblock) from the Radix tree. - * Instead of using this function, we can also used - * SCRadixRemoveKeyIPV6Netblock(), by supplying a netmask value of 128. - * - * \param key_stream Data that has to be removed from the Radix tree. In this - * case an IPV6 address - * \param tree Pointer to the Radix tree from which the key has to be - * removed - */ -void SCRadixRemoveKeyIPV6(uint8_t *key_stream, SCRadixTree *tree) -{ - SCRadixRemoveKey(key_stream, 128, tree, 128); - return; -} - -/** - * \brief Checks if an IP prefix falls under a netblock, in the path to the root - * of the tree, from the node. Used internally by SCRadixFindKey() - * - * \param prefix Pointer to the prefix that contains the ip address - * \param node Pointer to the node from where we have to climb the tree - */ -static inline SCRadixNode *SCRadixFindKeyIPNetblock(uint8_t *key_stream, uint8_t key_bitlen, - SCRadixNode *node, void **user_data_result) -{ - SCRadixNode *netmask_node = NULL; - int mask = 0; - int bytes = 0; - int i = 0; - int j = 0; - - while (node != NULL && node->netmasks == NULL) - node = node->parent; - - if (node == NULL) - return NULL; - /* hold the node found containing a netmask. We will need it when we call - * this function recursively */ - netmask_node = node; - - for (j = 0; j < netmask_node->netmask_cnt; j++) { - bytes = key_bitlen / 8; - for (i = 0; i < bytes; i++) { - mask = -1; - if ( ((i + 1) * 8) > netmask_node->netmasks[j]) { - if ( ((i + 1) * 8 - netmask_node->netmasks[j]) < 8) - mask = -1 << ((i + 1) * 8 - netmask_node->netmasks[j]); - else - mask = 0; - } - key_stream[i] &= mask; - } - - while (node->bit < key_bitlen) { - if (SC_RADIX_BITTEST(key_stream[node->bit >> 3], - (0x80 >> (node->bit % 8))) ) { - node = node->right; - } else { - node = node->left; - } - - if (node == NULL) - return NULL; - } - - if (node->bit != key_bitlen || node->prefix == NULL) - return NULL; - - if (SCMemcmp(node->prefix->stream, key_stream, bytes) == 0) { - mask = -1 << (8 - key_bitlen % 8); - - if (key_bitlen % 8 == 0 || - (node->prefix->stream[bytes] & mask) == (key_stream[bytes] & mask)) { - if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, netmask_node->netmasks[j], 0, user_data_result)) - return node; - } - } - } - - return SCRadixFindKeyIPNetblock(key_stream, key_bitlen, netmask_node->parent, user_data_result); -} - -/** - * \brief Checks if an IP address key is present in the tree. The function - * apart from handling any normal data, also handles ipv4/ipv6 netblocks - * - * \param key_stream Data that has to be found in the Radix tree - * \param key_bitlen The bitlen of the above stream. - * \param tree Pointer to the Radix tree - * \param exact_match The key to be searched is an ip address - */ -static SCRadixNode *SCRadixFindKey(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree, int exact_match, void **user_data_result) -{ - if (tree == NULL || tree->head == NULL) - return NULL; - - SCRadixNode *node = tree->head; - int mask = 0; - int bytes = 0; - uint8_t tmp_stream[255]; - - if (key_bitlen > 255) - return NULL; - - memset(tmp_stream, 0, 255); - memcpy(tmp_stream, key_stream, key_bitlen / 8); - - while (node->bit < key_bitlen) { - if (SC_RADIX_BITTEST(tmp_stream[node->bit >> 3], - (0x80 >> (node->bit % 8))) ) { - node = node->right; - } else { - node = node->left; - } - - if (node == NULL) { - return NULL; - } - } - - if (node->bit != key_bitlen || node->prefix == NULL) { - return NULL; - } - - bytes = key_bitlen / 8; - if (SCMemcmp(node->prefix->stream, tmp_stream, bytes) == 0) { - mask = -1 << (8 - key_bitlen % 8); - - if (key_bitlen % 8 == 0 || - (node->prefix->stream[bytes] & mask) == (tmp_stream[bytes] & mask)) { - if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, key_bitlen, 1, user_data_result)) { - return node; - } - } - } - - /* if you are not an ip key, get out of here */ - if (exact_match) { - return NULL; - } - - SCRadixNode *ret = SCRadixFindKeyIPNetblock(tmp_stream, key_bitlen, node, user_data_result); - return ret; -} - -/** - * \brief Checks if a key is present in the tree - * - * \param key_stream Data that has to be found in the Radix tree - * \param key_bitlen The bitlen of the the above stream. - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyGeneric(uint8_t *key_stream, uint16_t key_bitlen, - SCRadixTree *tree, void **user_data_result) -{ - return SCRadixFindKey(key_stream, key_bitlen, tree, 1, user_data_result); -} - -/** - * \brief Checks if an IPV4 address is present in the tree - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV4 address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV4ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result) -{ - return SCRadixFindKey(key_stream, 32, tree, 1, user_data_result); -} - -/** - * \brief Checks if an IPV4 address is present in the tree under a netblock - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV4 address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result) -{ - return SCRadixFindKey(key_stream, 32, tree, 0, user_data_result); -} - -/** - * \brief Checks if an IPV4 Netblock address is present in the tree - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV4 netblock address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV4Netblock(uint8_t *key_stream, SCRadixTree *tree, - uint8_t netmask, void **user_data_result) -{ - SCRadixNode *node = NULL; - node = SCRadixFindKey(key_stream, 32, tree, 0, user_data_result); - if (node == NULL) - return node; - - if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, netmask, 1, user_data_result)) - return node; - else - return NULL; -} - -/** - * \brief Checks if an IPV6 Netblock address is present in the tree - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV6 netblock address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV6Netblock(uint8_t *key_stream, SCRadixTree *tree, - uint8_t netmask, void **user_data_result) -{ - SCRadixNode *node = NULL; - node = SCRadixFindKey(key_stream, 128, tree, 0, user_data_result); - if (node == NULL) - return node; - - if (SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, (uint16_t)netmask, 1, user_data_result)) - return node; - else - return NULL; -} - -/** - * \brief Checks if an IPV6 address is present in the tree - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV6 address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV6ExactMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result) -{ - return SCRadixFindKey(key_stream, 128, tree, 1, user_data_result); -} - -/** - * \brief Checks if an IPV6 address is present in the tree under a netblock - * - * \param key_stream Data that has to be found in the Radix tree. In this case - * an IPV6 address - * \param tree Pointer to the Radix tree instance - */ -SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *key_stream, SCRadixTree *tree, void **user_data_result) -{ - return SCRadixFindKey(key_stream, 128, tree, 0, user_data_result); -} - -/** - * \brief Prints the node information from a Radix tree - * - * \param node Pointer to the Radix node whose information has to be printed - * \param level Used for indentation purposes - */ -void SCRadixPrintNodeInfo(SCRadixNode *node, int level, void (*PrintData)(void*)) -{ - int i = 0; - - if (node == NULL) - return; - - for (i = 0; i < level; i++) - printf(" "); - - printf("%d [", node->bit); - - if (node->netmasks == NULL) { - printf("%d, ", -1); - } else { - for (i = 0; i < node->netmask_cnt; i++) - printf("%s%d", (0 == i ? "" : ", "), node->netmasks[i]); - } - - printf("] ("); - if (node->prefix != NULL) { - for (i = 0; i * 8 < node->prefix->bitlen; i++) - printf("%s%d", (0 == i ? "" : "."), node->prefix->stream[i]); - printf(")\n"); - - SCRadixUserData *ud = NULL; - if (PrintData != NULL) { - do { - ud = node->prefix->user_data; - printf(" [%d], ", ud->netmask); - PrintData(ud->user); - ud = ud->next; - } while (ud != NULL); - } else { - //ud = node->prefix->user_data; - //while (ud != NULL) { - // printf(" [nm %d with data], ", ud->netmask); - // ud = ud->next; - //} - printf("No print function provided"); - } - printf("\n"); - } else { - printf("NULL)\n"); - } - - return; -} - -/** - * \brief Helper function used by SCRadixPrintTree. Prints the subtree with - * node as the root of the subtree - * - * \param node Pointer to the node that is the root of the subtree to be printed - * \param level Used for indentation purposes - */ -static void SCRadixPrintRadixSubtree(SCRadixNode *node, int level, void (*PrintData)(void*)) -{ - if (node != NULL) { - SCRadixPrintNodeInfo(node, level, PrintData); - SCRadixPrintRadixSubtree(node->left, level + 1, PrintData); - SCRadixPrintRadixSubtree(node->right, level + 1, PrintData); - } - - return; -} - -/** - * \brief Prints the Radix Tree. While printing the radix tree we use the - * following format - * - * Parent_0 - * Left_Child_1 - * Left_Child_2 - * Right_Child_2 - * Right_Child_1 - * Left_Child_2 - * Right_Child_2 and so on - * - * Each node printed out holds details on the next bit that differs - * amongst its children, and if the node holds a prefix, the perfix is - * printed as well. - * - * \param tree Pointer to the Radix tree that has to be printed - */ -void SCRadixPrintTree(SCRadixTree *tree) -{ - printf("Printing the Radix Tree: \n"); - - SCRadixPrintRadixSubtree(tree->head, 0, tree->PrintData); - - return; -} - -/*------------------------------------Unit_Tests------------------------------*/ - -#ifdef UNITTESTS - -int SCRadixTestInsertion01(void) -{ - SCRadixTree *tree = NULL; - SCRadixNode *node[2]; - - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - - node[0] = SCRadixAddKeyGeneric((uint8_t *)"abaa", 32, tree, NULL); - node[1] = SCRadixAddKeyGeneric((uint8_t *)"abab", 32, tree, NULL); - - result &= (tree->head->bit == 30); - result &= (tree->head->right == node[0]); - result &= (tree->head->left == node[1]); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestInsertion02(void) -{ - SCRadixTree *tree = NULL; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - SCRadixAddKeyGeneric((uint8_t *)"aaaaaa", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"aaaaab", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"aaaaaba", 56, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"abab", 32, tree, NULL); - SCRadixReleaseRadixTree(tree); - - /* If we don't have a segfault till here we have succeeded :) */ - return result; -} - -int SCRadixTestIPV4Insertion03(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - /* add a key that already exists in the tree */ - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - /* continue adding keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - /* test the existence of keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.3", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "127.234.2.62", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV4Removal04(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - /* remove the keys from the tree */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.1", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4((uint8_t *)&servaddr.sin_addr, tree); - - result &= (tree->head == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestCharacterInsertion05(void) -{ - SCRadixTree *tree = NULL; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* Let us have our team here ;-) */ - SCRadixAddKeyGeneric((uint8_t *)"Victor", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Matt", 32, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Josh", 32, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Margaret", 64, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Pablo", 40, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Brian", 40, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Jasonish", 64, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Jasonmc", 56, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Nathan", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Anoop", 40, tree, NULL); - - result &= (SCRadixFindKeyGeneric((uint8_t *)"Victor", 48, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Matt", 32, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Josh", 32, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Margaret", 64, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Pablo", 40, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Brian", 40, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Jasonish", 64, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Jasonmc", 56, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Nathan", 48, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Anoop", 40, tree, NULL) != NULL); - - result &= (SCRadixFindKeyGeneric((uint8_t *)"bamboo", 48, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"bool", 32, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"meerkat", 56, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Victor", 48, tree, NULL) == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestCharacterRemoval06(void) -{ - SCRadixTree *tree = NULL; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* Let us have our team here ;-) */ - SCRadixAddKeyGeneric((uint8_t *)"Victor", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Matt", 32, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Josh", 32, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Margaret", 64, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Pablo", 40, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Brian", 40, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Jasonish", 64, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Jasonmc", 56, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Nathan", 48, tree, NULL); - SCRadixAddKeyGeneric((uint8_t *)"Anoop", 40, tree, NULL); - - SCRadixRemoveKeyGeneric((uint8_t *)"Nathan", 48, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Brian", 40, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Margaret", 64, tree); - - result &= (SCRadixFindKeyGeneric((uint8_t *)"Victor", 48, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Matt", 32, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Josh", 32, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Margaret", 64, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Brian", 40, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Nathan", 48, tree, NULL) == NULL); - - SCRadixRemoveKeyGeneric((uint8_t *)"Victor", 48, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Josh", 32, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Jasonmc", 56, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Matt", 32, tree); - - result &= (SCRadixFindKeyGeneric((uint8_t *)"Pablo", 40, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Jasonish", 64, tree, NULL) != NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Anoop", 40, tree, NULL) != NULL); - - SCRadixRemoveKeyGeneric((uint8_t *)"Pablo", 40, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Jasonish", 64, tree); - SCRadixRemoveKeyGeneric((uint8_t *)"Anoop", 40, tree); - - result &= (SCRadixFindKeyGeneric((uint8_t *)"Pablo", 40, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Jasonish", 64, tree, NULL) == NULL); - result &= (SCRadixFindKeyGeneric((uint8_t *)"Anoop", 40, tree, NULL) == NULL); - - result &= (tree->head == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV6Insertion07(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* Try to add the prefix that already exists in the tree */ - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* test the existence of keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV6Removal08(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* Try to add the prefix that already exists in the tree */ - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* test the existence of keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "8888:0BF1:5346:BDEA:6422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2006:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* test for existance */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:DDDD:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - /* remove keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - /* test for existance */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - /* remove keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree); - - /* test for existance */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV4NetblockInsertion09(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.3", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.1.2", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.18", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.192.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18); - - if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.170.1.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.145", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.64.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.191.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.224.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.174.224.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.175.224.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV4NetblockInsertion10(void) -{ - SCRadixTree *tree = NULL; - SCRadixNode *node[2]; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0) - return 0; - node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, - 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18); - - if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]); - - /* let us remove a netblock */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV4NetblockInsertion11(void) -{ - SCRadixTree *tree = NULL; - SCRadixNode *node = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18); - - if (inet_pton(AF_INET, "192.175.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) - return 0; - node = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 0); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL && - SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "245.63.62.121", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL && - SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL && - SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node); - - /* remove node 0.0.0.0 */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixRemoveKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, 0); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.6", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "1.1.1.1", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.255.254.25", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "169.255.254.25", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV4NetblockInsertion12(void) -{ - SCRadixTree *tree = NULL; - SCRadixNode *node[2]; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.192.235.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.167.1.4", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "220.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "253.224.1.5", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.0", &servaddr.sin_addr) <= 0) - return 0; - node[0] = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 24); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - node[1] = SCRadixAddKeyIPV4((uint8_t *)&servaddr.sin_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 18); - - if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 32); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.53", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.45", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[1]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.128.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == node[0]); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.171.127.78", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "225.175.21.228", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "225.175.21.224", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "225.175.21.229", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "225.175.21.230", &servaddr.sin_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV4ExactMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) == NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV6NetblockInsertion13(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - /* test the existence of keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABC2:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF5:5346:1251:7422:1112:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBCA:1245:2342:1111:2212", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1146:6241", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1356:1241", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DAAA:1245:2342:1146:6241", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - - SCRadixReleaseRadixTree(tree); - - return result; -} - -int SCRadixTestIPV6NetblockInsertion14(void) -{ - SCRadixTree *tree = NULL; - SCRadixNode *node = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - /* add the keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2003:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "BD15:9791:5346:6223:AADB:8713:9882:2432", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "1111:A21B:6221:BDEA:BBBA::DBAA:9861", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "4444:0BF7:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "5555:0BF1:ABCD:ADEA:7922:ABCD:9124:2375", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DB00:0000:0000:0000:0000", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, 56); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241", - &servaddr.sin6_addr) <= 0) - return 0; - SCRadixAddKeyIPV6((uint8_t *)&servaddr.sin6_addr, tree, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "::", &servaddr.sin6_addr) <= 0) - return 0; - node = SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, NULL, - 0); - - /* test the existence of keys */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2004:0BF1:5346:BDEA:7422:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2004:0BF1:5346:B116:2362:8713:9124:2315", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "2004:0B23:3252:BDEA:7422:8713:9124:2341", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) == node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL && - SCRadixFindKeyIPV6ExactMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DBCA:ABCD:ABCD:DBAA:1245:2342:1145:6241", - &servaddr.sin6_addr) <= 0) - return 0; - result &= (SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != NULL && - SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, NULL) != node); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV4NetBlocksAndBestSearch15(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.1", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 32; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV4NetBlocksAndBestSearch16(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.1", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 32; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV4NetBlocksAndBestSearch17(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "10.0.0.1", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 32; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV4NetBlocksAndBestSearch18(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "172.26.0.1", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 32; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check special combinations of netblocks and addresses - * on best search checking the returned userdata - */ -int SCRadixTestIPV4NetBlocksAndBestSearch19(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - void *user_data = NULL; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 100; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 0); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - SCRadixNode *node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 100) { - result = 0; - goto end; - } - - user_data = NULL; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.0.0.0", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 200; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 8); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 200) { - result = 0; - goto end; - } - - user_data = NULL; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "178.168.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t*)user_data) != 100) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.168.0.0", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 300; - - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, user, 12); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.168.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t*)user_data) != 300) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.167.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 300) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "177.178.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 200) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "197.178.1.15", &servaddr.sin_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 100) { - result = 0; - goto end; - } - - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV6NetBlocksAndBestSearch20(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABAB:CDCD:ABAB:CDCD:1234:4321:1234:4321", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 128; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV6NetBlocksAndBestSearch21(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ff00::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 128; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV6NetBlocksAndBestSearch22(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ff00::192:168:1:1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 128; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check that the best match search works for all the - * possible netblocks of a fixed address - */ -int SCRadixTestIPV6NetBlocksAndBestSearch23(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t i = 0; - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "FF00:ABCD:BCDA::ABCD", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - for (; i <= 128; i++) { - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = i; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, i); - - void *user_data = NULL; - SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != i) { - printf("User data == %"PRIu32"; i == %"PRIu32": ", *( (uint32_t *)user_data), i); - result = 0; - goto end; - } - } - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test Check special combinations of netblocks and addresses - * on best search checking the returned userdata - */ -int SCRadixTestIPV6NetBlocksAndBestSearch24(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in6 servaddr; - int result = 1; - void *user_data = NULL; - - tree = SCRadixCreateRadixTree(free, NULL); - - uint32_t *user; - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "::", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 100; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 0); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - SCRadixNode *node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t*)user_data) != 100) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD::0", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 200; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 8); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 200) { - printf("User data == %"PRIu32"; i != 200 ", *( (uint32_t *)user_data)); - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "DCBA::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 100) { - printf("User data == %"PRIu32"; != 100 ", *( (uint32_t *)user_data)); - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD:ABCD::0", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - user = SCMalloc(sizeof(uint32_t)); - if (unlikely(user == NULL)) { - result = 0; - goto end; - } - - *user = 300; - - SCRadixAddKeyIPV6Netblock((uint8_t *)&servaddr.sin6_addr, tree, user, 12); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD:ABCD::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 300) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABCD:AAAA::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 300) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "ABAB::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 200) { - result = 0; - goto end; - } - - user_data = NULL; - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET6, "CABD::1", &servaddr.sin6_addr) <= 0) { - result = 0; - goto end; - } - - node = SCRadixFindKeyIPV6BestMatch((uint8_t *)&servaddr.sin6_addr, tree, &user_data); - if (node == NULL) { - printf("node == NULL: "); - result = 0; - goto end; - } - - if (user_data == NULL) { - printf("User data == NULL: "); - result = 0; - goto end; - } - - if ( *( (uint32_t *)user_data) != 100) { - result = 0; - goto end; - } - - -end: - SCRadixReleaseRadixTree(tree); - - return result; -} - - -/** - * \test SCRadixTestIPV4NetblockInsertion15 insert a node searching on it. - * Should always return true but the purposse of the test is to monitor - * the memory usage to detect memleaks (there was one on searching) - */ -int SCRadixTestIPV4NetblockInsertion25(void) -{ - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - - tree = SCRadixCreateRadixTree(free, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.0.0", &servaddr.sin_addr) <= 0) - return 0; - SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, NULL, 16); - - /* test for the existance of a key */ - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "192.168.128.53", &servaddr.sin_addr) <= 0) - return 0; - - result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree, NULL) != NULL); - - SCRadixReleaseRadixTree(tree); - - return result; -} - -/** - * \test SCRadixTestIPV4NetblockInsertion26 insert a node searching on it. - * Should always return true but the purposse of the test is to monitor - * the memory usage to detect memleaks (there was one on searching) - */ -int SCRadixTestIPV4NetblockInsertion26(void) -{ - SCRadixNode *tmp = NULL; - SCRadixTree *tree = NULL; - struct sockaddr_in servaddr; - int result = 1; - char *str = SCStrdup("Hello1"); - - tree = SCRadixCreateRadixTree(free, NULL); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) - return 0; - tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 0); - if (!tmp) { - printf("Not inserted correctly 1:"); - result = 0; - goto this_end; - } - str = SCStrdup("Hello1"); - - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "176.0.0.1", &servaddr.sin_addr) <= 0) - return 0; - tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 5); - if (!tmp) { - printf("Not inserted correctly 2:"); - result = 0; - goto this_end; - } - - str = SCStrdup("Hello1"); - bzero(&servaddr, sizeof(servaddr)); - if (inet_pton(AF_INET, "0.0.0.0", &servaddr.sin_addr) <= 0) { - SCFree(str); - return 0; - } - tmp = SCRadixAddKeyIPV4Netblock((uint8_t *)&servaddr.sin_addr, tree, str, 7); - if (!tmp) { - printf("Not inserted correctly 3:"); - result = 0; - goto this_end; - } - - /* test for the existance of a key */ - //result &= (SCRadixFindKeyIPV4BestMatch((uint8_t *)&servaddr.sin_addr, tree) != NULL); - -this_end: - SCRadixReleaseRadixTree(tree); - - //SCFree(str); - return result; -} - -#endif - -void SCRadixRegisterTests(void) -{ - -#ifdef UNITTESTS - //UtRegisterTest("SCRadixTestInsertion01", SCRadixTestInsertion01, 1); - //UtRegisterTest("SCRadixTestInsertion02", SCRadixTestInsertion02, 1); - UtRegisterTest("SCRadixTestIPV4Insertion03", SCRadixTestIPV4Insertion03, 1); - UtRegisterTest("SCRadixTestIPV4Removal04", SCRadixTestIPV4Removal04, 1); - //UtRegisterTest("SCRadixTestCharacterInsertion05", - // SCRadixTestCharacterInsertion05, 1); - //UtRegisterTest("SCRadixTestCharacterRemoval06", - // SCRadixTestCharacterRemoval06, 1); - UtRegisterTest("SCRadixTestIPV6Insertion07", SCRadixTestIPV6Insertion07, 1); - UtRegisterTest("SCRadixTestIPV6Removal08", SCRadixTestIPV6Removal08, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion09", - SCRadixTestIPV4NetblockInsertion09, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion10", - SCRadixTestIPV4NetblockInsertion10, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion11", - SCRadixTestIPV4NetblockInsertion11, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion12", - SCRadixTestIPV4NetblockInsertion12, 1); - UtRegisterTest("SCRadixTestIPV6NetblockInsertion13", - SCRadixTestIPV6NetblockInsertion13, 1); - UtRegisterTest("SCRadixTestIPV6NetblockInsertion14", - SCRadixTestIPV6NetblockInsertion14, 1); - UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch15", - SCRadixTestIPV4NetBlocksAndBestSearch15, 1); - UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch16", - SCRadixTestIPV4NetBlocksAndBestSearch16, 1); - UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch17", - SCRadixTestIPV4NetBlocksAndBestSearch17, 1); - UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch18", - SCRadixTestIPV4NetBlocksAndBestSearch18, 1); - UtRegisterTest("SCRadixTestIPV4NetBlocksAndBestSearch19", - SCRadixTestIPV4NetBlocksAndBestSearch19, 1); - UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch20", - SCRadixTestIPV6NetBlocksAndBestSearch20, 1); - UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch21", - SCRadixTestIPV6NetBlocksAndBestSearch21, 1); - UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch22", - SCRadixTestIPV6NetBlocksAndBestSearch22, 1); - UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch23", - SCRadixTestIPV6NetBlocksAndBestSearch23, 1); - UtRegisterTest("SCRadixTestIPV6NetBlocksAndBestSearch24", - SCRadixTestIPV6NetBlocksAndBestSearch24, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion25", - SCRadixTestIPV4NetblockInsertion25, 1); - UtRegisterTest("SCRadixTestIPV4NetblockInsertion26", - SCRadixTestIPV4NetblockInsertion26, 1); -#endif - - return; -} |