1219820Sjeff/* 2219820Sjeff * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved. 3219820Sjeff * Copyright (c) 2002-2006 Mellanox Technologies LTD. All rights reserved. 4219820Sjeff * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5219820Sjeff * 6219820Sjeff * This software is available to you under a choice of one of two 7219820Sjeff * licenses. You may choose to be licensed under the terms of the GNU 8219820Sjeff * General Public License (GPL) Version 2, available from the file 9219820Sjeff * COPYING in the main directory of this source tree, or the 10219820Sjeff * OpenIB.org BSD license below: 11219820Sjeff * 12219820Sjeff * Redistribution and use in source and binary forms, with or 13219820Sjeff * without modification, are permitted provided that the following 14219820Sjeff * conditions are met: 15219820Sjeff * 16219820Sjeff * - Redistributions of source code must retain the above 17219820Sjeff * copyright notice, this list of conditions and the following 18219820Sjeff * disclaimer. 19219820Sjeff * 20219820Sjeff * - Redistributions in binary form must reproduce the above 21219820Sjeff * copyright notice, this list of conditions and the following 22219820Sjeff * disclaimer in the documentation and/or other materials 23219820Sjeff * provided with the distribution. 24219820Sjeff * 25219820Sjeff * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26219820Sjeff * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27219820Sjeff * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28219820Sjeff * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29219820Sjeff * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30219820Sjeff * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31219820Sjeff * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32219820Sjeff * SOFTWARE. 33219820Sjeff * 34219820Sjeff */ 35219820Sjeff 36219820Sjeff/* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */ 37219820Sjeff 38219820Sjeff#if HAVE_CONFIG_H 39219820Sjeff# include <config.h> 40219820Sjeff#endif /* HAVE_CONFIG_H */ 41219820Sjeff 42219820Sjeff#include <stdio.h> 43219820Sjeff#include <string.h> 44219820Sjeff#include <opensm/st.h> 45219820Sjeff 46219820Sjeff#ifdef _WIN32 47219820Sjeff#include <malloc.h> 48219820Sjeff#endif 49219820Sjeff 50219820Sjefftypedef struct st_table_entry st_table_entry; 51219820Sjeff 52219820Sjeffstruct st_table_entry { 53219820Sjeff unsigned int hash; 54219820Sjeff st_data_t key; 55219820Sjeff st_data_t record; 56219820Sjeff st_table_entry *next; 57219820Sjeff}; 58219820Sjeff 59219820Sjeff#define ST_DEFAULT_MAX_DENSITY 5 60219820Sjeff#define ST_DEFAULT_INIT_TABLE_SIZE 11 61219820Sjeff 62219820Sjeff/* 63219820Sjeff * DEFAULT_MAX_DENSITY is the default for the largest we allow the 64219820Sjeff * average number of items per bin before increasing the number of 65219820Sjeff * bins 66219820Sjeff * 67219820Sjeff * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 68219820Sjeff * allocated initially 69219820Sjeff * 70219820Sjeff */ 71219820Sjeffstatic int numcmp(void *, void *); 72219820Sjeffstatic st_ptr_t numhash(void *); 73219820Sjeffstatic struct st_hash_type type_numhash = { 74219820Sjeff numcmp, 75219820Sjeff numhash, 76219820Sjeff}; 77219820Sjeff 78219820Sjeff/* extern int strcmp(const char *, const char *); */ 79219820Sjeffstatic int strhash(const char *); 80219820Sjeff 81219820Sjeffstatic inline st_ptr_t st_strhash(void *key) 82219820Sjeff{ 83219820Sjeff return strhash((const char *)key); 84219820Sjeff} 85219820Sjeff 86219820Sjeffstatic inline int st_strcmp(void *key1, void *key2) 87219820Sjeff{ 88219820Sjeff return strcmp((const char *)key1, (const char *)key2); 89219820Sjeff} 90219820Sjeff 91219820Sjeffstatic struct st_hash_type type_strhash = { 92219820Sjeff st_strcmp, 93219820Sjeff st_strhash 94219820Sjeff}; 95219820Sjeff 96219820Sjeff#define xmalloc malloc 97219820Sjeff#define xcalloc calloc 98219820Sjeff#define xrealloc realloc 99219820Sjeff#define xfree free 100219820Sjeff 101219820Sjeffstatic void rehash(st_table *); 102219820Sjeff 103219820Sjeff#define alloc(type) (type*)xmalloc(sizeof(type)) 104219820Sjeff#define Calloc(n,s) (char*)xcalloc((n), (s)) 105219820Sjeff 106219820Sjeff#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)(((void*)x),((void *)y)) == 0) 107219820Sjeff 108219820Sjeff#define do_hash(key,table) (unsigned int)(*(table)->type->hash)(((void*)key)) 109219820Sjeff#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 110219820Sjeff 111219820Sjeff/* 112219820Sjeff * MINSIZE is the minimum size of a dictionary. 113219820Sjeff */ 114219820Sjeff 115219820Sjeff#define MINSIZE 8 116219820Sjeff 117219820Sjeff/* 118219820Sjeff Table of prime numbers 2^n+a, 2<=n<=30. 119219820Sjeff*/ 120219820Sjeffstatic long primes[] = { 121219820Sjeff 8 + 3, 122219820Sjeff 16 + 3, 123219820Sjeff 32 + 5, 124219820Sjeff 64 + 3, 125219820Sjeff 128 + 3, 126219820Sjeff 256 + 27, 127219820Sjeff 512 + 9, 128219820Sjeff 1024 + 9, 129219820Sjeff 2048 + 5, 130219820Sjeff 4096 + 3, 131219820Sjeff 8192 + 27, 132219820Sjeff 16384 + 43, 133219820Sjeff 32768 + 3, 134219820Sjeff 65536 + 45, 135219820Sjeff 131072 + 29, 136219820Sjeff 262144 + 3, 137219820Sjeff 524288 + 21, 138219820Sjeff 1048576 + 7, 139219820Sjeff 2097152 + 17, 140219820Sjeff 4194304 + 15, 141219820Sjeff 8388608 + 9, 142219820Sjeff 16777216 + 43, 143219820Sjeff 33554432 + 35, 144219820Sjeff 67108864 + 15, 145219820Sjeff 134217728 + 29, 146219820Sjeff 268435456 + 3, 147219820Sjeff 536870912 + 11, 148219820Sjeff 1073741824 + 85, 149219820Sjeff 0 150219820Sjeff}; 151219820Sjeff 152219820Sjeffstatic int new_size(int size) 153219820Sjeff{ 154219820Sjeff int i; 155219820Sjeff 156219820Sjeff#if 0 157219820Sjeff for (i = 3; i < 31; i++) { 158219820Sjeff if ((1 << i) > size) 159219820Sjeff return 1 << i; 160219820Sjeff } 161219820Sjeff return -1; 162219820Sjeff#else 163219820Sjeff int newsize; 164219820Sjeff 165219820Sjeff for (i = 0, newsize = MINSIZE; 166219820Sjeff i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) { 167219820Sjeff if (newsize > size) 168219820Sjeff return primes[i]; 169219820Sjeff } 170219820Sjeff /* Ran out of polynomials */ 171219820Sjeff return -1; /* should raise exception */ 172219820Sjeff#endif 173219820Sjeff} 174219820Sjeff 175219820Sjeff#ifdef HASH_LOG 176219820Sjeffstatic int collision = 0; 177219820Sjeffstatic int init_st = 0; 178219820Sjeff 179219820Sjeffstatic void stat_col() 180219820Sjeff{ 181219820Sjeff FILE *f = fopen("/var/log/osm_st_col", "w"); 182219820Sjeff fprintf(f, "collision: %d\n", collision); 183219820Sjeff fclose(f); 184219820Sjeff} 185219820Sjeff#endif 186219820Sjeff 187219820Sjeffst_table *st_init_table_with_size(type, size) 188219820Sjeffstruct st_hash_type *type; 189219820Sjeffsize_t size; 190219820Sjeff{ 191219820Sjeff st_table *tbl; 192219820Sjeff 193219820Sjeff#ifdef HASH_LOG 194219820Sjeff if (init_st == 0) { 195219820Sjeff init_st = 1; 196219820Sjeff atexit(stat_col); 197219820Sjeff } 198219820Sjeff#endif 199219820Sjeff 200219820Sjeff size = new_size(size); /* round up to prime number */ 201219820Sjeff 202219820Sjeff tbl = alloc(st_table); 203219820Sjeff tbl->type = type; 204219820Sjeff tbl->num_entries = 0; 205219820Sjeff tbl->num_bins = size; 206219820Sjeff tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *)); 207219820Sjeff 208219820Sjeff return tbl; 209219820Sjeff} 210219820Sjeff 211219820Sjeffst_table *st_init_table(type) 212219820Sjeffstruct st_hash_type *type; 213219820Sjeff{ 214219820Sjeff return st_init_table_with_size(type, 0); 215219820Sjeff} 216219820Sjeff 217219820Sjeffst_table *st_init_numtable(void) 218219820Sjeff{ 219219820Sjeff return st_init_table(&type_numhash); 220219820Sjeff} 221219820Sjeff 222219820Sjeffst_table *st_init_numtable_with_size(size) 223219820Sjeffsize_t size; 224219820Sjeff{ 225219820Sjeff return st_init_table_with_size(&type_numhash, size); 226219820Sjeff} 227219820Sjeff 228219820Sjeffst_table *st_init_strtable(void) 229219820Sjeff{ 230219820Sjeff return st_init_table(&type_strhash); 231219820Sjeff} 232219820Sjeff 233219820Sjeffst_table *st_init_strtable_with_size(size) 234219820Sjeffsize_t size; 235219820Sjeff{ 236219820Sjeff return st_init_table_with_size(&type_strhash, size); 237219820Sjeff} 238219820Sjeff 239219820Sjeffvoid st_free_table(table) 240219820Sjeffst_table *table; 241219820Sjeff{ 242219820Sjeff register st_table_entry *ptr, *next; 243219820Sjeff int i; 244219820Sjeff 245219820Sjeff for (i = 0; i < table->num_bins; i++) { 246219820Sjeff ptr = table->bins[i]; 247219820Sjeff while (ptr != 0) { 248219820Sjeff next = ptr->next; 249219820Sjeff free(ptr); 250219820Sjeff ptr = next; 251219820Sjeff } 252219820Sjeff } 253219820Sjeff free(table->bins); 254219820Sjeff free(table); 255219820Sjeff} 256219820Sjeff 257219820Sjeff#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 258219820Sjeff((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 259219820Sjeff 260219820Sjeff#ifdef HASH_LOG 261219820Sjeff#define COLLISION collision++ 262219820Sjeff#else 263219820Sjeff#define COLLISION 264219820Sjeff#endif 265219820Sjeff 266219820Sjeff#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 267219820Sjeff bin_pos = hash_val%(table)->num_bins;\ 268219820Sjeff ptr = (table)->bins[bin_pos];\ 269219820Sjeff if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) \ 270219820Sjeff {\ 271219820Sjeff COLLISION;\ 272219820Sjeff while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 273219820Sjeff ptr = ptr->next;\ 274219820Sjeff }\ 275219820Sjeff ptr = ptr->next;\ 276219820Sjeff }\ 277219820Sjeff} while (0) 278219820Sjeff 279219820Sjeffint st_lookup(table, key, value) 280219820Sjeffst_table *table; 281219820Sjeffregister st_data_t key; 282219820Sjeffst_data_t *value; 283219820Sjeff{ 284219820Sjeff unsigned int hash_val, bin_pos; 285219820Sjeff register st_table_entry *ptr; 286219820Sjeff 287219820Sjeff hash_val = do_hash(key, table); 288219820Sjeff FIND_ENTRY(table, ptr, hash_val, bin_pos); 289219820Sjeff 290219820Sjeff if (ptr == 0) { 291219820Sjeff return 0; 292219820Sjeff } else { 293219820Sjeff if (value != 0) 294219820Sjeff *value = ptr->record; 295219820Sjeff return 1; 296219820Sjeff } 297219820Sjeff} 298219820Sjeff 299219820Sjeff#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 300219820Sjeffdo {\ 301219820Sjeff st_table_entry *entry;\ 302219820Sjeff if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) \ 303219820Sjeff {\ 304219820Sjeff rehash(table);\ 305219820Sjeff bin_pos = hash_val % table->num_bins;\ 306219820Sjeff }\ 307219820Sjeff \ 308219820Sjeff entry = alloc(st_table_entry);\ 309219820Sjeff \ 310219820Sjeff entry->hash = hash_val;\ 311219820Sjeff entry->key = key;\ 312219820Sjeff entry->record = value;\ 313219820Sjeff entry->next = table->bins[bin_pos];\ 314219820Sjeff table->bins[bin_pos] = entry;\ 315219820Sjeff table->num_entries++;\ 316219820Sjeff} while (0); 317219820Sjeff 318219820Sjeffint st_insert(table, key, value) 319219820Sjeffregister st_table *table; 320219820Sjeffregister st_data_t key; 321219820Sjeffst_data_t value; 322219820Sjeff{ 323219820Sjeff unsigned int hash_val, bin_pos; 324219820Sjeff register st_table_entry *ptr; 325219820Sjeff 326219820Sjeff hash_val = do_hash(key, table); 327219820Sjeff FIND_ENTRY(table, ptr, hash_val, bin_pos); 328219820Sjeff 329219820Sjeff if (ptr == 0) { 330219820Sjeff ADD_DIRECT(table, key, value, hash_val, bin_pos); 331219820Sjeff return 0; 332219820Sjeff } else { 333219820Sjeff ptr->record = value; 334219820Sjeff return 1; 335219820Sjeff } 336219820Sjeff} 337219820Sjeff 338219820Sjeffvoid st_add_direct(table, key, value) 339219820Sjeffst_table *table; 340219820Sjeffst_data_t key; 341219820Sjeffst_data_t value; 342219820Sjeff{ 343219820Sjeff unsigned int hash_val, bin_pos; 344219820Sjeff 345219820Sjeff hash_val = do_hash(key, table); 346219820Sjeff bin_pos = hash_val % table->num_bins; 347219820Sjeff ADD_DIRECT(table, key, value, hash_val, bin_pos); 348219820Sjeff} 349219820Sjeff 350219820Sjeffstatic void rehash(table) 351219820Sjeffregister st_table *table; 352219820Sjeff{ 353219820Sjeff register st_table_entry *ptr, *next, **new_bins; 354219820Sjeff int i, old_num_bins = table->num_bins, new_num_bins; 355219820Sjeff unsigned int hash_val; 356219820Sjeff 357219820Sjeff new_num_bins = new_size(old_num_bins + 1); 358219820Sjeff new_bins = 359219820Sjeff (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *)); 360219820Sjeff 361219820Sjeff for (i = 0; i < old_num_bins; i++) { 362219820Sjeff ptr = table->bins[i]; 363219820Sjeff while (ptr != 0) { 364219820Sjeff next = ptr->next; 365219820Sjeff hash_val = ptr->hash % new_num_bins; 366219820Sjeff ptr->next = new_bins[hash_val]; 367219820Sjeff new_bins[hash_val] = ptr; 368219820Sjeff ptr = next; 369219820Sjeff } 370219820Sjeff } 371219820Sjeff free(table->bins); 372219820Sjeff table->num_bins = new_num_bins; 373219820Sjeff table->bins = new_bins; 374219820Sjeff} 375219820Sjeff 376219820Sjeffst_table *st_copy(old_table) 377219820Sjeffst_table *old_table; 378219820Sjeff{ 379219820Sjeff st_table *new_table; 380219820Sjeff st_table_entry *ptr, *entry; 381219820Sjeff size_t i, num_bins = old_table->num_bins; 382219820Sjeff 383219820Sjeff new_table = alloc(st_table); 384219820Sjeff if (new_table == 0) { 385219820Sjeff return 0; 386219820Sjeff } 387219820Sjeff 388219820Sjeff *new_table = *old_table; 389219820Sjeff new_table->bins = (st_table_entry **) 390219820Sjeff Calloc(num_bins, sizeof(st_table_entry *)); 391219820Sjeff 392219820Sjeff if (new_table->bins == 0) { 393219820Sjeff free(new_table); 394219820Sjeff return 0; 395219820Sjeff } 396219820Sjeff 397219820Sjeff for (i = 0; i < num_bins; i++) { 398219820Sjeff new_table->bins[i] = 0; 399219820Sjeff ptr = old_table->bins[i]; 400219820Sjeff while (ptr != 0) { 401219820Sjeff entry = alloc(st_table_entry); 402219820Sjeff if (entry == 0) { 403219820Sjeff free(new_table->bins); 404219820Sjeff free(new_table); 405219820Sjeff return 0; 406219820Sjeff } 407219820Sjeff *entry = *ptr; 408219820Sjeff entry->next = new_table->bins[i]; 409219820Sjeff new_table->bins[i] = entry; 410219820Sjeff ptr = ptr->next; 411219820Sjeff } 412219820Sjeff } 413219820Sjeff return new_table; 414219820Sjeff} 415219820Sjeff 416219820Sjeffint st_delete(table, key, value) 417219820Sjeffregister st_table *table; 418219820Sjeffregister st_data_t *key; 419219820Sjeffst_data_t *value; 420219820Sjeff{ 421219820Sjeff unsigned int hash_val; 422219820Sjeff st_table_entry *tmp; 423219820Sjeff register st_table_entry *ptr; 424219820Sjeff 425219820Sjeff hash_val = do_hash_bin(*key, table); 426219820Sjeff ptr = table->bins[hash_val]; 427219820Sjeff 428219820Sjeff if (ptr == 0) { 429219820Sjeff if (value != 0) 430219820Sjeff *value = 0; 431219820Sjeff return 0; 432219820Sjeff } 433219820Sjeff 434219820Sjeff if (EQUAL(table, *key, ptr->key)) { 435219820Sjeff table->bins[hash_val] = ptr->next; 436219820Sjeff table->num_entries--; 437219820Sjeff if (value != 0) 438219820Sjeff *value = ptr->record; 439219820Sjeff *key = ptr->key; 440219820Sjeff free(ptr); 441219820Sjeff return 1; 442219820Sjeff } 443219820Sjeff 444219820Sjeff for (; ptr->next != 0; ptr = ptr->next) { 445219820Sjeff if (EQUAL(table, ptr->next->key, *key)) { 446219820Sjeff tmp = ptr->next; 447219820Sjeff ptr->next = ptr->next->next; 448219820Sjeff table->num_entries--; 449219820Sjeff if (value != 0) 450219820Sjeff *value = tmp->record; 451219820Sjeff *key = tmp->key; 452219820Sjeff free(tmp); 453219820Sjeff return 1; 454219820Sjeff } 455219820Sjeff } 456219820Sjeff 457219820Sjeff return 0; 458219820Sjeff} 459219820Sjeff 460219820Sjeffint st_delete_safe(table, key, value, never) 461219820Sjeffregister st_table *table; 462219820Sjeffregister st_data_t *key; 463219820Sjeffst_data_t *value; 464219820Sjeffst_data_t never; 465219820Sjeff{ 466219820Sjeff unsigned int hash_val; 467219820Sjeff register st_table_entry *ptr; 468219820Sjeff 469219820Sjeff hash_val = do_hash_bin(*key, table); 470219820Sjeff ptr = table->bins[hash_val]; 471219820Sjeff 472219820Sjeff if (ptr == 0) { 473219820Sjeff if (value != 0) 474219820Sjeff *value = 0; 475219820Sjeff return 0; 476219820Sjeff } 477219820Sjeff 478219820Sjeff for (; ptr != 0; ptr = ptr->next) { 479219820Sjeff if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 480219820Sjeff table->num_entries--; 481219820Sjeff *key = ptr->key; 482219820Sjeff if (value != 0) 483219820Sjeff *value = ptr->record; 484219820Sjeff ptr->key = ptr->record = never; 485219820Sjeff return 1; 486219820Sjeff } 487219820Sjeff } 488219820Sjeff 489219820Sjeff return 0; 490219820Sjeff} 491219820Sjeff 492219820Sjeffstatic int delete_never(st_data_t key, st_data_t value, st_data_t never) 493219820Sjeff{ 494219820Sjeff if (value == never) 495219820Sjeff return ST_DELETE; 496219820Sjeff return ST_CONTINUE; 497219820Sjeff} 498219820Sjeff 499219820Sjeffvoid st_cleanup_safe(table, never) 500219820Sjeffst_table *table; 501219820Sjeffst_data_t never; 502219820Sjeff{ 503219820Sjeff int num_entries = table->num_entries; 504219820Sjeff 505219820Sjeff st_foreach(table, delete_never, never); 506219820Sjeff table->num_entries = num_entries; 507219820Sjeff} 508219820Sjeff 509219820Sjeffvoid st_foreach(table, func, arg) 510219820Sjeffst_table *table; 511219820Sjeffint (*func) (st_data_t key, st_data_t val, st_data_t arg); 512219820Sjeffst_data_t arg; 513219820Sjeff{ 514219820Sjeff st_table_entry *ptr, *last, *tmp; 515219820Sjeff enum st_retval retval; 516219820Sjeff int i; 517219820Sjeff 518219820Sjeff for (i = 0; i < table->num_bins; i++) { 519219820Sjeff last = 0; 520219820Sjeff for (ptr = table->bins[i]; ptr != 0;) { 521219820Sjeff retval = (*func) (ptr->key, ptr->record, arg); 522219820Sjeff switch (retval) { 523219820Sjeff case ST_CONTINUE: 524219820Sjeff last = ptr; 525219820Sjeff ptr = ptr->next; 526219820Sjeff break; 527219820Sjeff case ST_STOP: 528219820Sjeff return; 529219820Sjeff case ST_DELETE: 530219820Sjeff tmp = ptr; 531219820Sjeff if (last == 0) { 532219820Sjeff table->bins[i] = ptr->next; 533219820Sjeff } else { 534219820Sjeff last->next = ptr->next; 535219820Sjeff } 536219820Sjeff ptr = ptr->next; 537219820Sjeff free(tmp); 538219820Sjeff table->num_entries--; 539219820Sjeff } 540219820Sjeff } 541219820Sjeff } 542219820Sjeff} 543219820Sjeff 544219820Sjeffstatic int strhash(string) 545219820Sjeffregister const char *string; 546219820Sjeff{ 547219820Sjeff register int c; 548219820Sjeff 549219820Sjeff#ifdef HASH_ELFHASH 550219820Sjeff register unsigned int h = 0, g; 551219820Sjeff 552219820Sjeff while ((c = *string++) != '\0') { 553219820Sjeff h = (h << 4) + c; 554219820Sjeff if (g = h & 0xF0000000) 555219820Sjeff h ^= g >> 24; 556219820Sjeff h &= ~g; 557219820Sjeff } 558219820Sjeff return h; 559219820Sjeff#elif HASH_PERL 560219820Sjeff register int val = 0; 561219820Sjeff 562219820Sjeff while ((c = *string++) != '\0') { 563219820Sjeff val = val * 33 + c; 564219820Sjeff } 565219820Sjeff 566219820Sjeff return val + (val >> 5); 567219820Sjeff#else 568219820Sjeff register int val = 0; 569219820Sjeff 570219820Sjeff while ((c = *string++) != '\0') { 571219820Sjeff val = val * 997 + c; 572219820Sjeff } 573219820Sjeff 574219820Sjeff return val + (val >> 5); 575219820Sjeff#endif 576219820Sjeff} 577219820Sjeff 578219820Sjeffstatic int numcmp(x, y) 579219820Sjeffvoid *x, *y; 580219820Sjeff{ 581219820Sjeff return (st_ptr_t) x != (st_ptr_t) y; 582219820Sjeff} 583219820Sjeff 584219820Sjeffstatic st_ptr_t numhash(n) 585219820Sjeffvoid *n; 586219820Sjeff{ 587219820Sjeff return (st_ptr_t) n; 588219820Sjeff} 589