/** * @file ethHash.c * * @brief Hashtable implementation *  * @par * IXP400 SW Release version 2.0 *  * -- Copyright Notice -- *  * @par * Copyright 2001-2005, Intel Corporation. * All rights reserved. *  * @par * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. Neither the name of the Intel Corporation nor the names of its contributors *    may be used to endorse or promote products derived from this software *    without specific prior written permission. *  * @par * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. *  * @par * -- End of Copyright Notice -- */#include "IxEthDB_p.h"#include "IxEthDBLocks_p.h"/** * @addtogroup EthDB * * @{ *//** * @brief initializes a hash table object * * @param hashTable uninitialized hash table structure * @param numBuckets number of buckets to use * @param entryHashFunction hash function used  * to hash entire hash node data block (for adding) * @param matchFunctions array of match functions, indexed on type, * used to differentiate records with the same hash value * @param freeFunction function used to free node data blocks * * Initializes the given hash table object. * * @internal */void ixEthDBInitHash(HashTable *hashTable,                      UINT32 numBuckets,                      HashFunction entryHashFunction,                      MatchFunction *matchFunctions,                      FreeFunction freeFunction){    UINT32 bucketIndex;    UINT32 hashSize = numBuckets * sizeof(HashNode *);    /* entry hashing, matching and freeing methods */    hashTable->entryHashFunction  = entryHashFunction;    hashTable->matchFunctions     = matchFunctions;    hashTable->freeFunction       = freeFunction;    /* buckets */    hashTable->numBuckets = numBuckets;    /* set to 0 all buckets */    memset(hashTable->hashBuckets, 0, hashSize);    /* init bucket locks - note that initially all mutexes are unlocked after MutexInit()*/    for (bucketIndex = 0 ; bucketIndex < numBuckets ; bucketIndex++)    {        ixOsalFastMutexInit(&hashTable->bucketLocks[bucketIndex]);    }}/** * @brief adds an entry to the hash table * * @param hashTable hash table to add the entry to * @param entry entry to add * * The entry will be hashed using the entry hashing function and added to the * hash table, unless a locking blockage occurs, in which case the caller * should retry. * * @retval IX_ETH_DB_SUCCESS if adding <i>entry</i> has succeeded * @retval IX_ETH_DB_NOMEM if there's no memory left in the hash node pool * @retval IX_ETH_DB_BUSY if there's a locking failure on the insertion path * * @internal */IX_ETH_DB_PUBLIC IxEthDBStatus ixEthDBAddHashEntry(HashTable *hashTable, void *entry){    UINT32 hashValue   = hashTable->entryHashFunction(entry);    UINT32 bucketIndex = hashValue % hashTable->numBuckets;    HashNode *bucket   = hashTable->hashBuckets[bucketIndex];    HashNode *newNode;    LockStack locks;    INIT_STACK(&locks);    /* lock bucket */    PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);    /* lock insertion element (first in chain), if any */    if (bucket != NULL)    {        PUSH_LOCK(&locks, &bucket->lock);    }    /* get new node */    newNode = ixEthDBAllocHashNode();    if (newNode == NULL)    {        /* unlock everything */        UNROLL_STACK(&locks);        return IX_ETH_DB_NOMEM;    }    /* init lock - note that mutexes are unlocked after MutexInit */    ixOsalFastMutexInit(&newNode->lock);    /* populate new link */    newNode->data = entry;    /* add to bucket */    newNode->next                       = bucket;    hashTable->hashBuckets[bucketIndex] = newNode;    /* unlock bucket and insertion point */    UNROLL_STACK(&locks);    return IX_ETH_DB_SUCCESS;}/** * @brief removes an entry from the hashtable * * @param hashTable hash table to remove entry from * @param keyType type of record key used for matching * @param reference reference key used to identify the entry * * The reference key will be hashed using the key hashing function, * the entry is searched using the hashed value and then examined * against the reference entry using the match function. A positive * match will trigger the deletion of the entry. * Locking failures are reported and the caller should retry. * * @retval IX_ETH_DB_SUCCESS if the removal was successful * @retval IX_ETH_DB_NO_SUCH_ADDR if the entry was not found * @retval IX_ETH_DB_BUSY if a locking failure occured during the process * * @internal */IxEthDBStatus ixEthDBRemoveHashEntry(HashTable *hashTable, int keyType, void *reference){    UINT32 hashValue       = hashTable->entryHashFunction(reference);    UINT32 bucketIndex     = hashValue % hashTable->numBuckets;    HashNode *node         = hashTable->hashBuckets[bucketIndex];    HashNode *previousNode = NULL;        LockStack locks;    INIT_STACK(&locks);    while (node != NULL)    {        /* try to lock node */        PUSH_LOCK(&locks, &node->lock);        if (hashTable->matchFunctions[keyType](reference, node->data))        {            /* found entry */            if (node->next != NULL)            {                PUSH_LOCK(&locks, &node->next->lock);            }            if (previousNode == NULL)            {                /* node is head of chain */                PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);                hashTable->hashBuckets[bucketIndex] = node->next;                POP_LOCK(&locks);            }            else            {                /* relink */                previousNode->next = node->next;            }            UNROLL_STACK(&locks);            /* free node */            hashTable->freeFunction(node->data);            ixEthDBFreeHashNode(node);            return IX_ETH_DB_SUCCESS;        }        else        {            if (previousNode != NULL)            {                /* unlock previous node */                SHIFT_STACK(&locks);            }            /* advance to next element in chain */            previousNode = node;            node         = node->next;        }    }    UNROLL_STACK(&locks);    /* not found */    return IX_ETH_DB_NO_SUCH_ADDR;}/** * @brief retrieves an entry from the hash table * * @param hashTable hash table to perform the search into * @param reference search key (a MAC address) * @param keyType type of record key used for matching * @param searchResult pointer where a reference to the located hash node  * is placed * * Searches the entry with the same key as <i>reference</i> and places the * pointer to the resulting node in <i>searchResult</i>. * An implicit write access lock is granted after a search, which gives the  * caller the opportunity to modify the entry. * Access should be released as soon as possible using @ref ixEthDBReleaseHashNode(). * * @see ixEthDBReleaseHashNode() * * @retval IX_ETH_DB_SUCCESS if the search was completed successfully * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case * the caller should retry * * @warning unless the return value is <b>IX_ETH_DB_SUCCESS</b> the searchResult * location is NOT modified and therefore using a NULL comparison test when the * value was not properly initialized would be an error * * @internal */IxEthDBStatus ixEthDBSearchHashEntry(HashTable *hashTable, int keyType, void *reference, HashNode **searchResult){    UINT32 hashValue;    HashNode *node;    hashValue = hashTable->entryHashFunction(reference);    node      = hashTable->hashBuckets[hashValue % hashTable->numBuckets];    while (node != NULL)    {        TRY_LOCK(&node->lock);        if (hashTable->matchFunctions[keyType](reference, node->data))        {            *searchResult = node;            return IX_ETH_DB_SUCCESS;        }        else        {            UNLOCK(&node->lock);            node = node->next;        }    }    /* not found */    return IX_ETH_DB_NO_SUCH_ADDR;}/** * @brief reports the existence of an entry in the hash table * * @param hashTable hash table to perform the search into * @param reference search key (a MAC address) * @param keyType type of record key used for matching * * Searches the entry with the same key as <i>reference</i>. * No implicit write access lock is granted after a search, hence the  * caller cannot access or modify the entry. The result is only temporary. * * @see ixEthDBReleaseHashNode() * * @retval IX_ETH_DB_SUCCESS if the search was completed successfully * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case * the caller should retry * * @internal