1 /* implementation of auto-resizing hash table */
2 /* ifile - intelligent mail filter for EXMH/MH
3 ifile is Copyright (C) 1997 Jason Rennie <jrennie@ai.mit.edu>
4
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either version 2
8 of the License, or (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program (see file 'COPYING'); if not, write to the Free
17 Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
19 */
20
21 #include <stddef.h> /* stdlib doesn't have NULL defined on SunOS 4.1.3_U1 */
22 #include <stdlib.h>
23 #include <assert.h>
24 #include <string.h>
25 #include <hash_table.h>
26
27 /* Crock: hashtables should create their own copies of string indices,
28 except when they're resizing */
29 /* Crock added by Jeremy Brown <jhbrown@ai.mit.edu>, who isn't proud
30 of it. */
31 int htable_privatize_indices = 1;
32
33
34 char * ifile_strdup (const char *s1);
35
36
37 /* Initializes values of hash table, allocates space for DATA array.
38 * HASH_TABLE->DATA *must* be malloced. */
39 /* written by Jason Rennie <jrennie@ai.mit.edu> */
40 void
htable_init(htable * hash_table,long int num_slots,unsigned long (* hash_fun)(const void *,long int))41 htable_init(htable * hash_table, long int num_slots,
42 unsigned long (*hash_fun) (const void *, long int))
43 {
44 long int i = 0;
45
46 /* makes the size of the array prime (up to about i=30) */
47 for (i=7; ((1 << i) - 1) < num_slots; i += 2);
48 num_slots = (1 << i) - 1;
49
50 hash_table->num_slots = num_slots;
51 hash_table->num_entries = 0;
52 hash_table->data = (hash_elem *) malloc(num_slots*sizeof(hash_elem));
53 hash_table->hash = hash_fun;
54
55 for (i=0; i < num_slots; i++)
56 {
57 hash_table->data[i].index = NULL;
58 hash_table->data[i].entry = NULL;
59 }
60 }
61
62
63 /* Frees all memory used by HASH TABLE. Uses caller-provided
64 functions to free entry and index; NULL functions mean nothing needs
65 to be done. */
66 /* written by Jason Rennie <jrennie@ai.mit.edu> */
67 void
htable_free_guts(htable * hash_table,void (* free_index)(void *),void (* free_entry)(void *))68 htable_free_guts(htable * hash_table, void (*free_index)(void *), void (*free_entry)(void *))
69 {
70 long int i;
71 long int slots = hash_table->num_slots;
72 hash_elem * data = hash_table->data;
73
74 if (free_index)
75 for (i=0; i < slots; i++)
76 free_index(data[i].index);
77
78 if (free_entry)
79 for (i=0; i < slots; i++)
80 free_entry(data[i].entry);
81
82 free(hash_table->data);
83 }
84
85 /* See above function */
86 void
htable_free(htable * hash_table,void (* free_index)(void *),void (* free_entry)(void *))87 htable_free(htable * hash_table, void (*free_index)(void *), void (*free_entry)(void *)) {
88 htable_free_guts(hash_table, free_index, free_entry);
89 free(hash_table);
90 }
91
92
93
94
95
96 /* Adds an entry to the hash table, expands the hash table if it is too
97 * crowded. Assumes that INDEX and ENTRY will not be deallocated during
98 * the life of the hash table */
99 /* written by Jason Rennie <jrennie@ai.mit.edu> */
100 void
htable_put(htable * hash_table,void * index,void * entry)101 htable_put(htable * hash_table, void * index, void * entry)
102 {
103 unsigned long key;
104 long int i;
105
106 if ((float)(hash_table->num_entries+1) / (float)(hash_table->num_slots) >=
107 CROWDED_PCT)
108 htable_resize(hash_table, hash_table->num_slots*2);
109
110 key = hash_table->hash(index, hash_table->num_slots);
111 i = key % hash_table->num_slots;
112
113 assert(i >= 0);
114
115 /* loop until we find an open slot, or a slot with the same index */
116 while (hash_table->data[i].entry != NULL &&
117 strcmp((char *) index, (char *) (hash_table->data[i].index)) != 0)
118 {
119 key++;
120 i = key % hash_table->num_slots;
121 assert(i >= 0);
122 }
123
124 if (hash_table->data[i].entry == NULL) {
125 hash_table->data[i].index = htable_privatize_indices? ifile_strdup(index) : index;
126 hash_table->num_entries++;
127 }
128
129 hash_table->data[i].entry = entry;
130 }
131
132
133 /* Returns the ENTRY for a given INDEX. Returns NULL if an ENTRY
134 * for INDEX does not exist in the hash table */
135 /* written by Jason Rennie <jrennie@ai.mit.edu> */
136 void *
htable_lookup(htable * hash_table,void * index)137 htable_lookup(htable * hash_table, void * index)
138 {
139 unsigned long key;
140 long int i;
141
142 key = hash_table->hash(index, hash_table->num_slots);
143 i = key % hash_table->num_slots;
144
145 assert(i >= 0);
146
147 /* loop until we find an open slot, or a slot with the same index */
148 while (hash_table->data[i].entry != NULL &&
149 strcmp((char *) index, (char *) (hash_table->data[i].index)) != 0)
150 {
151 key++;
152 i = key % hash_table->num_slots;
153 assert(i >= 0);
154 }
155
156 return hash_table->data[i].entry;
157 }
158
159
160 /* Returns first element in hash table. Returns NULL if hash table i
161 * empty. */
162 /* written by Jason Rennie <jrennie@ai.mit.edu> */
163 hash_elem *
htable_init_traversal(htable * hash_table)164 htable_init_traversal(htable * hash_table)
165 {
166 long int slots = hash_table->num_slots;
167 long int slot_size = sizeof(hash_elem);
168 long int elem;
169 long int base = (long int) hash_table->data;
170 long int limit = slots*slot_size + base;
171
172 for (elem = base;
173 elem < limit && (*(hash_elem *)elem).entry == NULL;
174 elem += slot_size);
175
176 if (elem >= limit)
177 return NULL;
178 else
179 return (hash_elem *) elem;
180 }
181
182
183 /* Returns the next element of the hash table. Sequential calls of
184 * this function traverses all hash table entries. Returns NULL if
185 * ELEM is the last element of the traversal */
186 /* written by Jason Rennie <jrennie@ai.mit.edu> */
187 hash_elem *
htable_next_traversal(htable * hash_table,hash_elem * elem)188 htable_next_traversal(htable * hash_table, hash_elem * elem)
189 {
190 long int slots = hash_table->num_slots;
191 long int slot_size = sizeof(hash_elem);
192 long int base = (long int) hash_table->data;
193 long int limit = slots*slot_size + base;
194 long int elem_ptr;
195
196 /* takes advantage of the fact that DATA is an array */
197 for (elem_ptr = (long int) elem + slot_size;
198 elem_ptr < limit && (*(hash_elem *)elem_ptr).entry == NULL;
199 elem_ptr += slot_size);
200
201 if ((long int) elem_ptr >= limit)
202 return NULL;
203 else
204 return (hash_elem *) elem_ptr;
205 }
206
207
208 /* Resizes DATA so that it is capable of containing at least NUM_SLOTS
209 * entries. This function is reliant on the current implementation
210 * of other htable functions. */
211 /* written by Jason Rennie <jrennie@ai.mit.edu> */
212 void
htable_resize(htable * hash_table,long int num_slots)213 htable_resize(htable * hash_table, long int num_slots)
214 {
215 htable fake_htable;
216 hash_elem * elem;
217
218 htable_init(&fake_htable, num_slots, hash_table->hash);
219
220 htable_privatize_indices = 0;
221 for (elem = htable_init_traversal(hash_table);
222 elem != NULL; elem = htable_next_traversal(hash_table, elem))
223 htable_put(&fake_htable, (*elem).index, (*elem).entry);
224 htable_privatize_indices = 1;
225
226 free(hash_table->data);
227 hash_table->data = fake_htable.data;
228 hash_table->num_slots = fake_htable.num_slots;
229 }
230