1/* hash - implement simple hashing table with string based keys. 2 Copyright (C) 1994-1995, 2000-2004 Free Software Foundation, Inc. 3 Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994. 4 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) 8 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; if not, write to the Free Software Foundation, 17 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 18 19#if HAVE_CONFIG_H 20# include <config.h> 21#endif 22 23/* Specification. */ 24#include "hash.h" 25 26#include <stdlib.h> 27#include <string.h> 28#include <stdio.h> 29#include <limits.h> 30#include <sys/types.h> 31 32#include <obstack.h> 33 34#include "xalloc.h" 35 36#define obstack_chunk_alloc xmalloc 37#define obstack_chunk_free free 38 39typedef struct hash_entry 40{ 41 unsigned long used; 42 const void *key; 43 size_t keylen; 44 void *data; 45 struct hash_entry *next; 46} 47hash_entry; 48 49/* Forward declaration of local functions. */ 50static void insert_entry_2 (hash_table *htab, 51 const void *key, size_t keylen, 52 unsigned long int hval, size_t idx, void *data); 53static size_t lookup (hash_table *htab, 54 const void *key, size_t keylen, 55 unsigned long int hval); 56static unsigned long compute_hashval (const void *key, size_t keylen); 57static int is_prime (unsigned long int candidate); 58 59 60int 61init_hash (hash_table *htab, unsigned long int init_size) 62{ 63 /* We need the size to be a prime. */ 64 init_size = next_prime (init_size); 65 66 /* Initialize the data structure. */ 67 htab->size = init_size; 68 htab->filled = 0; 69 htab->first = NULL; 70 htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry)); 71 72 obstack_init (&htab->mem_pool); 73 74 return 0; 75} 76 77 78int 79delete_hash (hash_table *htab) 80{ 81 free (htab->table); 82 obstack_free (&htab->mem_pool, NULL); 83 return 0; 84} 85 86 87int 88insert_entry (hash_table *htab, const void *key, size_t keylen, void *data) 89{ 90 unsigned long int hval = compute_hashval (key, keylen); 91 hash_entry *table = (hash_entry *) htab->table; 92 size_t idx = lookup (htab, key, keylen, hval); 93 94 if (table[idx].used) 95 /* We don't want to overwrite the old value. */ 96 return -1; 97 else 98 { 99 /* An empty bucket has been found. */ 100 insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen), 101 keylen, hval, idx, data); 102 return 0; 103 } 104} 105 106static void 107insert_entry_2 (hash_table *htab, 108 const void *key, size_t keylen, 109 unsigned long int hval, size_t idx, void *data) 110{ 111 hash_entry *table = (hash_entry *) htab->table; 112 113 table[idx].used = hval; 114 table[idx].key = key; 115 table[idx].keylen = keylen; 116 table[idx].data = data; 117 118 /* List the new value in the list. */ 119 if ((hash_entry *) htab->first == NULL) 120 { 121 table[idx].next = &table[idx]; 122 *(hash_entry **) &htab->first = &table[idx]; 123 } 124 else 125 { 126 table[idx].next = ((hash_entry *) htab->first)->next; 127 ((hash_entry *) htab->first)->next = &table[idx]; 128 *(hash_entry **) &htab->first = &table[idx]; 129 } 130 131 ++htab->filled; 132 if (100 * htab->filled > 75 * htab->size) 133 { 134 /* Table is filled more than 75%. Resize the table. */ 135 unsigned long int old_size = htab->size; 136 137 htab->size = next_prime (htab->size * 2); 138 htab->filled = 0; 139 htab->first = NULL; 140 htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry)); 141 142 for (idx = 1; idx <= old_size; ++idx) 143 if (table[idx].used) 144 insert_entry_2 (htab, table[idx].key, table[idx].keylen, 145 table[idx].used, 146 lookup (htab, table[idx].key, table[idx].keylen, 147 table[idx].used), 148 table[idx].data); 149 150 free (table); 151 } 152} 153 154 155int 156find_entry (hash_table *htab, const void *key, size_t keylen, void **result) 157{ 158 hash_entry *table = (hash_entry *) htab->table; 159 size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); 160 161 if (table[idx].used == 0) 162 return -1; 163 164 *result = table[idx].data; 165 return 0; 166} 167 168 169int 170iterate_table (hash_table *htab, void **ptr, const void **key, size_t *keylen, 171 void **data) 172{ 173 if (*ptr == NULL) 174 { 175 if (htab->first == NULL) 176 return -1; 177 *ptr = (void *) ((hash_entry *) htab->first)->next; 178 } 179 else 180 { 181 if (*ptr == htab->first) 182 return -1; 183 *ptr = (void *) (((hash_entry *) *ptr)->next); 184 } 185 186 *key = ((hash_entry *) *ptr)->key; 187 *keylen = ((hash_entry *) *ptr)->keylen; 188 *data = ((hash_entry *) *ptr)->data; 189 return 0; 190} 191 192 193/* References: 194 [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 195 [Knuth] The Art of Computer Programming, part3 (6.4) */ 196 197static size_t 198lookup (hash_table *htab, 199 const void *key, size_t keylen, 200 unsigned long int hval) 201{ 202 unsigned long int hash; 203 size_t idx; 204 hash_entry *table = (hash_entry *) htab->table; 205 206 /* First hash function: simply take the modul but prevent zero. */ 207 hash = 1 + hval % htab->size; 208 209 idx = hash; 210 211 if (table[idx].used) 212 { 213 if (table[idx].used == hval && table[idx].keylen == keylen 214 && memcmp (table[idx].key, key, keylen) == 0) 215 return idx; 216 217 /* Second hash function as suggested in [Knuth]. */ 218 hash = 1 + hval % (htab->size - 2); 219 220 do 221 { 222 if (idx <= hash) 223 idx = htab->size + idx - hash; 224 else 225 idx -= hash; 226 227 /* If entry is found use it. */ 228 if (table[idx].used == hval && table[idx].keylen == keylen 229 && memcmp (table[idx].key, key, keylen) == 0) 230 return idx; 231 } 232 while (table[idx].used); 233 } 234 return idx; 235} 236 237 238static unsigned long 239compute_hashval (const void *key, size_t keylen) 240{ 241 size_t cnt; 242 unsigned long int hval; 243 244 /* Compute the hash value for the given string. The algorithm 245 is taken from [Aho,Sethi,Ullman]. */ 246 cnt = 0; 247 hval = keylen; 248 while (cnt < keylen) 249 { 250 hval = (hval << 9) | (hval >> (sizeof (unsigned long) * CHAR_BIT - 9)); 251 hval += (unsigned long int) *(((const char *) key) + cnt++); 252 } 253 return hval != 0 ? hval : ~((unsigned long) 0); 254} 255 256 257unsigned long 258next_prime (unsigned long int seed) 259{ 260 /* Make it definitely odd. */ 261 seed |= 1; 262 263 while (!is_prime (seed)) 264 seed += 2; 265 266 return seed; 267} 268 269 270static int 271is_prime (unsigned long int candidate) 272{ 273 /* No even number and none less than 10 will be passed here. */ 274 unsigned long int divn = 3; 275 unsigned long int sq = divn * divn; 276 277 while (sq < candidate && candidate % divn != 0) 278 { 279 ++divn; 280 sq += 4 * divn; 281 ++divn; 282 } 283 284 return candidate % divn != 0; 285} 286