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