libctf, hash: introduce the ctf_dynset

There are many places in the deduplicator which use hashtables as tiny
sets: keys with no value (and usually, but not always, no freeing
function) often with only one or a few members.  For each of these, even
after the last change to not store the freeing functions, we are storing
a little malloced block for each item just to track the key/value pair,
and a little malloced block for the hash table itself just to track the
freeing function because we can't use libiberty hashtab's freeing
function because we are using that to free the little malloced per-item
block.

If we only have a key, we don't need any of that: we can ditch the
per-malloced block because we don't have a value, and we can ditch the
per-hashtab structure because we don't need to independently track the
freeing functions since libiberty hashtab is doing it for us.  That
means we don't need an owner field in the (now nonexistent) item block
either.

Roughly speaking, this datatype saves about 25% in time and 20% in peak
memory usage for normal links, even fairly big ones.  So this might seem
redundant, but it's really worth it.

Instead of a _lookup function, a dynset has two distinct functions:
ctf_dynset_exists, which returns true or false and an optional pointer
to the set member, and ctf_dynhash_lookup_any, which is used if all
members of the set are expected to be equivalent and we just want *any*
member and we don't care which one.

There is no iterator in this set of functions, not because we don't
iterate over dynset members -- we do, a lot -- but because the iterator
here is a member of an entirely new family of much more convenient
iteration functions, introduced in the next commit.

libctf/
	* ctf-hash.c (ctf_dynset_eq_string): New.
	(ctf_dynset_create): New.
	(DYNSET_EMPTY_ENTRY_REPLACEMENT): New.
	(DYNSET_DELETED_ENTRY_REPLACEMENT): New.
	(key_to_internal): New.
	(internal_to_key): New.
	(ctf_dynset_insert): New.
	(ctf_dynset_remove): New.
	(ctf_dynset_destroy): New.
	(ctf_dynset_lookup): New.
	(ctf_dynset_exists): New.
	(ctf_dynset_lookup_any): New.
	(ctf_hash_insert_type): Coding style.
	(ctf_hash_define_type): Likewise.

	* ctf-impl.h (ctf_dynset_t): New.
	(ctf_dynset_eq_string): New.
	(ctf_dynset_create): New.
	(ctf_dynset_insert): New.
	(ctf_dynset_remove): New.
	(ctf_dynset_destroy): New.
	(ctf_dynset_lookup): New.
	(ctf_dynset_exists): New.
	(ctf_dynset_lookup_any): New.
	* ctf-inlines.h (ctf_dynset_cinsert): New.

4 files changed, 203 insertions, 11 deletions

diff --git a/libctf/ChangeLog b/libctf/ChangeLog
index 27987f2..329e69c 100644
--- a/libctf/ChangeLog
+++ b/libctf/ChangeLog
@@ -1,5 +1,32 @@
 2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
 
+	* ctf-hash.c (ctf_dynset_eq_string): New.
+	(ctf_dynset_create): New.
+	(DYNSET_EMPTY_ENTRY_REPLACEMENT): New.
+	(DYNSET_DELETED_ENTRY_REPLACEMENT): New.
+	(key_to_internal): New.
+	(internal_to_key): New.
+	(ctf_dynset_insert): New.
+	(ctf_dynset_remove): New.
+	(ctf_dynset_destroy): New.
+	(ctf_dynset_lookup): New.
+	(ctf_dynset_exists): New.
+	(ctf_dynset_lookup_any): New.
+	(ctf_hash_insert_type): Coding style.
+	(ctf_hash_define_type): Likewise.
+	* ctf-impl.h (ctf_dynset_t): New.
+	(ctf_dynset_eq_string): New.
+	(ctf_dynset_create): New.
+	(ctf_dynset_insert): New.
+	(ctf_dynset_remove): New.
+	(ctf_dynset_destroy): New.
+	(ctf_dynset_lookup): New.
+	(ctf_dynset_exists): New.
+	(ctf_dynset_lookup_any): New.
+	* ctf-inlines.h (ctf_dynset_cinsert): New.
+
+2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-hash.c (ctf_helem_t) <key_free>: Remove.
 	<value_free>: Likewise.
 	<owner>: New.
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index caefd99..7eba494 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -22,14 +22,21 @@
 #include "libiberty.h"
 #include "hashtab.h"
 
-/* We have two hashtable implementations: one, ctf_dynhash_*(), is an interface to
-   a dynamically-expanding hash with unknown size that should support addition
-   of large numbers of items, and removal as well, and is used only at
-   type-insertion time; the other, ctf_dynhash_*(), is an interface to a
-   fixed-size hash from const char * -> ctf_id_t with number of elements
-   specified at creation time, that should support addition of items but need
-   not support removal.  These can be implemented by the same underlying hashmap
-   if you wish.  */
+/* We have three hashtable implementations:
+
+   - ctf_hash_* is an interface to a fixed-size hash from const char * ->
+     ctf_id_t with number of elements specified at creation time, that should
+     support addition of items but need not support removal.
+
+   - ctf_dynhash_* is an interface to a dynamically-expanding hash with
+     unknown size that should support addition of large numbers of items, and
+     removal as well, and is used only at type-insertion time and during
+     linking.
+
+   - ctf_dynset_* is an interface to a dynamically-expanding hash that contains
+     only keys: no values.
+
+   These can be implemented by the same underlying hashmap if you wish.  */
 
 /* The helem is used for general key/value mappings in both the ctf_hash and
    ctf_dynhash: the owner may not have space allocated for it, and will be
@@ -51,7 +58,7 @@ struct ctf_dynhash
   ctf_hash_free_fun value_free;
 };
 
-/* Hash functions. */
+/* Hash and eq functions for the dynhash and hash. */
 
 unsigned int
 ctf_hash_integer (const void *ptr)
@@ -109,6 +116,16 @@ ctf_hash_eq_type_mapping_key (const void *a, const void *b)
     && (key_a->cltm_idx == key_b->cltm_idx);
 }
 
+
+/* Hash and eq functions for the dynset.  Most of these can just use the
+   underlying hashtab functions directly.   */
+
+int
+ctf_dynset_eq_string (const void *a, const void *b)
+{
+  return !strcmp((const char *) a, (const char *) b);
+}
+
 /* The dynhash, used for hashes whose size is not known at creation time. */
 
 /* Free a single ctf_helem with arbitrary key/value functions.  */
@@ -369,6 +386,135 @@ ctf_dynhash_destroy (ctf_dynhash_t *hp)
   free (hp);
 }
 
+/* The dynset, used for sets of keys with no value.  The implementation of this
+   can be much simpler, because without a value the slot can simply be the
+   stored key, which means we don't need to store the freeing functions and the
+   dynset itself is just a htab.  */
+
+ctf_dynset_t *
+ctf_dynset_create (htab_hash hash_fun, htab_eq eq_fun,
+		   ctf_hash_free_fun key_free)
+{
+  /* 7 is arbitrary and untested for now.  */
+  return (ctf_dynset_t *) htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
+					     key_free, xcalloc, free);
+}
+
+/* The dynset has one complexity: the underlying implementation reserves two
+   values for internal hash table implementation details (empty versus deleted
+   entries).  These values are otherwise very useful for pointers cast to ints,
+   so transform the ctf_dynset_inserted value to allow for it.  (This
+   introduces an ambiguity in that one can no longer store these two values in
+   the dynset, but if we pick high enough values this is very unlikely to be a
+   problem.)
+
+   We leak this implementation detail to the freeing functions on the grounds
+   that any use of these functions is overwhelmingly likely to be in sets using
+   real pointers, which will be unaffected.  */
+
+#define DYNSET_EMPTY_ENTRY_REPLACEMENT ((void *) (uintptr_t) -64)
+#define DYNSET_DELETED_ENTRY_REPLACEMENT ((void *) (uintptr_t) -63)
+
+static void *
+key_to_internal (const void *key)
+{
+  if (key == HTAB_EMPTY_ENTRY)
+    return DYNSET_EMPTY_ENTRY_REPLACEMENT;
+  else if (key == HTAB_DELETED_ENTRY)
+    return DYNSET_DELETED_ENTRY_REPLACEMENT;
+
+  return (void *) key;
+}
+
+static void *
+internal_to_key (const void *internal)
+{
+  if (internal == DYNSET_EMPTY_ENTRY_REPLACEMENT)
+    return HTAB_EMPTY_ENTRY;
+  else if (internal == DYNSET_DELETED_ENTRY_REPLACEMENT)
+    return HTAB_DELETED_ENTRY;
+  return (void *) internal;
+}
+
+int
+ctf_dynset_insert (ctf_dynset_t *hp, void *key)
+{
+  struct htab *htab = (struct htab *) hp;
+  void **slot;
+
+  slot = htab_find_slot (htab, key, INSERT);
+
+  if (!slot)
+    {
+      errno = ENOMEM;
+      return -errno;
+    }
+
+  if (*slot)
+    {
+      if (htab->del_f)
+	(*htab->del_f) (*slot);
+    }
+
+  *slot = key_to_internal (key);
+
+  return 0;
+}
+
+void
+ctf_dynset_remove (ctf_dynset_t *hp, const void *key)
+{
+  htab_remove_elt ((struct htab *) hp, key_to_internal (key));
+}
+
+void
+ctf_dynset_destroy (ctf_dynset_t *hp)
+{
+  if (hp != NULL)
+    htab_delete ((struct htab *) hp);
+}
+
+void *
+ctf_dynset_lookup (ctf_dynset_t *hp, const void *key)
+{
+  void **slot = htab_find_slot ((struct htab *) hp,
+				key_to_internal (key), NO_INSERT);
+
+  if (slot)
+    return internal_to_key (*slot);
+  return NULL;
+}
+
+/* TRUE/FALSE return.  */
+int
+ctf_dynset_exists (ctf_dynset_t *hp, const void *key, const void **orig_key)
+{
+  void **slot = htab_find_slot ((struct htab *) hp,
+				key_to_internal (key), NO_INSERT);
+
+  if (orig_key && slot)
+    *orig_key = internal_to_key (*slot);
+  return (slot != NULL);
+}
+
+/* Look up a completely random value from the set, if any exist.
+   Keys with value zero cannot be distinguished from a nonexistent key.  */
+void *
+ctf_dynset_lookup_any (ctf_dynset_t *hp)
+{
+  struct htab *htab = (struct htab *) hp;
+  void **slot = htab->entries;
+  void **limit = slot + htab_size (htab);
+
+  while (slot < limit
+	 && (*slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY))
+      slot++;
+
+  if (slot < limit)
+    return internal_to_key (*slot);
+  return NULL;
+}
+
 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
    removal.  This is a straight cast of a hashtab.  */
 
@@ -415,12 +561,12 @@ ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 
 /* if the key is already in the hash, override the previous definition with
    this new official definition. If the key is not present, then call
-   ctf_hash_insert_type() and hash it in.  */
+   ctf_hash_insert_type and hash it in.  */
 int
 ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
                       uint32_t name)
 {
-  /* This matches the semantics of ctf_hash_insert_type() in this
+  /* This matches the semantics of ctf_hash_insert_type in this
      implementation anyway.  */
 
   return ctf_hash_insert_type (hp, fp, type, name);
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index 3e09779..7d583ab 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -34,6 +34,7 @@
 #include <ctype.h>
 #include <elf.h>
 #include <bfd.h>
+#include "hashtab.h"
 
 #ifdef	__cplusplus
 extern "C"
@@ -73,6 +74,7 @@ extern "C"
 
 typedef struct ctf_fixed_hash ctf_hash_t; /* Private to ctf-hash.c.  */
 typedef struct ctf_dynhash ctf_dynhash_t; /* Private to ctf-hash.c.  */
+typedef struct ctf_dynset ctf_dynset_t;   /* Private to ctf-hash.c.  */
 
 typedef struct ctf_strs
 {
@@ -378,6 +380,8 @@ extern int ctf_hash_eq_integer (const void *, const void *);
 extern int ctf_hash_eq_string (const void *, const void *);
 extern int ctf_hash_eq_type_mapping_key (const void *, const void *);
 
+extern int ctf_dynset_eq_string (const void *, const void *);
+
 typedef void (*ctf_hash_free_fun) (void *);
 
 typedef void (*ctf_hash_iter_f) (void *key, void *value, void *arg);
@@ -407,6 +411,15 @@ extern void ctf_dynhash_iter_remove (ctf_dynhash_t *, ctf_hash_iter_remove_f,
 extern void *ctf_dynhash_iter_find (ctf_dynhash_t *, ctf_hash_iter_find_f,
 				    void *);
 
+extern ctf_dynset_t *ctf_dynset_create (htab_hash, htab_eq, ctf_hash_free_fun);
+extern int ctf_dynset_insert (ctf_dynset_t *, void *);
+extern void ctf_dynset_remove (ctf_dynset_t *, const void *);
+extern void ctf_dynset_destroy (ctf_dynset_t *);
+extern void *ctf_dynset_lookup (ctf_dynset_t *, const void *);
+extern int ctf_dynset_exists (ctf_dynset_t *, const void *key,
+			      const void **orig_key);
+extern void *ctf_dynset_lookup_any (ctf_dynset_t *);
+
 #define	ctf_list_prev(elem)	((void *)(((ctf_list_t *)(elem))->l_prev))
 #define	ctf_list_next(elem)	((void *)(((ctf_list_t *)(elem))->l_next))
 
diff --git a/libctf/ctf-inlines.h b/libctf/ctf-inlines.h
index ad74b39..f9c1b2a 100644
--- a/libctf/ctf-inlines.h
+++ b/libctf/ctf-inlines.h
@@ -38,6 +38,12 @@ ctf_dynhash_cinsert (ctf_dynhash_t *h, const void *k, const void *v)
   return ctf_dynhash_insert (h, (void *) k, (void *) v);
 }
 
+static inline int
+ctf_dynset_cinsert (ctf_dynset_t *h, const void *k)
+{
+  return ctf_dynset_insert (h, (void *) k);
+}
+
 #ifdef	__cplusplus
 }
 #endif