Changes in common/adt/hash_table.c [0db0df2:ad9178bf] in mainline

File:

• common/adt/hash_table.c (modified) (5 diffs)

common/adt/hash_table.c

@@ -247 +247 @@
         assert(h && h->bucket);
 
-        size_t hash = h->op->key_hash(key);
-        size_t idx = hash % h->bucket_cnt;
+        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
 
         list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
-                if (h->op->key_equal(key, hash, cur_link))
+                /*
+                 * Is this is the item we are looking for? We could have first
+                 * checked if the hashes match but op->key_equal() may very well be
+                 * just as fast as op->hash().
+                 */
+                if (h->op->key_equal(key, cur_link)) {
                         return cur_link;
+                }
         }
 
@@ -260 +265 @@
 /** Find the next item equal to item. */
 ht_link_t *
-hash_table_find_next(const hash_table_t *h, ht_link_t *item)
+hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
 {
         assert(item);
@@ -266 +271 @@
 
         size_t idx = h->op->hash(item) % h->bucket_cnt;
-        list_t *list = &h->bucket[idx];
-        link_t *cur = list_next(&item->link, list);
-
-        /* Traverse the list until we reach its end. */
-        for (; cur != NULL; cur = list_next(cur, list)) {
+
+        /* Traverse the circular list until we reach the starting item again. */
+        for (link_t *cur = item->link.next; cur != &first->link;
+            cur = cur->next) {
+                assert(cur);
+
+                if (cur == &h->bucket[idx].head)
+                        continue;
+
                 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
-
-                if (h->op->equal(cur_link, item))
+                /*
+                 * Is this is the item we are looking for? We could have first
+                 * checked if the hashes match but op->equal() may very well be
+                 * just as fast as op->hash().
+                 */
+                if (h->op->equal(cur_link, item)) {
                         return cur_link;
+                }
         }
 
@@ -295 +309 @@
         assert(!h->apply_ongoing);
 
-        size_t hash = h->op->key_hash(key);
-        size_t idx = hash % h->bucket_cnt;
+        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
 
         size_t removed = 0;
@@ -303 +316 @@
                 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
 
-                if (h->op->key_equal(key, hash, cur_link)) {
+                if (h->op->key_equal(key, cur_link)) {
                         ++removed;
                         list_remove(cur);