1321936Shselasky/* 2321936Shselasky * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved. 3321936Shselasky * Copyright (c) 2002-2006 Mellanox Technologies LTD. All rights reserved. 4321936Shselasky * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5321936Shselasky * 6321936Shselasky * This software is available to you under a choice of one of two 7321936Shselasky * licenses. You may choose to be licensed under the terms of the GNU 8321936Shselasky * General Public License (GPL) Version 2, available from the file 9321936Shselasky * COPYING in the main directory of this source tree, or the 10321936Shselasky * OpenIB.org BSD license below: 11321936Shselasky * 12321936Shselasky * Redistribution and use in source and binary forms, with or 13321936Shselasky * without modification, are permitted provided that the following 14321936Shselasky * conditions are met: 15321936Shselasky * 16321936Shselasky * - Redistributions of source code must retain the above 17321936Shselasky * copyright notice, this list of conditions and the following 18321936Shselasky * disclaimer. 19321936Shselasky * 20321936Shselasky * - Redistributions in binary form must reproduce the above 21321936Shselasky * copyright notice, this list of conditions and the following 22321936Shselasky * disclaimer in the documentation and/or other materials 23321936Shselasky * provided with the distribution. 24321936Shselasky * 25321936Shselasky * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26321936Shselasky * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27321936Shselasky * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28321936Shselasky * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29321936Shselasky * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30321936Shselasky * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31321936Shselasky * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32321936Shselasky * SOFTWARE. 33321936Shselasky * 34321936Shselasky */ 35321936Shselasky 36321936Shselasky/* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */ 37321936Shselasky 38321936Shselasky#if HAVE_CONFIG_H 39321936Shselasky# include <config.h> 40321936Shselasky#endif /* HAVE_CONFIG_H */ 41321936Shselasky 42321936Shselasky#include <stdio.h> 43321936Shselasky#include <string.h> 44321936Shselasky#include <opensm/osm_file_ids.h> 45321936Shselasky#define FILE_ID OSM_FILE_ST_C 46321936Shselasky#include <opensm/st.h> 47321936Shselasky 48321936Shselaskytypedef struct st_table_entry st_table_entry; 49321936Shselasky 50321936Shselaskystruct st_table_entry { 51321936Shselasky unsigned int hash; 52321936Shselasky st_data_t key; 53321936Shselasky st_data_t record; 54321936Shselasky st_table_entry *next; 55321936Shselasky}; 56321936Shselasky 57321936Shselasky#define ST_DEFAULT_MAX_DENSITY 5 58321936Shselasky#define ST_DEFAULT_INIT_TABLE_SIZE 11 59321936Shselasky 60321936Shselasky/* 61321936Shselasky * DEFAULT_MAX_DENSITY is the default for the largest we allow the 62321936Shselasky * average number of items per bin before increasing the number of 63321936Shselasky * bins 64321936Shselasky * 65321936Shselasky * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 66321936Shselasky * allocated initially 67321936Shselasky * 68321936Shselasky */ 69321936Shselaskystatic int numcmp(void *, void *); 70321936Shselaskystatic st_ptr_t numhash(void *); 71321936Shselaskystatic struct st_hash_type type_numhash = { 72321936Shselasky numcmp, 73321936Shselasky numhash, 74321936Shselasky}; 75321936Shselasky 76321936Shselasky/* extern int strcmp(const char *, const char *); */ 77321936Shselaskystatic int strhash(const char *); 78321936Shselasky 79321936Shselaskystatic inline st_ptr_t st_strhash(void *key) 80321936Shselasky{ 81321936Shselasky return strhash((const char *)key); 82321936Shselasky} 83321936Shselasky 84321936Shselaskystatic inline int st_strcmp(void *key1, void *key2) 85321936Shselasky{ 86321936Shselasky return strcmp((const char *)key1, (const char *)key2); 87321936Shselasky} 88321936Shselasky 89321936Shselaskystatic struct st_hash_type type_strhash = { 90321936Shselasky st_strcmp, 91321936Shselasky st_strhash 92321936Shselasky}; 93321936Shselasky 94321936Shselasky#define xmalloc malloc 95321936Shselasky#define xcalloc calloc 96321936Shselasky#define xrealloc realloc 97321936Shselasky#define xfree free 98321936Shselasky 99321936Shselaskystatic void rehash(st_table *); 100321936Shselasky 101321936Shselasky#define alloc(type) (type*)xmalloc(sizeof(type)) 102321936Shselasky#define Calloc(n,s) (char*)xcalloc((n), (s)) 103321936Shselasky 104321936Shselasky#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)(((void*)x),((void *)y)) == 0) 105321936Shselasky 106321936Shselasky#define do_hash(key,table) (unsigned int)(*(table)->type->hash)(((void*)key)) 107321936Shselasky#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 108321936Shselasky 109321936Shselasky/* 110321936Shselasky * MINSIZE is the minimum size of a dictionary. 111321936Shselasky */ 112321936Shselasky 113321936Shselasky#define MINSIZE 8 114321936Shselasky 115321936Shselasky/* 116321936Shselasky Table of prime numbers 2^n+a, 2<=n<=30. 117321936Shselasky*/ 118321936Shselaskystatic long primes[] = { 119321936Shselasky 8 + 3, 120321936Shselasky 16 + 3, 121321936Shselasky 32 + 5, 122321936Shselasky 64 + 3, 123321936Shselasky 128 + 3, 124321936Shselasky 256 + 27, 125321936Shselasky 512 + 9, 126321936Shselasky 1024 + 9, 127321936Shselasky 2048 + 5, 128321936Shselasky 4096 + 3, 129321936Shselasky 8192 + 27, 130321936Shselasky 16384 + 43, 131321936Shselasky 32768 + 3, 132321936Shselasky 65536 + 45, 133321936Shselasky 131072 + 29, 134321936Shselasky 262144 + 3, 135321936Shselasky 524288 + 21, 136321936Shselasky 1048576 + 7, 137321936Shselasky 2097152 + 17, 138321936Shselasky 4194304 + 15, 139321936Shselasky 8388608 + 9, 140321936Shselasky 16777216 + 43, 141321936Shselasky 33554432 + 35, 142321936Shselasky 67108864 + 15, 143321936Shselasky 134217728 + 29, 144321936Shselasky 268435456 + 3, 145321936Shselasky 536870912 + 11, 146321936Shselasky 1073741824 + 85, 147321936Shselasky 0 148321936Shselasky}; 149321936Shselasky 150321936Shselaskystatic int new_size(int size) 151321936Shselasky{ 152321936Shselasky int i; 153321936Shselasky 154321936Shselasky#if 0 155321936Shselasky for (i = 3; i < 31; i++) { 156321936Shselasky if ((1 << i) > size) 157321936Shselasky return 1 << i; 158321936Shselasky } 159321936Shselasky return -1; 160321936Shselasky#else 161321936Shselasky int newsize; 162321936Shselasky 163321936Shselasky for (i = 0, newsize = MINSIZE; 164321936Shselasky i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) { 165321936Shselasky if (newsize > size) 166321936Shselasky return primes[i]; 167321936Shselasky } 168321936Shselasky /* Ran out of polynomials */ 169321936Shselasky return 0; /* should raise exception */ 170321936Shselasky#endif 171321936Shselasky} 172321936Shselasky 173321936Shselasky#ifdef HASH_LOG 174321936Shselaskystatic int collision = 0; 175321936Shselaskystatic int init_st = 0; 176321936Shselasky 177321936Shselaskystatic void stat_col() 178321936Shselasky{ 179321936Shselasky FILE *f = fopen("/var/log/osm_st_col", "w"); 180321936Shselasky fprintf(f, "collision: %d\n", collision); 181321936Shselasky fclose(f); 182321936Shselasky} 183321936Shselasky#endif 184321936Shselasky 185321936Shselaskyst_table *st_init_table_with_size(type, size) 186321936Shselaskystruct st_hash_type *type; 187321936Shselaskysize_t size; 188321936Shselasky{ 189321936Shselasky st_table *tbl; 190321936Shselasky 191321936Shselasky#ifdef HASH_LOG 192321936Shselasky if (init_st == 0) { 193321936Shselasky init_st = 1; 194321936Shselasky atexit(stat_col); 195321936Shselasky } 196321936Shselasky#endif 197321936Shselasky 198321936Shselasky size = new_size(size); /* round up to prime number */ 199321936Shselasky if (!size) 200321936Shselasky return NULL; 201321936Shselasky 202321936Shselasky tbl = alloc(st_table); 203321936Shselasky tbl->type = type; 204321936Shselasky tbl->num_entries = 0; 205321936Shselasky tbl->num_bins = size; 206321936Shselasky tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *)); 207321936Shselasky 208321936Shselasky return tbl; 209321936Shselasky} 210321936Shselasky 211321936Shselaskyst_table *st_init_table(type) 212321936Shselaskystruct st_hash_type *type; 213321936Shselasky{ 214321936Shselasky return st_init_table_with_size(type, 0); 215321936Shselasky} 216321936Shselasky 217321936Shselaskyst_table *st_init_numtable(void) 218321936Shselasky{ 219321936Shselasky return st_init_table(&type_numhash); 220321936Shselasky} 221321936Shselasky 222321936Shselaskyst_table *st_init_numtable_with_size(size) 223321936Shselaskysize_t size; 224321936Shselasky{ 225321936Shselasky return st_init_table_with_size(&type_numhash, size); 226321936Shselasky} 227321936Shselasky 228321936Shselaskyst_table *st_init_strtable(void) 229321936Shselasky{ 230321936Shselasky return st_init_table(&type_strhash); 231321936Shselasky} 232321936Shselasky 233321936Shselaskyst_table *st_init_strtable_with_size(size) 234321936Shselaskysize_t size; 235321936Shselasky{ 236321936Shselasky return st_init_table_with_size(&type_strhash, size); 237321936Shselasky} 238321936Shselasky 239321936Shselaskyvoid st_free_table(table) 240321936Shselaskyst_table *table; 241321936Shselasky{ 242321936Shselasky register st_table_entry *ptr, *next; 243321936Shselasky int i; 244321936Shselasky 245321936Shselasky for (i = 0; i < table->num_bins; i++) { 246321936Shselasky ptr = table->bins[i]; 247321936Shselasky while (ptr != 0) { 248321936Shselasky next = ptr->next; 249321936Shselasky free(ptr); 250321936Shselasky ptr = next; 251321936Shselasky } 252321936Shselasky } 253321936Shselasky free(table->bins); 254321936Shselasky free(table); 255321936Shselasky} 256321936Shselasky 257321936Shselasky#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 258321936Shselasky((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 259321936Shselasky 260321936Shselasky#ifdef HASH_LOG 261321936Shselasky#define COLLISION collision++ 262321936Shselasky#else 263321936Shselasky#define COLLISION 264321936Shselasky#endif 265321936Shselasky 266321936Shselasky#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 267321936Shselasky bin_pos = hash_val%(table)->num_bins;\ 268321936Shselasky ptr = (table)->bins[bin_pos];\ 269321936Shselasky if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) \ 270321936Shselasky {\ 271321936Shselasky COLLISION;\ 272321936Shselasky while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 273321936Shselasky ptr = ptr->next;\ 274321936Shselasky }\ 275321936Shselasky ptr = ptr->next;\ 276321936Shselasky }\ 277321936Shselasky} while (0) 278321936Shselasky 279321936Shselaskyint st_lookup(table, key, value) 280321936Shselaskyst_table *table; 281321936Shselaskyregister st_data_t key; 282321936Shselaskyst_data_t *value; 283321936Shselasky{ 284321936Shselasky unsigned int hash_val, bin_pos; 285321936Shselasky register st_table_entry *ptr; 286321936Shselasky 287321936Shselasky hash_val = do_hash(key, table); 288321936Shselasky FIND_ENTRY(table, ptr, hash_val, bin_pos); 289321936Shselasky 290321936Shselasky if (ptr == 0) { 291321936Shselasky return 0; 292321936Shselasky } else { 293321936Shselasky if (value != 0) 294321936Shselasky *value = ptr->record; 295321936Shselasky return 1; 296321936Shselasky } 297321936Shselasky} 298321936Shselasky 299321936Shselasky#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 300321936Shselaskydo {\ 301321936Shselasky st_table_entry *entry;\ 302321936Shselasky if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) \ 303321936Shselasky {\ 304321936Shselasky rehash(table);\ 305321936Shselasky bin_pos = hash_val % table->num_bins;\ 306321936Shselasky }\ 307321936Shselasky \ 308321936Shselasky entry = alloc(st_table_entry);\ 309321936Shselasky \ 310321936Shselasky entry->hash = hash_val;\ 311321936Shselasky entry->key = key;\ 312321936Shselasky entry->record = value;\ 313321936Shselasky entry->next = table->bins[bin_pos];\ 314321936Shselasky table->bins[bin_pos] = entry;\ 315321936Shselasky table->num_entries++;\ 316321936Shselasky} while (0); 317321936Shselasky 318321936Shselaskyint st_insert(table, key, value) 319321936Shselaskyregister st_table *table; 320321936Shselaskyregister st_data_t key; 321321936Shselaskyst_data_t value; 322321936Shselasky{ 323321936Shselasky unsigned int hash_val, bin_pos; 324321936Shselasky register st_table_entry *ptr; 325321936Shselasky 326321936Shselasky hash_val = do_hash(key, table); 327321936Shselasky FIND_ENTRY(table, ptr, hash_val, bin_pos); 328321936Shselasky 329321936Shselasky if (ptr == 0) { 330321936Shselasky ADD_DIRECT(table, key, value, hash_val, bin_pos); 331321936Shselasky return 0; 332321936Shselasky } else { 333321936Shselasky ptr->record = value; 334321936Shselasky return 1; 335321936Shselasky } 336321936Shselasky} 337321936Shselasky 338321936Shselaskyvoid st_add_direct(table, key, value) 339321936Shselaskyst_table *table; 340321936Shselaskyst_data_t key; 341321936Shselaskyst_data_t value; 342321936Shselasky{ 343321936Shselasky unsigned int hash_val, bin_pos; 344321936Shselasky 345321936Shselasky hash_val = do_hash(key, table); 346321936Shselasky bin_pos = hash_val % table->num_bins; 347321936Shselasky ADD_DIRECT(table, key, value, hash_val, bin_pos); 348321936Shselasky} 349321936Shselasky 350321936Shselaskystatic void rehash(table) 351321936Shselaskyregister st_table *table; 352321936Shselasky{ 353321936Shselasky register st_table_entry *ptr, *next, **new_bins; 354321936Shselasky int i, old_num_bins = table->num_bins, new_num_bins; 355321936Shselasky unsigned int hash_val; 356321936Shselasky 357321936Shselasky new_num_bins = new_size(old_num_bins + 1); 358321936Shselasky if (!new_num_bins) 359321936Shselasky return; 360321936Shselasky 361321936Shselasky new_bins = 362321936Shselasky (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *)); 363321936Shselasky 364321936Shselasky for (i = 0; i < old_num_bins; i++) { 365321936Shselasky ptr = table->bins[i]; 366321936Shselasky while (ptr != 0) { 367321936Shselasky next = ptr->next; 368321936Shselasky hash_val = ptr->hash % new_num_bins; 369321936Shselasky ptr->next = new_bins[hash_val]; 370321936Shselasky new_bins[hash_val] = ptr; 371321936Shselasky ptr = next; 372321936Shselasky } 373321936Shselasky } 374321936Shselasky free(table->bins); 375321936Shselasky table->num_bins = new_num_bins; 376321936Shselasky table->bins = new_bins; 377321936Shselasky} 378321936Shselasky 379321936Shselaskyst_table *st_copy(old_table) 380321936Shselaskyst_table *old_table; 381321936Shselasky{ 382321936Shselasky st_table *new_table; 383321936Shselasky st_table_entry *ptr, *entry; 384321936Shselasky size_t i, num_bins = old_table->num_bins; 385321936Shselasky 386321936Shselasky new_table = alloc(st_table); 387321936Shselasky if (new_table == 0) { 388321936Shselasky return 0; 389321936Shselasky } 390321936Shselasky 391321936Shselasky *new_table = *old_table; 392321936Shselasky new_table->bins = (st_table_entry **) 393321936Shselasky Calloc(num_bins, sizeof(st_table_entry *)); 394321936Shselasky 395321936Shselasky if (new_table->bins == 0) { 396321936Shselasky free(new_table); 397321936Shselasky return 0; 398321936Shselasky } 399321936Shselasky 400321936Shselasky for (i = 0; i < num_bins; i++) { 401321936Shselasky new_table->bins[i] = 0; 402321936Shselasky ptr = old_table->bins[i]; 403321936Shselasky while (ptr != 0) { 404321936Shselasky entry = alloc(st_table_entry); 405321936Shselasky if (entry == 0) { 406321936Shselasky free(new_table->bins); 407321936Shselasky free(new_table); 408321936Shselasky return 0; 409321936Shselasky } 410321936Shselasky *entry = *ptr; 411321936Shselasky entry->next = new_table->bins[i]; 412321936Shselasky new_table->bins[i] = entry; 413321936Shselasky ptr = ptr->next; 414321936Shselasky } 415321936Shselasky } 416321936Shselasky return new_table; 417321936Shselasky} 418321936Shselasky 419321936Shselaskyint st_delete(table, key, value) 420321936Shselaskyregister st_table *table; 421321936Shselaskyregister st_data_t *key; 422321936Shselaskyst_data_t *value; 423321936Shselasky{ 424321936Shselasky unsigned int hash_val; 425321936Shselasky st_table_entry *tmp; 426321936Shselasky register st_table_entry *ptr; 427321936Shselasky 428321936Shselasky hash_val = do_hash_bin(*key, table); 429321936Shselasky ptr = table->bins[hash_val]; 430321936Shselasky 431321936Shselasky if (ptr == 0) { 432321936Shselasky if (value != 0) 433321936Shselasky *value = 0; 434321936Shselasky return 0; 435321936Shselasky } 436321936Shselasky 437321936Shselasky if (EQUAL(table, *key, ptr->key)) { 438321936Shselasky table->bins[hash_val] = ptr->next; 439321936Shselasky table->num_entries--; 440321936Shselasky if (value != 0) 441321936Shselasky *value = ptr->record; 442321936Shselasky *key = ptr->key; 443321936Shselasky free(ptr); 444321936Shselasky return 1; 445321936Shselasky } 446321936Shselasky 447321936Shselasky for (; ptr->next != 0; ptr = ptr->next) { 448321936Shselasky if (EQUAL(table, ptr->next->key, *key)) { 449321936Shselasky tmp = ptr->next; 450321936Shselasky ptr->next = ptr->next->next; 451321936Shselasky table->num_entries--; 452321936Shselasky if (value != 0) 453321936Shselasky *value = tmp->record; 454321936Shselasky *key = tmp->key; 455321936Shselasky free(tmp); 456321936Shselasky return 1; 457321936Shselasky } 458321936Shselasky } 459321936Shselasky 460321936Shselasky return 0; 461321936Shselasky} 462321936Shselasky 463321936Shselaskyint st_delete_safe(table, key, value, never) 464321936Shselaskyregister st_table *table; 465321936Shselaskyregister st_data_t *key; 466321936Shselaskyst_data_t *value; 467321936Shselaskyst_data_t never; 468321936Shselasky{ 469321936Shselasky unsigned int hash_val; 470321936Shselasky register st_table_entry *ptr; 471321936Shselasky 472321936Shselasky hash_val = do_hash_bin(*key, table); 473321936Shselasky ptr = table->bins[hash_val]; 474321936Shselasky 475321936Shselasky if (ptr == 0) { 476321936Shselasky if (value != 0) 477321936Shselasky *value = 0; 478321936Shselasky return 0; 479321936Shselasky } 480321936Shselasky 481321936Shselasky for (; ptr != 0; ptr = ptr->next) { 482321936Shselasky if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 483321936Shselasky table->num_entries--; 484321936Shselasky *key = ptr->key; 485321936Shselasky if (value != 0) 486321936Shselasky *value = ptr->record; 487321936Shselasky ptr->key = ptr->record = never; 488321936Shselasky return 1; 489321936Shselasky } 490321936Shselasky } 491321936Shselasky 492321936Shselasky return 0; 493321936Shselasky} 494321936Shselasky 495321936Shselaskystatic int delete_never(st_data_t key, st_data_t value, st_data_t never) 496321936Shselasky{ 497321936Shselasky if (value == never) 498321936Shselasky return ST_DELETE; 499321936Shselasky return ST_CONTINUE; 500321936Shselasky} 501321936Shselasky 502321936Shselaskyvoid st_cleanup_safe(table, never) 503321936Shselaskyst_table *table; 504321936Shselaskyst_data_t never; 505321936Shselasky{ 506321936Shselasky int num_entries = table->num_entries; 507321936Shselasky 508321936Shselasky st_foreach(table, delete_never, never); 509321936Shselasky table->num_entries = num_entries; 510321936Shselasky} 511321936Shselasky 512321936Shselaskyvoid st_foreach(table, func, arg) 513321936Shselaskyst_table *table; 514321936Shselaskyint (*func) (st_data_t key, st_data_t val, st_data_t arg); 515321936Shselaskyst_data_t arg; 516321936Shselasky{ 517321936Shselasky st_table_entry *ptr, *last, *tmp; 518321936Shselasky enum st_retval retval; 519321936Shselasky int i; 520321936Shselasky 521321936Shselasky for (i = 0; i < table->num_bins; i++) { 522321936Shselasky last = 0; 523321936Shselasky for (ptr = table->bins[i]; ptr != 0;) { 524321936Shselasky retval = (*func) (ptr->key, ptr->record, arg); 525321936Shselasky switch (retval) { 526321936Shselasky case ST_CONTINUE: 527321936Shselasky last = ptr; 528321936Shselasky ptr = ptr->next; 529321936Shselasky break; 530321936Shselasky case ST_STOP: 531321936Shselasky return; 532321936Shselasky case ST_DELETE: 533321936Shselasky tmp = ptr; 534321936Shselasky if (last == 0) { 535321936Shselasky table->bins[i] = ptr->next; 536321936Shselasky } else { 537321936Shselasky last->next = ptr->next; 538321936Shselasky } 539321936Shselasky ptr = ptr->next; 540321936Shselasky free(tmp); 541321936Shselasky table->num_entries--; 542321936Shselasky } 543321936Shselasky } 544321936Shselasky } 545321936Shselasky} 546321936Shselasky 547321936Shselaskystatic int strhash(string) 548321936Shselaskyregister const char *string; 549321936Shselasky{ 550321936Shselasky register int c; 551321936Shselasky 552321936Shselasky#ifdef HASH_ELFHASH 553321936Shselasky register unsigned int h = 0, g; 554321936Shselasky 555321936Shselasky while ((c = *string++) != '\0') { 556321936Shselasky h = (h << 4) + c; 557321936Shselasky if (g = h & 0xF0000000) 558321936Shselasky h ^= g >> 24; 559321936Shselasky h &= ~g; 560321936Shselasky } 561321936Shselasky return h; 562321936Shselasky#elif HASH_PERL 563321936Shselasky register int val = 0; 564321936Shselasky 565321936Shselasky while ((c = *string++) != '\0') { 566321936Shselasky val = val * 33 + c; 567321936Shselasky } 568321936Shselasky 569321936Shselasky return val + (val >> 5); 570321936Shselasky#else 571321936Shselasky register int val = 0; 572321936Shselasky 573321936Shselasky while ((c = *string++) != '\0') { 574321936Shselasky val = val * 997 + c; 575321936Shselasky } 576321936Shselasky 577321936Shselasky return val + (val >> 5); 578321936Shselasky#endif 579321936Shselasky} 580321936Shselasky 581321936Shselaskystatic int numcmp(x, y) 582321936Shselaskyvoid *x, *y; 583321936Shselasky{ 584321936Shselasky return (st_ptr_t) x != (st_ptr_t) y; 585321936Shselasky} 586321936Shselasky 587321936Shselaskystatic st_ptr_t numhash(n) 588321936Shselaskyvoid *n; 589321936Shselasky{ 590321936Shselasky return (st_ptr_t) n; 591321936Shselasky} 592