1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/* Header file for generic hash table support.
Copyright (C) 1993, 94 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, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
#ifndef IN_GCC
#include <ansidecl.h>
#endif /* ! IN_GCC */
#include "obstack.h"
typedef enum {false, true} boolean;
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. */
boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
/* An obstack for this hash table. */
struct obstack memory;
};
/* Initialize a hash table. */
extern boolean 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),
boolean (*comp) (hash_table_key, hash_table_key)));
/* Initialize a hash table specifying a size. */
extern boolean 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),
boolean (*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, boolean 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 *,
boolean (*) (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 boolean 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));
|
