ixethdbhashtable.c

AMCC POWERPC 44X系列的U-BOOT文件

/**
 * @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