Changeset 30f1a25 in mainline for uspace

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.

Location:

uspace/lib/c

Files:

• generic/adt/hash_table.c (modified) (2 diffs)
• include/adt/hash_table.h (modified) (1 diff)

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

uspace/lib/c/include/adt/hash_table.h

@@ -95 +95 @@
 extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
 extern ht_link_t *hash_table_find(const hash_table_t *, void *);
-extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *,
+    ht_link_t *);
 extern size_t hash_table_remove(hash_table_t *, void *);
 extern void hash_table_remove_item(hash_table_t *, ht_link_t *);