ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);    }    /* forget last used search tree */    port->updateMethod.searchTree             = NULL;    port->updateMethod.searchTreePendingWrite = FALSE;    /* dependending on the update type we do different things */    if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)    {        IX_STATUS result;        FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),             epDelta, blockCount,             IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));        IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);        if (result == IX_SUCCESS)	{            IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);        }        else        {            ixEthDBPortInfo[portID].agingEnabled                = FALSE;            ixEthDBPortInfo[portID].updateMethod.updateEnabled  = FALSE;            ixEthDBPortInfo[portID].updateMethod.userControlled = TRUE;            ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);            ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);            return IX_ETH_DB_FAIL;        }	return IX_ETH_DB_SUCCESS;    }    else if (type == IX_ETH_DB_FIREWALL_RECORD)    {        return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);    }        return IX_ETH_DB_INVALID_ARG;}/** * @brief queries the database for a set of records to be inserted into a given tree * * @param searchTree pointer to a tree where insertions will be performed; can be NULL * @param query set of ports that a database record must match to be inserted into the tree * * The query method browses through the database, extracts all the descriptors matching * the given query parameter and inserts them into the given learning tree. * Note that this is an append procedure, the given tree needs not to be empty. * A "descriptor matching the query" is a descriptor whose port id is in the query map. * If the given tree is empty (NULL) a new tree is created and returned. *  * @return the tree root * * @internal */IX_ETH_DB_PUBLICMacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries){    HashIterator iterator;    UINT32 entryCount = 0;    /* browse database */    BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));    while (IS_ITERATOR_VALID(&iterator))    {        MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data;        IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",             mac2string(descriptor->macAddress),             descriptor->portID);	if ((descriptor->type & recordFilter) != 0             && IS_PORT_INCLUDED(descriptor->portID, query))	{            MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);            IX_ETH_DB_UPDATE_TRACE("match\n");            if (descriptorClone != NULL)            {                /* add descriptor to tree */                searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);                entryCount++;            }        }        else        {            IX_ETH_DB_UPDATE_TRACE("no match\n");        }        if (entryCount < maxEntries)        {            /* advance to the next record */	        BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));        }        else        {            /* the NPE won't accept more entries so we can stop now */            ixEthDBReleaseHashIterator(&iterator);            IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");            break;        }    }    IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);    return ixEthDBTreeRebalance(searchTree);}/** * @brief inserts a mac descriptor into an tree * * @param searchTree tree where the insertion is to be performed (may be NULL) * @param descriptor descriptor to insert into tree * * @return the tree root * * @internal */IX_ETH_DB_PRIVATEMacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor){    MacTreeNode *currentNode    = searchTree;    MacTreeNode *insertLocation = NULL;    MacTreeNode *newNode;    INT32 insertPosition = RIGHT;    if (descriptor == NULL)    {        return searchTree;    }    /* create a new node */    newNode = ixEthDBAllocMacTreeNode();    if (newNode == NULL)    {        /* out of memory */        ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);        ixEthDBFreeMacDescriptor(descriptor);        return NULL;    }    /* populate node */    newNode->descriptor = descriptor;    /* an empty initial tree is a special case */    if (searchTree == NULL)    {        return newNode;    }    /* get insertion location */    while (insertLocation == NULL)    {        MacTreeNode *nextNode;        /* compare given key with current node key */        insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);        /* navigate down */        if (insertPosition == RIGHT)        {            nextNode = currentNode->right;        }        else if (insertPosition == LEFT)        {            nextNode = currentNode->left;        }        else        {            /* error, duplicate key */            ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");            /* this will free the MAC descriptor as well */            ixEthDBFreeMacTreeNode(newNode);            return searchTree;        }        /* when we can no longer dive through the tree we found the insertion place */        if (nextNode != NULL)        {            currentNode = nextNode;        }        else        {            insertLocation = currentNode;        }    }    /* insert node */    if (insertPosition == RIGHT)    {        insertLocation->right = newNode;    }    else    {        insertLocation->left = newNode;    }    return searchTree;}/** * @brief balance a tree * * @param searchTree tree to balance * * Converts a tree into a balanced tree and returns the root of * the balanced tree. The resulting tree is <i>route balanced</i> * not <i>perfectly balanced</i>. This makes no difference to the * average tree search time which is the same in both cases, O(log2(n)). * * @return root of the balanced tree or NULL if there's no memory left * * @internal */IX_ETH_DB_PRIVATEMacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree){    MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();    UINT32 size;    if (pseudoRoot == NULL)    {        /* out of memory */        return NULL;    }    pseudoRoot->right = searchTree;    ixEthDBRebalanceTreeToVine(pseudoRoot, &size);    ixEthDBRebalanceVineToTree(pseudoRoot, size);    searchTree = pseudoRoot->right;    /* remove pseudoRoot right branch, otherwise it will free the entire tree */    pseudoRoot->right = NULL;    ixEthDBFreeMacTreeNode(pseudoRoot);    return searchTree;}/** * @brief converts a tree into a vine * * @param root root of tree to convert * @param size depth of vine (equal to the number of nodes in the tree) * * @internal */IX_ETH_DB_PRIVATEvoid ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size){    MacTreeNode *vineTail  = root;    MacTreeNode *remainder = vineTail->right;    MacTreeNode *tempPtr;    *size = 0;    while (remainder != NULL)    {        if (remainder->left == NULL)        {            /* move tail down one */            vineTail  = remainder;            remainder = remainder->right;            (*size)++;        }        else        {            /* rotate around remainder */            tempPtr         = remainder->left;            remainder->left = tempPtr->right;            tempPtr->right  = remainder;            remainder       = tempPtr;            vineTail->right = tempPtr;        }    }}/** * @brief converts a vine into a balanced tree * * @param root vine to convert * @param size depth of vine * * @internal */IX_ETH_DB_PRIVATEvoid ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size){    UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));    ixEthDBRebalanceCompression(root, leafCount);    size = size - leafCount;    while (size > 1)    {        ixEthDBRebalanceCompression(root, size / 2);        size /= 2;    }}/** * @brief compresses a vine/tree stage into a more balanced vine/tree * * @param root root of the tree to compress * @param count number of "spine" nodes * * @internal */IX_ETH_DB_PRIVATEvoid ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count){    MacTreeNode *scanner = root;    MacTreeNode *child;    UINT32 local_index;    for (local_index = 0 ; local_index < count ; local_index++)    {        child          = scanner->right;        scanner->right = child->right;        scanner        = scanner->right;        child->right   = scanner->left;        scanner->left  = child;    }}/** * @brief computes |_log2(x)_| (a.k.a. floor(log2(x))) * * @param x number to compute |_log2(x)_| for * * @return |_log2(x)_| * * @internal */IX_ETH_DB_PRIVATEUINT32 ixEthDBRebalanceLog2Floor(UINT32 x){    UINT32 log = 0;    UINT32 val = 1;    while (val < x)    {        log++;        val <<= 1;    }    return val == x ? log : log - 1;}