[thirdparty/gcc.git] / gcc / hash.h

/* Header file for generic hash table support.
   Copyright (C) 1993, 1994, 1997, 1998, 2001 Free Software Foundation, Inc.
   Written by Steve Chamberlain <sac@cygnus.com>

This file was lifted from BFD, the Binary File Descriptor library.

This program 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 of the License, 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; if not, write to the Free Software
Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#ifndef IN_GCC
#include <ansidecl.h>
#endif /* ! IN_GCC */

#include "obstack.h"

typedef PTR hash_table_key;

/* Hash table routines.  There is no way to free up a hash table.  */

/* An element in the hash table.  Most uses will actually use a larger
   structure, and an instance of this will be the first field.  */

struct hash_entry
{
  /* Next entry for this hash code.  */
  struct hash_entry *next;
  /* The thing being hashed.  */
  hash_table_key key;
  /* Hash code.  This is the full hash code, not the index into the
     table.  */
  unsigned long hash;
};

/* A hash table.  */

struct hash_table
{
  /* The hash array.  */
  struct hash_entry **table;
  /* The number of slots in the hash table.  */
  unsigned int size;
  /* A function used to create new elements in the hash table.  The
     first entry is itself a pointer to an element.  When this
     function is first invoked, this pointer will be NULL.  However,
     having the pointer permits a hierarchy of method functions to be
     built each of which calls the function in the superclass.  Thus
     each function should be written to allocate a new block of memory
     only if the argument is NULL.  */
  struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
					 struct hash_table *,
					 hash_table_key));
  /* A function to compute the hash code for a key in the hash table.  */
  unsigned long (*hash) PARAMS ((hash_table_key));
  /* A function to compare two keys.  */
  bool (*comp) PARAMS ((hash_table_key, hash_table_key));
  /* An obstack for this hash table.  */
  struct obstack memory;
};

/* Initialize a hash table.  */
extern void hash_table_init
  PARAMS ((struct hash_table *,
	   struct hash_entry *(*) (struct hash_entry *,
				   struct hash_table *,
				   hash_table_key),
	   unsigned long (*hash) (hash_table_key),
	   bool (*comp) (hash_table_key, hash_table_key)));

/* Initialize a hash table specifying a size.  */
extern void hash_table_init_n
  PARAMS ((struct hash_table *,
	   struct hash_entry *(*) (struct hash_entry *,
				   struct hash_table *,
				   hash_table_key),
	   unsigned long (*hash) (hash_table_key),
	   bool (*comp) (hash_table_key, hash_table_key),
	   unsigned int size));

/* Free up a hash table.  */
extern void hash_table_free PARAMS ((struct hash_table *));

/* Look up KEY in a hash table.  If CREATE is true, a new entry
   will be created for this KEY if one does not already exist.  If
   COPY is non-NULL, it is used to copy the KEY before storing it in
   the hash table.  */
extern struct hash_entry *hash_lookup
  PARAMS ((struct hash_table *, hash_table_key key, int create,
	   hash_table_key (*copy)(struct obstack*, hash_table_key)));

/* Base method for creating a hash table entry.  */
extern struct hash_entry *hash_newfunc
  PARAMS ((struct hash_entry *, struct hash_table *, 
	   hash_table_key key));

/* Grab some space for a hash table entry.  */
extern PTR hash_allocate PARAMS ((struct hash_table *,
				  unsigned int));

/* Traverse a hash table in a random order, calling a function on each
   element.  If the function returns false, the traversal stops.  The
   INFO argument is passed to the function.  */
extern void hash_traverse PARAMS ((struct hash_table *,
				   bool (*) (struct hash_entry *,
						hash_table_key),
				   hash_table_key info));

/* Hash a string K, which is really of type `char*'.  */
extern unsigned long string_hash PARAMS ((hash_table_key k));

/* Compare two strings K1, K2 which are really of type `char*'.  */
extern bool string_compare PARAMS ((hash_table_key k1, 
				       hash_table_key k2));

/* Copy a string K, which is really of type `char*'.  */
extern hash_table_key string_copy PARAMS ((struct obstack* memory,
					   hash_table_key k));
Commit	Line	Data
aa32d841	1	/* Header file for generic hash table support.
400500c4	2	Copyright (C) 1993, 1994, 1997, 1998, 2001 Free Software Foundation, Inc.
aa32d841 JL	3	Written by Steve Chamberlain <sac@cygnus.com>
	4
	5	This file was lifted from BFD, the Binary File Descriptor library.
	6
	7	This program is free software; you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 2 of the License, or
	10	(at your option) any later version.
	11
	12	This program is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with this program; if not, write to the Free Software
63fdf24a JL	19	Foundation, 59 Temple Place - Suite 330,
63fdf24a JL	20	Boston, MA 02111-1307, USA. */
aa32d841	21
5148a72b	22	#ifndef IN_GCC
aa32d841	23	#include <ansidecl.h>
5148a72b	24	#endif /* ! IN_GCC */
aa32d841 JL	25
	26	#include "obstack.h"
	27
a87ec9e6 MM	28	typedef PTR hash_table_key;
a87ec9e6 MM	29
aa32d841 JL	30	/* Hash table routines. There is no way to free up a hash table. */
	31
	32	/* An element in the hash table. Most uses will actually use a larger
	33	structure, and an instance of this will be the first field. */
	34
	35	struct hash_entry
	36	{
	37	/* Next entry for this hash code. */
	38	struct hash_entry *next;
a87ec9e6 MM	39	/* The thing being hashed. */
a87ec9e6 MM	40	hash_table_key key;
aa32d841 JL	41	/* Hash code. This is the full hash code, not the index into the
	42	table. */
	43	unsigned long hash;
	44	};
	45
	46	/* A hash table. */
	47
	48	struct hash_table
	49	{
	50	/* The hash array. */
	51	struct hash_entry **table;
	52	/* The number of slots in the hash table. */
	53	unsigned int size;
	54	/* A function used to create new elements in the hash table. The
	55	first entry is itself a pointer to an element. When this
	56	function is first invoked, this pointer will be NULL. However,
	57	having the pointer permits a hierarchy of method functions to be
	58	built each of which calls the function in the superclass. Thus
	59	each function should be written to allocate a new block of memory
	60	only if the argument is NULL. */
	61	struct hash_entry (newfunc) PARAMS ((struct hash_entry *,
	62	struct hash_table *,
a87ec9e6 MM	63	hash_table_key));
	64	/* A function to compute the hash code for a key in the hash table. */
	65	unsigned long (*hash) PARAMS ((hash_table_key));
	66	/* A function to compare two keys. */
d6edb99e	67	bool (*comp) PARAMS ((hash_table_key, hash_table_key));
aa32d841 JL	68	/* An obstack for this hash table. */
	69	struct obstack memory;
	70	};
	71
	72	/* Initialize a hash table. */
400500c4	73	extern void hash_table_init
aa32d841 JL	74	PARAMS ((struct hash_table *,
	75	struct hash_entry () (struct hash_entry *,
	76	struct hash_table *,
a87ec9e6 MM	77	hash_table_key),
a87ec9e6 MM	78	unsigned long (*hash) (hash_table_key),
d6edb99e	79	bool (*comp) (hash_table_key, hash_table_key)));
aa32d841 JL	80
aa32d841 JL	81	/* Initialize a hash table specifying a size. */
400500c4	82	extern void hash_table_init_n
aa32d841 JL	83	PARAMS ((struct hash_table *,
	84	struct hash_entry () (struct hash_entry *,
	85	struct hash_table *,
a87ec9e6 MM	86	hash_table_key),
a87ec9e6 MM	87	unsigned long (*hash) (hash_table_key),
d6edb99e	88	bool (*comp) (hash_table_key, hash_table_key),
aa32d841 JL	89	unsigned int size));
	90
	91	/* Free up a hash table. */
	92	extern void hash_table_free PARAMS ((struct hash_table *));
	93
a87ec9e6 MM	94	/* Look up KEY in a hash table. If CREATE is true, a new entry
	95	will be created for this KEY if one does not already exist. If
	96	COPY is non-NULL, it is used to copy the KEY before storing it in
	97	the hash table. */
aa32d841	98	extern struct hash_entry *hash_lookup
37a58036	99	PARAMS ((struct hash_table *, hash_table_key key, int create,
a87ec9e6	100	hash_table_key (copy)(struct obstack, hash_table_key)));
aa32d841 JL	101
	102	/* Base method for creating a hash table entry. */
	103	extern struct hash_entry *hash_newfunc
a87ec9e6 MM	104	PARAMS ((struct hash_entry , struct hash_table ,
a87ec9e6 MM	105	hash_table_key key));
aa32d841 JL	106
	107	/* Grab some space for a hash table entry. */
	108	extern PTR hash_allocate PARAMS ((struct hash_table *,
	109	unsigned int));
	110
	111	/* Traverse a hash table in a random order, calling a function on each
	112	element. If the function returns false, the traversal stops. The
	113	INFO argument is passed to the function. */
	114	extern void hash_traverse PARAMS ((struct hash_table *,
d6edb99e	115	bool () (struct hash_entry ,
a87ec9e6 MM	116	hash_table_key),
	117	hash_table_key info));
	118
	119	/* Hash a string K, which is really of type `char'. /
	120	extern unsigned long string_hash PARAMS ((hash_table_key k));
	121
	122	/* Compare two strings K1, K2 which are really of type `char'. /
d6edb99e	123	extern bool string_compare PARAMS ((hash_table_key k1,
a87ec9e6 MM	124	hash_table_key k2));
	125
	126	/* Copy a string K, which is really of type `char'. /
	127	extern hash_table_key string_copy PARAMS ((struct obstack* memory,
	128	hash_table_key k));
	129