1a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* hash.c -- hash table maintenance 2a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc. 3a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org> 4a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 5a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerThis program is free software; you can redistribute it and/or modify 6a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerit under the terms of the GNU General Public License as published by 7a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerthe Free Software Foundation; either version 2, or (at your option) 8a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerany later version. 9a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 10a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerThis program is distributed in the hope that it will be useful, 11a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerbut WITHOUT ANY WARRANTY; without even the implied warranty of 12a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerGNU General Public License for more details. 14a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 15a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerYou should have received a copy of the GNU General Public License along with 16a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerthis program; see the file COPYING. If not, write to the Free Software 17a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' TurnerFoundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. */ 18a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 19a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#include "make.h" 20a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#include "hash.h" 21a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 22a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#define CALLOC(t, n) ((t *) calloc (sizeof (t), (n))) 23a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n))) 24a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n))) 25a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n))) 26a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 27a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerstatic void hash_rehash __P((struct hash_table* ht)); 28a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerstatic unsigned long round_up_2 __P((unsigned long rough)); 29a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 30a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Implement double hashing with open addressing. The table size is 31a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner always a power of two. The secondary (`increment') hash function 32a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner is forced to return an odd-value, in order to be relatively prime 33a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner to the table size. This guarantees that the increment can 34a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner potentially hit every slot in the table during collision 35a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner resolution. */ 36a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 37a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid *hash_deleted_item = &hash_deleted_item; 38a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 39a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Force the table size to be a power of two, possibly rounding up the 40a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner given size. */ 41a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 42a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 43a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_init (struct hash_table *ht, unsigned long size, 44a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp) 45a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 46a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_size = round_up_2 (size); 47a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots = ht->ht_size; 48a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size); 49a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (ht->ht_vec == 0) 50a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 51a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"), 52a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_size * sizeof(struct token *)); 53a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner exit (1); 54a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 55a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 56a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */ 57a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill = 0; 58a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_collisions = 0; 59a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_lookups = 0; 60a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_rehashes = 0; 61a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_hash_1 = hash_1; 62a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_hash_2 = hash_2; 63a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_compare = hash_cmp; 64a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 65a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 66a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Load an array of items into `ht'. */ 67a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 68a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 69a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_load (struct hash_table *ht, void *item_table, 70a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner unsigned long cardinality, unsigned long size) 71a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 72a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner char *items = (char *) item_table; 73a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner while (cardinality--) 74a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 75a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_insert (ht, items); 76a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner items += size; 77a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 78a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 79a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 80a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Returns the address of the table slot matching `key'. If `key' is 81a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner not found, return the address of an empty slot suitable for 82a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner inserting `key'. The caller is responsible for incrementing 83a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht_fill on insertion. */ 84a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 85a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid ** 86a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_find_slot (struct hash_table *ht, const void *key) 87a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 88a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot; 89a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **deleted_slot = 0; 90a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner unsigned int hash_2 = 0; 91a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner unsigned int hash_1 = (*ht->ht_hash_1) (key); 92a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 93a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_lookups++; 94a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (;;) 95a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 96a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_1 &= (ht->ht_size - 1); 97a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner slot = &ht->ht_vec[hash_1]; 98a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 99a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (*slot == 0) 100a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return (deleted_slot ? deleted_slot : slot); 101a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (*slot == hash_deleted_item) 102a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 103a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (deleted_slot == 0) 104a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner deleted_slot = slot; 105a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 106a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner else 107a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 108a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (key == *slot) 109a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return slot; 110a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if ((*ht->ht_compare) (key, *slot) == 0) 111a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return slot; 112a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_collisions++; 113a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 114a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!hash_2) 115a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_2 = (*ht->ht_hash_2) (key) | 1; 116a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_1 += hash_2; 117a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 118a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 119a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 120a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid * 121a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_find_item (struct hash_table *ht, const void *key) 122a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 123a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot = hash_find_slot (ht, key); 124a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return ((HASH_VACANT (*slot)) ? 0 : *slot); 125a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 126a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 127a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid * 128a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_insert (struct hash_table *ht, const void *item) 129a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 130a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot = hash_find_slot (ht, item); 131a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner const void *old_item = slot ? *slot : 0; 132a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_insert_at (ht, item, slot); 133a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return (void *)((HASH_VACANT (old_item)) ? 0 : old_item); 134a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 135a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 136a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid * 137a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_insert_at (struct hash_table *ht, const void *item, const void *slot) 138a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 139a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner const void *old_item = *(void **) slot; 140a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (HASH_VACANT (old_item)) 141a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 142a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill++; 143a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (old_item == 0) 144a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots--; 145a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner old_item = item; 146a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 147a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *(void const **) slot = item; 148a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity) 149a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 150a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_rehash (ht); 151a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return (void *) hash_find_slot (ht, item); 152a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 153a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner else 154a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return (void *) slot; 155a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 156a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 157a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid * 158a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_delete (struct hash_table *ht, const void *item) 159a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 160a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot = hash_find_slot (ht, item); 161a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return hash_delete_at (ht, slot); 162a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 163a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 164a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid * 165a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_delete_at (struct hash_table *ht, const void *slot) 166a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 167a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void *item = *(void **) slot; 168a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!HASH_VACANT (item)) 169a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 170a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *(void const **) slot = hash_deleted_item; 171a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill--; 172a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return item; 173a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 174a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner else 175a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return 0; 176a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 177a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 178a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 179a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_free_items (struct hash_table *ht) 180a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 181a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **vec = ht->ht_vec; 182a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **end = &vec[ht->ht_size]; 183a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (; vec < end; vec++) 184a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 185a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void *item = *vec; 186a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!HASH_VACANT (item)) 187a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner free (item); 188a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *vec = 0; 189a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 190a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill = 0; 191a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots = ht->ht_size; 192a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 193a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 194a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 195a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_delete_items (struct hash_table *ht) 196a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 197a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **vec = ht->ht_vec; 198a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **end = &vec[ht->ht_size]; 199a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (; vec < end; vec++) 200a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *vec = 0; 201a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill = 0; 202a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_collisions = 0; 203a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_lookups = 0; 204a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_rehashes = 0; 205a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots = ht->ht_size; 206a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 207a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 208a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 209a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_free (struct hash_table *ht, int free_items) 210a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 211a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (free_items) 212a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner hash_free_items (ht); 213a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner else 214a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 215a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_fill = 0; 216a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots = ht->ht_size; 217a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 218a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner free (ht->ht_vec); 219a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_vec = 0; 220a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_capacity = 0; 221a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 222a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 223a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 224a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_map (struct hash_table *ht, hash_map_func_t map) 225a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 226a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot; 227a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **end = &ht->ht_vec[ht->ht_size]; 228a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 229a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (slot = ht->ht_vec; slot < end; slot++) 230a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 231a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!HASH_VACANT (*slot)) 232a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner (*map) (*slot); 233a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 234a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 235a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 236a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 237a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg) 238a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 239a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot; 240a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **end = &ht->ht_vec[ht->ht_size]; 241a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 242a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (slot = ht->ht_vec; slot < end; slot++) 243a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 244a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!HASH_VACANT (*slot)) 245a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner (*map) (*slot, arg); 246a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 247a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 248a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 249a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Double the size of the hash table in the event of overflow... */ 250a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 251a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerstatic void 252a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_rehash (struct hash_table *ht) 253a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 254a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner unsigned long old_ht_size = ht->ht_size; 255a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **old_vec = ht->ht_vec; 256a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **ovp; 257a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 258a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (ht->ht_fill >= ht->ht_capacity) 259a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 260a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_size *= 2; 261a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4); 262a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 263a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_rehashes++; 264a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size); 265a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 266a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++) 267a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 268a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (! HASH_VACANT (*ovp)) 269a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner { 270a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot = hash_find_slot (ht, *ovp); 271a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *slot = *ovp; 272a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 273a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner } 274a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ht->ht_empty_slots = ht->ht_size - ht->ht_fill; 275a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner free (old_vec); 276a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 277a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 278a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid 279a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_print_stats (struct hash_table *ht, FILE *out_FILE) 280a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 281a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner /* GKM FIXME: honor NO_FLOAT */ 282a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size, 283a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 100.0 * (double) ht->ht_fill / (double) ht->ht_size); 284a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes); 285a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups, 286a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner (ht->ht_lookups 287a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups) 288a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner : 0)); 289a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 290a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 291a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Dump all items into a NULL-terminated vector. Use the 292a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner user-supplied vector, or malloc one. */ 293a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 294a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnervoid ** 295a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerhash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare) 296a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 297a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **vector; 298a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **slot; 299a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner void **end = &ht->ht_vec[ht->ht_size]; 300a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 301a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (vector_0 == 0) 302a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner vector_0 = MALLOC (void *, ht->ht_fill + 1); 303a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner vector = vector_0; 304a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 305a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner for (slot = ht->ht_vec; slot < end; slot++) 306a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (!HASH_VACANT (*slot)) 307a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *vector++ = *slot; 308a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner *vector = 0; 309a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 310a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner if (compare) 311a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner qsort (vector_0, ht->ht_fill, sizeof (void *), compare); 312a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return vector_0; 313a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 314a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 315a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner/* Round a given number up to the nearest power of 2. */ 316a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 317a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerstatic unsigned long 318a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turnerround_up_2 (unsigned long n) 319a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner{ 320a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 1); 321a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 2); 322a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 4); 323a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 8); 324a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 16); 325a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 326a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295 327a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner /* We only need this on systems where unsigned long is >32 bits. */ 328a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner n |= (n >> 32); 329a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner#endif 330a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner 331a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner return n + 1; 332a86d4c1bde70365cbbe874ad9ddb3f06916d2085David 'Digit' Turner} 333