[binutils.git] / gas / hash.c

/* hash.c -- gas hash table code
   Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
   2000, 2001, 2002
   Free Software Foundation, Inc.

   This file is part of GAS, the GNU Assembler.

   GAS 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 2, or (at your option)
   any later version.

   GAS 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 GAS; see the file COPYING.  If not, write to the Free
   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */

/* This version of the hash table code is a wholescale replacement of
   the old hash table code, which was fairly bad.  This is based on
   the hash table code in BFD, but optimized slightly for the
   asssembler.  The assembler does not need to derive structures that
   are stored in the hash table.  Instead, it always stores a pointer.
   The assembler uses the hash table mostly to store symbols, and we
   don't need to confuse the symbol structure with a hash table
   structure.  */

#include "as.h"
#include "safe-ctype.h"
#include "obstack.h"

/* The default number of entries to use when creating a hash table.  */

#define DEFAULT_SIZE (4051)

/* An entry in a hash table.  */

struct hash_entry {
  /* Next entry for this hash code.  */
  struct hash_entry *next;
  /* String being hashed.  */
  const char *string;
  /* Hash code.  This is the full hash code, not the index into the
     table.  */
  unsigned long hash;
  /* Pointer being stored in the hash table.  */
  PTR data;
};

/* A hash table.  */

struct hash_control {
  /* The hash array.  */
  struct hash_entry **table;
  /* The number of slots in the hash table.  */
  unsigned int size;
  /* An obstack for this hash table.  */
  struct obstack memory;

#ifdef HASH_STATISTICS
  /* Statistics.  */
  unsigned long lookups;
  unsigned long hash_compares;
  unsigned long string_compares;
  unsigned long insertions;
  unsigned long replacements;
  unsigned long deletions;
#endif /* HASH_STATISTICS */
};

/* Create a hash table.  This return a control block.  */

struct hash_control *
hash_new ()
{
  unsigned int size;
  struct hash_control *ret;
  unsigned int alloc;

  size = DEFAULT_SIZE;

  ret = (struct hash_control *) xmalloc (sizeof *ret);
  obstack_begin (&ret->memory, chunksize);
  alloc = size * sizeof (struct hash_entry *);
  ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  memset (ret->table, 0, alloc);
  ret->size = size;

#ifdef HASH_STATISTICS
  ret->lookups = 0;
  ret->hash_compares = 0;
  ret->string_compares = 0;
  ret->insertions = 0;
  ret->replacements = 0;
  ret->deletions = 0;
#endif

  return ret;
}

/* Delete a hash table, freeing all allocated memory.  */

void
hash_die (table)
     struct hash_control *table;
{
  obstack_free (&table->memory, 0);
  free (table);
}

/* Look up a string in a hash table.  This returns a pointer to the
   hash_entry, or NULL if the string is not in the table.  If PLIST is
   not NULL, this sets *PLIST to point to the start of the list which
   would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
   to the hash code for KEY.

   Each time we look up a string, we move it to the start of the list
   for its hash code, to take advantage of referential locality.  */

static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
					       const char *,
					       struct hash_entry ***,
					       unsigned long *));

static struct hash_entry *
hash_lookup (table, key, plist, phash)
     struct hash_control *table;
     const char *key;
     struct hash_entry ***plist;
     unsigned long *phash;
{
  register unsigned long hash;
  unsigned int len;
  register const unsigned char *s;
  register unsigned int c;
  unsigned int index;
  struct hash_entry **list;
  struct hash_entry *p;
  struct hash_entry *prev;

#ifdef HASH_STATISTICS
  ++table->lookups;
#endif

  hash = 0;
  len = 0;
  s = (const unsigned char *) key;
  while ((c = *s++) != '\0')
    {
      hash += c + (c << 17);
      hash ^= hash >> 2;
      ++len;
    }
  hash += len + (len << 17);
  hash ^= hash >> 2;

  if (phash != NULL)
    *phash = hash;

  index = hash % table->size;
  list = table->table + index;

  if (plist != NULL)
    *plist = list;

  prev = NULL;
  for (p = *list; p != NULL; p = p->next)
    {
#ifdef HASH_STATISTICS
      ++table->hash_compares;
#endif

      if (p->hash == hash)
	{
#ifdef HASH_STATISTICS
	  ++table->string_compares;
#endif

	  if (strcmp (p->string, key) == 0)
	    {
	      if (prev != NULL)
		{
		  prev->next = p->next;
		  p->next = *list;
		  *list = p;
		}

	      return p;
	    }
	}

      prev = p;
    }

  return NULL;
}

/* Insert an entry into a hash table.  This returns NULL on success.
   On error, it returns a printable string indicating the error.  It
   is considered to be an error if the entry already exists in the
   hash table.  */

const char *
hash_insert (table, key, value)
     struct hash_control *table;
     const char *key;
     PTR value;
{
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;

  p = hash_lookup (table, key, &list, &hash);
  if (p != NULL)
    return "exists";

#ifdef HASH_STATISTICS
  ++table->insertions;
#endif

  p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
  p->string = key;
  p->hash = hash;
  p->data = value;

  p->next = *list;
  *list = p;

  return NULL;
}

/* Insert or replace an entry in a hash table.  This returns NULL on
   success.  On error, it returns a printable string indicating the
   error.  If an entry already exists, its value is replaced.  */

const char *
hash_jam (table, key, value)
     struct hash_control *table;
     const char *key;
     PTR value;
{
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;

  p = hash_lookup (table, key, &list, &hash);
  if (p != NULL)
    {
#ifdef HASH_STATISTICS
      ++table->replacements;
#endif

      p->data = value;
    }
  else
    {
#ifdef HASH_STATISTICS
      ++table->insertions;
#endif

      p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
      p->string = key;
      p->hash = hash;
      p->data = value;

      p->next = *list;
      *list = p;
    }

  return NULL;
}

/* Replace an existing entry in a hash table.  This returns the old
   value stored for the entry.  If the entry is not found in the hash
   table, this does nothing and returns NULL.  */

PTR
hash_replace (table, key, value)
     struct hash_control *table;
     const char *key;
     PTR value;
{
  struct hash_entry *p;
  PTR ret;

  p = hash_lookup (table, key, NULL, NULL);
  if (p == NULL)
    return NULL;

#ifdef HASH_STATISTICS
  ++table->replacements;
#endif

  ret = p->data;

  p->data = value;

  return ret;
}

/* Find an entry in a hash table, returning its value.  Returns NULL
   if the entry is not found.  */

PTR
hash_find (table, key)
     struct hash_control *table;
     const char *key;
{
  struct hash_entry *p;

  p = hash_lookup (table, key, NULL, NULL);
  if (p == NULL)
    return NULL;

  return p->data;
}

/* Delete an entry from a hash table.  This returns the value stored
   for that entry, or NULL if there is no such entry.  */

PTR
hash_delete (table, key)
     struct hash_control *table;
     const char *key;
{
  struct hash_entry *p;
  struct hash_entry **list;

  p = hash_lookup (table, key, &list, NULL);
  if (p == NULL)
    return NULL;

  if (p != *list)
    abort ();

#ifdef HASH_STATISTICS
  ++table->deletions;
#endif

  *list = p->next;

  /* Note that we never reclaim the memory for this entry.  If gas
     ever starts deleting hash table entries in a big way, this will
     have to change.  */

  return p->data;
}

/* Traverse a hash table.  Call the function on every entry in the
   hash table.  */

void
hash_traverse (table, pfn)
     struct hash_control *table;
     void (*pfn) PARAMS ((const char *key, PTR value));
{
  unsigned int i;

  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;

      for (p = table->table[i]; p != NULL; p = p->next)
	(*pfn) (p->string, p->data);
    }
}

/* Print hash table statistics on the specified file.  NAME is the
   name of the hash table, used for printing a header.  */

void
hash_print_statistics (f, name, table)
     FILE *f ATTRIBUTE_UNUSED;
     const char *name ATTRIBUTE_UNUSED;
     struct hash_control *table ATTRIBUTE_UNUSED;
{
#ifdef HASH_STATISTICS
  unsigned int i;
  unsigned long total;
  unsigned long empty;

  fprintf (f, "%s hash statistics:\n", name);
  fprintf (f, "\t%lu lookups\n", table->lookups);
  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
  fprintf (f, "\t%lu insertions\n", table->insertions);
  fprintf (f, "\t%lu replacements\n", table->replacements);
  fprintf (f, "\t%lu deletions\n", table->deletions);

  total = 0;
  empty = 0;
  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;

      if (table->table[i] == NULL)
	++empty;
      else
	{
	  for (p = table->table[i]; p != NULL; p = p->next)
	    ++total;
	}
    }

  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
  fprintf (f, "\t%lu empty slots\n", empty);
#endif
}
\f
#ifdef TEST

/* This test program is left over from the old hash table code.  */

/* Number of hash tables to maintain (at once) in any testing.  */
#define TABLES (6)

/* We can have 12 statistics.  */
#define STATBUFSIZE (12)

/* Display statistics here.  */
int statbuf[STATBUFSIZE];

/* Human farts here.  */
char answer[100];

/* We test many hash tables at once.  */
char *hashtable[TABLES];

/* Points to curent hash_control.  */
char *h;
char **pp;
char *p;
char *name;
char *value;
int size;
int used;
char command;

/* Number 0:TABLES-1 of current hashed symbol table.  */
int number;

int
main ()
{
  void applicatee ();
  void destroy ();
  char *what ();
  int *ip;

  number = 0;
  h = 0;
  printf ("type h <RETURN> for help\n");
  for (;;)
    {
      printf ("hash_test command: ");
      gets (answer);
      command = answer[0];
      command = TOLOWER (command);	/* Ecch!  */
      switch (command)
	{
	case '#':
	  printf ("old hash table #=%d.\n", number);
	  whattable ();
	  break;
	case '?':
	  for (pp = hashtable; pp < hashtable + TABLES; pp++)
	    {
	      printf ("address of hash table #%d control block is %xx\n",
		      pp - hashtable, *pp);
	    }
	  break;
	case 'a':
	  hash_traverse (h, applicatee);
	  break;
	case 'd':
	  hash_traverse (h, destroy);
	  hash_die (h);
	  break;
	case 'f':
	  p = hash_find (h, name = what ("symbol"));
	  printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
	  break;
	case 'h':
	  printf ("# show old, select new default hash table number\n");
	  printf ("? display all hashtable control block addresses\n");
	  printf ("a apply a simple display-er to each symbol in table\n");
	  printf ("d die: destroy hashtable\n");
	  printf ("f find value of nominated symbol\n");
	  printf ("h this help\n");
	  printf ("i insert value into symbol\n");
	  printf ("j jam value into symbol\n");
	  printf ("n new hashtable\n");
	  printf ("r replace a value with another\n");
	  printf ("s say what %% of table is used\n");
	  printf ("q exit this program\n");
	  printf ("x delete a symbol from table, report its value\n");
	  break;
	case 'i':
	  p = hash_insert (h, name = what ("symbol"), value = what ("value"));
	  if (p)
	    {
	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
		      p);
	    }
	  break;
	case 'j':
	  p = hash_jam (h, name = what ("symbol"), value = what ("value"));
	  if (p)
	    {
	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
	    }
	  break;
	case 'n':
	  h = hashtable[number] = (char *) hash_new ();
	  break;
	case 'q':
	  exit (EXIT_SUCCESS);
	case 'r':
	  p = hash_replace (h, name = what ("symbol"), value = what ("value"));
	  printf ("old value was \"%s\"\n", p ? p : "{}");
	  break;
	case 's':
	  hash_say (h, statbuf, STATBUFSIZE);
	  for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
	    {
	      printf ("%d ", *ip);
	    }
	  printf ("\n");
	  break;
	case 'x':
	  p = hash_delete (h, name = what ("symbol"));
	  printf ("old value was \"%s\"\n", p ? p : "{}");
	  break;
	default:
	  printf ("I can't understand command \"%c\"\n", command);
	  break;
	}
    }
}

char *
what (description)
     char *description;
{
  printf ("   %s : ", description);
  gets (answer);
  return xstrdup (answer);
}

void
destroy (string, value)
     char *string;
     char *value;
{
  free (string);
  free (value);
}

void
applicatee (string, value)
     char *string;
     char *value;
{
  printf ("%.20s-%.20s\n", string, value);
}

/* Determine number: what hash table to use.
   Also determine h: points to hash_control.  */

void
whattable ()
{
  for (;;)
    {
      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
      gets (answer);
      sscanf (answer, "%d", &number);
      if (number >= 0 && number < TABLES)
	{
	  h = hashtable[number];
	  if (!h)
	    {
	      printf ("warning: current hash-table-#%d. has no hash-control\n", number);
	    }
	  return;
	}
      else
	{
	  printf ("invalid hash table number: %d\n", number);
	}
    }
}

#endif /* TEST */
Commit	Line	Data
54d22525	1	/* hash.c -- gas hash table code
f7e42eb4	2	Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
a2c36061	3	2000, 2001, 2002
252b5132 RH	4	Free Software Foundation, Inc.
	5
	6	This file is part of GAS, the GNU Assembler.
	7
	8	GAS is free software; you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 2, or (at your option)
	11	any later version.
	12
	13	GAS is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
54d22525 ILT	19	along with GAS; see the file COPYING. If not, write to the Free
	20	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	21	02111-1307, USA. */
	22
	23	/* This version of the hash table code is a wholescale replacement of
	24	the old hash table code, which was fairly bad. This is based on
	25	the hash table code in BFD, but optimized slightly for the
	26	asssembler. The assembler does not need to derive structures that
	27	are stored in the hash table. Instead, it always stores a pointer.
	28	The assembler uses the hash table mostly to store symbols, and we
	29	don't need to confuse the symbol structure with a hash table
	30	structure. */
252b5132 RH	31
252b5132 RH	32	#include "as.h"
3882b010	33	#include "safe-ctype.h"
54d22525	34	#include "obstack.h"
252b5132	35
54d22525	36	/* The default number of entries to use when creating a hash table. */
252b5132	37
54d22525	38	#define DEFAULT_SIZE (4051)
252b5132	39
54d22525	40	/* An entry in a hash table. */
252b5132	41
b041f888	42	struct hash_entry {
54d22525 ILT	43	/* Next entry for this hash code. */
	44	struct hash_entry *next;
	45	/* String being hashed. */
	46	const char *string;
	47	/* Hash code. This is the full hash code, not the index into the
	48	table. */
	49	unsigned long hash;
	50	/* Pointer being stored in the hash table. */
	51	PTR data;
252b5132 RH	52	};
252b5132 RH	53
54d22525 ILT	54	/* A hash table. */
54d22525 ILT	55
b041f888	56	struct hash_control {
54d22525 ILT	57	/* The hash array. */
	58	struct hash_entry **table;
	59	/* The number of slots in the hash table. */
	60	unsigned int size;
	61	/* An obstack for this hash table. */
	62	struct obstack memory;
	63
	64	#ifdef HASH_STATISTICS
	65	/* Statistics. */
	66	unsigned long lookups;
	67	unsigned long hash_compares;
	68	unsigned long string_compares;
	69	unsigned long insertions;
	70	unsigned long replacements;
	71	unsigned long deletions;
	72	#endif /* HASH_STATISTICS */
252b5132	73	};
54d22525 ILT	74
	75	/* Create a hash table. This return a control block. */
	76
252b5132 RH	77	struct hash_control *
	78	hash_new ()
	79	{
54d22525 ILT	80	unsigned int size;
	81	struct hash_control *ret;
	82	unsigned int alloc;
	83
	84	size = DEFAULT_SIZE;
	85
	86	ret = (struct hash_control ) xmalloc (sizeof ret);
	87	obstack_begin (&ret->memory, chunksize);
	88	alloc = size * sizeof (struct hash_entry *);
	89	ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
	90	memset (ret->table, 0, alloc);
	91	ret->size = size;
	92
	93	#ifdef HASH_STATISTICS
	94	ret->lookups = 0;
	95	ret->hash_compares = 0;
	96	ret->string_compares = 0;
	97	ret->insertions = 0;
	98	ret->replacements = 0;
	99	ret->deletions = 0;
	100	#endif
	101
8fc2faa7	102	return ret;
252b5132 RH	103	}
252b5132 RH	104
54d22525 ILT	105	/* Delete a hash table, freeing all allocated memory. */
54d22525 ILT	106
252b5132	107	void
54d22525 ILT	108	hash_die (table)
54d22525 ILT	109	struct hash_control *table;
252b5132	110	{
54d22525 ILT	111	obstack_free (&table->memory, 0);
54d22525 ILT	112	free (table);
252b5132	113	}
54d22525 ILT	114
	115	/* Look up a string in a hash table. This returns a pointer to the
	116	hash_entry, or NULL if the string is not in the table. If PLIST is
	117	not NULL, this sets *PLIST to point to the start of the list which
	118	would hold this hash entry. If PHASH is not NULL, this sets *PHASH
	119	to the hash code for KEY.
	120
	121	Each time we look up a string, we move it to the start of the list
	122	for its hash code, to take advantage of referential locality. */
	123
	124	static struct hash_entry hash_lookup PARAMS ((struct hash_control ,
	125	const char *,
	126	struct hash_entry ***,
	127	unsigned long *));
	128
	129	static struct hash_entry *
	130	hash_lookup (table, key, plist, phash)
	131	struct hash_control *table;
	132	const char *key;
	133	struct hash_entry ***plist;
	134	unsigned long *phash;
252b5132	135	{
54d22525 ILT	136	register unsigned long hash;
	137	unsigned int len;
	138	register const unsigned char *s;
	139	register unsigned int c;
	140	unsigned int index;
	141	struct hash_entry **list;
	142	struct hash_entry *p;
	143	struct hash_entry *prev;
	144
	145	#ifdef HASH_STATISTICS
	146	++table->lookups;
	147	#endif
252b5132	148
54d22525 ILT	149	hash = 0;
	150	len = 0;
	151	s = (const unsigned char *) key;
	152	while ((c = *s++) != '\0')
252b5132	153	{
54d22525 ILT	154	hash += c + (c << 17);
	155	hash ^= hash >> 2;
	156	++len;
252b5132	157	}
54d22525 ILT	158	hash += len + (len << 17);
	159	hash ^= hash >> 2;
	160
	161	if (phash != NULL)
	162	*phash = hash;
	163
	164	index = hash % table->size;
	165	list = table->table + index;
252b5132	166
54d22525 ILT	167	if (plist != NULL)
	168	*plist = list;
	169
	170	prev = NULL;
	171	for (p = *list; p != NULL; p = p->next)
252b5132	172	{
54d22525 ILT	173	#ifdef HASH_STATISTICS
	174	++table->hash_compares;
	175	#endif
	176
	177	if (p->hash == hash)
252b5132	178	{
54d22525 ILT	179	#ifdef HASH_STATISTICS
	180	++table->string_compares;
	181	#endif
	182
	183	if (strcmp (p->string, key) == 0)
	184	{
	185	if (prev != NULL)
	186	{
	187	prev->next = p->next;
	188	p->next = *list;
	189	*list = p;
	190	}
	191
	192	return p;
	193	}
252b5132	194	}
252b5132	195
54d22525	196	prev = p;
252b5132	197	}
54d22525 ILT	198
54d22525 ILT	199	return NULL;
252b5132	200	}
54d22525 ILT	201
	202	/* Insert an entry into a hash table. This returns NULL on success.
	203	On error, it returns a printable string indicating the error. It
	204	is considered to be an error if the entry already exists in the
	205	hash table. */
	206
	207	const char *
	208	hash_insert (table, key, value)
	209	struct hash_control *table;
	210	const char *key;
252b5132 RH	211	PTR value;
252b5132 RH	212	{
54d22525 ILT	213	struct hash_entry *p;
	214	struct hash_entry **list;
	215	unsigned long hash;
252b5132	216
54d22525 ILT	217	p = hash_lookup (table, key, &list, &hash);
	218	if (p != NULL)
	219	return "exists";
	220
	221	#ifdef HASH_STATISTICS
	222	++table->insertions;
	223	#endif
	224
8fc2faa7	225	p = (struct hash_entry ) obstack_alloc (&table->memory, sizeof (p));
54d22525 ILT	226	p->string = key;
	227	p->hash = hash;
	228	p->data = value;
	229
	230	p->next = *list;
	231	*list = p;
	232
	233	return NULL;
252b5132	234	}
54d22525 ILT	235
	236	/* Insert or replace an entry in a hash table. This returns NULL on
	237	success. On error, it returns a printable string indicating the
	238	error. If an entry already exists, its value is replaced. */
	239
252b5132	240	const char *
54d22525 ILT	241	hash_jam (table, key, value)
	242	struct hash_control *table;
	243	const char *key;
252b5132 RH	244	PTR value;
252b5132 RH	245	{
54d22525 ILT	246	struct hash_entry *p;
	247	struct hash_entry **list;
	248	unsigned long hash;
252b5132	249
54d22525 ILT	250	p = hash_lookup (table, key, &list, &hash);
54d22525 ILT	251	if (p != NULL)
252b5132	252	{
54d22525 ILT	253	#ifdef HASH_STATISTICS
	254	++table->replacements;
	255	#endif
	256
	257	p->data = value;
252b5132	258	}
54d22525	259	else
252b5132	260	{
54d22525 ILT	261	#ifdef HASH_STATISTICS
	262	++table->insertions;
	263	#endif
	264
8fc2faa7	265	p = (struct hash_entry ) obstack_alloc (&table->memory, sizeof (p));
54d22525 ILT	266	p->string = key;
	267	p->hash = hash;
	268	p->data = value;
	269
	270	p->next = *list;
	271	*list = p;
252b5132	272	}
54d22525 ILT	273
54d22525 ILT	274	return NULL;
252b5132 RH	275	}
252b5132 RH	276
54d22525 ILT	277	/* Replace an existing entry in a hash table. This returns the old
	278	value stored for the entry. If the entry is not found in the hash
	279	table, this does nothing and returns NULL. */
	280
	281	PTR
	282	hash_replace (table, key, value)
	283	struct hash_control *table;
	284	const char *key;
	285	PTR value;
252b5132	286	{
54d22525 ILT	287	struct hash_entry *p;
54d22525 ILT	288	PTR ret;
252b5132	289
54d22525 ILT	290	p = hash_lookup (table, key, NULL, NULL);
	291	if (p == NULL)
	292	return NULL;
	293
	294	#ifdef HASH_STATISTICS
	295	++table->replacements;
252b5132 RH	296	#endif
252b5132 RH	297
54d22525	298	ret = p->data;
252b5132	299
54d22525	300	p->data = value;
252b5132	301
54d22525	302	return ret;
252b5132	303	}
54d22525 ILT	304
	305	/* Find an entry in a hash table, returning its value. Returns NULL
	306	if the entry is not found. */
	307
252b5132	308	PTR
54d22525 ILT	309	hash_find (table, key)
	310	struct hash_control *table;
	311	const char *key;
252b5132	312	{
54d22525	313	struct hash_entry *p;
252b5132	314
54d22525 ILT	315	p = hash_lookup (table, key, NULL, NULL);
54d22525 ILT	316	if (p == NULL)
252b5132	317	return NULL;
54d22525 ILT	318
54d22525 ILT	319	return p->data;
252b5132	320	}
54d22525 ILT	321
	322	/* Delete an entry from a hash table. This returns the value stored
	323	for that entry, or NULL if there is no such entry. */
	324
	325	PTR
	326	hash_delete (table, key)
	327	struct hash_control *table;
	328	const char *key;
252b5132	329	{
54d22525 ILT	330	struct hash_entry *p;
	331	struct hash_entry **list;
	332
	333	p = hash_lookup (table, key, &list, NULL);
	334	if (p == NULL)
	335	return NULL;
	336
	337	if (p != *list)
	338	abort ();
	339
	340	#ifdef HASH_STATISTICS
	341	++table->deletions;
252b5132	342	#endif
54d22525 ILT	343
	344	*list = p->next;
	345
	346	/* Note that we never reclaim the memory for this entry. If gas
	347	ever starts deleting hash table entries in a big way, this will
	348	have to change. */
	349
	350	return p->data;
252b5132	351	}
54d22525 ILT	352
	353	/* Traverse a hash table. Call the function on every entry in the
	354	hash table. */
	355
252b5132	356	void
54d22525 ILT	357	hash_traverse (table, pfn)
	358	struct hash_control *table;
	359	void (pfn) PARAMS ((const char key, PTR value));
252b5132	360	{
54d22525	361	unsigned int i;
252b5132	362
54d22525 ILT	363	for (i = 0; i < table->size; ++i)
	364	{
	365	struct hash_entry *p;
252b5132	366
54d22525 ILT	367	for (p = table->table[i]; p != NULL; p = p->next)
	368	(*pfn) (p->string, p->data);
	369	}
	370	}
252b5132	371
54d22525 ILT	372	/* Print hash table statistics on the specified file. NAME is the
54d22525 ILT	373	name of the hash table, used for printing a header. */
252b5132	374
54d22525 ILT	375	void
54d22525 ILT	376	hash_print_statistics (f, name, table)
ab9da554 ILT	377	FILE *f ATTRIBUTE_UNUSED;
	378	const char *name ATTRIBUTE_UNUSED;
	379	struct hash_control *table ATTRIBUTE_UNUSED;
54d22525 ILT	380	{
	381	#ifdef HASH_STATISTICS
	382	unsigned int i;
	383	unsigned long total;
	384	unsigned long empty;
	385
	386	fprintf (f, "%s hash statistics:\n", name);
	387	fprintf (f, "\t%lu lookups\n", table->lookups);
	388	fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
	389	fprintf (f, "\t%lu string comparisons\n", table->string_compares);
	390	fprintf (f, "\t%lu insertions\n", table->insertions);
	391	fprintf (f, "\t%lu replacements\n", table->replacements);
	392	fprintf (f, "\t%lu deletions\n", table->deletions);
	393
	394	total = 0;
	395	empty = 0;
	396	for (i = 0; i < table->size; ++i)
	397	{
	398	struct hash_entry *p;
252b5132	399
54d22525 ILT	400	if (table->table[i] == NULL)
	401	++empty;
	402	else
	403	{
	404	for (p = table->table[i]; p != NULL; p = p->next)
	405	++total;
	406	}
	407	}
252b5132	408
54d22525 ILT	409	fprintf (f, "\t%g average chain length\n", (double) total / table->size);
	410	fprintf (f, "\t%lu empty slots\n", empty);
	411	#endif
252b5132 RH	412	}
252b5132 RH	413	\f
252b5132 RH	414	#ifdef TEST
252b5132 RH	415
54d22525 ILT	416	/* This test program is left over from the old hash table code. */
54d22525 ILT	417
8fc2faa7 KH	418	/* Number of hash tables to maintain (at once) in any testing. */
	419	#define TABLES (6)
	420
	421	/* We can have 12 statistics. */
	422	#define STATBUFSIZE (12)
	423
	424	/* Display statistics here. */
	425	int statbuf[STATBUFSIZE];
	426
	427	/* Human farts here. */
	428	char answer[100];
	429
	430	/* We test many hash tables at once. */
	431	char *hashtable[TABLES];
252b5132	432
8fc2faa7 KH	433	/* Points to curent hash_control. */
8fc2faa7 KH	434	char *h;
252b5132 RH	435	char **pp;
	436	char *p;
	437	char *name;
	438	char *value;
	439	int size;
	440	int used;
	441	char command;
8fc2faa7 KH	442
	443	/* Number 0:TABLES-1 of current hashed symbol table. */
	444	int number;
252b5132	445
54d22525	446	int
252b5132 RH	447	main ()
	448	{
	449	void applicatee ();
	450	void destroy ();
	451	char *what ();
	452	int *ip;
	453
	454	number = 0;
	455	h = 0;
	456	printf ("type h <RETURN> for help\n");
	457	for (;;)
	458	{
	459	printf ("hash_test command: ");
	460	gets (answer);
	461	command = answer[0];
3882b010	462	command = TOLOWER (command); /* Ecch! */
252b5132 RH	463	switch (command)
	464	{
	465	case '#':
	466	printf ("old hash table #=%d.\n", number);
	467	whattable ();
	468	break;
	469	case '?':
	470	for (pp = hashtable; pp < hashtable + TABLES; pp++)
	471	{
8fc2faa7 KH	472	printf ("address of hash table #%d control block is %xx\n",
8fc2faa7 KH	473	pp - hashtable, *pp);
252b5132 RH	474	}
	475	break;
	476	case 'a':
54d22525	477	hash_traverse (h, applicatee);
252b5132 RH	478	break;
252b5132 RH	479	case 'd':
54d22525	480	hash_traverse (h, destroy);
252b5132 RH	481	hash_die (h);
	482	break;
	483	case 'f':
	484	p = hash_find (h, name = what ("symbol"));
	485	printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
	486	break;
	487	case 'h':
	488	printf ("# show old, select new default hash table number\n");
	489	printf ("? display all hashtable control block addresses\n");
	490	printf ("a apply a simple display-er to each symbol in table\n");
	491	printf ("d die: destroy hashtable\n");
	492	printf ("f find value of nominated symbol\n");
	493	printf ("h this help\n");
	494	printf ("i insert value into symbol\n");
	495	printf ("j jam value into symbol\n");
	496	printf ("n new hashtable\n");
	497	printf ("r replace a value with another\n");
	498	printf ("s say what %% of table is used\n");
	499	printf ("q exit this program\n");
	500	printf ("x delete a symbol from table, report its value\n");
	501	break;
	502	case 'i':
	503	p = hash_insert (h, name = what ("symbol"), value = what ("value"));
	504	if (p)
	505	{
	506	printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
	507	p);
	508	}
	509	break;
	510	case 'j':
	511	p = hash_jam (h, name = what ("symbol"), value = what ("value"));
	512	if (p)
	513	{
	514	printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
	515	}
	516	break;
	517	case 'n':
	518	h = hashtable[number] = (char *) hash_new ();
	519	break;
	520	case 'q':
	521	exit (EXIT_SUCCESS);
	522	case 'r':
	523	p = hash_replace (h, name = what ("symbol"), value = what ("value"));
	524	printf ("old value was \"%s\"\n", p ? p : "{}");
	525	break;
	526	case 's':
	527	hash_say (h, statbuf, STATBUFSIZE);
	528	for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
	529	{
	530	printf ("%d ", *ip);
	531	}
	532	printf ("\n");
	533	break;
	534	case 'x':
	535	p = hash_delete (h, name = what ("symbol"));
	536	printf ("old value was \"%s\"\n", p ? p : "{}");
	537	break;
	538	default:
	539	printf ("I can't understand command \"%c\"\n", command);
	540	break;
	541	}
	542	}
	543	}
	544
545	char *
546	what (description)
547	char *description;
548	{
252b5132 RH	549	printf (" %s : ", description);
252b5132 RH	550	gets (answer);
a2c36061	551	return xstrdup (answer);
252b5132 RH	552	}
	553
	554	void
	555	destroy (string, value)
	556	char *string;
	557	char *value;
	558	{
	559	free (string);
	560	free (value);
	561	}
	562
252b5132 RH	563	void
	564	applicatee (string, value)
	565	char *string;
	566	char *value;
	567	{
	568	printf ("%.20s-%.20s\n", string, value);
	569	}
	570
8fc2faa7 KH	571	/* Determine number: what hash table to use.
	572	Also determine h: points to hash_control. */
	573
54d22525	574	void
8fc2faa7	575	whattable ()
252b5132	576	{
252b5132 RH	577	for (;;)
	578	{
	579	printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
	580	gets (answer);
	581	sscanf (answer, "%d", &number);
	582	if (number >= 0 && number < TABLES)
	583	{
	584	h = hashtable[number];
	585	if (!h)
	586	{
	587	printf ("warning: current hash-table-#%d. has no hash-control\n", number);
	588	}
	589	return;
	590	}
	591	else
	592	{
	593	printf ("invalid hash table number: %d\n", number);
	594	}
	595	}
	596	}
	597
8fc2faa7	598	#endif /* TEST */