1/* 2 * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved. 3 * Copyright (c) 2002-2006 Mellanox Technologies LTD. All rights reserved. 4 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5 * 6 * This software is available to you under a choice of one of two 7 * licenses. You may choose to be licensed under the terms of the GNU 8 * General Public License (GPL) Version 2, available from the file 9 * COPYING in the main directory of this source tree, or the 10 * OpenIB.org BSD license below: 11 * 12 * Redistribution and use in source and binary forms, with or 13 * without modification, are permitted provided that the following 14 * conditions are met: 15 * 16 * - Redistributions of source code must retain the above 17 * copyright notice, this list of conditions and the following 18 * disclaimer. 19 * 20 * - Redistributions in binary form must reproduce the above 21 * copyright notice, this list of conditions and the following 22 * disclaimer in the documentation and/or other materials 23 * provided with the distribution. 24 * 25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32 * SOFTWARE. 33 * 34 */ 35 36/* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */ 37 38#if HAVE_CONFIG_H 39# include <config.h> 40#endif /* HAVE_CONFIG_H */ 41 42#include <stdio.h> 43#include <string.h> 44#include <opensm/st.h> 45 46#ifdef _WIN32 47#include <malloc.h> 48#endif 49 50typedef struct st_table_entry st_table_entry; 51 52struct st_table_entry { 53 unsigned int hash; 54 st_data_t key; 55 st_data_t record; 56 st_table_entry *next; 57}; 58 59#define ST_DEFAULT_MAX_DENSITY 5 60#define ST_DEFAULT_INIT_TABLE_SIZE 11 61 62/* 63 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 64 * average number of items per bin before increasing the number of 65 * bins 66 * 67 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 68 * allocated initially 69 * 70 */ 71static int numcmp(void *, void *); 72static st_ptr_t numhash(void *); 73static struct st_hash_type type_numhash = { 74 numcmp, 75 numhash, 76}; 77 78/* extern int strcmp(const char *, const char *); */ 79static int strhash(const char *); 80 81static inline st_ptr_t st_strhash(void *key) 82{ 83 return strhash((const char *)key); 84} 85 86static inline int st_strcmp(void *key1, void *key2) 87{ 88 return strcmp((const char *)key1, (const char *)key2); 89} 90 91static struct st_hash_type type_strhash = { 92 st_strcmp, 93 st_strhash 94}; 95 96#define xmalloc malloc 97#define xcalloc calloc 98#define xrealloc realloc 99#define xfree free 100 101static void rehash(st_table *); 102 103#define alloc(type) (type*)xmalloc(sizeof(type)) 104#define Calloc(n,s) (char*)xcalloc((n), (s)) 105 106#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)(((void*)x),((void *)y)) == 0) 107 108#define do_hash(key,table) (unsigned int)(*(table)->type->hash)(((void*)key)) 109#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 110 111/* 112 * MINSIZE is the minimum size of a dictionary. 113 */ 114 115#define MINSIZE 8 116 117/* 118 Table of prime numbers 2^n+a, 2<=n<=30. 119*/ 120static long primes[] = { 121 8 + 3, 122 16 + 3, 123 32 + 5, 124 64 + 3, 125 128 + 3, 126 256 + 27, 127 512 + 9, 128 1024 + 9, 129 2048 + 5, 130 4096 + 3, 131 8192 + 27, 132 16384 + 43, 133 32768 + 3, 134 65536 + 45, 135 131072 + 29, 136 262144 + 3, 137 524288 + 21, 138 1048576 + 7, 139 2097152 + 17, 140 4194304 + 15, 141 8388608 + 9, 142 16777216 + 43, 143 33554432 + 35, 144 67108864 + 15, 145 134217728 + 29, 146 268435456 + 3, 147 536870912 + 11, 148 1073741824 + 85, 149 0 150}; 151 152static int new_size(int size) 153{ 154 int i; 155 156#if 0 157 for (i = 3; i < 31; i++) { 158 if ((1 << i) > size) 159 return 1 << i; 160 } 161 return -1; 162#else 163 int newsize; 164 165 for (i = 0, newsize = MINSIZE; 166 i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) { 167 if (newsize > size) 168 return primes[i]; 169 } 170 /* Ran out of polynomials */ 171 return -1; /* should raise exception */ 172#endif 173} 174 175#ifdef HASH_LOG 176static int collision = 0; 177static int init_st = 0; 178 179static void stat_col() 180{ 181 FILE *f = fopen("/var/log/osm_st_col", "w"); 182 fprintf(f, "collision: %d\n", collision); 183 fclose(f); 184} 185#endif 186 187st_table *st_init_table_with_size(type, size) 188struct st_hash_type *type; 189size_t size; 190{ 191 st_table *tbl; 192 193#ifdef HASH_LOG 194 if (init_st == 0) { 195 init_st = 1; 196 atexit(stat_col); 197 } 198#endif 199 200 size = new_size(size); /* round up to prime number */ 201 202 tbl = alloc(st_table); 203 tbl->type = type; 204 tbl->num_entries = 0; 205 tbl->num_bins = size; 206 tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *)); 207 208 return tbl; 209} 210 211st_table *st_init_table(type) 212struct st_hash_type *type; 213{ 214 return st_init_table_with_size(type, 0); 215} 216 217st_table *st_init_numtable(void) 218{ 219 return st_init_table(&type_numhash); 220} 221 222st_table *st_init_numtable_with_size(size) 223size_t size; 224{ 225 return st_init_table_with_size(&type_numhash, size); 226} 227 228st_table *st_init_strtable(void) 229{ 230 return st_init_table(&type_strhash); 231} 232 233st_table *st_init_strtable_with_size(size) 234size_t size; 235{ 236 return st_init_table_with_size(&type_strhash, size); 237} 238 239void st_free_table(table) 240st_table *table; 241{ 242 register st_table_entry *ptr, *next; 243 int i; 244 245 for (i = 0; i < table->num_bins; i++) { 246 ptr = table->bins[i]; 247 while (ptr != 0) { 248 next = ptr->next; 249 free(ptr); 250 ptr = next; 251 } 252 } 253 free(table->bins); 254 free(table); 255} 256 257#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 258((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 259 260#ifdef HASH_LOG 261#define COLLISION collision++ 262#else 263#define COLLISION 264#endif 265 266#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 267 bin_pos = hash_val%(table)->num_bins;\ 268 ptr = (table)->bins[bin_pos];\ 269 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) \ 270 {\ 271 COLLISION;\ 272 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 273 ptr = ptr->next;\ 274 }\ 275 ptr = ptr->next;\ 276 }\ 277} while (0) 278 279int st_lookup(table, key, value) 280st_table *table; 281register st_data_t key; 282st_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 return 0; 292 } else { 293 if (value != 0) 294 *value = ptr->record; 295 return 1; 296 } 297} 298 299#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 300do {\ 301 st_table_entry *entry;\ 302 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) \ 303 {\ 304 rehash(table);\ 305 bin_pos = hash_val % table->num_bins;\ 306 }\ 307 \ 308 entry = alloc(st_table_entry);\ 309 \ 310 entry->hash = hash_val;\ 311 entry->key = key;\ 312 entry->record = value;\ 313 entry->next = table->bins[bin_pos];\ 314 table->bins[bin_pos] = entry;\ 315 table->num_entries++;\ 316} while (0); 317 318int st_insert(table, key, value) 319register st_table *table; 320register st_data_t key; 321st_data_t value; 322{ 323 unsigned int hash_val, bin_pos; 324 register st_table_entry *ptr; 325 326 hash_val = do_hash(key, table); 327 FIND_ENTRY(table, ptr, hash_val, bin_pos); 328 329 if (ptr == 0) { 330 ADD_DIRECT(table, key, value, hash_val, bin_pos); 331 return 0; 332 } else { 333 ptr->record = value; 334 return 1; 335 } 336} 337 338void st_add_direct(table, key, value) 339st_table *table; 340st_data_t key; 341st_data_t value; 342{ 343 unsigned int hash_val, bin_pos; 344 345 hash_val = do_hash(key, table); 346 bin_pos = hash_val % table->num_bins; 347 ADD_DIRECT(table, key, value, hash_val, bin_pos); 348} 349 350static void rehash(table) 351register st_table *table; 352{ 353 register st_table_entry *ptr, *next, **new_bins; 354 int i, old_num_bins = table->num_bins, new_num_bins; 355 unsigned int hash_val; 356 357 new_num_bins = new_size(old_num_bins + 1); 358 new_bins = 359 (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *)); 360 361 for (i = 0; i < old_num_bins; i++) { 362 ptr = table->bins[i]; 363 while (ptr != 0) { 364 next = ptr->next; 365 hash_val = ptr->hash % new_num_bins; 366 ptr->next = new_bins[hash_val]; 367 new_bins[hash_val] = ptr; 368 ptr = next; 369 } 370 } 371 free(table->bins); 372 table->num_bins = new_num_bins; 373 table->bins = new_bins; 374} 375 376st_table *st_copy(old_table) 377st_table *old_table; 378{ 379 st_table *new_table; 380 st_table_entry *ptr, *entry; 381 size_t i, num_bins = old_table->num_bins; 382 383 new_table = alloc(st_table); 384 if (new_table == 0) { 385 return 0; 386 } 387 388 *new_table = *old_table; 389 new_table->bins = (st_table_entry **) 390 Calloc(num_bins, sizeof(st_table_entry *)); 391 392 if (new_table->bins == 0) { 393 free(new_table); 394 return 0; 395 } 396 397 for (i = 0; i < num_bins; i++) { 398 new_table->bins[i] = 0; 399 ptr = old_table->bins[i]; 400 while (ptr != 0) { 401 entry = alloc(st_table_entry); 402 if (entry == 0) { 403 free(new_table->bins); 404 free(new_table); 405 return 0; 406 } 407 *entry = *ptr; 408 entry->next = new_table->bins[i]; 409 new_table->bins[i] = entry; 410 ptr = ptr->next; 411 } 412 } 413 return new_table; 414} 415 416int st_delete(table, key, value) 417register st_table *table; 418register st_data_t *key; 419st_data_t *value; 420{ 421 unsigned int hash_val; 422 st_table_entry *tmp; 423 register st_table_entry *ptr; 424 425 hash_val = do_hash_bin(*key, table); 426 ptr = table->bins[hash_val]; 427 428 if (ptr == 0) { 429 if (value != 0) 430 *value = 0; 431 return 0; 432 } 433 434 if (EQUAL(table, *key, ptr->key)) { 435 table->bins[hash_val] = ptr->next; 436 table->num_entries--; 437 if (value != 0) 438 *value = ptr->record; 439 *key = ptr->key; 440 free(ptr); 441 return 1; 442 } 443 444 for (; ptr->next != 0; ptr = ptr->next) { 445 if (EQUAL(table, ptr->next->key, *key)) { 446 tmp = ptr->next; 447 ptr->next = ptr->next->next; 448 table->num_entries--; 449 if (value != 0) 450 *value = tmp->record; 451 *key = tmp->key; 452 free(tmp); 453 return 1; 454 } 455 } 456 457 return 0; 458} 459 460int st_delete_safe(table, key, value, never) 461register st_table *table; 462register st_data_t *key; 463st_data_t *value; 464st_data_t never; 465{ 466 unsigned int hash_val; 467 register st_table_entry *ptr; 468 469 hash_val = do_hash_bin(*key, table); 470 ptr = table->bins[hash_val]; 471 472 if (ptr == 0) { 473 if (value != 0) 474 *value = 0; 475 return 0; 476 } 477 478 for (; ptr != 0; ptr = ptr->next) { 479 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 480 table->num_entries--; 481 *key = ptr->key; 482 if (value != 0) 483 *value = ptr->record; 484 ptr->key = ptr->record = never; 485 return 1; 486 } 487 } 488 489 return 0; 490} 491 492static int delete_never(st_data_t key, st_data_t value, st_data_t never) 493{ 494 if (value == never) 495 return ST_DELETE; 496 return ST_CONTINUE; 497} 498 499void st_cleanup_safe(table, never) 500st_table *table; 501st_data_t never; 502{ 503 int num_entries = table->num_entries; 504 505 st_foreach(table, delete_never, never); 506 table->num_entries = num_entries; 507} 508 509void st_foreach(table, func, arg) 510st_table *table; 511int (*func) (st_data_t key, st_data_t val, st_data_t arg); 512st_data_t arg; 513{ 514 st_table_entry *ptr, *last, *tmp; 515 enum st_retval retval; 516 int i; 517 518 for (i = 0; i < table->num_bins; i++) { 519 last = 0; 520 for (ptr = table->bins[i]; ptr != 0;) { 521 retval = (*func) (ptr->key, ptr->record, arg); 522 switch (retval) { 523 case ST_CONTINUE: 524 last = ptr; 525 ptr = ptr->next; 526 break; 527 case ST_STOP: 528 return; 529 case ST_DELETE: 530 tmp = ptr; 531 if (last == 0) { 532 table->bins[i] = ptr->next; 533 } else { 534 last->next = ptr->next; 535 } 536 ptr = ptr->next; 537 free(tmp); 538 table->num_entries--; 539 } 540 } 541 } 542} 543 544static int strhash(string) 545register const char *string; 546{ 547 register int c; 548 549#ifdef HASH_ELFHASH 550 register unsigned int h = 0, g; 551 552 while ((c = *string++) != '\0') { 553 h = (h << 4) + c; 554 if (g = h & 0xF0000000) 555 h ^= g >> 24; 556 h &= ~g; 557 } 558 return h; 559#elif HASH_PERL 560 register int val = 0; 561 562 while ((c = *string++) != '\0') { 563 val = val * 33 + c; 564 } 565 566 return val + (val >> 5); 567#else 568 register int val = 0; 569 570 while ((c = *string++) != '\0') { 571 val = val * 997 + c; 572 } 573 574 return val + (val >> 5); 575#endif 576} 577 578static int numcmp(x, y) 579void *x, *y; 580{ 581 return (st_ptr_t) x != (st_ptr_t) y; 582} 583 584static st_ptr_t numhash(n) 585void *n; 586{ 587 return (st_ptr_t) n; 588} 589