diff options
| -rw-r--r-- | libctf/ChangeLog | 22 | ||||
| -rw-r--r-- | libctf/ctf-hash.c | 225 | ||||
| -rw-r--r-- | libctf/ctf-impl.h | 21 | ||||
| -rw-r--r-- | libctf/ctf-inlines.h | 21 | ||||
| -rw-r--r-- | libctf/ctf-util.c | 17 |
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; } |