Mercurial > hg > octave-kai > gnulib-hg
annotate lib/hash.c @ 1039:4d7cd20a6c87
(hash_free_0): Remove prototype.
Move function to precede first use.
| author | Jim Meyering <jim@meyering.net> |
|---|---|
| date | Sun, 21 Sep 1997 04:41:19 +0000 |
| parents | b12d8086ca7a |
| children | f9473b8f6df1 |
| rev | line source |
|---|---|
|
1038
b12d8086ca7a
(ZALLOC): Take Ht parameter instead of relying on one being in scope.
Jim Meyering <jim@meyering.net>
parents:
1037
diff
changeset
|
1 /* A generic hash table package. */ |
| 1031 | 2 |
| 3 #include <stdio.h> | |
| 4 #include <stdlib.h> | |
| 5 #include <assert.h> | |
| 6 | |
| 7 #include "hash.h" | |
| 8 | |
| 9 #ifdef USE_OBSTACK | |
|
1038
b12d8086ca7a
(ZALLOC): Take Ht parameter instead of relying on one being in scope.
Jim Meyering <jim@meyering.net>
parents:
1037
diff
changeset
|
10 # define ZALLOC(Ht, N) obstack_alloc (&(ht->ht_obstack), (N)) |
| 1031 | 11 #else |
|
1038
b12d8086ca7a
(ZALLOC): Take Ht parameter instead of relying on one being in scope.
Jim Meyering <jim@meyering.net>
parents:
1037
diff
changeset
|
12 # define ZALLOC(Ht, N) malloc ((N)) |
| 1031 | 13 #endif |
| 14 | |
| 15 #define BUCKET_HEAD(ht, idx) ((ht)->hash_table[(idx)]) | |
| 16 | |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
17 static int |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
18 is_prime (candidate) |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
19 unsigned long candidate; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
20 { |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
21 /* No even number and none less than 10 will be passed here. */ |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
22 unsigned long divn = 3; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
23 unsigned long sq = divn * divn; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
24 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
25 while (sq < candidate && (candidate % divn)) |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
26 { |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
27 divn++; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
28 sq += 4 * divn; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
29 divn++; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
30 } |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
31 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
32 return (candidate % divn); |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
33 } |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
34 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
35 /* Round a given number up to the nearest prime. */ |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
36 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
37 static unsigned long |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
38 next_prime (candidate) |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
39 unsigned long candidate; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
40 { |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
41 /* Make it definitely odd. */ |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
42 candidate |= 1; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
43 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
44 while (!is_prime (candidate)) |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
45 candidate += 2; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
46 |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
47 return candidate; |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
48 } |
|
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
49 |
| 1031 | 50 static void |
| 51 hash_free_entry (HT *ht, HASH_ENT *e) | |
| 52 { | |
| 53 e->key = NULL; | |
| 54 e->next = ht->hash_free_entry_list; | |
| 55 ht->hash_free_entry_list = e; | |
| 56 } | |
| 57 | |
| 58 static HASH_ENT * | |
| 59 hash_allocate_entry (HT *ht) | |
| 60 { | |
| 61 HASH_ENT *new; | |
| 62 if (ht->hash_free_entry_list) | |
| 63 { | |
| 64 new = ht->hash_free_entry_list; | |
| 65 ht->hash_free_entry_list = new->next; | |
| 66 } | |
| 67 else | |
| 68 { | |
|
1038
b12d8086ca7a
(ZALLOC): Take Ht parameter instead of relying on one being in scope.
Jim Meyering <jim@meyering.net>
parents:
1037
diff
changeset
|
69 new = (HASH_ENT *) ZALLOC (ht, sizeof (HASH_ENT)); |
| 1031 | 70 } |
| 71 return new; | |
| 72 } | |
| 73 | |
| 74 unsigned int | |
| 75 hash_get_n_slots_used (const HT *ht) | |
| 76 { | |
| 77 return ht->hash_n_slots_used; | |
| 78 } | |
| 79 | |
|
1039
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
80 /* Free all storage associated with HT that functions in this package |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
81 have allocated. If a key_freer function has been supplied (when HT |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
82 was created), this function applies it to the key of each entry before |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
83 freeing that entry. */ |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
84 |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
85 static void |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
86 hash_free_0 (HT *ht, int free_user_data) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
87 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
88 if (free_user_data && ht->hash_key_freer != NULL) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
89 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
90 unsigned int i; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
91 |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
92 for (i = 0; i < ht->hash_table_size; i++) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
93 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
94 HASH_ENT *p; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
95 HASH_ENT *next; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
96 |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
97 for (p = BUCKET_HEAD (ht, i); p; p = next) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
98 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
99 next = p->next; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
100 ht->hash_key_freer (p->key); |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
101 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
102 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
103 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
104 |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
105 #ifdef USE_OBSTACK |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
106 obstack_free (&(ht->ht_obstack), NULL); |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
107 #else |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
108 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
109 unsigned int i; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
110 for (i = 0; i < ht->hash_table_size; i++) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
111 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
112 HASH_ENT *p; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
113 HASH_ENT *next; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
114 |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
115 for (p = BUCKET_HEAD (ht, i); p; p = next) |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
116 { |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
117 next = p->next; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
118 free (p); |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
119 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
120 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
121 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
122 #endif |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
123 ht->hash_free_entry_list = NULL; |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
124 free (ht->hash_table); |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
125 } |
|
4d7cd20a6c87
(hash_free_0): Remove prototype.
Jim Meyering <jim@meyering.net>
parents:
1038
diff
changeset
|
126 |
| 1031 | 127 /* FIXME-comment */ |
| 128 | |
| 129 int | |
| 130 hash_rehash (HT *ht, unsigned int new_table_size) | |
| 131 { | |
| 132 HT *ht_new; | |
| 133 unsigned int i; | |
| 134 | |
| 135 if (ht->hash_table_size <= 0 || new_table_size == 0) | |
| 136 return 1; | |
| 137 | |
| 138 ht_new = hash_initialize (new_table_size, ht->hash_key_freer, | |
| 139 ht->hash_hash, ht->hash_key_comparator); | |
| 140 | |
| 141 if (ht_new == NULL) | |
| 142 return 1; | |
| 143 | |
| 144 for (i = 0; i < ht->hash_table_size; i++) | |
| 145 { | |
| 146 HASH_ENT *p = BUCKET_HEAD (ht, i); | |
| 147 for ( /* empty */ ; p; p = p->next) | |
| 148 { | |
| 149 int failed; | |
| 150 const void *already_in_table; | |
| 151 already_in_table = hash_insert_if_absent (ht_new, p->key, &failed); | |
| 152 assert (failed == 0 && already_in_table == 0); | |
| 153 } | |
| 154 } | |
| 155 | |
| 156 hash_free_0 (ht, 0); | |
| 157 | |
| 158 #ifdef TESTING | |
| 159 assert (hash_table_ok (ht_new)); | |
| 160 #endif | |
| 161 *ht = *ht_new; | |
| 162 free (ht_new); | |
| 163 | |
| 164 /* FIXME: fill in ht_new->n_slots_used and other statistics fields. */ | |
| 165 | |
| 166 return 0; | |
| 167 } | |
| 168 | |
| 169 /* FIXME-comment */ | |
| 170 | |
| 171 unsigned int | |
| 172 hash_get_max_chain_length (HT *ht) | |
| 173 { | |
| 174 unsigned int i; | |
| 175 unsigned int max_chain_length = 0; | |
| 176 | |
| 177 if (!ht->hash_dirty_max_chain_length) | |
| 178 return ht->hash_max_chain_length; | |
| 179 | |
| 180 for (i = 0; i < ht->hash_table_size; i++) | |
| 181 { | |
| 182 unsigned int chain_length = 0; | |
| 183 HASH_ENT *p = BUCKET_HEAD (ht, i); | |
| 184 for ( /* empty */ ; p; p = p->next) | |
| 185 ++chain_length; | |
| 186 if (chain_length > max_chain_length) | |
| 187 max_chain_length = chain_length; | |
| 188 } | |
| 189 | |
| 190 ht->hash_max_chain_length = max_chain_length; | |
| 191 ht->hash_dirty_max_chain_length = 0; | |
| 192 return ht->hash_max_chain_length; | |
| 193 } | |
| 194 | |
| 195 unsigned int | |
| 196 hash_get_n_keys (const HT *ht) | |
| 197 { | |
| 198 return ht->hash_n_keys; | |
| 199 } | |
| 200 | |
| 201 unsigned int | |
| 202 hash_get_table_size (const HT *ht) | |
| 203 { | |
| 204 return ht->hash_table_size; | |
| 205 } | |
| 206 | |
| 1036 | 207 /* CANDIDATE_TABLE_SIZE need not be prime. If WHEN_TO_REHASH (FIXME: add |
| 208 this parameter) is positive, when that percentage of table entries have | |
| 209 been used, the table size is increased; then a new, larger table | |
| 210 (GROW_FACTOR (FIXME: maybe add this parameter) times larger than the previous | |
| 211 size) is allocated and all entries in the old table are rehashed into | |
| 212 the new, larger one. The old table is freed. If WHEN_TO_REHASH is zero | |
| 213 or negative, the table is never resized. | |
| 1031 | 214 |
| 215 The function returns non-zero | |
| 1036 | 216 - if CANDIDATE_TABLE_SIZE is zero or negative |
| 217 - if KEY_COMPARATOR or HASH is null | |
| 1031 | 218 - if it was unable to allocate sufficient storage for the hash table |
| 219 - if WHEN_TO_REHASH is zero or negative | |
| 1037 | 220 Otherwise it returns zero. */ |
| 1031 | 221 |
| 222 HT * | |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
223 hash_initialize (unsigned int candidate_table_size, |
| 1031 | 224 Hash_key_freer_type key_freer, |
| 225 unsigned int (*hash) (const void *, unsigned int), | |
| 226 int (*key_comparator) (const void *, const void *)) | |
| 227 { | |
| 228 HT *ht; | |
| 229 unsigned int i; | |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
230 unsigned int table_size; |
| 1031 | 231 |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
232 if (candidate_table_size <= 0) |
| 1031 | 233 return NULL; |
| 234 | |
| 235 if (hash == NULL || key_comparator == NULL) | |
| 236 return NULL; | |
| 237 | |
| 238 ht = (HT *) malloc (sizeof (HT)); | |
| 239 if (ht == NULL) | |
| 240 return NULL; | |
| 241 | |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
242 table_size = next_prime (candidate_table_size); |
| 1031 | 243 ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *)); |
| 244 if (ht->hash_table == NULL) | |
| 245 return NULL; | |
| 246 | |
| 247 for (i = 0; i < table_size; i++) | |
| 248 { | |
| 249 BUCKET_HEAD (ht, i) = NULL; | |
| 250 } | |
| 251 | |
| 252 ht->hash_free_entry_list = NULL; | |
| 253 ht->hash_table_size = table_size; | |
| 254 ht->hash_hash = hash; | |
| 255 ht->hash_key_comparator = key_comparator; | |
| 256 ht->hash_key_freer = key_freer; | |
| 257 ht->hash_n_slots_used = 0; | |
| 258 ht->hash_max_chain_length = 0; | |
| 259 ht->hash_n_keys = 0; | |
| 260 ht->hash_dirty_max_chain_length = 0; | |
| 261 #ifdef USE_OBSTACK | |
| 262 obstack_init (&(ht->ht_obstack)); | |
| 263 #endif | |
| 264 | |
| 265 return ht; | |
| 266 } | |
| 267 | |
| 268 /* This private function is used to help with insertion and deletion. | |
| 269 If E does *not* compare equal to the key of any entry in the table, | |
| 270 return NULL. | |
| 271 When E matches an entry in the table, return a pointer to the matching | |
| 272 entry. When DELETE is non-zero and E matches an entry in the table, | |
| 273 unlink the matching entry. Set *CHAIN_LENGTH to the number of keys | |
| 274 that have hashed to the bucket E hashed to. */ | |
| 275 | |
| 276 static HASH_ENT * | |
| 277 hash_find_entry (HT *ht, const void *e, unsigned int *table_idx, | |
| 278 unsigned int *chain_length, int delete) | |
| 279 { | |
| 280 unsigned int idx; | |
| 281 int found; | |
| 282 HASH_ENT *p, *prev; | |
| 283 | |
| 284 idx = ht->hash_hash (e, ht->hash_table_size); | |
| 285 assert (idx < ht->hash_table_size); | |
| 286 | |
| 287 *table_idx = idx; | |
| 288 *chain_length = 0; | |
| 289 | |
| 290 prev = ht->hash_table[idx]; | |
| 291 | |
| 292 if (prev == NULL) | |
| 293 return NULL; | |
| 294 | |
| 295 *chain_length = 1; | |
| 296 if (ht->hash_key_comparator (e, prev->key) == 0) | |
| 297 { | |
| 298 if (delete) | |
| 299 ht->hash_table[idx] = prev->next; | |
| 300 return prev; | |
| 301 } | |
| 302 | |
| 303 p = prev->next; | |
| 304 found = 0; | |
| 305 while (p) | |
| 306 { | |
| 307 ++(*chain_length); | |
| 308 if (ht->hash_key_comparator (e, p->key) == 0) | |
| 309 { | |
| 310 found = 1; | |
| 311 break; | |
| 312 } | |
| 313 prev = p; | |
| 314 p = p->next; | |
| 315 } | |
| 316 | |
| 317 if (!found) | |
| 318 return NULL; | |
| 319 | |
| 320 assert (p != NULL); | |
| 321 if (delete) | |
| 322 prev->next = p->next; | |
| 323 | |
| 324 return p; | |
| 325 } | |
| 326 | |
| 327 /* Return non-zero if E is already in the table, zero otherwise. */ | |
| 328 | |
| 329 int | |
| 330 hash_query_in_table (const HT *ht, const void *e) | |
| 331 { | |
| 332 unsigned int idx; | |
| 333 HASH_ENT *p; | |
| 334 | |
| 335 idx = ht->hash_hash (e, ht->hash_table_size); | |
| 336 assert (idx < ht->hash_table_size); | |
| 337 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next) | |
| 338 if (ht->hash_key_comparator (e, p->key) == 0) | |
| 339 return 1; | |
| 340 return 0; | |
| 341 } | |
| 342 | |
| 343 void * | |
| 344 hash_lookup (const HT *ht, const void *e) | |
| 345 { | |
| 346 unsigned int idx; | |
| 347 HASH_ENT *p; | |
| 348 | |
| 349 idx = ht->hash_hash (e, ht->hash_table_size); | |
| 350 assert (idx < ht->hash_table_size); | |
| 351 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next) | |
| 352 if (ht->hash_key_comparator (e, p->key) == 0) | |
| 353 return p->key; | |
| 354 return NULL; | |
| 355 } | |
| 356 | |
| 357 /* If E matches an entry already in the hash table, don't modify the | |
| 358 table and return a pointer to the matched entry. If E does not | |
| 359 match any item in the table, insert E and return NULL. | |
| 360 If the storage required for insertion cannot be allocated | |
| 361 set *FAILED to non-zero and return NULL. */ | |
| 362 | |
| 363 void * | |
| 364 hash_insert_if_absent (HT *ht, const void *e, int *failed) | |
| 365 { | |
| 366 const HASH_ENT *ent; | |
| 367 HASH_ENT *new; | |
| 368 unsigned int idx; | |
| 369 unsigned int chain_length; | |
| 370 | |
| 371 assert (e != NULL); /* Can't insert a NULL key. */ | |
| 372 | |
| 373 *failed = 0; | |
| 374 ent = hash_find_entry (ht, e, &idx, &chain_length, 0); | |
| 375 if (ent != NULL) | |
| 376 { | |
| 377 /* E matches a key from an entry already in the table. */ | |
| 378 return ent->key; | |
| 379 } | |
| 380 | |
| 381 new = hash_allocate_entry (ht); | |
| 382 if (new == NULL) | |
| 383 { | |
| 384 *failed = 1; | |
| 385 return NULL; | |
| 386 } | |
| 387 | |
| 388 new->key = (void *) e; | |
| 389 new->next = BUCKET_HEAD (ht, idx); | |
| 390 BUCKET_HEAD (ht, idx) = new; | |
| 391 | |
| 392 if (chain_length == 0) | |
| 393 ++(ht->hash_n_slots_used); | |
| 394 | |
| 395 /* The insertion has just increased chain_length by 1. */ | |
| 396 ++chain_length; | |
| 397 | |
| 398 if (chain_length > ht->hash_max_chain_length) | |
| 399 ht->hash_max_chain_length = chain_length; | |
| 400 | |
| 401 ++(ht->hash_n_keys); | |
| 402 if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80) | |
| 403 { | |
| 404 unsigned int new_size; | |
|
1033
f4f00c32582a
use malloc, not xmalloc in obstack #define
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
405 new_size = next_prime (2 * ht->hash_table_size + 1); |
| 1031 | 406 *failed = hash_rehash (ht, new_size); |
| 407 } | |
| 408 | |
| 409 #ifdef TESTING | |
| 410 assert (hash_table_ok (ht)); | |
| 411 #endif | |
| 412 | |
| 413 return NULL; | |
| 414 } | |
| 415 | |
| 416 /* If E is already in the table, remove it and return a pointer to | |
| 417 the just-deleted key (the user may want to deallocate its storage). | |
| 418 If E is not in the table, don't modify the table and return NULL. */ | |
| 419 | |
| 420 void * | |
| 421 hash_delete_if_present (HT *ht, const void *e) | |
| 422 { | |
| 423 HASH_ENT *ent; | |
| 424 void *key; | |
| 425 unsigned int idx; | |
| 426 unsigned int chain_length; | |
| 427 | |
| 428 ent = hash_find_entry (ht, e, &idx, &chain_length, 1); | |
| 429 if (ent == NULL) | |
| 430 return NULL; | |
| 431 | |
| 432 if (ent->next == NULL && chain_length == 1) | |
| 433 --(ht->hash_n_slots_used); | |
| 434 | |
| 435 key = ent->key; | |
| 436 | |
| 437 --(ht->hash_n_keys); | |
| 438 ht->hash_dirty_max_chain_length = 1; | |
| 439 if (ent->next == NULL && chain_length < ht->hash_max_chain_length) | |
| 440 ht->hash_dirty_max_chain_length = 0; | |
| 441 | |
| 442 hash_free_entry (ht, ent); | |
| 443 | |
| 444 #ifdef TESTING | |
| 445 assert (hash_table_ok (ht)); | |
| 446 #endif | |
| 447 return key; | |
| 448 } | |
| 449 | |
| 450 void | |
| 451 hash_print_statistics (const HT *ht, FILE *stream) | |
| 452 { | |
| 453 unsigned int n_slots_used; | |
| 454 unsigned int n_keys; | |
| 455 unsigned int max_chain_length; | |
| 456 int err; | |
| 457 | |
| 458 err = hash_get_statistics (ht, &n_slots_used, &n_keys, &max_chain_length); | |
| 459 assert (err == 0); | |
| 460 fprintf (stream, "table size: %d\n", ht->hash_table_size); | |
| 461 fprintf (stream, "# slots used: %u (%.2f%%)\n", n_slots_used, | |
| 462 (100.0 * n_slots_used) / ht->hash_table_size); | |
| 463 fprintf (stream, "# keys: %u\n", n_keys); | |
| 464 fprintf (stream, "max chain length: %u\n", max_chain_length); | |
| 465 } | |
| 466 | |
| 467 /* If there is *NO* table (so, no meaningful stats) return non-zero | |
| 468 and don't reference the argument pointers. Otherwise compute the | |
| 469 performance statistics and return non-zero. */ | |
| 470 | |
| 471 int | |
| 472 hash_get_statistics (const HT *ht, | |
| 473 unsigned int *n_slots_used, | |
| 474 unsigned int *n_keys, | |
| 475 unsigned int *max_chain_length) | |
| 476 { | |
| 477 unsigned int i; | |
| 478 | |
| 479 if (ht == NULL || ht->hash_table == NULL) | |
| 480 return 1; | |
| 481 | |
| 482 *max_chain_length = 0; | |
| 483 *n_slots_used = 0; | |
| 484 *n_keys = 0; | |
| 485 | |
| 486 for (i = 0; i < ht->hash_table_size; i++) | |
| 487 { | |
| 488 unsigned int chain_length = 0; | |
| 489 HASH_ENT *p; | |
| 490 | |
| 491 p = BUCKET_HEAD (ht, i); | |
| 492 if (p != NULL) | |
| 493 ++(*n_slots_used); | |
| 494 | |
| 495 for (; p; p = p->next) | |
| 496 ++chain_length; | |
| 497 | |
| 498 *n_keys += chain_length; | |
| 499 if (chain_length > *max_chain_length) | |
| 500 *max_chain_length = chain_length; | |
| 501 } | |
| 502 return 0; | |
| 503 } | |
| 504 | |
| 505 int | |
| 506 hash_table_ok (HT *ht) | |
| 507 { | |
| 508 int code; | |
| 509 unsigned int n_slots_used; | |
| 510 unsigned int n_keys; | |
| 511 unsigned int max_chain_length; | |
| 512 | |
| 513 if (ht == NULL || ht->hash_table == NULL) | |
| 514 return 1; | |
| 515 | |
| 516 code = hash_get_statistics (ht, &n_slots_used, &n_keys, | |
| 517 &max_chain_length); | |
| 518 | |
| 519 if (code != 0 | |
| 520 || n_slots_used != ht->hash_n_slots_used | |
| 521 || n_keys != ht->hash_n_keys | |
| 522 || max_chain_length != hash_get_max_chain_length (ht)) | |
| 523 return 0; | |
| 524 | |
| 525 return 1; | |
| 526 } | |
| 527 | |
| 528 /* See hash_do_for_each_2 (below) for a variant. */ | |
| 529 | |
| 530 void | |
| 531 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux) | |
| 532 { | |
| 533 unsigned int i; | |
| 534 | |
| 535 #ifdef TESTING | |
| 536 assert (hash_table_ok (ht)); | |
| 537 #endif | |
| 538 | |
| 539 if (ht->hash_table == NULL) | |
| 540 return; | |
| 541 | |
| 542 for (i = 0; i < ht->hash_table_size; i++) | |
| 543 { | |
| 544 HASH_ENT *p; | |
| 545 for (p = BUCKET_HEAD (ht, i); p; p = p->next) | |
| 546 { | |
| 547 (*f) (p->key, aux); | |
| 548 } | |
| 549 } | |
| 550 } | |
| 551 | |
| 552 /* Just like hash_do_for_each, except that function F returns an int | |
| 553 that can signal (when non-zero) we should return early. */ | |
| 554 | |
| 555 int | |
| 556 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux) | |
| 557 { | |
| 558 unsigned int i; | |
| 559 | |
| 560 #ifdef TESTING | |
| 561 assert (hash_table_ok (ht)); | |
| 562 #endif | |
| 563 | |
| 564 if (ht->hash_table == NULL) | |
| 565 return 0; | |
| 566 | |
| 567 for (i = 0; i < ht->hash_table_size; i++) | |
| 568 { | |
| 569 HASH_ENT *p; | |
| 570 for (p = BUCKET_HEAD (ht, i); p; p = p->next) | |
| 571 { | |
| 572 int return_code; | |
| 573 | |
| 574 return_code = (*f) (p->key, aux); | |
| 575 if (return_code != 0) | |
| 576 return return_code; | |
| 577 } | |
| 578 } | |
| 579 return 0; | |
| 580 } | |
| 581 | |
| 582 /* For each entry in the bucket addressed by BUCKET_KEY of the hash | |
| 583 table HT, invoke the function F. If F returns non-zero, stop | |
| 584 iterating and return that value. Otherwise, apply F to all entries | |
| 585 in the selected bucket and return zero. The AUX argument to this | |
| 586 function is passed as the last argument in each invocation of F. | |
| 587 The first argument to F is BUCKET_KEY, and the second is the key of | |
| 588 an entry in the selected bucket. */ | |
| 589 | |
| 590 int | |
| 591 hash_do_for_each_in_selected_bucket (HT *ht, const void *bucket_key, | |
| 592 int (*f) (const void *bucket_key, | |
| 593 void *e, void *aux), | |
| 594 void *aux) | |
| 595 { | |
| 596 int idx; | |
| 597 HASH_ENT *p; | |
| 598 | |
| 599 #ifdef TESTING | |
| 600 assert (hash_table_ok (ht)); | |
| 601 #endif | |
| 602 | |
| 603 if (ht->hash_table == NULL) | |
| 604 return 0; | |
| 605 | |
| 606 idx = ht->hash_hash (bucket_key, ht->hash_table_size); | |
| 607 | |
| 608 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next) | |
| 609 { | |
| 610 int return_code; | |
| 611 | |
| 612 return_code = (*f) (bucket_key, p->key, aux); | |
| 613 if (return_code != 0) | |
| 614 return return_code; | |
| 615 } | |
| 616 | |
| 617 return 0; | |
| 618 } | |
| 619 | |
| 620 /* Make all buckets empty, placing any chained entries on the free list. | |
| 621 As with hash_free, apply the user-specified function key_freer | |
| 622 (if it's not NULL) to the keys of any affected entries. */ | |
| 623 | |
| 624 void | |
| 625 hash_clear (HT *ht) | |
| 626 { | |
| 627 unsigned int i; | |
| 628 HASH_ENT *p; | |
| 629 | |
| 630 for (i = 0; i < ht->hash_table_size; i++) | |
| 631 { | |
| 632 HASH_ENT *tail = NULL; | |
| 633 HASH_ENT *head = BUCKET_HEAD (ht, i); | |
| 634 | |
| 635 /* Free any keys and get tail pointer to last entry in chain. */ | |
| 636 for (p = head; p; p = p->next) | |
| 637 { | |
| 638 if (ht->hash_key_freer != NULL) | |
| 639 ht->hash_key_freer (p->key); | |
| 640 p->key = NULL; /* Make sure no one tries to use this key later. */ | |
| 641 tail = p; | |
| 642 } | |
| 643 BUCKET_HEAD (ht, i) = NULL; | |
| 644 | |
| 645 /* If there's a chain in this bucket, tack it onto the | |
| 646 beginning of the free list. */ | |
| 647 if (head != NULL) | |
| 648 { | |
| 649 assert (tail != NULL && tail->next == NULL); | |
| 650 tail->next = ht->hash_free_entry_list; | |
| 651 ht->hash_free_entry_list = head; | |
| 652 } | |
| 653 } | |
| 654 ht->hash_n_slots_used = 0; | |
| 655 ht->hash_max_chain_length = 0; | |
| 656 ht->hash_n_keys = 0; | |
| 657 ht->hash_dirty_max_chain_length = 0; | |
| 658 } | |
| 659 | |
| 660 void | |
| 661 hash_free (HT *ht) | |
| 662 { | |
| 663 hash_free_0 (ht, 1); | |
| 664 free (ht); | |
| 665 } | |
| 666 | |
| 667 #ifdef TESTING | |
| 668 | |
| 669 void | |
| 670 hash_print (const HT *ht) | |
| 671 { | |
| 672 int i; | |
| 673 | |
| 674 for (i = 0; i < ht->hash_table_size; i++) | |
| 675 { | |
| 676 HASH_ENT *p; | |
| 677 | |
| 678 if (BUCKET_HEAD (ht, i) != NULL) | |
| 679 printf ("%d:\n", i); | |
| 680 | |
| 681 for (p = BUCKET_HEAD (ht, i); p; p = p->next) | |
| 682 { | |
| 683 char *s = (char *) p->key; | |
| 684 /* FIXME */ | |
| 685 printf (" %s\n", s); | |
| 686 } | |
| 687 } | |
| 688 } | |
| 689 | |
| 690 #endif /* TESTING */ | |
| 691 | |
| 692 void | |
| 693 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf) | |
| 694 { | |
| 695 unsigned int i; | |
| 696 unsigned int c = 0; | |
| 697 | |
| 698 for (i = 0; i < ht->hash_table_size; i++) | |
| 699 { | |
| 700 HASH_ENT *p; | |
| 701 | |
| 702 for (p = BUCKET_HEAD (ht, i); p; p = p->next) | |
| 703 { | |
| 704 if (c >= bufsize) | |
| 705 return; | |
| 706 buf[c++] = p->key; | |
| 707 } | |
| 708 } | |
| 709 } | |
| 710 | |
| 711 /* Return the first key in the table. If the table is empty, return NULL. */ | |
| 712 | |
| 713 void * | |
| 714 hash_get_first (const HT *ht) | |
| 715 { | |
| 716 unsigned int idx; | |
| 717 HASH_ENT *p; | |
| 718 | |
| 719 if (ht->hash_n_keys == 0) | |
| 720 return NULL; | |
| 721 | |
| 722 for (idx = 0; idx < ht->hash_table_size; idx++) | |
| 723 { | |
| 724 if ((p = BUCKET_HEAD (ht, idx)) != NULL) | |
| 725 return p->key; | |
| 726 } | |
| 727 abort (); | |
| 728 } | |
| 729 | |
| 730 /* Return the key in the entry following the entry whose key matches E. | |
| 731 If there is the only one key in the table and that key matches E, | |
| 732 return the matching key. If E is not in the table, return NULL. */ | |
| 733 | |
| 734 void * | |
| 735 hash_get_next (const HT *ht, const void *e) | |
| 736 { | |
| 737 unsigned int idx; | |
| 738 HASH_ENT *p; | |
| 739 | |
| 740 idx = ht->hash_hash (e, ht->hash_table_size); | |
| 741 assert (idx < ht->hash_table_size); | |
| 742 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next) | |
| 743 { | |
| 744 if (ht->hash_key_comparator (e, p->key) == 0) | |
| 745 { | |
| 746 if (p->next != NULL) | |
| 747 { | |
| 748 return p->next->key; | |
| 749 } | |
| 750 else | |
| 751 { | |
| 752 unsigned int bucket; | |
| 753 | |
| 754 /* E is the last or only key in the bucket chain. */ | |
| 755 if (ht->hash_n_keys == 1) | |
| 756 { | |
| 757 /* There is only one key in the table, and it matches E. */ | |
| 758 return p->key; | |
| 759 } | |
| 760 bucket = idx; | |
| 761 do | |
| 762 { | |
| 763 idx = (idx + 1) % ht->hash_table_size; | |
| 764 if ((p = BUCKET_HEAD (ht, idx)) != NULL) | |
| 765 return p->key; | |
| 766 } | |
| 767 while (idx != bucket); | |
| 768 } | |
| 769 } | |
| 770 } | |
| 771 | |
| 772 /* E is not in the table. */ | |
| 773 return NULL; | |
| 774 } |