4 * @brief Hashtable implementation
7 * IXP400 SW Release version 2.0
9 * -- Copyright Notice --
12 * Copyright 2001-2005, Intel Corporation.
13 * All rights reserved.
16 * SPDX-License-Identifier: BSD-3-Clause
18 * -- End of Copyright Notice --
22 #include "IxEthDB_p.h"
23 #include "IxEthDBLocks_p.h"
32 * @brief initializes a hash table object
34 * @param hashTable uninitialized hash table structure
35 * @param numBuckets number of buckets to use
36 * @param entryHashFunction hash function used
37 * to hash entire hash node data block (for adding)
38 * @param matchFunctions array of match functions, indexed on type,
39 * used to differentiate records with the same hash value
40 * @param freeFunction function used to free node data blocks
42 * Initializes the given hash table object.
46 void ixEthDBInitHash(HashTable *hashTable,
48 HashFunction entryHashFunction,
49 MatchFunction *matchFunctions,
50 FreeFunction freeFunction)
53 UINT32 hashSize = numBuckets * sizeof(HashNode *);
55 /* entry hashing, matching and freeing methods */
56 hashTable->entryHashFunction = entryHashFunction;
57 hashTable->matchFunctions = matchFunctions;
58 hashTable->freeFunction = freeFunction;
61 hashTable->numBuckets = numBuckets;
63 /* set to 0 all buckets */
64 memset(hashTable->hashBuckets, 0, hashSize);
66 /* init bucket locks - note that initially all mutexes are unlocked after MutexInit()*/
67 for (bucketIndex = 0 ; bucketIndex < numBuckets ; bucketIndex++)
69 ixOsalFastMutexInit(&hashTable->bucketLocks[bucketIndex]);
74 * @brief adds an entry to the hash table
76 * @param hashTable hash table to add the entry to
77 * @param entry entry to add
79 * The entry will be hashed using the entry hashing function and added to the
80 * hash table, unless a locking blockage occurs, in which case the caller
83 * @retval IX_ETH_DB_SUCCESS if adding <i>entry</i> has succeeded
84 * @retval IX_ETH_DB_NOMEM if there's no memory left in the hash node pool
85 * @retval IX_ETH_DB_BUSY if there's a locking failure on the insertion path
89 IX_ETH_DB_PUBLIC IxEthDBStatus ixEthDBAddHashEntry(HashTable *hashTable, void *entry)
91 UINT32 hashValue = hashTable->entryHashFunction(entry);
92 UINT32 bucketIndex = hashValue % hashTable->numBuckets;
93 HashNode *bucket = hashTable->hashBuckets[bucketIndex];
101 PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);
103 /* lock insertion element (first in chain), if any */
106 PUSH_LOCK(&locks, &bucket->lock);
110 newNode = ixEthDBAllocHashNode();
114 /* unlock everything */
115 UNROLL_STACK(&locks);
117 return IX_ETH_DB_NOMEM;
120 /* init lock - note that mutexes are unlocked after MutexInit */
121 ixOsalFastMutexInit(&newNode->lock);
123 /* populate new link */
124 newNode->data = entry;
127 newNode->next = bucket;
128 hashTable->hashBuckets[bucketIndex] = newNode;
130 /* unlock bucket and insertion point */
131 UNROLL_STACK(&locks);
133 return IX_ETH_DB_SUCCESS;
137 * @brief removes an entry from the hashtable
139 * @param hashTable hash table to remove entry from
140 * @param keyType type of record key used for matching
141 * @param reference reference key used to identify the entry
143 * The reference key will be hashed using the key hashing function,
144 * the entry is searched using the hashed value and then examined
145 * against the reference entry using the match function. A positive
146 * match will trigger the deletion of the entry.
147 * Locking failures are reported and the caller should retry.
149 * @retval IX_ETH_DB_SUCCESS if the removal was successful
150 * @retval IX_ETH_DB_NO_SUCH_ADDR if the entry was not found
151 * @retval IX_ETH_DB_BUSY if a locking failure occured during the process
155 IxEthDBStatus ixEthDBRemoveHashEntry(HashTable *hashTable, int keyType, void *reference)
157 UINT32 hashValue = hashTable->entryHashFunction(reference);
158 UINT32 bucketIndex = hashValue % hashTable->numBuckets;
159 HashNode *node = hashTable->hashBuckets[bucketIndex];
160 HashNode *previousNode = NULL;
168 /* try to lock node */
169 PUSH_LOCK(&locks, &node->lock);
171 if (hashTable->matchFunctions[keyType](reference, node->data))
174 if (node->next != NULL)
176 PUSH_LOCK(&locks, &node->next->lock);
179 if (previousNode == NULL)
181 /* node is head of chain */
182 PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);
184 hashTable->hashBuckets[bucketIndex] = node->next;
191 previousNode->next = node->next;
194 UNROLL_STACK(&locks);
197 hashTable->freeFunction(node->data);
198 ixEthDBFreeHashNode(node);
200 return IX_ETH_DB_SUCCESS;
204 if (previousNode != NULL)
206 /* unlock previous node */
210 /* advance to next element in chain */
216 UNROLL_STACK(&locks);
219 return IX_ETH_DB_NO_SUCH_ADDR;
223 * @brief retrieves an entry from the hash table
225 * @param hashTable hash table to perform the search into
226 * @param reference search key (a MAC address)
227 * @param keyType type of record key used for matching
228 * @param searchResult pointer where a reference to the located hash node
231 * Searches the entry with the same key as <i>reference</i> and places the
232 * pointer to the resulting node in <i>searchResult</i>.
233 * An implicit write access lock is granted after a search, which gives the
234 * caller the opportunity to modify the entry.
235 * Access should be released as soon as possible using @ref ixEthDBReleaseHashNode().
237 * @see ixEthDBReleaseHashNode()
239 * @retval IX_ETH_DB_SUCCESS if the search was completed successfully
240 * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found
241 * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case
242 * the caller should retry
244 * @warning unless the return value is <b>IX_ETH_DB_SUCCESS</b> the searchResult
245 * location is NOT modified and therefore using a NULL comparison test when the
246 * value was not properly initialized would be an error
250 IxEthDBStatus ixEthDBSearchHashEntry(HashTable *hashTable, int keyType, void *reference, HashNode **searchResult)
255 hashValue = hashTable->entryHashFunction(reference);
256 node = hashTable->hashBuckets[hashValue % hashTable->numBuckets];
260 TRY_LOCK(&node->lock);
262 if (hashTable->matchFunctions[keyType](reference, node->data))
264 *searchResult = node;
266 return IX_ETH_DB_SUCCESS;
277 return IX_ETH_DB_NO_SUCH_ADDR;
281 * @brief reports the existence of an entry in the hash table
283 * @param hashTable hash table to perform the search into
284 * @param reference search key (a MAC address)
285 * @param keyType type of record key used for matching
287 * Searches the entry with the same key as <i>reference</i>.
288 * No implicit write access lock is granted after a search, hence the
289 * caller cannot access or modify the entry. The result is only temporary.
291 * @see ixEthDBReleaseHashNode()
293 * @retval IX_ETH_DB_SUCCESS if the search was completed successfully
294 * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found
295 * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case
296 * the caller should retry
300 IxEthDBStatus ixEthDBPeekHashEntry(HashTable *hashTable, int keyType, void *reference)
305 hashValue = hashTable->entryHashFunction(reference);
306 node = hashTable->hashBuckets[hashValue % hashTable->numBuckets];
310 TRY_LOCK(&node->lock);
312 if (hashTable->matchFunctions[keyType](reference, node->data))
316 return IX_ETH_DB_SUCCESS;
327 return IX_ETH_DB_NO_SUCH_ADDR;
331 * @brief releases the write access lock
333 * @pre the node should have been obtained via @ref ixEthDBSearchHashEntry()
335 * @see ixEthDBSearchHashEntry()
339 void ixEthDBReleaseHashNode(HashNode *node)
345 * @brief initializes a hash iterator
347 * @param hashTable hash table to be iterated
348 * @param iterator iterator object
350 * If the initialization is successful the iterator will point to the
351 * first hash table record (if any).
352 * Testing if the iterator has not passed the end of the table should be
353 * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
354 * An implicit write access lock is granted on the entry pointed by the iterator.
355 * The access is automatically revoked when the iterator is incremented.
356 * If the caller decides to terminate the iteration before the end of the table is
357 * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
360 * @see ixEthDBReleaseHashIterator()
362 * @retval IX_ETH_DB_SUCCESS if initialization was successful and the iterator points
363 * to the first valid table node
364 * @retval IX_ETH_DB_FAIL if the table is empty
365 * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
368 * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
369 * might place the database in a permanent invalid lock state
373 IxEthDBStatus ixEthDBInitHashIterator(HashTable *hashTable, HashIterator *iterator)
375 iterator->bucketIndex = 0;
376 iterator->node = NULL;
377 iterator->previousNode = NULL;
379 return ixEthDBIncrementHashIterator(hashTable, iterator);
383 * @brief releases the write access locks of the iterator nodes
385 * @warning use of this function is required only when the caller terminates an iteration
386 * before reaching the end of the table
388 * @see ixEthDBInitHashIterator()
389 * @see ixEthDBIncrementHashIterator()
391 * @param iterator iterator whose node(s) should be unlocked
395 void ixEthDBReleaseHashIterator(HashIterator *iterator)
397 if (iterator->previousNode != NULL)
399 UNLOCK(&iterator->previousNode->lock);
402 if (iterator->node != NULL)
404 UNLOCK(&iterator->node->lock);
409 * @brief incremenents an iterator so that it points to the next valid entry of the table
412 * @param hashTable hash table to iterate
413 * @param iterator iterator object
415 * @pre the iterator object must be initialized using @ref ixEthDBInitHashIterator()
417 * If the increment operation is successful the iterator will point to the
418 * next hash table record (if any).
419 * Testing if the iterator has not passed the end of the table should be
420 * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
421 * An implicit write access lock is granted on the entry pointed by the iterator.
422 * The access is automatically revoked when the iterator is re-incremented.
423 * If the caller decides to terminate the iteration before the end of the table is
424 * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
426 * Is is guaranteed that no other thread can remove or change the iterated entry until
427 * the iterator is incremented successfully.
429 * @see ixEthDBReleaseHashIterator()
431 * @retval IX_ETH_DB_SUCCESS if the operation was successful and the iterator points
432 * to the next valid table node
433 * @retval IX_ETH_DB_FAIL if the iterator has passed the end of the table
434 * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
437 * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
438 * might place the database in a permanent invalid lock state
442 IxEthDBStatus ixEthDBIncrementHashIterator(HashTable *hashTable, HashIterator *iterator)
444 /* unless iterator is just initialized... */
445 if (iterator->node != NULL)
447 /* try next in chain */
448 if (iterator->node->next != NULL)
450 TRY_LOCK(&iterator->node->next->lock);
452 if (iterator->previousNode != NULL)
454 UNLOCK(&iterator->previousNode->lock);
457 iterator->previousNode = iterator->node;
458 iterator->node = iterator->node->next;
460 return IX_ETH_DB_SUCCESS;
464 /* last in chain, prepare for next bucket */
465 iterator->bucketIndex++;
469 /* try next used bucket */
470 for (; iterator->bucketIndex < hashTable->numBuckets ; iterator->bucketIndex++)
472 HashNode **nodePtr = &(hashTable->hashBuckets[iterator->bucketIndex]);
473 HashNode *node = *nodePtr;
474 #if (CPU!=SIMSPARCSOLARIS) && !defined (__wince)
475 if (((iterator->bucketIndex & IX_ETHDB_BUCKET_INDEX_MASK) == 0) &&
476 (iterator->bucketIndex < (hashTable->numBuckets - IX_ETHDB_BUCKETPTR_AHEAD)))
478 /* preload next cache line (2 cache line ahead) */
479 nodePtr += IX_ETHDB_BUCKETPTR_AHEAD;
480 __asm__ ("pld [%0];\n": : "r" (nodePtr));
485 TRY_LOCK(&node->lock);
487 /* unlock last one or two nodes in the previous chain */
488 if (iterator->node != NULL)
490 UNLOCK(&iterator->node->lock);
492 if (iterator->previousNode != NULL)
494 UNLOCK(&iterator->previousNode->lock);
498 /* redirect iterator */
499 iterator->previousNode = NULL;
500 iterator->node = node;
502 return IX_ETH_DB_SUCCESS;
506 /* could not advance iterator */
507 if (iterator->node != NULL)
509 UNLOCK(&iterator->node->lock);
511 if (iterator->previousNode != NULL)
513 UNLOCK(&iterator->previousNode->lock);
516 iterator->node = NULL;
519 return IX_ETH_DB_END;
523 * @brief removes an entry pointed by an iterator
525 * @param hashTable iterated hash table
526 * @param iterator iterator object
528 * Removes the entry currently pointed by the iterator and repositions the iterator
529 * on the next valid entry (if any). Handles locking issues automatically and
530 * implicitely grants write access lock to the new pointed entry.
531 * Failures due to concurrent threads having write access locks in the same region
532 * preserve the state of the database and the iterator object, leaving the caller
533 * free to retry without loss of access. It is guaranteed that only the thread owning
534 * the iterator can remove the object pointed by the iterator.
536 * @retval IX_ETH_DB_SUCCESS if removal has succeeded
537 * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
542 IxEthDBStatus ixEthDBRemoveEntryAtHashIterator(HashTable *hashTable, HashIterator *iterator)
544 HashIterator nextIteratorPos;
549 /* set initial bucket index for next position */
550 nextIteratorPos.bucketIndex = iterator->bucketIndex;
552 /* compute iterator position before removing anything and lock ahead */
553 if (iterator->node->next != NULL)
555 PUSH_LOCK(&locks, &iterator->node->next->lock);
557 /* reposition on the next node in the chain */
558 nextIteratorPos.node = iterator->node->next;
559 nextIteratorPos.previousNode = iterator->previousNode;
563 /* try next chain - don't know yet if we'll find anything */
564 nextIteratorPos.node = NULL;
566 /* if we find something it's a chain head */
567 nextIteratorPos.previousNode = NULL;
569 /* browse up in the buckets to find a non-null chain */
570 while (++nextIteratorPos.bucketIndex < hashTable->numBuckets)
572 nextIteratorPos.node = hashTable->hashBuckets[nextIteratorPos.bucketIndex];
574 if (nextIteratorPos.node != NULL)
576 /* found a non-empty chain, try to lock head */
577 PUSH_LOCK(&locks, &nextIteratorPos.node->lock);
584 /* restore links over the to-be-deleted item */
585 if (iterator->previousNode == NULL)
587 /* first in chain, lock bucket */
588 PUSH_LOCK(&locks, &hashTable->bucketLocks[iterator->bucketIndex]);
590 hashTable->hashBuckets[iterator->bucketIndex] = iterator->node->next;
597 iterator->previousNode->next = iterator->node->next;
599 /* unlock last remaining node in current chain when moving between chains */
600 if (iterator->node->next == NULL)
602 UNLOCK(&iterator->previousNode->lock);
607 hashTable->freeFunction(iterator->node->data);
608 ixEthDBFreeHashNode(iterator->node);
610 /* reposition iterator */
611 *iterator = nextIteratorPos;
613 return IX_ETH_DB_SUCCESS;