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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#ifndef HASH_H
# define HASH_H 1
# if HAVE_CONFIG_H
# include <config.h>
# endif
# include <stdio.h>
# include <assert.h>
# ifdef STDC_HEADERS
# include <stdlib.h>
# else
void free ();
char *malloc ();
# endif
# define USE_OBSTACK
# ifdef USE_OBSTACK
# include "obstack.h"
# endif
# define obstack_chunk_alloc malloc
# define obstack_chunk_free free
struct hash_ent
{
void *key;
struct hash_ent *next;
};
typedef struct hash_ent HASH_ENT;
/* This is particularly useful to cast uses in hash_initialize of the
system free function. */
typedef void (*Hash_key_freer_type) (void *key);
struct HT
{
/* User-supplied function for freeing keys. It is specified in
hash_initialize. If non-null, it is used by hash_free and
hash_clear. You should specify `free' here only if you want
these functions to free all of your `key' data. This is typically
the case when your key is simply an auxilliary struct that you
have malloc'd to aggregate several values. */
Hash_key_freer_type hash_key_freer;
/* User-supplied hash function that hashes entry E to an integer
in the range 0..TABLE_SIZE-1. */
unsigned int (*hash_hash) (const void *e, unsigned int table_size);
/* User-supplied function that determines whether a new entry is
unique by comparing the new entry to entries that hashed to the
same bucket index. It should return zero for a pair of entries
that compare equal, non-zero otherwise. */
int (*hash_key_comparator) (const void *, const void *);
HASH_ENT **hash_table;
unsigned int hash_table_size;
unsigned int hash_n_slots_used;
unsigned int hash_max_chain_length;
/* Gets set when an entry is deleted from a chain of length
hash_max_chain_length. Indicates that hash_max_chain_length
may no longer be valid. */
unsigned int hash_dirty_max_chain_length;
/* Sum of lengths of all chains (not counting any dummy
header entries). */
unsigned int hash_n_keys;
/* A linked list of freed HASH_ENT structs.
FIXME: Perhaps this is unnecessary and we should simply free
and reallocate such structs. */
HASH_ENT *hash_free_entry_list;
/* FIXME: comment. */
# ifdef USE_OBSTACK
struct obstack ht_obstack;
# endif
};
typedef struct HT HT;
unsigned int
hash_get_n_slots_used (const HT *ht);
unsigned int
hash_get_max_chain_length (HT *ht);
int
hash_rehash (HT *ht, unsigned int new_table_size);
unsigned int
hash_get_table_size (const HT *ht);
HT *
hash_initialize (unsigned int table_size,
void (*key_freer) (void *key),
unsigned int (*hash) (const void *, unsigned int),
int (*equality_tester) (const void *, const void *));
unsigned int
hash_get_n_keys (const HT *ht);
int
hash_query_in_table (const HT *ht, const void *e);
void *
hash_lookup (const HT *ht, const void *e);
void *
hash_insert_if_absent (HT *ht, const void *e, int *failed);
void *
hash_delete_if_present (HT *ht, const void *e);
void
hash_print_statistics (const HT *ht, FILE *stream);
int
hash_get_statistics (const HT *ht, unsigned int *n_slots_used,
unsigned int *n_keys,
unsigned int *max_chain_length);
int
hash_table_ok (HT *ht);
void
hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux);
int
hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux);
int
hash_do_for_each_in_selected_bucket (HT *ht, const void *key,
int (*f) (const void *bucket_key,
void *e, void *aux),
void *aux);
void
hash_clear (HT *ht);
void
hash_free (HT *ht);
void
hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf);
void *
hash_get_first (const HT *ht);
void *
hash_get_next (const HT *ht, const void *e);
/* This interface to hash_insert_if_absent is used frequently enough to
merit a macro here. */
# define HASH_INSERT_NEW_ITEM(Ht, Item, Failp) \
do \
{ \
void *_already; \
_already = hash_insert_if_absent ((Ht), (Item), Failp); \
assert (_already == NULL); \
} \
while (0)
#endif /* HASH_H */
|
