ixethdbhashtable.c

有关ARM开发板上的IXP400网络驱动程序的源码以。

    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);
    }
}

#ifdef _DIAB_TOOL
__asm volatile void _nodePtrPrefetch (volatile HashNode **nodePtr) 
{
% reg nodePtr;
	pld [nodePtr];
}
#endif /* #ifdef _DIAB_TOOL */


/**
 * @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;
#ifdef _DIAB_TOOL
            _nodePtrPrefetch(nodePtr);
#else
            __asm__ ("pld [%0];\n": : "r" (nodePtr));
#endif /* #ifdef _DIAB_TOOL */
        }
#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;
}

/**
 * @}
 */