1 /* hash.c -- hash table maintenance
2 Copyright (C) 1995, 1999, 2002, 2010 Free Software Foundation, Inc.
3 Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
5 GNU Make is free software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the Free Software
7 Foundation; either version 3 of the License, or (at your option) any later
10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
12 A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License along with
15 this program. If not, see <http://www.gnu.org/licenses/>. */
20 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
21 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
22 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
23 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
25 static void hash_rehash
__P((struct hash_table
* ht
));
26 static unsigned long round_up_2
__P((unsigned long rough
));
28 /* Implement double hashing with open addressing. The table size is
29 always a power of two. The secondary ('increment') hash function
30 is forced to return an odd-value, in order to be relatively prime
31 to the table size. This guarantees that the increment can
32 potentially hit every slot in the table during collision
35 void *hash_deleted_item
= &hash_deleted_item
;
37 /* Force the table size to be a power of two, possibly rounding up the
41 hash_init (struct hash_table
*ht
, unsigned long size
,
42 hash_func_t hash_1
, hash_func_t hash_2
, hash_cmp_func_t hash_cmp
)
44 ht
->ht_size
= round_up_2 (size
);
45 ht
->ht_empty_slots
= ht
->ht_size
;
46 ht
->ht_vec
= (void**) CALLOC (struct token
*, ht
->ht_size
);
49 fprintf (stderr
, _("can't allocate %lu bytes for hash table: memory exhausted"),
50 ht
->ht_size
* (unsigned long) sizeof (struct token
*));
54 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
/ 16); /* 93.75% loading factor */
56 ht
->ht_collisions
= 0;
59 ht
->ht_hash_1
= hash_1
;
60 ht
->ht_hash_2
= hash_2
;
61 ht
->ht_compare
= hash_cmp
;
64 /* Load an array of items into 'ht'. */
67 hash_load (struct hash_table
*ht
, void *item_table
,
68 unsigned long cardinality
, unsigned long size
)
70 char *items
= (char *) item_table
;
73 hash_insert (ht
, items
);
78 /* Returns the address of the table slot matching 'key'. If 'key' is
79 not found, return the address of an empty slot suitable for
80 inserting 'key'. The caller is responsible for incrementing
81 ht_fill on insertion. */
84 hash_find_slot (struct hash_table
*ht
, const void *key
)
87 void **deleted_slot
= 0;
88 unsigned int hash_2
= 0;
89 unsigned int hash_1
= (*ht
->ht_hash_1
) (key
);
94 hash_1
&= (ht
->ht_size
- 1);
95 slot
= &ht
->ht_vec
[hash_1
];
98 return (deleted_slot
? deleted_slot
: slot
);
99 if (*slot
== hash_deleted_item
)
101 if (deleted_slot
== 0)
108 if ((*ht
->ht_compare
) (key
, *slot
) == 0)
113 hash_2
= (*ht
->ht_hash_2
) (key
) | 1;
119 hash_find_item (struct hash_table
*ht
, const void *key
)
121 void **slot
= hash_find_slot (ht
, key
);
122 return ((HASH_VACANT (*slot
)) ? 0 : *slot
);
126 hash_insert (struct hash_table
*ht
, const void *item
)
128 void **slot
= hash_find_slot (ht
, item
);
129 const void *old_item
= *slot
;
130 hash_insert_at (ht
, item
, slot
);
131 return (void *)((HASH_VACANT (old_item
)) ? 0 : old_item
);
135 hash_insert_at (struct hash_table
*ht
, const void *item
, const void *slot
)
137 const void *old_item
= *(void **) slot
;
138 if (HASH_VACANT (old_item
))
142 ht
->ht_empty_slots
--;
145 *(void const **) slot
= item
;
146 if (ht
->ht_empty_slots
< ht
->ht_size
- ht
->ht_capacity
)
149 return (void *) hash_find_slot (ht
, item
);
152 return (void *) slot
;
156 hash_delete (struct hash_table
*ht
, const void *item
)
158 void **slot
= hash_find_slot (ht
, item
);
159 return hash_delete_at (ht
, slot
);
163 hash_delete_at (struct hash_table
*ht
, const void *slot
)
165 void *item
= *(void **) slot
;
166 if (!HASH_VACANT (item
))
168 *(void const **) slot
= hash_deleted_item
;
177 hash_free_items (struct hash_table
*ht
)
179 void **vec
= ht
->ht_vec
;
180 void **end
= &vec
[ht
->ht_size
];
181 for (; vec
< end
; vec
++)
184 if (!HASH_VACANT (item
))
189 ht
->ht_empty_slots
= ht
->ht_size
;
193 hash_delete_items (struct hash_table
*ht
)
195 void **vec
= ht
->ht_vec
;
196 void **end
= &vec
[ht
->ht_size
];
197 for (; vec
< end
; vec
++)
200 ht
->ht_collisions
= 0;
203 ht
->ht_empty_slots
= ht
->ht_size
;
207 hash_free (struct hash_table
*ht
, int free_items
)
210 hash_free_items (ht
);
214 ht
->ht_empty_slots
= ht
->ht_size
;
222 hash_map (struct hash_table
*ht
, hash_map_func_t map
)
225 void **end
= &ht
->ht_vec
[ht
->ht_size
];
227 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
229 if (!HASH_VACANT (*slot
))
235 hash_map_arg (struct hash_table
*ht
, hash_map_arg_func_t map
, void *arg
)
238 void **end
= &ht
->ht_vec
[ht
->ht_size
];
240 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
242 if (!HASH_VACANT (*slot
))
247 /* Double the size of the hash table in the event of overflow... */
250 hash_rehash (struct hash_table
*ht
)
252 unsigned long old_ht_size
= ht
->ht_size
;
253 void **old_vec
= ht
->ht_vec
;
256 if (ht
->ht_fill
>= ht
->ht_capacity
)
259 ht
->ht_capacity
= ht
->ht_size
- (ht
->ht_size
>> 4);
262 ht
->ht_vec
= (void **) CALLOC (struct token
*, ht
->ht_size
);
264 for (ovp
= old_vec
; ovp
< &old_vec
[old_ht_size
]; ovp
++)
266 if (! HASH_VACANT (*ovp
))
268 void **slot
= hash_find_slot (ht
, *ovp
);
272 ht
->ht_empty_slots
= ht
->ht_size
- ht
->ht_fill
;
277 hash_print_stats (struct hash_table
*ht
, FILE *out_FILE
)
279 /* GKM FIXME: honor NO_FLOAT */
280 fprintf (out_FILE
, _("Load=%ld/%ld=%.0f%%, "), ht
->ht_fill
, ht
->ht_size
,
281 100.0 * (double) ht
->ht_fill
/ (double) ht
->ht_size
);
282 fprintf (out_FILE
, _("Rehash=%d, "), ht
->ht_rehashes
);
283 fprintf (out_FILE
, _("Collisions=%ld/%ld=%.0f%%"), ht
->ht_collisions
, ht
->ht_lookups
,
285 ? (100.0 * (double) ht
->ht_collisions
/ (double) ht
->ht_lookups
)
289 /* Dump all items into a NULL-terminated vector. Use the
290 user-supplied vector, or malloc one. */
293 hash_dump (struct hash_table
*ht
, void **vector_0
, qsort_cmp_t compare
)
297 void **end
= &ht
->ht_vec
[ht
->ht_size
];
300 vector_0
= MALLOC (void *, ht
->ht_fill
+ 1);
303 for (slot
= ht
->ht_vec
; slot
< end
; slot
++)
304 if (!HASH_VACANT (*slot
))
309 qsort (vector_0
, ht
->ht_fill
, sizeof (void *), compare
);
313 /* Round a given number up to the nearest power of 2. */
316 round_up_2 (unsigned long n
)
324 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
325 /* We only need this on systems where unsigned long is >32 bits. */