libctf, next, hash: add dynhash and dynset _next iteration

This lets you iterate over dynhashes and dynsets using the _next API.
dynhashes can be iterated over in sorted order, which works by
populating an array of key/value pairs using ctf_dynhash_next itself,
then sorting it with qsort.

Convenience inline functions named ctf_dyn{hash,set}_cnext are also
provided that take (-> return) const keys and values.

libctf/
	* ctf-impl.h (ctf_next_hkv_t): New, kv-pairs passed to
	sorting functions.
	(ctf_next_t) <u.ctn_sorted_hkv>: New, sorted kv-pairs for
	ctf_dynhash_next_sorted.
	<cu.ctn_h>: New, pointer to the dynhash under iteration.
	<cu.ctn_s>: New, pointer to the dynset under iteration.
	(ctf_hash_sort_f): Sorting function passed to...
	(ctf_dynhash_next_sorted): ... this new function.
	(ctf_dynhash_next): New.
	(ctf_dynset_next): New.
	* ctf-inlines.h (ctf_dynhash_cnext_sorted): New.
	(ctf_dynhash_cnext): New.
	(ctf_dynset_cnext): New.
	* ctf-hash.c (ctf_dynhash_next_sorted): New.
	(ctf_dynhash_next): New.
	(ctf_dynset_next): New.
	* ctf-util.c (ctf_next_destroy): Free the u.ctn_sorted_hkv if
	needed.
	(ctf_next_copy): Alloc-and-copy the u.ctn_sorted_hkv if needed.

5 files changed, 305 insertions, 1 deletions

diff --git a/libctf/ChangeLog b/libctf/ChangeLog
index 3009f4e..779f7b1 100644
--- a/libctf/ChangeLog
+++ b/libctf/ChangeLog
@@ -1,5 +1,27 @@
 2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
 
+	* ctf-impl.h (ctf_next_hkv_t): New, kv-pairs passed to
+	sorting functions.
+	(ctf_next_t) <u.ctn_sorted_hkv>: New, sorted kv-pairs for
+	ctf_dynhash_next_sorted.
+	<cu.ctn_h>: New, pointer to the dynhash under iteration.
+	<cu.ctn_s>: New, pointer to the dynset under iteration.
+	(ctf_hash_sort_f): Sorting function passed to...
+	(ctf_dynhash_next_sorted): ... this new function.
+	(ctf_dynhash_next): New.
+	(ctf_dynset_next): New.
+	* ctf-inlines.h (ctf_dynhash_cnext_sorted): New.
+	(ctf_dynhash_cnext): New.
+	(ctf_dynset_cnext): New.
+	* ctf-hash.c (ctf_dynhash_next_sorted): New.
+	(ctf_dynhash_next): New.
+	(ctf_dynset_next): New.
+	* ctf-util.c (ctf_next_destroy): Free the u.ctn_sorted_hkv if
+	needed.
+	(ctf_next_copy): Alloc-and-copy the u.ctn_sorted_hkv if needed.
+
+2020-07-22  Nick Alcock  <nick.alcock@oracle.com>
+
 	* ctf-impl.h (ctf_next): New.
 	(ctf_get_dict): New prototype.
 	* ctf-lookup.c (ctf_get_dict): New, split out of...
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index 7eba494..a026ef2 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -378,6 +378,163 @@ ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun,
   htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg);
 }
 
+/* Traverse a dynhash in arbitrary order, in _next iterator form.
+
+   Mutating the dynhash while iterating is not supported (just as it isn't for
+   htab_traverse).
+
+   Note: unusually, this returns zero on success and a *positive* value on
+   error, because it does not take an fp, taking an error pointer would be
+   incredibly clunky, and nearly all error-handling ends up stuffing the result
+   of this into some sort of errno or ctf_errno, which is invariably
+   positive.  So doing this simplifies essentially all callers.  */
+int
+ctf_dynhash_next (ctf_dynhash_t *h, ctf_next_t **it, void **key, void **value)
+{
+  ctf_next_t *i = *it;
+  ctf_helem_t *slot;
+
+  if (!i)
+    {
+      size_t size = htab_size (h->htab);
+
+      /* If the table has too many entries to fit in an ssize_t, just give up.
+	 This might be spurious, but if any type-related hashtable has ever been
+	 nearly as large as that then something very odd is going on.  */
+      if (((ssize_t) size) < 0)
+	return EDOM;
+
+      if ((i = ctf_next_create ()) == NULL)
+	return ENOMEM;
+
+      i->u.ctn_hash_slot = h->htab->entries;
+      i->cu.ctn_h = h;
+      i->ctn_n = 0;
+      i->ctn_size = (ssize_t) size;
+      i->ctn_iter_fun = (void (*) (void)) ctf_dynhash_next;
+      *it = i;
+    }
+
+  if ((void (*) (void)) ctf_dynhash_next != i->ctn_iter_fun)
+    return ECTF_NEXT_WRONGFUN;
+
+  if (h != i->cu.ctn_h)
+    return ECTF_NEXT_WRONGFP;
+
+  if ((ssize_t) i->ctn_n == i->ctn_size)
+    goto hash_end;
+
+  while ((ssize_t) i->ctn_n < i->ctn_size
+	 && (*i->u.ctn_hash_slot == HTAB_EMPTY_ENTRY
+	     || *i->u.ctn_hash_slot == HTAB_DELETED_ENTRY))
+    {
+      i->u.ctn_hash_slot++;
+      i->ctn_n++;
+    }
+
+  if ((ssize_t) i->ctn_n == i->ctn_size)
+    goto hash_end;
+
+  slot = *i->u.ctn_hash_slot;
+
+  if (key)
+    *key = slot->key;
+  if (value)
+    *value = slot->value;
+
+  i->u.ctn_hash_slot++;
+  i->ctn_n++;
+
+  return 0;
+
+ hash_end:
+  ctf_next_destroy (i);
+  *it = NULL;
+  return ECTF_NEXT_END;
+}
+
+/* Traverse a sorted dynhash, in _next iterator form.
+
+   See ctf_dynhash_next for notes on error returns, etc.
+
+   Sort keys before iterating over them using the SORT_FUN and SORT_ARG.
+
+   If SORT_FUN is null, thunks to ctf_dynhash_next.  */
+int
+ctf_dynhash_next_sorted (ctf_dynhash_t *h, ctf_next_t **it, void **key,
+			 void **value, ctf_hash_sort_f sort_fun, void *sort_arg)
+{
+  ctf_next_t *i = *it;
+
+  if (sort_fun == NULL)
+    return ctf_dynhash_next (h, it, key, value);
+
+  if (!i)
+    {
+      size_t els = ctf_dynhash_elements (h);
+      ctf_next_t *accum_i = NULL;
+      void *key, *value;
+      int err;
+      ctf_next_hkv_t *walk;
+
+      if (((ssize_t) els) < 0)
+	return EDOM;
+
+      if ((i = ctf_next_create ()) == NULL)
+	return ENOMEM;
+
+      if ((i->u.ctn_sorted_hkv = calloc (els, sizeof (ctf_next_hkv_t))) == NULL)
+	{
+	  ctf_next_destroy (i);
+	  return ENOMEM;
+	}
+      walk = i->u.ctn_sorted_hkv;
+
+      i->cu.ctn_h = h;
+
+      while ((err = ctf_dynhash_next (h, &accum_i, &key, &value)) == 0)
+	{
+	  walk->hkv_key = key;
+	  walk->hkv_value = value;
+	  walk++;
+	}
+      if (err != ECTF_NEXT_END)
+	{
+	  ctf_next_destroy (i);
+	  return err;
+	}
+
+      if (sort_fun)
+	  ctf_qsort_r (i->u.ctn_sorted_hkv, els, sizeof (ctf_next_hkv_t),
+		       (int (*) (const void *, const void *, void *)) sort_fun,
+		       sort_arg);
+      i->ctn_n = 0;
+      i->ctn_size = (ssize_t) els;
+      i->ctn_iter_fun = (void (*) (void)) ctf_dynhash_next_sorted;
+      *it = i;
+    }
+
+  if ((void (*) (void)) ctf_dynhash_next_sorted != i->ctn_iter_fun)
+    return ECTF_NEXT_WRONGFUN;
+
+  if (h != i->cu.ctn_h)
+    return ECTF_NEXT_WRONGFP;
+
+  if ((ssize_t) i->ctn_n == i->ctn_size)
+    {
+      ctf_next_destroy (i);
+      *it = NULL;
+      return ECTF_NEXT_END;
+    }
+
+  if (key)
+    *key = i->u.ctn_sorted_hkv[i->ctn_n].hkv_key;
+  if (value)
+    *value = i->u.ctn_sorted_hkv[i->ctn_n].hkv_value;
+  i->ctn_n++;
+  return 0;
+}
+
 void
 ctf_dynhash_destroy (ctf_dynhash_t *hp)
 {
@@ -515,6 +672,74 @@ ctf_dynset_lookup_any (ctf_dynset_t *hp)
   return NULL;
 }
 
+/* Traverse a dynset in arbitrary order, in _next iterator form.
+
+   Otherwise, just like ctf_dynhash_next.  */
+int
+ctf_dynset_next (ctf_dynset_t *hp, ctf_next_t **it, void **key)
+{
+  struct htab *htab = (struct htab *) hp;
+  ctf_next_t *i = *it;
+  void *slot;
+
+  if (!i)
+    {
+      size_t size = htab_size (htab);
+
+      /* If the table has too many entries to fit in an ssize_t, just give up.
+	 This might be spurious, but if any type-related hashtable has ever been
+	 nearly as large as that then somthing very odd is going on.  */
+
+      if (((ssize_t) size) < 0)
+	return EDOM;
+
+      if ((i = ctf_next_create ()) == NULL)
+	return ENOMEM;
+
+      i->u.ctn_hash_slot = htab->entries;
+      i->cu.ctn_s = hp;
+      i->ctn_n = 0;
+      i->ctn_size = (ssize_t) size;
+      i->ctn_iter_fun = (void (*) (void)) ctf_dynset_next;
+      *it = i;
+    }
+
+  if ((void (*) (void)) ctf_dynset_next != i->ctn_iter_fun)
+    return ECTF_NEXT_WRONGFUN;
+
+  if (hp != i->cu.ctn_s)
+    return ECTF_NEXT_WRONGFP;
+
+  if ((ssize_t) i->ctn_n == i->ctn_size)
+    goto set_end;
+
+  while ((ssize_t) i->ctn_n < i->ctn_size
+	 && (*i->u.ctn_hash_slot == HTAB_EMPTY_ENTRY
+	     || *i->u.ctn_hash_slot == HTAB_DELETED_ENTRY))
+    {
+      i->u.ctn_hash_slot++;
+      i->ctn_n++;
+    }
+
+  if ((ssize_t) i->ctn_n == i->ctn_size)
+    goto set_end;
+
+  slot = *i->u.ctn_hash_slot;
+
+  if (key)
+    *key = internal_to_key (slot);
+
+  i->u.ctn_hash_slot++;
+  i->ctn_n++;
+
+  return 0;
+
+ set_end:
+  ctf_next_destroy (i);
+  *it = NULL;
+  return ECTF_NEXT_END;
+}
+
 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
    removal.  This is a straight cast of a hashtab.  */
 
diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h
index b18ba94..eea5204 100644
--- a/libctf/ctf-impl.h
+++ b/libctf/ctf-impl.h
@@ -328,6 +328,13 @@ struct ctf_archive_internal
 
 /* Iterator state for the *_next() functions.  */
 
+/* A single hash key/value pair.  */
+typedef struct ctf_next_hkv
+{
+  void *hkv_key;
+  void *hkv_value;
+} ctf_next_hkv_t;
+
 struct ctf_next
 {
   void (*ctn_iter_fun) (void);
@@ -346,13 +353,17 @@ struct ctf_next
     const ctf_dmdef_t *ctn_dmd;
     const ctf_enum_t *ctn_en;
     const ctf_dvdef_t *ctn_dvd;
+    ctf_next_hkv_t *ctn_sorted_hkv;
+    void **ctn_hash_slot;
   } u;
   /* This union is of various sorts of container we can iterate over:
-     currently dictionaries and archives.  */
+     currently dictionaries and archives, dynhashes, and dynsets.  */
   union
   {
     const ctf_file_t *ctn_fp;
     const ctf_archive_t *ctn_arc;
+    const ctf_dynhash_t *ctn_h;
+    const ctf_dynset_t *ctn_s;
   } cu;
 };
 
@@ -411,6 +422,8 @@ typedef void (*ctf_hash_free_fun) (void *);
 typedef void (*ctf_hash_iter_f) (void *key, void *value, void *arg);
 typedef int (*ctf_hash_iter_remove_f) (void *key, void *value, void *arg);
 typedef int (*ctf_hash_iter_find_f) (void *key, void *value, void *arg);
+typedef int (*ctf_hash_sort_f) (const ctf_next_hkv_t *, const ctf_next_hkv_t *,
+				void *arg);
 
 extern ctf_hash_t *ctf_hash_create (unsigned long, ctf_hash_fun, ctf_hash_eq_fun);
 extern int ctf_hash_insert_type (ctf_hash_t *, ctf_file_t *, uint32_t, uint32_t);
@@ -434,6 +447,11 @@ extern void ctf_dynhash_iter_remove (ctf_dynhash_t *, ctf_hash_iter_remove_f,
 				     void *);
 extern void *ctf_dynhash_iter_find (ctf_dynhash_t *, ctf_hash_iter_find_f,
 				    void *);
+extern int ctf_dynhash_next (ctf_dynhash_t *, ctf_next_t **,
+			     void **key, void **value);
+extern int ctf_dynhash_next_sorted (ctf_dynhash_t *, ctf_next_t **,
+				    void **key, void **value, ctf_hash_sort_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 *);
@@ -442,6 +460,7 @@ 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 int ctf_dynset_next (ctf_dynset_t *, ctf_next_t **, void **key);
 extern void *ctf_dynset_lookup_any (ctf_dynset_t *);
 
 #define	ctf_list_prev(elem)	((void *)(((ctf_list_t *)(elem))->l_prev))
diff --git a/libctf/ctf-inlines.h b/libctf/ctf-inlines.h
index 3b912bd..a35b6cd 100644
--- a/libctf/ctf-inlines.h
+++ b/libctf/ctf-inlines.h
@@ -46,6 +46,21 @@ ctf_forwardable_kind (int kind)
   return (kind == CTF_K_STRUCT || kind == CTF_K_UNION || kind == CTF_K_ENUM);
 }
 
+static inline int
+ctf_dynhash_cnext_sorted (ctf_dynhash_t *h, ctf_next_t **i, const void **key,
+			  const void **value, ctf_hash_sort_f sort_fun,
+			  void *sort_arg)
+{
+  return ctf_dynhash_next_sorted (h, i, (void **) key, (void **) value,
+				  sort_fun, sort_arg);
+}
+
+static inline int
+ctf_dynhash_cnext (ctf_dynhash_t *h, ctf_next_t **it,
+		  const void **key, const void **value)
+{
+  return ctf_dynhash_next (h, it, (void **) key, (void **) value);
+}
 
 static inline int
 ctf_dynhash_cinsert (ctf_dynhash_t *h, const void *k, const void *v)
@@ -54,6 +69,12 @@ ctf_dynhash_cinsert (ctf_dynhash_t *h, const void *k, const void *v)
 }
 
 static inline int
+ctf_dynset_cnext (ctf_dynset_t *h, ctf_next_t **it, const void **key)
+{
+  return ctf_dynset_next (h, it, (void **) key);
+}
+
+static inline int
 ctf_dynset_cinsert (ctf_dynset_t *h, const void *k)
 {
   return ctf_dynset_insert (h, (void *) k);
diff --git a/libctf/ctf-util.c b/libctf/ctf-util.c
index 5abea6a..c113dfc 100644
--- a/libctf/ctf-util.c
+++ b/libctf/ctf-util.c
@@ -187,6 +187,11 @@ ctf_next_create (void)
 void
 ctf_next_destroy (ctf_next_t *i)
 {
+  if (i == NULL)
+    return;
+
+  if (i->ctn_iter_fun == (void (*) (void)) ctf_dynhash_next_sorted)
+    free (i->u.ctn_sorted_hkv);
   free (i);
 }
 
@@ -200,5 +205,17 @@ ctf_next_copy (ctf_next_t *i)
   if ((i2 = ctf_next_create()) == NULL)
     return NULL;
   memcpy (i2, i, sizeof (struct ctf_next));
+
+  if (i2->ctn_iter_fun == (void (*) (void)) ctf_dynhash_next_sorted)
+    {
+      size_t els = ctf_dynhash_elements ((ctf_dynhash_t *) i->cu.ctn_h);
+      if ((i2->u.ctn_sorted_hkv = calloc (els, sizeof (ctf_next_hkv_t))) == NULL)
+	{
+	  free (i2);
+	  return NULL;
+	}
+      memcpy (i2->u.ctn_sorted_hkv, i->u.ctn_sorted_hkv,
+	      els * sizeof (ctf_next_hkv_t));
+    }
   return i2;
 }