1 /* hash.c -- hash table maintenance
2 Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
3 Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
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.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
24 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
25 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
26 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
28 static void hash_rehash
__P((struct hash_table
* ht
));
29 static unsigned long round_up_2
__P((unsigned long rough
));
31 /* Implement double hashing with open addressing. The table size is
32 always a power of two. The secondary (`increment') hash function
33 is forced to return an odd-value, in order to be relatively prime
34 to the table size. This guarantees that the increment can
35 potentially hit every slot in the table during collision
38 void *hash_deleted_item
= &hash_deleted_item
;
40 /* Force the table size to be a power of two, possibly rounding up the
44 hash_init (ht
, size
, hash_1
, hash_2
, hash_cmp
)
45 struct hash_table
* ht
;
49 hash_cmp_func_t hash_cmp
;
51 ht
->ht_size
= round_up_2 (size
);
52 ht
->ht_empty_slots
= ht
->ht_size
;
53 ht
->ht_vec
= (void**) CALLOC (struct token
*, ht
->ht_size
);
56 fprintf (stderr
, _("can't allocate %ld bytes for hash table: memory exhausted"),
57 ht
->ht_size
* sizeof(struct token
*));
61 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
/ 16); /* 93.75% loading factor */
63 ht
->ht_collisions
= 0;
66 ht
->ht_hash_1
= hash_1
;
67 ht
->ht_hash_2
= hash_2
;
68 ht
->ht_compare
= hash_cmp
;
71 /* Load an array of items into `ht'. */
74 hash_load (ht
, item_table
, cardinality
, size
)
75 struct hash_table
* ht
;
77 unsigned long cardinality
;
80 char *items
= (char *) item_table
;
83 hash_insert (ht
, items
);
88 /* Returns the address of the table slot matching `key'. If `key' is
89 not found, return the address of an empty slot suitable for
90 inserting `key'. The caller is responsible for incrementing
91 ht_fill on insertion. */
94 hash_find_slot (ht
, key
)
95 struct hash_table
* ht
;
99 void **deleted_slot
= 0;
100 unsigned int hash_2
= 0;
101 unsigned int hash_1
= (*ht
->ht_hash_1
) (key
);
106 hash_1
&= (ht
->ht_size
- 1);
107 slot
= &ht
->ht_vec
[hash_1
];
110 return (deleted_slot
? deleted_slot
: slot
);
111 if (*slot
== hash_deleted_item
)
113 if (deleted_slot
== 0)
120 if ((*ht
->ht_compare
) (key
, *slot
) == 0)
125 hash_2
= (*ht
->ht_hash_2
) (key
) | 1;
131 hash_find_item (ht
, key
)
132 struct hash_table
* ht
;
135 void **slot
= hash_find_slot (ht
, key
);
136 return ((HASH_VACANT (*slot
)) ? 0 : *slot
);
140 hash_insert (ht
, item
)
141 struct hash_table
* ht
;
144 void **slot
= hash_find_slot (ht
, item
);
145 void *old_item
= slot
? *slot
: 0;
146 hash_insert_at (ht
, item
, slot
);
147 return ((HASH_VACANT (old_item
)) ? 0 : old_item
);
151 hash_insert_at (ht
, item
, slot
)
152 struct hash_table
* ht
;
156 void *old_item
= *(void **) slot
;
157 if (HASH_VACANT (old_item
))
161 ht
->ht_empty_slots
--;
164 *(void const **) slot
= item
;
165 if (ht
->ht_empty_slots
< ht
->ht_size
- ht
->ht_capacity
)
168 return (void *) hash_find_slot (ht
, item
);
171 return (void *) slot
;
175 hash_delete (ht
, item
)
176 struct hash_table
* ht
;
179 void **slot
= hash_find_slot (ht
, item
);
180 return hash_delete_at (ht
, slot
);
184 hash_delete_at (ht
, slot
)
185 struct hash_table
* ht
;
188 void *item
= *(void **) slot
;
189 if (!HASH_VACANT (item
))
191 *(void const **) slot
= hash_deleted_item
;
201 struct hash_table
* ht
;
203 void **vec
= ht
->ht_vec
;
204 void **end
= &vec
[ht
->ht_size
];
205 for (; vec
< end
; vec
++)
208 if (!HASH_VACANT (item
))
213 ht
->ht_empty_slots
= ht
->ht_size
;
217 hash_delete_items (ht
)
218 struct hash_table
* ht
;
220 void **vec
= ht
->ht_vec
;
221 void **end
= &vec
[ht
->ht_size
];
222 for (; vec
< end
; vec
++)
225 ht
->ht_collisions
= 0;
228 ht
->ht_empty_slots
= ht
->ht_size
;
232 hash_free (ht
, free_items
)
233 struct hash_table
* ht
;
237 hash_free_items (ht
);
241 ht
->ht_empty_slots
= ht
->ht_size
;
250 struct hash_table
*ht
;
254 void **end
= &ht
->ht_vec
[ht
->ht_size
];
256 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
258 if (!HASH_VACANT (*slot
))
264 hash_map_arg (ht
, map
, arg
)
265 struct hash_table
*ht
;
266 hash_map_arg_func_t map
;
270 void **end
= &ht
->ht_vec
[ht
->ht_size
];
272 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
274 if (!HASH_VACANT (*slot
))
279 /* Double the size of the hash table in the event of overflow... */
283 struct hash_table
* ht
;
285 unsigned long old_ht_size
= ht
->ht_size
;
286 void **old_vec
= ht
->ht_vec
;
289 if (ht
->ht_fill
>= ht
->ht_capacity
)
292 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
>> 4);
295 ht
->ht_vec
= (void **) CALLOC (struct token
*, ht
->ht_size
);
297 for (ovp
= old_vec
; ovp
< &old_vec
[old_ht_size
]; ovp
++)
299 if (! HASH_VACANT (*ovp
))
301 void **slot
= hash_find_slot (ht
, *ovp
);
305 ht
->ht_empty_slots
= ht
->ht_size
- ht
->ht_fill
;
310 hash_print_stats (ht
, out_FILE
)
311 struct hash_table
*ht
;
314 /* GKM FIXME: honor NO_FLOAT */
315 fprintf (out_FILE
, _("Load=%ld/%ld=%.0f%%, "), ht
->ht_fill
, ht
->ht_size
,
316 100.0 * (double) ht
->ht_fill
/ (double) ht
->ht_size
);
317 fprintf (out_FILE
, _("Rehash=%d, "), ht
->ht_rehashes
);
318 fprintf (out_FILE
, _("Collisions=%ld/%ld=%.0f%%"), ht
->ht_collisions
, ht
->ht_lookups
,
320 ? (100.0 * (double) ht
->ht_collisions
/ (double) ht
->ht_lookups
)
324 /* Dump all items into a NULL-terminated vector. Use the
325 user-supplied vector, or malloc one. */
328 hash_dump (ht
, vector_0
, compare
)
329 struct hash_table
*ht
;
335 void **end
= &ht
->ht_vec
[ht
->ht_size
];
338 vector_0
= MALLOC (void *, ht
->ht_fill
+ 1);
341 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
342 if (!HASH_VACANT (*slot
))
347 qsort (vector_0
, ht
->ht_fill
, sizeof (void *), compare
);
351 /* Round a given number up to the nearest power of 2. */