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 along with
16 this program; see the file COPYING. If not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. */
22 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
23 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
24 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
25 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
27 static void hash_rehash
__P((struct hash_table
* ht
));
28 static unsigned long round_up_2
__P((unsigned long rough
));
30 /* Implement double hashing with open addressing. The table size is
31 always a power of two. The secondary (`increment') hash function
32 is forced to return an odd-value, in order to be relatively prime
33 to the table size. This guarantees that the increment can
34 potentially hit every slot in the table during collision
37 void *hash_deleted_item
= &hash_deleted_item
;
39 /* Force the table size to be a power of two, possibly rounding up the
43 hash_init (struct hash_table
*ht
, unsigned long size
,
44 hash_func_t hash_1
, hash_func_t hash_2
, hash_cmp_func_t hash_cmp
)
46 ht
->ht_size
= round_up_2 (size
);
47 ht
->ht_empty_slots
= ht
->ht_size
;
48 ht
->ht_vec
= (void**) CALLOC (struct token
*, ht
->ht_size
);
51 fprintf (stderr
, _("can't allocate %ld bytes for hash table: memory exhausted"),
52 ht
->ht_size
* sizeof(struct token
*));
56 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
/ 16); /* 93.75% loading factor */
58 ht
->ht_collisions
= 0;
61 ht
->ht_hash_1
= hash_1
;
62 ht
->ht_hash_2
= hash_2
;
63 ht
->ht_compare
= hash_cmp
;
66 /* Load an array of items into `ht'. */
69 hash_load (struct hash_table
*ht
, void *item_table
,
70 unsigned long cardinality
, unsigned long size
)
72 char *items
= (char *) item_table
;
75 hash_insert (ht
, items
);
80 /* Returns the address of the table slot matching `key'. If `key' is
81 not found, return the address of an empty slot suitable for
82 inserting `key'. The caller is responsible for incrementing
83 ht_fill on insertion. */
86 hash_find_slot (struct hash_table
*ht
, const void *key
)
89 void **deleted_slot
= 0;
90 unsigned int hash_2
= 0;
91 unsigned int hash_1
= (*ht
->ht_hash_1
) (key
);
96 hash_1
&= (ht
->ht_size
- 1);
97 slot
= &ht
->ht_vec
[hash_1
];
100 return (deleted_slot
? deleted_slot
: slot
);
101 if (*slot
== hash_deleted_item
)
103 if (deleted_slot
== 0)
110 if ((*ht
->ht_compare
) (key
, *slot
) == 0)
115 hash_2
= (*ht
->ht_hash_2
) (key
) | 1;
121 hash_find_item (struct hash_table
*ht
, const void *key
)
123 void **slot
= hash_find_slot (ht
, key
);
124 return ((HASH_VACANT (*slot
)) ? 0 : *slot
);
128 hash_insert (struct hash_table
*ht
, const void *item
)
130 void **slot
= hash_find_slot (ht
, item
);
131 const void *old_item
= slot
? *slot
: 0;
132 hash_insert_at (ht
, item
, slot
);
133 return (void *)((HASH_VACANT (old_item
)) ? 0 : old_item
);
137 hash_insert_at (struct hash_table
*ht
, const void *item
, const void *slot
)
139 const void *old_item
= *(void **) slot
;
140 if (HASH_VACANT (old_item
))
144 ht
->ht_empty_slots
--;
147 *(void const **) slot
= item
;
148 if (ht
->ht_empty_slots
< ht
->ht_size
- ht
->ht_capacity
)
151 return (void *) hash_find_slot (ht
, item
);
154 return (void *) slot
;
158 hash_delete (struct hash_table
*ht
, const void *item
)
160 void **slot
= hash_find_slot (ht
, item
);
161 return hash_delete_at (ht
, slot
);
165 hash_delete_at (struct hash_table
*ht
, const void *slot
)
167 void *item
= *(void **) slot
;
168 if (!HASH_VACANT (item
))
170 *(void const **) slot
= hash_deleted_item
;
179 hash_free_items (struct hash_table
*ht
)
181 void **vec
= ht
->ht_vec
;
182 void **end
= &vec
[ht
->ht_size
];
183 for (; vec
< end
; vec
++)
186 if (!HASH_VACANT (item
))
191 ht
->ht_empty_slots
= ht
->ht_size
;
195 hash_delete_items (struct hash_table
*ht
)
197 void **vec
= ht
->ht_vec
;
198 void **end
= &vec
[ht
->ht_size
];
199 for (; vec
< end
; vec
++)
202 ht
->ht_collisions
= 0;
205 ht
->ht_empty_slots
= ht
->ht_size
;
209 hash_free (struct hash_table
*ht
, int free_items
)
212 hash_free_items (ht
);
216 ht
->ht_empty_slots
= ht
->ht_size
;
224 hash_map (struct hash_table
*ht
, hash_map_func_t map
)
227 void **end
= &ht
->ht_vec
[ht
->ht_size
];
229 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
231 if (!HASH_VACANT (*slot
))
237 hash_map_arg (struct hash_table
*ht
, hash_map_arg_func_t map
, void *arg
)
240 void **end
= &ht
->ht_vec
[ht
->ht_size
];
242 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
244 if (!HASH_VACANT (*slot
))
249 /* Double the size of the hash table in the event of overflow... */
252 hash_rehash (struct hash_table
*ht
)
254 unsigned long old_ht_size
= ht
->ht_size
;
255 void **old_vec
= ht
->ht_vec
;
258 if (ht
->ht_fill
>= ht
->ht_capacity
)
261 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
>> 4);
264 ht
->ht_vec
= (void **) CALLOC (struct token
*, ht
->ht_size
);
266 for (ovp
= old_vec
; ovp
< &old_vec
[old_ht_size
]; ovp
++)
268 if (! HASH_VACANT (*ovp
))
270 void **slot
= hash_find_slot (ht
, *ovp
);
274 ht
->ht_empty_slots
= ht
->ht_size
- ht
->ht_fill
;
279 hash_print_stats (struct hash_table
*ht
, FILE *out_FILE
)
281 /* GKM FIXME: honor NO_FLOAT */
282 fprintf (out_FILE
, _("Load=%ld/%ld=%.0f%%, "), ht
->ht_fill
, ht
->ht_size
,
283 100.0 * (double) ht
->ht_fill
/ (double) ht
->ht_size
);
284 fprintf (out_FILE
, _("Rehash=%d, "), ht
->ht_rehashes
);
285 fprintf (out_FILE
, _("Collisions=%ld/%ld=%.0f%%"), ht
->ht_collisions
, ht
->ht_lookups
,
287 ? (100.0 * (double) ht
->ht_collisions
/ (double) ht
->ht_lookups
)
291 /* Dump all items into a NULL-terminated vector. Use the
292 user-supplied vector, or malloc one. */
295 hash_dump (struct hash_table
*ht
, void **vector_0
, qsort_cmp_t compare
)
299 void **end
= &ht
->ht_vec
[ht
->ht_size
];
302 vector_0
= MALLOC (void *, ht
->ht_fill
+ 1);
305 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
306 if (!HASH_VACANT (*slot
))
311 qsort (vector_0
, ht
->ht_fill
, sizeof (void *), compare
);
315 /* Round a given number up to the nearest power of 2. */
318 round_up_2 (unsigned long n
)
326 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
327 /* We only need this on systems where unsigned long is >32 bits. */