[ovs-dev] [PATCH 3/3] Unroll operations inside shash_find_and_delete

anton.ivanov at cambridgegreys.com anton.ivanov at cambridgegreys.com
Fri Jul 31 09:23:23 UTC 2020


From: Anton Ivanov <anton.ivanov at cambridgegreys.com>

shash_find_and_delete at present looks up an item using
shash_find then uses hmap_delete to delete it.

As a result it computes the hash twice and does two walks of
the linked list in the bucket.

This change unrolls the first walk to preserve extra information
making the second computation and walk unnecessary.

Signed-off-by: Anton Ivanov <anton.ivanov at cambridgegreys.com>
---
 lib/shash.c | 36 ++++++++++++++++++++++++++++++------
 1 file changed, 30 insertions(+), 6 deletions(-)

diff --git a/lib/shash.c b/lib/shash.c
index f378d1656..d2793c2e7 100644
--- a/lib/shash.c
+++ b/lib/shash.c
@@ -276,14 +276,38 @@ shash_find_data(const struct shash *sh, const char *name)
 void *
 shash_find_and_delete(struct shash *sh, const char *name)
 {
-    struct shash_node *node = shash_find(sh, name);
-    if (node) {
-        void *data = node->data;
-        shash_delete(sh, node);
-        return data;
-    } else {
+    struct shash_node *node;
+
+    /* unroll shash_find and hmap_find */
+
+    struct hmap_node
+        **bucket = &sh->map.buckets[hash_name(name) & sh->map.mask];
+    ssize_t name_len = strlen(name);
+
+    while (*bucket != NULL) {
+        node = CONTAINER_OF(*bucket, struct shash_node, node);
+        if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
+            break;
+        }
+        bucket = &(*bucket)->next;
+    }
+
+    if (*bucket == NULL) {
         return NULL;
     }
+
+    void *data = node->data;
+
+    /* use the underlying hmap node to do a direct hmap remove */
+
+    *bucket = node->node.next;
+    sh->map.n--;
+
+    /* unroll smap_steal and smap_delete */
+
+    free(node->name);
+    free(node);
+    return data;
 }
 
 void *
-- 
2.20.1



More information about the dev mailing list