[DTrace-devel] [PATCH v2 08/11] htab: add a _next-style iterator
Nick Alcock
nick.alcock at oracle.com
Wed Oct 20 11:54:01 PDT 2021
This commit defines an in the libctf _next style because it's *so much*
nicer to use than the function-calling _iter form:
extern void *dt_htab_next(const dt_htab_t *htab, dt_htab_next_t **it);
extern void dt_htab_next_destroy(dt_htab_next_t *i);
extern void dt_htab_next_delete(dt_htab_next_t *i);
Call dt_htab_next with the htab to iterate over and a dt_htab_next_t
initialized to NULL. It allocates an iterator, returns new elements from
the hash until iteration is complete, then frees the iterator and
re-annuls it, ready for another iteration cycle. If you need to exit
early, dt_htab_next_destroy frees the iterator for you (it's just a
free() for now, but see binutils-gdb/libctf/ctf-util.c:ctf_next_destroy
for how this can change over time if your iterator family can iterate
over many different things, like the ctf_next_t can.)
There are no restrictions whatsoever on what you can do inside iteration
(iterate over other things, fork, longjmp out of it, you name it) except
for deleting the hash entry you're iterating over: for that, we have
dt_htab_next_delete. (You might repeat some elements you've already seen
after calling this, but for most use cases I can think of this is much
safer than missing some. This is not a fundamental limitation: I just
need to add a .prev htab operation, symmetric with .next, to fix it. For
now this feels unnecessary: the only likely caller of
dt_htab_next_delete doesn't care if it sees some elements more than
once.)
Signed-off-by: Nick Alcock <nick.alcock at oracle.com>
---
libdtrace/dt_consume.c | 1 +
libdtrace/dt_htab.c | 79 ++++++++++++++++++++++++++++++++++++
libdtrace/dt_htab.h | 14 ++++++-
libdtrace/dt_kernel_module.c | 3 +-
4 files changed, 95 insertions(+), 2 deletions(-)
diff --git a/libdtrace/dt_consume.c b/libdtrace/dt_consume.c
index b80f071956b7..617e8691b516 100644
--- a/libdtrace/dt_consume.c
+++ b/libdtrace/dt_consume.c
@@ -409,6 +409,7 @@ static dt_htab_ops_t dt_spec_buf_htab_ops = {
.hval = (htab_hval_fn)dt_spec_buf_hval,
.cmp = (htab_cmp_fn)dt_spec_buf_cmp,
.add = (htab_add_fn)dt_spec_buf_add,
+ .next = (htab_next_fn)dt_spec_buf_next,
.del = (htab_del_fn)dt_spec_buf_del_buf
};
diff --git a/libdtrace/dt_htab.c b/libdtrace/dt_htab.c
index b8910442cd07..a77c04e51c6f 100644
--- a/libdtrace/dt_htab.c
+++ b/libdtrace/dt_htab.c
@@ -47,6 +47,13 @@ struct dt_htab {
size_t nentries;
};
+struct dt_htab_next {
+ const dt_htab_t *htab;
+ int idx;
+ dt_hbucket_t *bucket;
+ void *ent;
+};
+
/*
* Create a new (empty) hashtable.
*/
@@ -246,6 +253,78 @@ int dt_htab_delete(dt_htab_t *htab, void *entry)
return 0;
}
+/*
+ * Iterate over a hashtable, returning each element in turn (as a pointer to
+ * void). NULL is returned at end-of-iteration (and OOM).
+ */
+void *
+dt_htab_next(const dt_htab_t *htab, dt_htab_next_t **it)
+{
+ dt_htab_next_t *i = *it;
+ /*
+ * Start of iteration.
+ */
+ if (!i) {
+ if ((i = malloc(sizeof(dt_htab_next_t))) == NULL)
+ return NULL;
+ i->htab = htab;
+ i->idx = 0;
+ i->bucket = NULL;
+ i->ent = NULL;
+ *it = i;
+ }
+
+ /*
+ * One iteration cycle. Exhaust the current idx: moving on to the next
+ * restarts the bucket and ent subloops.
+ */
+ for (; i->idx < i->htab->size; i->idx++, i->bucket = NULL, i->ent = NULL) {
+
+ if (i->htab->tab[i->idx] == NULL)
+ continue;
+ if (i->bucket == NULL)
+ i->bucket = i->htab->tab[i->idx];
+
+ /*
+ * Check the current bucket: moving on to the next restarts the
+ * ent subloop.
+ */
+ for (; i->bucket; i->bucket = i->bucket->next, i->ent = NULL) {
+
+ if (i->ent == NULL)
+ i->ent = i->bucket->head;
+ else
+ i->ent = i->htab->ops->next(i->ent);
+ if (i->ent)
+ return i->ent;
+ }
+ }
+
+ free(i);
+ *it = NULL;
+ return NULL;
+}
+
+/*
+ * Delete the htab element the iterator is currently pointing to (if any).
+ * May cause repeated iteration over some of the hashtab.
+ */
+void
+dt_htab_next_delete(dt_htab_next_t *i)
+{
+ if (!i->ent)
+ return;
+
+ dt_htab_delete((dt_htab_t *) i->htab, i->ent);
+ i->ent = NULL;
+}
+
+void
+dt_htab_next_destroy(dt_htab_next_t *i)
+{
+ free(i);
+}
+
/*
* Return the number of entries in the hashtable.
*/
diff --git a/libdtrace/dt_htab.h b/libdtrace/dt_htab.h
index e12c96fc9006..865e9d220585 100644
--- a/libdtrace/dt_htab.h
+++ b/libdtrace/dt_htab.h
@@ -18,6 +18,7 @@ typedef uint32_t (*htab_hval_fn)(const void *);
typedef int (*htab_cmp_fn)(const void *, const void *);
typedef void *(*htab_add_fn)(void *, void *);
typedef void *(*htab_del_fn)(void *, void *);
+typedef void *(*htab_next_fn)(void *);
#define DEFINE_HE_STD_LINK_FUNCS(ID, TYPE, HE) \
static TYPE *ID##_add(TYPE *head, TYPE *new) \
@@ -59,6 +60,11 @@ typedef void *(*htab_del_fn)(void *, void *);
ent->HE.prev = ent->HE.next = NULL; \
\
return head; \
+ } \
+ \
+ static TYPE *ID##_next(TYPE *ent) \
+ { \
+ return ent->HE.next; \
}
#define DEFINE_HTAB_STD_OPS(ID) \
@@ -67,6 +73,7 @@ typedef void *(*htab_del_fn)(void *, void *);
.cmp = (htab_cmp_fn)ID##_cmp, \
.add = (htab_add_fn)ID##_add, \
.del = (htab_del_fn)ID##_del, \
+ .next = (htab_next_fn)ID##_next, \
};
@@ -75,6 +82,7 @@ typedef struct dt_htab_ops {
htab_cmp_fn cmp;
htab_add_fn add;
htab_del_fn del;
+ htab_next_fn next;
} dt_htab_ops_t;
typedef struct dt_hentry {
@@ -82,7 +90,8 @@ typedef struct dt_hentry {
void *prev;
} dt_hentry_t;
-typedef struct dt_htab dt_htab_t;
+typedef struct dt_htab dt_htab_t;
+typedef struct dt_htab_next dt_htab_next_t;
extern dt_htab_t *dt_htab_create(struct dtrace_hdl *dtp, dt_htab_ops_t *ops);
extern void dt_htab_destroy(struct dtrace_hdl *dtp, dt_htab_t *htab);
@@ -90,6 +99,9 @@ extern int dt_htab_insert(dt_htab_t *htab, void *entry);
extern void *dt_htab_lookup(const dt_htab_t *htab, const void *entry);
extern size_t dt_htab_entries(const dt_htab_t *htab);
extern int dt_htab_delete(dt_htab_t *htab, void *entry);
+extern void *dt_htab_next(const dt_htab_t *htab, dt_htab_next_t **it);
+extern void dt_htab_next_delete(dt_htab_next_t *i);
+extern void dt_htab_next_destroy(dt_htab_next_t *i);
extern void dt_htab_stats(const char *name, const dt_htab_t *htab);
#ifdef __cplusplus
diff --git a/libdtrace/dt_kernel_module.c b/libdtrace/dt_kernel_module.c
index 1d147405af9d..38a2b91217c6 100644
--- a/libdtrace/dt_kernel_module.c
+++ b/libdtrace/dt_kernel_module.c
@@ -58,7 +58,8 @@ static dt_htab_ops_t kernpath_htab_ops = {
.hval = (htab_hval_fn)kernpath_hval,
.cmp = (htab_cmp_fn)kernpath_cmp,
.add = (htab_add_fn)kernpath_add,
- .del = (htab_del_fn)kernpath_del_path
+ .next = (htab_next_fn)kernpath_next,
+ .del = (htab_del_fn)kernpath_del_path,
};
/*
--
2.33.1.257.g9e0974a4e8
More information about the DTrace-devel
mailing list