diff options
| author | Nick Alcock <nick.alcock@oracle.com> | 2023-12-18 17:47:48 +0000 |
|---|---|---|
| committer | Nick Alcock <nick.alcock@oracle.com> | 2024-04-19 16:14:46 +0100 |
| commit | 54a0219150d9dd2b0034e9682072900d4ec403b3 (patch) | |
| tree | e27705e3a8e7045f642e26330bacb5020b415d79 /libctf/ctf-hash.c | |
| parent | ca019227843f62f5ac0a1c432680e3ca05c4377b (diff) | |
| download | binutils-54a0219150d9dd2b0034e9682072900d4ec403b3.zip binutils-54a0219150d9dd2b0034e9682072900d4ec403b3.tar.gz binutils-54a0219150d9dd2b0034e9682072900d4ec403b3.tar.bz2 | |
libctf: remove static/dynamic name lookup distinction
libctf internally maintains a set of hash tables for type name lookups,
one for each valid C type namespace (struct, union, enum, and everything
else).
Or, rather, it maintains *two* sets of hash tables: one, a ctf_hash *,
is meant for lookups in ctf_(buf)open()ed dicts with fixed content; the
other, a ctf_dynhash *, is meant for lookups in ctf_create()d dicts.
This distinction was somewhat valuable in the far pre-binutils past when
two different hashtable implementations were used (one expanding, the
other fixed-size), but those days are long gone: the hash table
implementations are almost identical, both wrappers around the libiberty
hashtab. The ctf_dynhash has many more capabilities than the ctf_hash
(iteration, deletion, etc etc) and has no downsides other than starting
at a fixed, arbitrary small size.
That limitation is easy to lift (via a new ctf_dynhash_create_sized()),
following which we can throw away nearly all the ctf_hash
implementation, and all the code to choose between readable and writable
hashtabs; the few convenience functions that are still useful (for
insertion of name -> type mappings) can also be generalized a bit so
that the extra string verification they do is potentially available to
other string lookups as well.
(libctf still has two hashtable implementations, ctf_dynhash, above,
and ctf_dynset, which is a key-only hashtab that can avoid a great many
malloc()s, used for high-volume applications in the deduplicator.)
libctf/
* ctf-create.c (ctf_create): Eliminate ctn_writable.
(ctf_dtd_insert): Likewise.
(ctf_dtd_delete): Likewise.
(ctf_rollback): Likewise.
(ctf_name_table): Eliminate ctf_names_t.
* ctf-hash.c (ctf_dynhash_create): Comment update.
Reimplement in terms of...
(ctf_dynhash_create_sized): ... this new function.
(ctf_hash_create): Remove.
(ctf_hash_size): Remove.
(ctf_hash_define_type): Remove.
(ctf_hash_destroy): Remove.
(ctf_hash_lookup_type): Rename to...
(ctf_dynhash_lookup_type): ... this.
(ctf_hash_insert_type): Rename to...
(ctf_dynhash_insert_type): ... this, moving validation to...
* ctf-string.c (ctf_strptr_validate): ... this new function.
* ctf-impl.h (struct ctf_names): Extirpate.
(struct ctf_lookup.ctl_hash): Now a ctf_dynhash_t.
(struct ctf_dict): All ctf_names_t fields are now ctf_dynhash_t.
(ctf_name_table): Now returns a ctf_dynhash_t.
(ctf_lookup_by_rawhash): Remove.
(ctf_hash_create): Likewise.
(ctf_hash_insert_type): Likewise.
(ctf_hash_define_type): Likewise.
(ctf_hash_lookup_type): Likewise.
(ctf_hash_size): Likewise.
(ctf_hash_destroy): Likewise.
(ctf_dynhash_create_sized): New.
(ctf_dynhash_insert_type): New.
(ctf_dynhash_lookup_type): New.
(ctf_strptr_validate): New.
* ctf-lookup.c (ctf_lookup_by_name_internal): Adapt.
* ctf-open.c (init_types): Adapt.
(ctf_set_ctl_hashes): Adapt.
(ctf_dict_close): Adapt.
* ctf-serialize.c (ctf_serialize): Adapt.
* ctf-types.c (ctf_lookup_by_rawhash): Remove.
Diffstat (limited to 'libctf/ctf-hash.c')
| -rw-r--r-- | libctf/ctf-hash.c | 106 |
1 files changed, 35 insertions, 71 deletions
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c index 1bc539e..f8032ae 100644 --- a/libctf/ctf-hash.c +++ b/libctf/ctf-hash.c @@ -22,25 +22,22 @@ #include "libiberty.h" #include "hashtab.h" -/* 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. +/* We have two hashtable implementations: - 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. + 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. It can be constructed with an expected initial number of + elements, but need not be. - 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 - garbage (not NULL!) in that case. */ +/* The helem is used for general key/value mappings in the ctf_dynhash: the + owner may not have space allocated for it, and will be garbage (not + NULL!) in that case. */ typedef struct ctf_helem { @@ -157,8 +154,9 @@ ctf_dynhash_item_free (void *item) } ctf_dynhash_t * -ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, - ctf_hash_free_fun key_free, ctf_hash_free_fun value_free) +ctf_dynhash_create_sized (unsigned long nelems, ctf_hash_fun hash_fun, + ctf_hash_eq_fun eq_fun, ctf_hash_free_fun key_free, + ctf_hash_free_fun value_free) { ctf_dynhash_t *dynhash; htab_del del = ctf_dynhash_item_free; @@ -173,8 +171,7 @@ ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, if (key_free == NULL && value_free == NULL) del = free; - /* 7 is arbitrary and untested for now. */ - if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun, + if ((dynhash->htab = htab_create_alloc (nelems, (htab_hash) hash_fun, eq_fun, del, xcalloc, free)) == NULL) { free (dynhash); @@ -190,6 +187,15 @@ ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, return dynhash; } +ctf_dynhash_t * +ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, + ctf_hash_free_fun key_free, ctf_hash_free_fun value_free) +{ + /* 7 is arbitrary and not benchmarked yet. */ + + return ctf_dynhash_create_sized (7, hash_fun, eq_fun, key_free, value_free); +} + static ctf_helem_t ** ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert) { @@ -767,80 +773,38 @@ ctf_dynset_next (ctf_dynset_t *hp, ctf_next_t **it, void **key) 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. */ - -ctf_hash_t * -ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun, - ctf_hash_eq_fun eq_fun) -{ - return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun, - eq_fun, free, xcalloc, free); -} - -uint32_t -ctf_hash_size (const ctf_hash_t *hp) -{ - return htab_elements ((struct htab *) hp); -} +/* Helper functions for insertion/removal of types. */ int -ctf_hash_insert_type (ctf_hash_t *hp, ctf_dict_t *fp, uint32_t type, - uint32_t name) +ctf_dynhash_insert_type (ctf_dict_t *fp, ctf_dynhash_t *hp, uint32_t type, + uint32_t name) { - const char *str = ctf_strraw (fp, name); + const char *str; + int err; if (type == 0) return EINVAL; - if (str == NULL - && CTF_NAME_STID (name) == CTF_STRTAB_1 - && fp->ctf_syn_ext_strtab == NULL - && fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL) - return ECTF_STRTAB; - - if (str == NULL) - return ECTF_BADNAME; + if ((str = ctf_strptr_validate (fp, name)) == NULL) + return ctf_errno (fp); if (str[0] == '\0') return 0; /* Just ignore empty strings on behalf of caller. */ - if (ctf_hashtab_insert ((struct htab *) hp, (char *) str, - (void *) (ptrdiff_t) type, NULL, NULL) != NULL) + if ((err = ctf_dynhash_insert (hp, (char *) str, + (void *) (ptrdiff_t) type)) == 0) return 0; - return errno; -} - -/* 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. */ -int -ctf_hash_define_type (ctf_hash_t *hp, ctf_dict_t *fp, uint32_t type, - uint32_t name) -{ - /* This matches the semantics of ctf_hash_insert_type in this - implementation anyway. */ - return ctf_hash_insert_type (hp, fp, type, name); + return err; } ctf_id_t -ctf_hash_lookup_type (ctf_hash_t *hp, ctf_dict_t *fp __attribute__ ((__unused__)), - const char *key) +ctf_dynhash_lookup_type (ctf_dynhash_t *hp, const char *key) { - ctf_helem_t **slot; + void *value; - slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT); - - if (slot) - return (ctf_id_t) (uintptr_t) ((*slot)->value); + if (ctf_dynhash_lookup_kv (hp, key, NULL, &value)) + return (ctf_id_t) (uintptr_t) value; return 0; } - -void -ctf_hash_destroy (ctf_hash_t *hp) -{ - if (hp != NULL) - htab_delete ((struct htab *) hp); -} |