[DTrace-devel] [PATCH v3 08/11] htab: add an iterator
Nick Alcock
nick.alcock at oracle.com
Mon Nov 1 14:29:44 UTC 2021
This commit defines an iterator 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);
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
that you should not delete hash entries that the iterator has not yet
returned: if you insert new ones, they may or may not be returned by
this iteration cycle.
Signed-off-by: Nick Alcock <nick.alcock at oracle.com>
---
libdtrace/dt_consume.c | 1 +
libdtrace/dt_htab.c | 92 ++++++++++++++++++++++++++++++++++++
libdtrace/dt_htab.h | 13 ++++-
libdtrace/dt_kernel_module.c | 3 +-
4 files changed, 107 insertions(+), 2 deletions(-)
diff --git a/libdtrace/dt_consume.c b/libdtrace/dt_consume.c
index 54e30a38184b..70359dd48b40 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 b04a70e88fc2..41c409a2caff 100644
--- a/libdtrace/dt_htab.c
+++ b/libdtrace/dt_htab.c
@@ -47,6 +47,21 @@ struct dt_htab {
dt_htab_ops_t *ops;
};
+/*
+ * The dt_htab_next iteration state is somewhat unusual. It points not to the
+ * element most recently returned by the iterator, but to the element which
+ * will be returned on the *next* iteration cycle (so it spends the last
+ * iteration cycle "off-the-end", all-NULL). This allows the user to
+ * delete the current element returned by dt_htab_next().
+ */
+struct dt_htab_next {
+ const dt_htab_t *htab;
+ int idx;
+ dt_hbucket_t *bucket;
+ void *ent;
+ int exhausted;
+};
+
/*
* Create a new (empty) hashtable.
*/
@@ -251,6 +266,83 @@ 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;
+ void *ret;
+
+ /*
+ * Start of iteration.
+ */
+ if (!i) {
+ if ((i = calloc(1, sizeof(dt_htab_next_t))) == NULL)
+ return NULL;
+ i->htab = htab;
+ *it = i;
+
+ /*
+ * Tick through one iteration. Ignore the return value,
+ * since it is meaningless at this stage.
+ */
+ (void) dt_htab_next(htab, it);
+ }
+
+ /*
+ * Capture the value we will return after advancing the iterator, and
+ * handle end-of-iteration.
+ */
+
+ ret = i->ent;
+ if (i->exhausted) {
+ free(i);
+ *it = NULL;
+ return NULL;
+ }
+
+ /*
+ * 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 ret;
+ }
+ }
+
+ /*
+ * End of advancement, but that doesn't mean we can't return.
+ */
+ i->exhausted = 1;
+ return ret;
+}
+
+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..6dae0262c890 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,8 @@ 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_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