[deliverable/binutils-gdb.git] / libctf / ctf-hash.c

/* Interface to hashtable implementations.
   Copyright (C) 2006-2020 Free Software Foundation, Inc.

   This file is part of libctf.

   libctf is free software; you can redistribute it and/or modify it under
   the terms of the GNU General Public License as published by the Free
   Software Foundation; either version 3, or (at your option) any later
   version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   See the GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; see the file COPYING.  If not see
   <http://www.gnu.org/licenses/>.  */

#include <ctf-impl.h>
#include <string.h>
#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.  */

typedef struct ctf_helem
{
  void *key;			 /* Either a pointer, or a coerced ctf_id_t.  */
  void *value;			 /* The value (possibly a coerced int).  */
  ctf_hash_free_fun key_free;
  ctf_hash_free_fun value_free;
} ctf_helem_t;

struct ctf_dynhash
{
  struct htab *htab;
  ctf_hash_free_fun key_free;
  ctf_hash_free_fun value_free;
};

/* Hash functions. */

unsigned int
ctf_hash_integer (const void *ptr)
{
  ctf_helem_t *hep = (ctf_helem_t *) ptr;

  return htab_hash_pointer (hep->key);
}

int
ctf_hash_eq_integer (const void *a, const void *b)
{
  ctf_helem_t *hep_a = (ctf_helem_t *) a;
  ctf_helem_t *hep_b = (ctf_helem_t *) b;

  return htab_eq_pointer (hep_a->key, hep_b->key);
}

unsigned int
ctf_hash_string (const void *ptr)
{
  ctf_helem_t *hep = (ctf_helem_t *) ptr;

  return htab_hash_string (hep->key);
}

int
ctf_hash_eq_string (const void *a, const void *b)
{
  ctf_helem_t *hep_a = (ctf_helem_t *) a;
  ctf_helem_t *hep_b = (ctf_helem_t *) b;

  return !strcmp((const char *) hep_a->key, (const char *) hep_b->key);
}

/* Hash a type_mapping_key.  */
unsigned int
ctf_hash_type_mapping_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;

  return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx);
}

int
ctf_hash_eq_type_mapping_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;

  return (key_a->cltm_fp == key_b->cltm_fp)
    && (key_a->cltm_idx == key_b->cltm_idx);
}

/* The dynhash, used for hashes whose size is not known at creation time. */

/* Free a single ctf_helem.  */

static void
ctf_dynhash_item_free (void *item)
{
  ctf_helem_t *helem = item;

  if (helem->key_free && helem->key)
    helem->key_free (helem->key);
  if (helem->value_free && helem->value)
    helem->value_free (helem->value);
  free (helem);
}

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_t *dynhash;

  dynhash = malloc (sizeof (ctf_dynhash_t));
  if (!dynhash)
    return NULL;

  /* 7 is arbitrary and untested for now..  */
  if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
                                          ctf_dynhash_item_free, xcalloc, free)) == NULL)
    {
      free (dynhash);
      return NULL;
    }

  dynhash->key_free = key_free;
  dynhash->value_free = value_free;

  return dynhash;
}

static ctf_helem_t **
ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert)
{
  ctf_helem_t tmp = { .key = (void *) key };
  return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert);
}

static ctf_helem_t *
ctf_hashtab_insert (struct htab *htab, void *key, void *value,
		    ctf_hash_free_fun key_free,
		    ctf_hash_free_fun value_free)
{
  ctf_helem_t **slot;

  slot = ctf_hashtab_lookup (htab, key, INSERT);

  if (!slot)
    {
      errno = -ENOMEM;
      return NULL;
    }

  if (!*slot)
    {
      *slot = malloc (sizeof (ctf_helem_t));
      if (!*slot)
	return NULL;
    }
  else
    {
      if (key_free)
	  key_free ((*slot)->key);
      if (value_free)
	  value_free ((*slot)->value);
    }
  (*slot)->key = key;
  (*slot)->value = value;
  return *slot;
}

int
ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
{
  ctf_helem_t *slot;

  slot = ctf_hashtab_insert (hp->htab, key, value,
			     hp->key_free, hp->value_free);

  if (!slot)
    return errno;

  /* We need to keep the key_free and value_free around in each item because the
     del function has no visibility into the hash as a whole, only into the
     individual items.  */

  slot->key_free = hp->key_free;
  slot->value_free = hp->value_free;

  return 0;
}

void
ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key)
{
  ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
  htab_remove_elt (hp->htab, &hep);
}

void
ctf_dynhash_empty (ctf_dynhash_t *hp)
{
  htab_empty (hp->htab);
}

void *
ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key)
{
  ctf_helem_t **slot;

  slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT);

  if (slot)
    return (*slot)->value;

  return NULL;
}

typedef struct ctf_traverse_cb_arg
{
  ctf_hash_iter_f fun;
  void *arg;
} ctf_traverse_cb_arg_t;

static int
ctf_hashtab_traverse (void **slot, void *arg_)
{
  ctf_helem_t *helem = *((ctf_helem_t **) slot);
  ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_;

  arg->fun (helem->key, helem->value, arg->arg);
  return 1;
}

void
ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_)
{
  ctf_traverse_cb_arg_t arg = { fun, arg_ };
  htab_traverse (hp->htab, ctf_hashtab_traverse, &arg);
}

typedef struct ctf_traverse_remove_cb_arg
{
  struct htab *htab;
  ctf_hash_iter_remove_f fun;
  void *arg;
} ctf_traverse_remove_cb_arg_t;

static int
ctf_hashtab_traverse_remove (void **slot, void *arg_)
{
  ctf_helem_t *helem = *((ctf_helem_t **) slot);
  ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_;

  if (arg->fun (helem->key, helem->value, arg->arg))
    htab_clear_slot (arg->htab, slot);
  return 1;
}

void
ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun,
                         void *arg_)
{
  ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ };
  htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg);
}

void
ctf_dynhash_destroy (ctf_dynhash_t *hp)
{
  if (hp != NULL)
    htab_delete (hp->htab);
  free (hp);
}

/* 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);
}

int
ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
		      uint32_t name)
{
  const char *str = ctf_strraw (fp, name);

  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[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)
    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_file_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);
}

ctf_id_t
ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)),
		      const char *key)
{
  ctf_helem_t **slot;

  slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);

  if (slot)
    return (ctf_id_t) ((*slot)->value);

  return 0;
}

void
ctf_hash_destroy (ctf_hash_t *hp)
{
  if (hp != NULL)
    htab_delete ((struct htab *) hp);
}
Commit	Line	Data
c0754cdd	1	/* Interface to hashtable implementations.
b3adc24a	2	Copyright (C) 2006-2020 Free Software Foundation, Inc.
c0754cdd NA	3
	4	This file is part of libctf.
	5
	6	libctf is free software; you can redistribute it and/or modify it under
	7	the terms of the GNU General Public License as published by the Free
	8	Software Foundation; either version 3, or (at your option) any later
	9	version.
	10
	11	This program is distributed in the hope that it will be useful, but
	12	WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
	14	See the GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with this program; see the file COPYING. If not see
	18	<http://www.gnu.org/licenses/>. */
	19
	20	#include <ctf-impl.h>
	21	#include <string.h>
	22	#include "libiberty.h"
	23	#include "hashtab.h"
	24
	25	/* We have two hashtable implementations: one, ctf_dynhash_*(), is an interface to
	26	a dynamically-expanding hash with unknown size that should support addition
	27	of large numbers of items, and removal as well, and is used only at
	28	type-insertion time; the other, ctf_dynhash_*(), is an interface to a
	29	fixed-size hash from const char * -> ctf_id_t with number of elements
	30	specified at creation time, that should support addition of items but need
	31	not support removal. These can be implemented by the same underlying hashmap
	32	if you wish. */
	33
	34	typedef struct ctf_helem
	35	{
	36	void key; / Either a pointer, or a coerced ctf_id_t. */
	37	void value; / The value (possibly a coerced int). */
	38	ctf_hash_free_fun key_free;
	39	ctf_hash_free_fun value_free;
	40	} ctf_helem_t;
	41
	42	struct ctf_dynhash
	43	{
	44	struct htab *htab;
	45	ctf_hash_free_fun key_free;
	46	ctf_hash_free_fun value_free;
	47	};
	48
	49	/* Hash functions. */
	50
	51	unsigned int
	52	ctf_hash_integer (const void *ptr)
	53	{
	54	ctf_helem_t hep = (ctf_helem_t ) ptr;
	55
	56	return htab_hash_pointer (hep->key);
	57	}
	58
	59	int
	60	ctf_hash_eq_integer (const void a, const void b)
	61	{
	62	ctf_helem_t hep_a = (ctf_helem_t ) a;
	63	ctf_helem_t hep_b = (ctf_helem_t ) b;
	64
	65	return htab_eq_pointer (hep_a->key, hep_b->key);
	66	}
67
68	unsigned int
69	ctf_hash_string (const void *ptr)
70	{
71	ctf_helem_t hep = (ctf_helem_t ) ptr;
72
73	return htab_hash_string (hep->key);
74	}
75
76	int
77	ctf_hash_eq_string (const void a, const void b)
78	{
79	ctf_helem_t hep_a = (ctf_helem_t ) a;
80	ctf_helem_t hep_b = (ctf_helem_t ) b;
81
82	return !strcmp((const char ) hep_a->key, (const char ) hep_b->key);
83	}
84
886453cb NA	85	/* Hash a type_mapping_key. */
	86	unsigned int
	87	ctf_hash_type_mapping_key (const void *ptr)
	88	{
	89	ctf_helem_t hep = (ctf_helem_t ) ptr;
	90	ctf_link_type_mapping_key_t k = (ctf_link_type_mapping_key_t ) hep->key;
	91
	92	return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx);
	93	}
	94
	95	int
	96	ctf_hash_eq_type_mapping_key (const void a, const void b)
	97	{
	98	ctf_helem_t hep_a = (ctf_helem_t ) a;
	99	ctf_helem_t hep_b = (ctf_helem_t ) b;
	100	ctf_link_type_mapping_key_t key_a = (ctf_link_type_mapping_key_t ) hep_a->key;
	101	ctf_link_type_mapping_key_t key_b = (ctf_link_type_mapping_key_t ) hep_b->key;
	102
	103	return (key_a->cltm_fp == key_b->cltm_fp)
	104	&& (key_a->cltm_idx == key_b->cltm_idx);
	105	}
	106
c0754cdd NA	107	/* The dynhash, used for hashes whose size is not known at creation time. */
	108
	109	/* Free a single ctf_helem. */
	110
	111	static void
	112	ctf_dynhash_item_free (void *item)
	113	{
	114	ctf_helem_t *helem = item;
	115
	116	if (helem->key_free && helem->key)
	117	helem->key_free (helem->key);
	118	if (helem->value_free && helem->value)
	119	helem->value_free (helem->value);
	120	free (helem);
	121	}
	122
	123	ctf_dynhash_t *
	124	ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun,
	125	ctf_hash_free_fun key_free, ctf_hash_free_fun value_free)
	126	{
	127	ctf_dynhash_t *dynhash;
	128
	129	dynhash = malloc (sizeof (ctf_dynhash_t));
	130	if (!dynhash)
	131	return NULL;
	132
	133	/* 7 is arbitrary and untested for now.. */
	134	if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
	135	ctf_dynhash_item_free, xcalloc, free)) == NULL)
	136	{
	137	free (dynhash);
	138	return NULL;
	139	}
	140
	141	dynhash->key_free = key_free;
	142	dynhash->value_free = value_free;
	143
	144	return dynhash;
	145	}
	146
	147	static ctf_helem_t **
	148	ctf_hashtab_lookup (struct htab htab, const void key, enum insert_option insert)
	149	{
	150	ctf_helem_t tmp = { .key = (void *) key };
	151	return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert);
	152	}
	153
	154	static ctf_helem_t *
1820745a NA	155	ctf_hashtab_insert (struct htab htab, void key, void *value,
	156	ctf_hash_free_fun key_free,
	157	ctf_hash_free_fun value_free)
c0754cdd NA	158	{
	159	ctf_helem_t **slot;
	160
	161	slot = ctf_hashtab_lookup (htab, key, INSERT);
	162
	163	if (!slot)
	164	{
	165	errno = -ENOMEM;
	166	return NULL;
	167	}
	168
	169	if (!*slot)
	170	{
	171	*slot = malloc (sizeof (ctf_helem_t));
	172	if (!*slot)
	173	return NULL;
c0754cdd	174	}
1820745a NA	175	else
	176	{
	177	if (key_free)
	178	key_free ((*slot)->key);
	179	if (value_free)
	180	value_free ((*slot)->value);
	181	}
	182	(*slot)->key = key;
c0754cdd NA	183	(*slot)->value = value;
	184	return *slot;
	185	}
	186
	187	int
	188	ctf_dynhash_insert (ctf_dynhash_t hp, void key, void *value)
	189	{
	190	ctf_helem_t *slot;
	191
1820745a NA	192	slot = ctf_hashtab_insert (hp->htab, key, value,
1820745a NA	193	hp->key_free, hp->value_free);
c0754cdd NA	194
	195	if (!slot)
	196	return errno;
	197
	198	/* We need to keep the key_free and value_free around in each item because the
886453cb	199	del function has no visibility into the hash as a whole, only into the
c0754cdd NA	200	individual items. */
	201
	202	slot->key_free = hp->key_free;
	203	slot->value_free = hp->value_free;
	204
	205	return 0;
	206	}
	207
	208	void
	209	ctf_dynhash_remove (ctf_dynhash_t hp, const void key)
	210	{
3e10cffc NA	211	ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
3e10cffc NA	212	htab_remove_elt (hp->htab, &hep);
c0754cdd NA	213	}
c0754cdd NA	214
886453cb NA	215	void
	216	ctf_dynhash_empty (ctf_dynhash_t *hp)
	217	{
	218	htab_empty (hp->htab);
	219	}
	220
c0754cdd NA	221	void *
	222	ctf_dynhash_lookup (ctf_dynhash_t hp, const void key)
	223	{
	224	ctf_helem_t **slot;
	225
	226	slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT);
	227
	228	if (slot)
	229	return (*slot)->value;
	230
	231	return NULL;
	232	}
	233
9658dc39 NA	234	typedef struct ctf_traverse_cb_arg
	235	{
	236	ctf_hash_iter_f fun;
	237	void *arg;
	238	} ctf_traverse_cb_arg_t;
	239
	240	static int
	241	ctf_hashtab_traverse (void *slot, void arg_)
	242	{
	243	ctf_helem_t helem = ((ctf_helem_t **) slot);
	244	ctf_traverse_cb_arg_t arg = (ctf_traverse_cb_arg_t ) arg_;
	245
	246	arg->fun (helem->key, helem->value, arg->arg);
	247	return 1;
	248	}
	249
	250	void
	251	ctf_dynhash_iter (ctf_dynhash_t hp, ctf_hash_iter_f fun, void arg_)
	252	{
	253	ctf_traverse_cb_arg_t arg = { fun, arg_ };
	254	htab_traverse (hp->htab, ctf_hashtab_traverse, &arg);
	255	}
	256
	257	typedef struct ctf_traverse_remove_cb_arg
	258	{
	259	struct htab *htab;
	260	ctf_hash_iter_remove_f fun;
	261	void *arg;
	262	} ctf_traverse_remove_cb_arg_t;
	263
	264	static int
	265	ctf_hashtab_traverse_remove (void *slot, void arg_)
	266	{
	267	ctf_helem_t helem = ((ctf_helem_t **) slot);
	268	ctf_traverse_remove_cb_arg_t arg = (ctf_traverse_remove_cb_arg_t ) arg_;
	269
	270	if (arg->fun (helem->key, helem->value, arg->arg))
	271	htab_clear_slot (arg->htab, slot);
	272	return 1;
	273	}
	274
	275	void
	276	ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun,
	277	void *arg_)
	278	{
	279	ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ };
	280	htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg);
	281	}
	282
c0754cdd NA	283	void
	284	ctf_dynhash_destroy (ctf_dynhash_t *hp)
	285	{
	286	if (hp != NULL)
	287	htab_delete (hp->htab);
	288	free (hp);
	289	}
	290
	291	/* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
	292	removal. This is a straight cast of a hashtab. */
	293
	294	ctf_hash_t *
	295	ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun,
	296	ctf_hash_eq_fun eq_fun)
	297	{
	298	return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun,
	299	eq_fun, free, xcalloc, free);
	300	}
	301
	302	uint32_t
	303	ctf_hash_size (const ctf_hash_t *hp)
	304	{
	305	return htab_elements ((struct htab *) hp);
	306	}
	307
	308	int
	309	ctf_hash_insert_type (ctf_hash_t hp, ctf_file_t fp, uint32_t type,
	310	uint32_t name)
	311	{
d851ecd3	312	const char *str = ctf_strraw (fp, name);
c0754cdd NA	313
	314	if (type == 0)
	315	return EINVAL;
	316
d851ecd3 NA	317	if (str == NULL
	318	&& CTF_NAME_STID (name) == CTF_STRTAB_1
	319	&& fp->ctf_syn_ext_strtab == NULL
	320	&& fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL)
c0754cdd NA	321	return ECTF_STRTAB;
c0754cdd NA	322
d851ecd3	323	if (str == NULL)
c0754cdd NA	324	return ECTF_BADNAME;
	325
	326	if (str[0] == '\0')
	327	return 0; /* Just ignore empty strings on behalf of caller. */
	328
	329	if (ctf_hashtab_insert ((struct htab ) hp, (char ) str,
1820745a	330	(void *) (ptrdiff_t) type, NULL, NULL) != NULL)
c0754cdd NA	331	return 0;
	332	return errno;
	333	}
	334
	335	/* if the key is already in the hash, override the previous definition with
	336	this new official definition. If the key is not present, then call
	337	ctf_hash_insert_type() and hash it in. */
	338	int
	339	ctf_hash_define_type (ctf_hash_t hp, ctf_file_t fp, uint32_t type,
	340	uint32_t name)
	341	{
	342	/* This matches the semantics of ctf_hash_insert_type() in this
	343	implementation anyway. */
	344
	345	return ctf_hash_insert_type (hp, fp, type, name);
	346	}
	347
	348	ctf_id_t
	349	ctf_hash_lookup_type (ctf_hash_t hp, ctf_file_t fp __attribute__ ((__unused__)),
	350	const char *key)
	351	{
	352	ctf_helem_t **slot;
	353
	354	slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
	355
	356	if (slot)
	357	return (ctf_id_t) ((*slot)->value);
	358
	359	return 0;
	360	}
	361
	362	void
	363	ctf_hash_destroy (ctf_hash_t *hp)
	364	{
	365	if (hp != NULL)
	366	htab_delete ((struct htab *) hp);
	367	}