Re: [PATCH 3/3] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.

[Mark Wielaard <mark at klomp dot org>]

Hi,

On Fri, 2019-10-25 at 23:11 -0500, Jonathon Anderson wrote:
> > I tried to simplify the code a little. You already observed that
> > COMPARE can be zero. But it always is. We never try comparing values.
> > So all the COMPARE and value passing to the find functions can simply
> > be removed. So if you agree I would like to merge the attached
> > simplification diff into this patch.
> 
> I'm fine with it, although at a glance it seems that this means 
> insert_helper will never return -1. Which doesn't quite sound accurate, 
> so I'll have to defer to Srdan on this one.

Srdan, any feedback on this?

Thanks,

Mark

From b70b350242d9752f41407c0ed7fe4683c8f31ce6 Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mark@klomp.org>
Date: Sat, 26 Oct 2019 01:54:43 +0200
Subject: [PATCH] no compare or val pass

---
 lib/dynamicsizehash_concurrent.c | 51 +++++---------------------------
 lib/dynamicsizehash_concurrent.h |  2 +-
 libdw/dwarf_abbrev_hash.h        |  1 -
 libdw/dwarf_getabbrev.c          |  2 +-
 libdw/dwarf_tag.c                |  2 +-
 5 files changed, 10 insertions(+), 48 deletions(-)

diff --git a/lib/dynamicsizehash_concurrent.c b/lib/dynamicsizehash_concurrent.c
index d645b143..5fa38713 100644
--- a/lib/dynamicsizehash_concurrent.c
+++ b/lib/dynamicsizehash_concurrent.c
@@ -36,46 +36,24 @@
 
    NAME      name of the hash table structure.
    TYPE      data type of the hash table entries
-   COMPARE   comparison function taking two pointers to TYPE objects
-
-   The following macros if present select features:
-
-   ITERATE   iterating over the table entries is possible
-   REVERSE   iterate in reverse order of insert
  */
 
 
 static size_t
-lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
+lookup (NAME *htab, HASHTYPE hval)
 {
   /* First hash function: simply take the modul but prevent zero.  Small values
       can skip the division, which helps performance when this is common.  */
   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
 
-#if COMPARE != 0  /* A handful of tables don't actually compare the entries in
-                    the table, they instead rely on the hash.  In that case, we
-                    can skip parts that relate to the value. */
-  TYPE val_ptr;
-#endif
   HASHTYPE hash;
 
   hash = atomic_load_explicit(&htab->table[idx].hashval,
                               memory_order_acquire);
   if (hash == hval)
-    {
-#if COMPARE == 0
-      return idx;
-#else
-      val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
-                                            memory_order_acquire);
-      if (COMPARE(val_ptr, val) == 0)
-          return idx;
-#endif
-    }
+    return idx;
   else if (hash == 0)
-    {
-      return 0;
-    }
+    return 0;
 
   /* Second hash function as suggested in [Knuth].  */
   HASHTYPE second_hash = 1 + hval % (htab->size - 2);
@@ -90,20 +68,9 @@ lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
       hash = atomic_load_explicit(&htab->table[idx].hashval,
                                   memory_order_acquire);
       if (hash == hval)
-        {
-#if COMPARE == 0
-          return idx;
-#else
-          val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
-                                                memory_order_acquire);
-          if (COMPARE(val_ptr, val) == 0)
-              return idx;
-#endif
-        }
+	return idx;
       else if (hash == 0)
-        {
-          return 0;
-        }
+	return 0;
     }
 }
 
@@ -123,8 +90,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
     {
       val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
                                             memory_order_acquire);
-      if (COMPARE(val_ptr, val) != 0)
-          return -1;
     }
   else if (hash == 0)
     {
@@ -168,8 +133,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
         {
           val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
                                                 memory_order_acquire);
-          if (COMPARE(val_ptr, val) != 0)
-              return -1;
         }
       else if (hash == 0)
         {
@@ -495,7 +458,7 @@ TYPE
 #define FIND(name) _FIND (name)
 #define _FIND(name) \
   name##_find
-FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
+FIND(NAME) (NAME *htab, HASHTYPE hval)
 {
   while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
       resize_worker(htab);
@@ -504,7 +467,7 @@ FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
 
   /* Make the hash data nonzero.  */
   hval = hval ?: 1;
-  idx = lookup(htab, hval, val);
+  idx = lookup(htab, hval);
 
   if (idx == 0)
     {
diff --git a/lib/dynamicsizehash_concurrent.h b/lib/dynamicsizehash_concurrent.h
index a137cbd0..73e66e91 100644
--- a/lib/dynamicsizehash_concurrent.h
+++ b/lib/dynamicsizehash_concurrent.h
@@ -97,7 +97,7 @@ extern int name##_free (name *htab);                                \
 extern int name##_insert (name *htab, HASHTYPE hval, TYPE data);    \
                                                                     \
 /* Find entry in hash table.  */                                    \
-extern TYPE name##_find (name *htab, HASHTYPE hval, TYPE val);
+extern TYPE name##_find (name *htab, HASHTYPE hval);
 #define FUNCTIONS(name) _FUNCTIONS (name)
 FUNCTIONS (NAME)
 
diff --git a/libdw/dwarf_abbrev_hash.h b/libdw/dwarf_abbrev_hash.h
index bc3d62c7..a368c598 100644
--- a/libdw/dwarf_abbrev_hash.h
+++ b/libdw/dwarf_abbrev_hash.h
@@ -32,7 +32,6 @@
 
 #define NAME Dwarf_Abbrev_Hash
 #define TYPE Dwarf_Abbrev *
-#define COMPARE(a, b) (0)
 
 #include <dynamicsizehash_concurrent.h>
 
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 6a7e981b..7e767fc1 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -83,7 +83,7 @@ __libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, Dwarf_Off offset,
   bool foundit = false;
   Dwarf_Abbrev *abb = NULL;
   if (cu == NULL
-      || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL)) == NULL)
+      || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code)) == NULL)
     {
       if (result == NULL)
 	abb = libdw_typed_alloc (dbg, Dwarf_Abbrev);
diff --git a/libdw/dwarf_tag.c b/libdw/dwarf_tag.c
index 331eaa0d..d784970c 100644
--- a/libdw/dwarf_tag.c
+++ b/libdw/dwarf_tag.c
@@ -45,7 +45,7 @@ __libdw_findabbrev (struct Dwarf_CU *cu, unsigned int code)
     return DWARF_END_ABBREV;
 
   /* See whether the entry is already in the hash table.  */
-  abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+  abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code);
   if (abb == NULL)
     while (cu->last_abbrev_offset != (size_t) -1l)
       {
-- 
2.18.1