Changeset 30f1a25 in mainline for uspace/lib/c/generic/adt/hash_table.c

Timestamp:

2018-03-14T18:54:08Z (7 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

67f11a0

Parents:

963037b0

Message:

Make hash_table_find_next immune to livelocks

By giving hash_table_find_next the item returned from hash_table_find,
we provide it with a fixed reference with which the outer loop which
calls hash_table_find_next can terminate even if the respective bucket
contains more matching elements.

File:

• uspace/lib/c/generic/adt/hash_table.c (modified) (2 diffs)

uspace/lib/c/generic/adt/hash_table.c

@@ -269 +269 @@
 
 /** Find the next item equal to item. */
-ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
+ht_link_t *
+hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
 {
         assert(item);
@@ -277 +278 @@
 
         /* Traverse the circular list until we reach the starting item again. */
-        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
+        for (link_t *cur = item->link.next; cur != &first->link;
+            cur = cur->next) {
                 assert(cur);