summaryrefslogtreecommitdiff
path: root/cpu/ixp/npe/IxEthDBHashtable.c
diff options
context:
space:
mode:
Diffstat (limited to 'cpu/ixp/npe/IxEthDBHashtable.c')
-rw-r--r--cpu/ixp/npe/IxEthDBHashtable.c642
1 files changed, 0 insertions, 642 deletions
diff --git a/cpu/ixp/npe/IxEthDBHashtable.c b/cpu/ixp/npe/IxEthDBHashtable.c
deleted file mode 100644
index f1b18e6..0000000
--- a/cpu/ixp/npe/IxEthDBHashtable.c
+++ /dev/null
@@ -1,642 +0,0 @@
-/**
- * @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
- */
-IxEthDBStatus ixEthDBPeekHashEntry(HashTable *hashTable, int keyType, void *reference)
-{
- 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))
- {
- UNLOCK(&node->lock);
-
- return IX_ETH_DB_SUCCESS;
- }
- else
- {
- UNLOCK(&node->lock);
-
- node = node->next;
- }
- }
-
- /* not found */
- return IX_ETH_DB_NO_SUCH_ADDR;
-}
-
-/**
- * @brief releases the write access lock
- *
- * @pre the node should have been obtained via @ref ixEthDBSearchHashEntry()
- *
- * @see ixEthDBSearchHashEntry()
- *
- * @internal
- */
-void ixEthDBReleaseHashNode(HashNode *node)
-{
- UNLOCK(&node->lock);
-}
-
-/**
- * @brief initializes a hash iterator
- *
- * @param hashTable hash table to be iterated
- * @param iterator iterator object
- *
- * If the initialization is successful the iterator will point to the
- * first hash table record (if any).
- * Testing if the iterator has not passed the end of the table should be
- * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
- * An implicit write access lock is granted on the entry pointed by the iterator.
- * The access is automatically revoked when the iterator is incremented.
- * If the caller decides to terminate the iteration before the end of the table is
- * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
- * must be called.
- *
- * @see ixEthDBReleaseHashIterator()
- *
- * @retval IX_ETH_DB_SUCCESS if initialization was successful and the iterator points
- * to the first valid table node
- * @retval IX_ETH_DB_FAIL if the table is empty
- * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
- * should retry
- *
- * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
- * might place the database in a permanent invalid lock state
- *
- * @internal
- */
-IxEthDBStatus ixEthDBInitHashIterator(HashTable *hashTable, HashIterator *iterator)
-{
- iterator->bucketIndex = 0;
- iterator->node = NULL;
- iterator->previousNode = NULL;
-
- return ixEthDBIncrementHashIterator(hashTable, iterator);
-}
-
-/**
- * @brief releases the write access locks of the iterator nodes
- *
- * @warning use of this function is required only when the caller terminates an iteration
- * before reaching the end of the table
- *
- * @see ixEthDBInitHashIterator()
- * @see ixEthDBIncrementHashIterator()
- *
- * @param iterator iterator whose node(s) should be unlocked
- *
- * @internal
- */
-void ixEthDBReleaseHashIterator(HashIterator *iterator)
-{
- if (iterator->previousNode != NULL)
- {
- UNLOCK(&iterator->previousNode->lock);
- }
-
- if (iterator->node != NULL)
- {
- UNLOCK(&iterator->node->lock);
- }
-}
-
-/**
- * @brief incremenents an iterator so that it points to the next valid entry of the table
- * (if any)
- *
- * @param hashTable hash table to iterate
- * @param iterator iterator object
- *
- * @pre the iterator object must be initialized using @ref ixEthDBInitHashIterator()
- *
- * If the increment operation is successful the iterator will point to the
- * next hash table record (if any).
- * Testing if the iterator has not passed the end of the table should be
- * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
- * An implicit write access lock is granted on the entry pointed by the iterator.
- * The access is automatically revoked when the iterator is re-incremented.
- * If the caller decides to terminate the iteration before the end of the table is
- * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
- * must be called.
- * Is is guaranteed that no other thread can remove or change the iterated entry until
- * the iterator is incremented successfully.
- *
- * @see ixEthDBReleaseHashIterator()
- *
- * @retval IX_ETH_DB_SUCCESS if the operation was successful and the iterator points
- * to the next valid table node
- * @retval IX_ETH_DB_FAIL if the iterator has passed the end of the table
- * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
- * should retry
- *
- * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
- * might place the database in a permanent invalid lock state
- *
- * @internal
- */
-IxEthDBStatus ixEthDBIncrementHashIterator(HashTable *hashTable, HashIterator *iterator)
-{
- /* unless iterator is just initialized... */
- if (iterator->node != NULL)
- {
- /* try next in chain */
- if (iterator->node->next != NULL)
- {
- TRY_LOCK(&iterator->node->next->lock);
-
- if (iterator->previousNode != NULL)
- {
- UNLOCK(&iterator->previousNode->lock);
- }
-
- iterator->previousNode = iterator->node;
- iterator->node = iterator->node->next;
-
- return IX_ETH_DB_SUCCESS;
- }
- else
- {
- /* last in chain, prepare for next bucket */
- iterator->bucketIndex++;
- }
- }
-
- /* try next used bucket */
- for (; iterator->bucketIndex < hashTable->numBuckets ; iterator->bucketIndex++)
- {
- HashNode **nodePtr = &(hashTable->hashBuckets[iterator->bucketIndex]);
- HashNode *node = *nodePtr;
-#if (CPU!=SIMSPARCSOLARIS) && !defined (__wince)
- if (((iterator->bucketIndex & IX_ETHDB_BUCKET_INDEX_MASK) == 0) &&
- (iterator->bucketIndex < (hashTable->numBuckets - IX_ETHDB_BUCKETPTR_AHEAD)))
- {
- /* preload next cache line (2 cache line ahead) */
- nodePtr += IX_ETHDB_BUCKETPTR_AHEAD;
- __asm__ ("pld [%0];\n": : "r" (nodePtr));
- }
-#endif
- if (node != NULL)
- {
- TRY_LOCK(&node->lock);
-
- /* unlock last one or two nodes in the previous chain */
- if (iterator->node != NULL)
- {
- UNLOCK(&iterator->node->lock);
-
- if (iterator->previousNode != NULL)
- {
- UNLOCK(&iterator->previousNode->lock);
- }
- }
-
- /* redirect iterator */
- iterator->previousNode = NULL;
- iterator->node = node;
-
- return IX_ETH_DB_SUCCESS;
- }
- }
-
- /* could not advance iterator */
- if (iterator->node != NULL)
- {
- UNLOCK(&iterator->node->lock);
-
- if (iterator->previousNode != NULL)
- {
- UNLOCK(&iterator->previousNode->lock);
- }
-
- iterator->node = NULL;
- }
-
- return IX_ETH_DB_END;
-}
-
-/**
- * @brief removes an entry pointed by an iterator
- *
- * @param hashTable iterated hash table
- * @param iterator iterator object
- *
- * Removes the entry currently pointed by the iterator and repositions the iterator
- * on the next valid entry (if any). Handles locking issues automatically and
- * implicitely grants write access lock to the new pointed entry.
- * Failures due to concurrent threads having write access locks in the same region
- * preserve the state of the database and the iterator object, leaving the caller
- * free to retry without loss of access. It is guaranteed that only the thread owning
- * the iterator can remove the object pointed by the iterator.
- *
- * @retval IX_ETH_DB_SUCCESS if removal has succeeded
- * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
- * should retry
- *
- * @internal
- */
-IxEthDBStatus ixEthDBRemoveEntryAtHashIterator(HashTable *hashTable, HashIterator *iterator)
-{
- HashIterator nextIteratorPos;
- LockStack locks;
-
- INIT_STACK(&locks);
-
- /* set initial bucket index for next position */
- nextIteratorPos.bucketIndex = iterator->bucketIndex;
-
- /* compute iterator position before removing anything and lock ahead */
- if (iterator->node->next != NULL)
- {
- PUSH_LOCK(&locks, &iterator->node->next->lock);
-
- /* reposition on the next node in the chain */
- nextIteratorPos.node = iterator->node->next;
- nextIteratorPos.previousNode = iterator->previousNode;
- }
- else
- {
- /* try next chain - don't know yet if we'll find anything */
- nextIteratorPos.node = NULL;
-
- /* if we find something it's a chain head */
- nextIteratorPos.previousNode = NULL;
-
- /* browse up in the buckets to find a non-null chain */
- while (++nextIteratorPos.bucketIndex < hashTable->numBuckets)
- {
- nextIteratorPos.node = hashTable->hashBuckets[nextIteratorPos.bucketIndex];
-
- if (nextIteratorPos.node != NULL)
- {
- /* found a non-empty chain, try to lock head */
- PUSH_LOCK(&locks, &nextIteratorPos.node->lock);
-
- break;
- }
- }
- }
-
- /* restore links over the to-be-deleted item */
- if (iterator->previousNode == NULL)
- {
- /* first in chain, lock bucket */
- PUSH_LOCK(&locks, &hashTable->bucketLocks[iterator->bucketIndex]);
-
- hashTable->hashBuckets[iterator->bucketIndex] = iterator->node->next;
-
- POP_LOCK(&locks);
- }
- else
- {
- /* relink */
- iterator->previousNode->next = iterator->node->next;
-
- /* unlock last remaining node in current chain when moving between chains */
- if (iterator->node->next == NULL)
- {
- UNLOCK(&iterator->previousNode->lock);
- }
- }
-
- /* delete entry */
- hashTable->freeFunction(iterator->node->data);
- ixEthDBFreeHashNode(iterator->node);
-
- /* reposition iterator */
- *iterator = nextIteratorPos;
-
- return IX_ETH_DB_SUCCESS;
-}
-
-/**
- * @}
- */