diff options
| -rw-r--r-- | libctf/ChangeLog | 27 | ||||
| -rw-r--r-- | libctf/ctf-hash.c | 168 | ||||
| -rw-r--r-- | libctf/ctf-impl.h | 13 | ||||
| -rw-r--r-- | libctf/ctf-inlines.h | 6 |
4 files changed, 203 insertions, 11 deletions
diff --git a/libctf/ChangeLog b/libctf/ChangeLog index 27987f2..329e69c 100644 --- a/libctf/ChangeLog +++ b/libctf/ChangeLog @@ -1,5 +1,32 @@ 2020-07-22 Nick Alcock <nick.alcock@oracle.com> + * ctf-hash.c (ctf_dynset_eq_string): New. + (ctf_dynset_create): New. + (DYNSET_EMPTY_ENTRY_REPLACEMENT): New. + (DYNSET_DELETED_ENTRY_REPLACEMENT): New. + (key_to_internal): New. + (internal_to_key): New. + (ctf_dynset_insert): New. + (ctf_dynset_remove): New. + (ctf_dynset_destroy): New. + (ctf_dynset_lookup): New. + (ctf_dynset_exists): New. + (ctf_dynset_lookup_any): New. + (ctf_hash_insert_type): Coding style. + (ctf_hash_define_type): Likewise. + * ctf-impl.h (ctf_dynset_t): New. + (ctf_dynset_eq_string): New. + (ctf_dynset_create): New. + (ctf_dynset_insert): New. + (ctf_dynset_remove): New. + (ctf_dynset_destroy): New. + (ctf_dynset_lookup): New. + (ctf_dynset_exists): New. + (ctf_dynset_lookup_any): New. + * ctf-inlines.h (ctf_dynset_cinsert): New. + +2020-07-22 Nick Alcock <nick.alcock@oracle.com> + * ctf-hash.c (ctf_helem_t) <key_free>: Remove. <value_free>: Likewise. <owner>: New. diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c index caefd99..7eba494 100644 --- a/libctf/ctf-hash.c +++ b/libctf/ctf-hash.c @@ -22,14 +22,21 @@ #include "libiberty.h" #include "hashtab.h" -/* We have two hashtable implementations: one, 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; the other, ctf_dynhash_*(), 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. These can be implemented by the same underlying hashmap - if you wish. */ +/* 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. + + - 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. + + - 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 @@ -51,7 +58,7 @@ struct ctf_dynhash ctf_hash_free_fun value_free; }; -/* Hash functions. */ +/* Hash and eq functions for the dynhash and hash. */ unsigned int ctf_hash_integer (const void *ptr) @@ -109,6 +116,16 @@ ctf_hash_eq_type_mapping_key (const void *a, const void *b) && (key_a->cltm_idx == key_b->cltm_idx); } + +/* Hash and eq functions for the dynset. Most of these can just use the + underlying hashtab functions directly. */ + +int +ctf_dynset_eq_string (const void *a, const void *b) +{ + return !strcmp((const char *) a, (const char *) b); +} + /* The dynhash, used for hashes whose size is not known at creation time. */ /* Free a single ctf_helem with arbitrary key/value functions. */ @@ -369,6 +386,135 @@ ctf_dynhash_destroy (ctf_dynhash_t *hp) free (hp); } +/* The dynset, used for sets of keys with no value. The implementation of this + can be much simpler, because without a value the slot can simply be the + stored key, which means we don't need to store the freeing functions and the + dynset itself is just a htab. */ + +ctf_dynset_t * +ctf_dynset_create (htab_hash hash_fun, htab_eq eq_fun, + ctf_hash_free_fun key_free) +{ + /* 7 is arbitrary and untested for now. */ + return (ctf_dynset_t *) htab_create_alloc (7, (htab_hash) hash_fun, eq_fun, + key_free, xcalloc, free); +} + +/* The dynset has one complexity: the underlying implementation reserves two + values for internal hash table implementation details (empty versus deleted + entries). These values are otherwise very useful for pointers cast to ints, + so transform the ctf_dynset_inserted value to allow for it. (This + introduces an ambiguity in that one can no longer store these two values in + the dynset, but if we pick high enough values this is very unlikely to be a + problem.) + + We leak this implementation detail to the freeing functions on the grounds + that any use of these functions is overwhelmingly likely to be in sets using + real pointers, which will be unaffected. */ + +#define DYNSET_EMPTY_ENTRY_REPLACEMENT ((void *) (uintptr_t) -64) +#define DYNSET_DELETED_ENTRY_REPLACEMENT ((void *) (uintptr_t) -63) + +static void * +key_to_internal (const void *key) +{ + if (key == HTAB_EMPTY_ENTRY) + return DYNSET_EMPTY_ENTRY_REPLACEMENT; + else if (key == HTAB_DELETED_ENTRY) + return DYNSET_DELETED_ENTRY_REPLACEMENT; + + return (void *) key; +} + +static void * +internal_to_key (const void *internal) +{ + if (internal == DYNSET_EMPTY_ENTRY_REPLACEMENT) + return HTAB_EMPTY_ENTRY; + else if (internal == DYNSET_DELETED_ENTRY_REPLACEMENT) + return HTAB_DELETED_ENTRY; + return (void *) internal; +} + +int +ctf_dynset_insert (ctf_dynset_t *hp, void *key) +{ + struct htab *htab = (struct htab *) hp; + void **slot; + + slot = htab_find_slot (htab, key, INSERT); + + if (!slot) + { + errno = ENOMEM; + return -errno; + } + + if (*slot) + { + if (htab->del_f) + (*htab->del_f) (*slot); + } + + *slot = key_to_internal (key); + + return 0; +} + +void +ctf_dynset_remove (ctf_dynset_t *hp, const void *key) +{ + htab_remove_elt ((struct htab *) hp, key_to_internal (key)); +} + +void +ctf_dynset_destroy (ctf_dynset_t *hp) +{ + if (hp != NULL) + htab_delete ((struct htab *) hp); +} + +void * +ctf_dynset_lookup (ctf_dynset_t *hp, const void *key) +{ + void **slot = htab_find_slot ((struct htab *) hp, + key_to_internal (key), NO_INSERT); + + if (slot) + return internal_to_key (*slot); + return NULL; +} + +/* TRUE/FALSE return. */ +int +ctf_dynset_exists (ctf_dynset_t *hp, const void *key, const void **orig_key) +{ + void **slot = htab_find_slot ((struct htab *) hp, + key_to_internal (key), NO_INSERT); + + if (orig_key && slot) + *orig_key = internal_to_key (*slot); + return (slot != NULL); +} + +/* Look up a completely random value from the set, if any exist. + Keys with value zero cannot be distinguished from a nonexistent key. */ +void * +ctf_dynset_lookup_any (ctf_dynset_t *hp) +{ + struct htab *htab = (struct htab *) hp; + void **slot = htab->entries; + void **limit = slot + htab_size (htab); + + while (slot < limit + && (*slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)) + slot++; + + if (slot < limit) + return internal_to_key (*slot); + return NULL; +} + /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without removal. This is a straight cast of a hashtab. */ @@ -415,12 +561,12 @@ ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, /* 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. */ + ctf_hash_insert_type and hash it in. */ int ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, uint32_t name) { - /* This matches the semantics of ctf_hash_insert_type() in this + /* This matches the semantics of ctf_hash_insert_type in this implementation anyway. */ return ctf_hash_insert_type (hp, fp, type, name); diff --git a/libctf/ctf-impl.h b/libctf/ctf-impl.h index 3e09779..7d583ab 100644 --- a/libctf/ctf-impl.h +++ b/libctf/ctf-impl.h @@ -34,6 +34,7 @@ #include <ctype.h> #include <elf.h> #include <bfd.h> +#include "hashtab.h" #ifdef __cplusplus extern "C" @@ -73,6 +74,7 @@ extern "C" typedef struct ctf_fixed_hash ctf_hash_t; /* Private to ctf-hash.c. */ typedef struct ctf_dynhash ctf_dynhash_t; /* Private to ctf-hash.c. */ +typedef struct ctf_dynset ctf_dynset_t; /* Private to ctf-hash.c. */ typedef struct ctf_strs { @@ -378,6 +380,8 @@ extern int ctf_hash_eq_integer (const void *, const void *); extern int ctf_hash_eq_string (const void *, const void *); extern int ctf_hash_eq_type_mapping_key (const void *, const void *); +extern int ctf_dynset_eq_string (const void *, const void *); + typedef void (*ctf_hash_free_fun) (void *); typedef void (*ctf_hash_iter_f) (void *key, void *value, void *arg); @@ -407,6 +411,15 @@ extern void ctf_dynhash_iter_remove (ctf_dynhash_t *, ctf_hash_iter_remove_f, extern void *ctf_dynhash_iter_find (ctf_dynhash_t *, ctf_hash_iter_find_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 *); +extern void ctf_dynset_remove (ctf_dynset_t *, const void *); +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 void *ctf_dynset_lookup_any (ctf_dynset_t *); + #define ctf_list_prev(elem) ((void *)(((ctf_list_t *)(elem))->l_prev)) #define ctf_list_next(elem) ((void *)(((ctf_list_t *)(elem))->l_next)) diff --git a/libctf/ctf-inlines.h b/libctf/ctf-inlines.h index ad74b39..f9c1b2a 100644 --- a/libctf/ctf-inlines.h +++ b/libctf/ctf-inlines.h @@ -38,6 +38,12 @@ ctf_dynhash_cinsert (ctf_dynhash_t *h, const void *k, const void *v) return ctf_dynhash_insert (h, (void *) k, (void *) v); } +static inline int +ctf_dynset_cinsert (ctf_dynset_t *h, const void *k) +{ + return ctf_dynset_insert (h, (void *) k); +} + #ifdef __cplusplus } #endif |