#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
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)
return !strcmp((const char *) hep_a->key, (const char *) hep_b->key);
}
-/* Hash a type_mapping_key. */
+/* Hash a type_key. */
unsigned int
-ctf_hash_type_mapping_key (const void *ptr)
+ctf_hash_type_key (const void *ptr)
{
ctf_helem_t *hep = (ctf_helem_t *) ptr;
- ctf_link_type_mapping_key_t *k = (ctf_link_type_mapping_key_t *) hep->key;
+ ctf_link_type_key_t *k = (ctf_link_type_key_t *) hep->key;
- return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx);
+ return htab_hash_pointer (k->cltk_fp) + 59
+ * htab_hash_pointer ((void *) (uintptr_t) k->cltk_idx);
}
int
-ctf_hash_eq_type_mapping_key (const void *a, const void *b)
+ctf_hash_eq_type_key (const void *a, const void *b)
{
ctf_helem_t *hep_a = (ctf_helem_t *) a;
ctf_helem_t *hep_b = (ctf_helem_t *) b;
- ctf_link_type_mapping_key_t *key_a = (ctf_link_type_mapping_key_t *) hep_a->key;
- ctf_link_type_mapping_key_t *key_b = (ctf_link_type_mapping_key_t *) hep_b->key;
+ ctf_link_type_key_t *key_a = (ctf_link_type_key_t *) hep_a->key;
+ ctf_link_type_key_t *key_b = (ctf_link_type_key_t *) hep_b->key;
+
+ return (key_a->cltk_fp == key_b->cltk_fp)
+ && (key_a->cltk_idx == key_b->cltk_idx);
+}
+
+/* Hash a type_id_key. */
+unsigned int
+ctf_hash_type_id_key (const void *ptr)
+{
+ ctf_helem_t *hep = (ctf_helem_t *) ptr;
+ ctf_type_id_key_t *k = (ctf_type_id_key_t *) hep->key;
+
+ return htab_hash_pointer ((void *) (uintptr_t) k->ctii_input_num)
+ + 59 * htab_hash_pointer ((void *) (uintptr_t) k->ctii_type);
+}
+
+int
+ctf_hash_eq_type_id_key (const void *a, const void *b)
+{
+ ctf_helem_t *hep_a = (ctf_helem_t *) a;
+ ctf_helem_t *hep_b = (ctf_helem_t *) b;
+ ctf_type_id_key_t *key_a = (ctf_type_id_key_t *) hep_a->key;
+ ctf_type_id_key_t *key_b = (ctf_type_id_key_t *) hep_b->key;
+
+ return (key_a->ctii_input_num == key_b->ctii_input_num)
+ && (key_a->ctii_type == key_b->ctii_type);
+}
- return (key_a->cltm_fp == key_b->cltm_fp)
- && (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. */
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)
{
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;
+}
+
+/* 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. */
/* 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);
slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
if (slot)
- return (ctf_id_t) ((*slot)->value);
+ return (ctf_id_t) (uintptr_t) ((*slot)->value);
return 0;
}
projects / deliverable / binutils-gdb.git / blobdiff