[279] | 1 | /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
|
---|
| 2 |
|
---|
| 3 | /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
|
---|
| 4 |
|
---|
| 5 | #include <stdio.h>
|
---|
| 6 | #include <stdlib.h>
|
---|
| 7 | #include <string.h>
|
---|
| 8 |
|
---|
| 9 | #ifdef _WIN32
|
---|
| 10 | #include <malloc.h>
|
---|
| 11 | #endif
|
---|
| 12 |
|
---|
| 13 | #include "regint.h"
|
---|
| 14 | #include "st.h"
|
---|
| 15 |
|
---|
| 16 | typedef struct st_table_entry st_table_entry;
|
---|
| 17 |
|
---|
| 18 | struct st_table_entry {
|
---|
| 19 | unsigned int hash;
|
---|
| 20 | st_data_t key;
|
---|
| 21 | st_data_t record;
|
---|
| 22 | st_table_entry *next;
|
---|
| 23 | };
|
---|
| 24 |
|
---|
| 25 | #define ST_DEFAULT_MAX_DENSITY 5
|
---|
| 26 | #define ST_DEFAULT_INIT_TABLE_SIZE 11
|
---|
| 27 |
|
---|
| 28 | /*
|
---|
| 29 | * DEFAULT_MAX_DENSITY is the default for the largest we allow the
|
---|
| 30 | * average number of items per bin before increasing the number of
|
---|
| 31 | * bins
|
---|
| 32 | *
|
---|
| 33 | * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
|
---|
| 34 | * allocated initially
|
---|
| 35 | *
|
---|
| 36 | */
|
---|
| 37 |
|
---|
| 38 | static int numcmp(long, long);
|
---|
| 39 | static int numhash(long);
|
---|
| 40 | static struct st_hash_type type_numhash = {
|
---|
| 41 | numcmp,
|
---|
| 42 | numhash,
|
---|
| 43 | };
|
---|
| 44 |
|
---|
| 45 | /* extern int strcmp(const char *, const char *); */
|
---|
| 46 | static int strhash(const char *);
|
---|
| 47 | static struct st_hash_type type_strhash = {
|
---|
| 48 | strcmp,
|
---|
| 49 | strhash,
|
---|
| 50 | };
|
---|
| 51 |
|
---|
| 52 | static void rehash(st_table *);
|
---|
| 53 |
|
---|
| 54 | #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
|
---|
| 55 | #define Calloc(n,s) (char*)xcalloc((n),(s))
|
---|
| 56 |
|
---|
| 57 | #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
|
---|
| 58 |
|
---|
| 59 | #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
|
---|
| 60 | #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
|
---|
| 61 |
|
---|
| 62 | /*
|
---|
| 63 | * MINSIZE is the minimum size of a dictionary.
|
---|
| 64 | */
|
---|
| 65 |
|
---|
| 66 | #define MINSIZE 8
|
---|
| 67 |
|
---|
| 68 | /*
|
---|
| 69 | Table of prime numbers 2^n+a, 2<=n<=30.
|
---|
| 70 | */
|
---|
| 71 | static const long primes[] = {
|
---|
| 72 | 8 + 3,
|
---|
| 73 | 16 + 3,
|
---|
| 74 | 32 + 5,
|
---|
| 75 | 64 + 3,
|
---|
| 76 | 128 + 3,
|
---|
| 77 | 256 + 27,
|
---|
| 78 | 512 + 9,
|
---|
| 79 | 1024 + 9,
|
---|
| 80 | 2048 + 5,
|
---|
| 81 | 4096 + 3,
|
---|
| 82 | 8192 + 27,
|
---|
| 83 | 16384 + 43,
|
---|
| 84 | 32768 + 3,
|
---|
| 85 | 65536 + 45,
|
---|
| 86 | 131072 + 29,
|
---|
| 87 | 262144 + 3,
|
---|
| 88 | 524288 + 21,
|
---|
| 89 | 1048576 + 7,
|
---|
| 90 | 2097152 + 17,
|
---|
| 91 | 4194304 + 15,
|
---|
| 92 | 8388608 + 9,
|
---|
| 93 | 16777216 + 43,
|
---|
| 94 | 33554432 + 35,
|
---|
| 95 | 67108864 + 15,
|
---|
| 96 | 134217728 + 29,
|
---|
| 97 | 268435456 + 3,
|
---|
| 98 | 536870912 + 11,
|
---|
| 99 | 1073741824 + 85,
|
---|
| 100 | 0
|
---|
| 101 | };
|
---|
| 102 |
|
---|
| 103 | static int
|
---|
| 104 | new_size(size)
|
---|
| 105 | int size;
|
---|
| 106 | {
|
---|
| 107 | int i;
|
---|
| 108 |
|
---|
| 109 | #if 0
|
---|
| 110 | for (i=3; i<31; i++) {
|
---|
| 111 | if ((1<<i) > size) return 1<<i;
|
---|
| 112 | }
|
---|
| 113 | return -1;
|
---|
| 114 | #else
|
---|
| 115 | int newsize;
|
---|
| 116 |
|
---|
| 117 | for (i = 0, newsize = MINSIZE;
|
---|
| 118 | i < (int )(sizeof(primes)/sizeof(primes[0]));
|
---|
| 119 | i++, newsize <<= 1)
|
---|
| 120 | {
|
---|
| 121 | if (newsize > size) return primes[i];
|
---|
| 122 | }
|
---|
| 123 | /* Ran out of polynomials */
|
---|
| 124 | return -1; /* should raise exception */
|
---|
| 125 | #endif
|
---|
| 126 | }
|
---|
| 127 |
|
---|
| 128 | #ifdef HASH_LOG
|
---|
| 129 | static int collision = 0;
|
---|
| 130 | static int init_st = 0;
|
---|
| 131 |
|
---|
| 132 | static void
|
---|
| 133 | stat_col()
|
---|
| 134 | {
|
---|
| 135 | FILE *f = fopen("/tmp/col", "w");
|
---|
| 136 | fprintf(f, "collision: %d\n", collision);
|
---|
| 137 | fclose(f);
|
---|
| 138 | }
|
---|
| 139 | #endif
|
---|
| 140 |
|
---|
| 141 | st_table*
|
---|
| 142 | st_init_table_with_size(type, size)
|
---|
| 143 | struct st_hash_type *type;
|
---|
| 144 | int size;
|
---|
| 145 | {
|
---|
| 146 | st_table *tbl;
|
---|
| 147 |
|
---|
| 148 | #ifdef HASH_LOG
|
---|
| 149 | if (init_st == 0) {
|
---|
| 150 | init_st = 1;
|
---|
| 151 | atexit(stat_col);
|
---|
| 152 | }
|
---|
| 153 | #endif
|
---|
| 154 |
|
---|
| 155 | size = new_size(size); /* round up to prime number */
|
---|
| 156 |
|
---|
| 157 | tbl = alloc(st_table);
|
---|
| 158 | tbl->type = type;
|
---|
| 159 | tbl->num_entries = 0;
|
---|
| 160 | tbl->num_bins = size;
|
---|
| 161 | tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
|
---|
| 162 |
|
---|
| 163 | return tbl;
|
---|
| 164 | }
|
---|
| 165 |
|
---|
| 166 | st_table*
|
---|
| 167 | st_init_table(type)
|
---|
| 168 | struct st_hash_type *type;
|
---|
| 169 | {
|
---|
| 170 | return st_init_table_with_size(type, 0);
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | st_table*
|
---|
| 174 | st_init_numtable(void)
|
---|
| 175 | {
|
---|
| 176 | return st_init_table(&type_numhash);
|
---|
| 177 | }
|
---|
| 178 |
|
---|
| 179 | st_table*
|
---|
| 180 | st_init_numtable_with_size(size)
|
---|
| 181 | int size;
|
---|
| 182 | {
|
---|
| 183 | return st_init_table_with_size(&type_numhash, size);
|
---|
| 184 | }
|
---|
| 185 |
|
---|
| 186 | st_table*
|
---|
| 187 | st_init_strtable(void)
|
---|
| 188 | {
|
---|
| 189 | return st_init_table(&type_strhash);
|
---|
| 190 | }
|
---|
| 191 |
|
---|
| 192 | st_table*
|
---|
| 193 | st_init_strtable_with_size(size)
|
---|
| 194 | int size;
|
---|
| 195 | {
|
---|
| 196 | return st_init_table_with_size(&type_strhash, size);
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 | void
|
---|
| 200 | st_free_table(table)
|
---|
| 201 | st_table *table;
|
---|
| 202 | {
|
---|
| 203 | register st_table_entry *ptr, *next;
|
---|
| 204 | int i;
|
---|
| 205 |
|
---|
| 206 | for(i = 0; i < table->num_bins; i++) {
|
---|
| 207 | ptr = table->bins[i];
|
---|
| 208 | while (ptr != 0) {
|
---|
| 209 | next = ptr->next;
|
---|
| 210 | free(ptr);
|
---|
| 211 | ptr = next;
|
---|
| 212 | }
|
---|
| 213 | }
|
---|
| 214 | free(table->bins);
|
---|
| 215 | free(table);
|
---|
| 216 | }
|
---|
| 217 |
|
---|
| 218 | #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
|
---|
| 219 | ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
|
---|
| 220 |
|
---|
| 221 | #ifdef HASH_LOG
|
---|
| 222 | #define COLLISION collision++
|
---|
| 223 | #else
|
---|
| 224 | #define COLLISION
|
---|
| 225 | #endif
|
---|
| 226 |
|
---|
| 227 | #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
|
---|
| 228 | bin_pos = hash_val%(table)->num_bins;\
|
---|
| 229 | ptr = (table)->bins[bin_pos];\
|
---|
| 230 | if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
|
---|
| 231 | COLLISION;\
|
---|
| 232 | while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
|
---|
| 233 | ptr = ptr->next;\
|
---|
| 234 | }\
|
---|
| 235 | ptr = ptr->next;\
|
---|
| 236 | }\
|
---|
| 237 | } while (0)
|
---|
| 238 |
|
---|
| 239 | int
|
---|
| 240 | st_lookup(table, key, value)
|
---|
| 241 | st_table *table;
|
---|
| 242 | register st_data_t key;
|
---|
| 243 | st_data_t *value;
|
---|
| 244 | {
|
---|
| 245 | unsigned int hash_val, bin_pos;
|
---|
| 246 | register st_table_entry *ptr;
|
---|
| 247 |
|
---|
| 248 | hash_val = do_hash(key, table);
|
---|
| 249 | FIND_ENTRY(table, ptr, hash_val, bin_pos);
|
---|
| 250 |
|
---|
| 251 | if (ptr == 0) {
|
---|
| 252 | return 0;
|
---|
| 253 | }
|
---|
| 254 | else {
|
---|
| 255 | if (value != 0) *value = ptr->record;
|
---|
| 256 | return 1;
|
---|
| 257 | }
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
|
---|
| 261 | do {\
|
---|
| 262 | st_table_entry *entry;\
|
---|
| 263 | if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
|
---|
| 264 | rehash(table);\
|
---|
| 265 | bin_pos = hash_val % table->num_bins;\
|
---|
| 266 | }\
|
---|
| 267 | \
|
---|
| 268 | entry = alloc(st_table_entry);\
|
---|
| 269 | \
|
---|
| 270 | entry->hash = hash_val;\
|
---|
| 271 | entry->key = key;\
|
---|
| 272 | entry->record = value;\
|
---|
| 273 | entry->next = table->bins[bin_pos];\
|
---|
| 274 | table->bins[bin_pos] = entry;\
|
---|
| 275 | table->num_entries++;\
|
---|
| 276 | } while (0)
|
---|
| 277 |
|
---|
| 278 | int
|
---|
| 279 | st_insert(table, key, value)
|
---|
| 280 | register st_table *table;
|
---|
| 281 | register st_data_t key;
|
---|
| 282 | st_data_t value;
|
---|
| 283 | {
|
---|
| 284 | unsigned int hash_val, bin_pos;
|
---|
| 285 | register st_table_entry *ptr;
|
---|
| 286 |
|
---|
| 287 | hash_val = do_hash(key, table);
|
---|
| 288 | FIND_ENTRY(table, ptr, hash_val, bin_pos);
|
---|
| 289 |
|
---|
| 290 | if (ptr == 0) {
|
---|
| 291 | ADD_DIRECT(table, key, value, hash_val, bin_pos);
|
---|
| 292 | return 0;
|
---|
| 293 | }
|
---|
| 294 | else {
|
---|
| 295 | ptr->record = value;
|
---|
| 296 | return 1;
|
---|
| 297 | }
|
---|
| 298 | }
|
---|
| 299 |
|
---|
| 300 | void
|
---|
| 301 | st_add_direct(table, key, value)
|
---|
| 302 | st_table *table;
|
---|
| 303 | st_data_t key;
|
---|
| 304 | st_data_t value;
|
---|
| 305 | {
|
---|
| 306 | unsigned int hash_val, bin_pos;
|
---|
| 307 |
|
---|
| 308 | hash_val = do_hash(key, table);
|
---|
| 309 | bin_pos = hash_val % table->num_bins;
|
---|
| 310 | ADD_DIRECT(table, key, value, hash_val, bin_pos);
|
---|
| 311 | }
|
---|
| 312 |
|
---|
| 313 | static void
|
---|
| 314 | rehash(table)
|
---|
| 315 | register st_table *table;
|
---|
| 316 | {
|
---|
| 317 | register st_table_entry *ptr, *next, **new_bins;
|
---|
| 318 | int i, old_num_bins = table->num_bins, new_num_bins;
|
---|
| 319 | unsigned int hash_val;
|
---|
| 320 |
|
---|
| 321 | new_num_bins = new_size(old_num_bins+1);
|
---|
| 322 | new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
|
---|
| 323 |
|
---|
| 324 | for(i = 0; i < old_num_bins; i++) {
|
---|
| 325 | ptr = table->bins[i];
|
---|
| 326 | while (ptr != 0) {
|
---|
| 327 | next = ptr->next;
|
---|
| 328 | hash_val = ptr->hash % new_num_bins;
|
---|
| 329 | ptr->next = new_bins[hash_val];
|
---|
| 330 | new_bins[hash_val] = ptr;
|
---|
| 331 | ptr = next;
|
---|
| 332 | }
|
---|
| 333 | }
|
---|
| 334 | free(table->bins);
|
---|
| 335 | table->num_bins = new_num_bins;
|
---|
| 336 | table->bins = new_bins;
|
---|
| 337 | }
|
---|
| 338 |
|
---|
| 339 | st_table*
|
---|
| 340 | st_copy(old_table)
|
---|
| 341 | st_table *old_table;
|
---|
| 342 | {
|
---|
| 343 | st_table *new_table;
|
---|
| 344 | st_table_entry *ptr, *entry;
|
---|
| 345 | int i, num_bins = old_table->num_bins;
|
---|
| 346 |
|
---|
| 347 | new_table = alloc(st_table);
|
---|
| 348 | if (new_table == 0) {
|
---|
| 349 | return 0;
|
---|
| 350 | }
|
---|
| 351 |
|
---|
| 352 | *new_table = *old_table;
|
---|
| 353 | new_table->bins = (st_table_entry**)
|
---|
| 354 | Calloc((unsigned)num_bins, sizeof(st_table_entry*));
|
---|
| 355 |
|
---|
| 356 | if (new_table->bins == 0) {
|
---|
| 357 | free(new_table);
|
---|
| 358 | return 0;
|
---|
| 359 | }
|
---|
| 360 |
|
---|
| 361 | for(i = 0; i < num_bins; i++) {
|
---|
| 362 | new_table->bins[i] = 0;
|
---|
| 363 | ptr = old_table->bins[i];
|
---|
| 364 | while (ptr != 0) {
|
---|
| 365 | entry = alloc(st_table_entry);
|
---|
| 366 | if (entry == 0) {
|
---|
| 367 | free(new_table->bins);
|
---|
| 368 | free(new_table);
|
---|
| 369 | return 0;
|
---|
| 370 | }
|
---|
| 371 | *entry = *ptr;
|
---|
| 372 | entry->next = new_table->bins[i];
|
---|
| 373 | new_table->bins[i] = entry;
|
---|
| 374 | ptr = ptr->next;
|
---|
| 375 | }
|
---|
| 376 | }
|
---|
| 377 | return new_table;
|
---|
| 378 | }
|
---|
| 379 |
|
---|
| 380 | int
|
---|
| 381 | st_delete(table, key, value)
|
---|
| 382 | register st_table *table;
|
---|
| 383 | register st_data_t *key;
|
---|
| 384 | st_data_t *value;
|
---|
| 385 | {
|
---|
| 386 | unsigned int hash_val;
|
---|
| 387 | st_table_entry *tmp;
|
---|
| 388 | register st_table_entry *ptr;
|
---|
| 389 |
|
---|
| 390 | hash_val = do_hash_bin(*key, table);
|
---|
| 391 | ptr = table->bins[hash_val];
|
---|
| 392 |
|
---|
| 393 | if (ptr == 0) {
|
---|
| 394 | if (value != 0) *value = 0;
|
---|
| 395 | return 0;
|
---|
| 396 | }
|
---|
| 397 |
|
---|
| 398 | if (EQUAL(table, *key, ptr->key)) {
|
---|
| 399 | table->bins[hash_val] = ptr->next;
|
---|
| 400 | table->num_entries--;
|
---|
| 401 | if (value != 0) *value = ptr->record;
|
---|
| 402 | *key = ptr->key;
|
---|
| 403 | free(ptr);
|
---|
| 404 | return 1;
|
---|
| 405 | }
|
---|
| 406 |
|
---|
| 407 | for(; ptr->next != 0; ptr = ptr->next) {
|
---|
| 408 | if (EQUAL(table, ptr->next->key, *key)) {
|
---|
| 409 | tmp = ptr->next;
|
---|
| 410 | ptr->next = ptr->next->next;
|
---|
| 411 | table->num_entries--;
|
---|
| 412 | if (value != 0) *value = tmp->record;
|
---|
| 413 | *key = tmp->key;
|
---|
| 414 | free(tmp);
|
---|
| 415 | return 1;
|
---|
| 416 | }
|
---|
| 417 | }
|
---|
| 418 |
|
---|
| 419 | return 0;
|
---|
| 420 | }
|
---|
| 421 |
|
---|
| 422 | int
|
---|
| 423 | st_delete_safe(table, key, value, never)
|
---|
| 424 | register st_table *table;
|
---|
| 425 | register st_data_t *key;
|
---|
| 426 | st_data_t *value;
|
---|
| 427 | st_data_t never;
|
---|
| 428 | {
|
---|
| 429 | unsigned int hash_val;
|
---|
| 430 | register st_table_entry *ptr;
|
---|
| 431 |
|
---|
| 432 | hash_val = do_hash_bin(*key, table);
|
---|
| 433 | ptr = table->bins[hash_val];
|
---|
| 434 |
|
---|
| 435 | if (ptr == 0) {
|
---|
| 436 | if (value != 0) *value = 0;
|
---|
| 437 | return 0;
|
---|
| 438 | }
|
---|
| 439 |
|
---|
| 440 | for(; ptr != 0; ptr = ptr->next) {
|
---|
| 441 | if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
|
---|
| 442 | table->num_entries--;
|
---|
| 443 | *key = ptr->key;
|
---|
| 444 | if (value != 0) *value = ptr->record;
|
---|
| 445 | ptr->key = ptr->record = never;
|
---|
| 446 | return 1;
|
---|
| 447 | }
|
---|
| 448 | }
|
---|
| 449 |
|
---|
| 450 | return 0;
|
---|
| 451 | }
|
---|
| 452 |
|
---|
| 453 | static int
|
---|
| 454 | #if defined(__GNUC__)
|
---|
| 455 | delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,
|
---|
| 456 | st_data_t never)
|
---|
| 457 | #else
|
---|
| 458 | delete_never(key, value, never)
|
---|
| 459 | st_data_t key, value, never;
|
---|
| 460 | #endif
|
---|
| 461 | {
|
---|
| 462 | if (value == never) return ST_DELETE;
|
---|
| 463 | return ST_CONTINUE;
|
---|
| 464 | }
|
---|
| 465 |
|
---|
| 466 | void
|
---|
| 467 | st_cleanup_safe(table, never)
|
---|
| 468 | st_table *table;
|
---|
| 469 | st_data_t never;
|
---|
| 470 | {
|
---|
| 471 | int num_entries = table->num_entries;
|
---|
| 472 |
|
---|
| 473 | st_foreach(table, delete_never, never);
|
---|
| 474 | table->num_entries = num_entries;
|
---|
| 475 | }
|
---|
| 476 |
|
---|
| 477 | int
|
---|
| 478 | st_foreach(table, func, arg)
|
---|
| 479 | st_table *table;
|
---|
| 480 | int (*func)();
|
---|
| 481 | st_data_t arg;
|
---|
| 482 | {
|
---|
| 483 | st_table_entry *ptr, *last, *tmp;
|
---|
| 484 | enum st_retval retval;
|
---|
| 485 | int i;
|
---|
| 486 |
|
---|
| 487 | for(i = 0; i < table->num_bins; i++) {
|
---|
| 488 | last = 0;
|
---|
| 489 | for(ptr = table->bins[i]; ptr != 0;) {
|
---|
| 490 | retval = (*func)(ptr->key, ptr->record, arg);
|
---|
| 491 | switch (retval) {
|
---|
| 492 | case ST_CHECK: /* check if hash is modified during iteration */
|
---|
| 493 | tmp = 0;
|
---|
| 494 | if (i < table->num_bins) {
|
---|
| 495 | for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
|
---|
| 496 | if (tmp == ptr) break;
|
---|
| 497 | }
|
---|
| 498 | }
|
---|
| 499 | if (!tmp) {
|
---|
| 500 | /* call func with error notice */
|
---|
| 501 | return 1;
|
---|
| 502 | }
|
---|
| 503 | /* fall through */
|
---|
| 504 | case ST_CONTINUE:
|
---|
| 505 | last = ptr;
|
---|
| 506 | ptr = ptr->next;
|
---|
| 507 | break;
|
---|
| 508 | case ST_STOP:
|
---|
| 509 | return 0;
|
---|
| 510 | case ST_DELETE:
|
---|
| 511 | tmp = ptr;
|
---|
| 512 | if (last == 0) {
|
---|
| 513 | table->bins[i] = ptr->next;
|
---|
| 514 | }
|
---|
| 515 | else {
|
---|
| 516 | last->next = ptr->next;
|
---|
| 517 | }
|
---|
| 518 | ptr = ptr->next;
|
---|
| 519 | free(tmp);
|
---|
| 520 | table->num_entries--;
|
---|
| 521 | }
|
---|
| 522 | }
|
---|
| 523 | }
|
---|
| 524 | return 0;
|
---|
| 525 | }
|
---|
| 526 |
|
---|
| 527 | static int
|
---|
| 528 | strhash(string)
|
---|
| 529 | register const char *string;
|
---|
| 530 | {
|
---|
| 531 | register int c;
|
---|
| 532 |
|
---|
| 533 | #ifdef HASH_ELFHASH
|
---|
| 534 | register unsigned int h = 0, g;
|
---|
| 535 |
|
---|
| 536 | while ((c = *string++) != '\0') {
|
---|
| 537 | h = ( h << 4 ) + c;
|
---|
| 538 | if ( g = h & 0xF0000000 )
|
---|
| 539 | h ^= g >> 24;
|
---|
| 540 | h &= ~g;
|
---|
| 541 | }
|
---|
| 542 | return h;
|
---|
| 543 | #elif HASH_PERL
|
---|
| 544 | register int val = 0;
|
---|
| 545 |
|
---|
| 546 | while ((c = *string++) != '\0') {
|
---|
| 547 | val += c;
|
---|
| 548 | val += (val << 10);
|
---|
| 549 | val ^= (val >> 6);
|
---|
| 550 | }
|
---|
| 551 | val += (val << 3);
|
---|
| 552 | val ^= (val >> 11);
|
---|
| 553 |
|
---|
| 554 | return val + (val << 15);
|
---|
| 555 | #else
|
---|
| 556 | register int val = 0;
|
---|
| 557 |
|
---|
| 558 | while ((c = *string++) != '\0') {
|
---|
| 559 | val = val*997 + c;
|
---|
| 560 | }
|
---|
| 561 |
|
---|
| 562 | return val + (val>>5);
|
---|
| 563 | #endif
|
---|
| 564 | }
|
---|
| 565 |
|
---|
| 566 | static int
|
---|
| 567 | numcmp(x, y)
|
---|
| 568 | long x, y;
|
---|
| 569 | {
|
---|
| 570 | return x != y;
|
---|
| 571 | }
|
---|
| 572 |
|
---|
| 573 | static int
|
---|
| 574 | numhash(n)
|
---|
| 575 | long n;
|
---|
| 576 | {
|
---|
| 577 | return n;
|
---|
| 578 | }
|
---|