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/osm_file_ids.h> 45 #define FILE_ID OSM_FILE_ST_C 46 #include <opensm/st.h> 47 48 typedef struct st_table_entry st_table_entry; 49 50 struct st_table_entry { 51 unsigned int hash; 52 st_data_t key; 53 st_data_t record; 54 st_table_entry *next; 55 }; 56 57 #define ST_DEFAULT_MAX_DENSITY 5 58 #define ST_DEFAULT_INIT_TABLE_SIZE 11 59 60 /* 61 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 62 * average number of items per bin before increasing the number of 63 * bins 64 * 65 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 66 * allocated initially 67 * 68 */ 69 static int numcmp(void *, void *); 70 static st_ptr_t numhash(void *); 71 static struct st_hash_type type_numhash = { 72 numcmp, 73 numhash, 74 }; 75 76 /* extern int strcmp(const char *, const char *); */ 77 static int strhash(const char *); 78 79 static inline st_ptr_t st_strhash(void *key) 80 { 81 return strhash((const char *)key); 82 } 83 84 static inline int st_strcmp(void *key1, void *key2) 85 { 86 return strcmp((const char *)key1, (const char *)key2); 87 } 88 89 static struct st_hash_type type_strhash = { 90 st_strcmp, 91 st_strhash 92 }; 93 94 #define xmalloc malloc 95 #define xcalloc calloc 96 #define xrealloc realloc 97 #define xfree free 98 99 static void rehash(st_table *); 100 101 #define alloc(type) (type*)xmalloc(sizeof(type)) 102 #define Calloc(n,s) (char*)xcalloc((n), (s)) 103 104 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)(((void*)x),((void *)y)) == 0) 105 106 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)(((void*)key)) 107 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 108 109 /* 110 * MINSIZE is the minimum size of a dictionary. 111 */ 112 113 #define MINSIZE 8 114 115 /* 116 Table of prime numbers 2^n+a, 2<=n<=30. 117 */ 118 static long primes[] = { 119 8 + 3, 120 16 + 3, 121 32 + 5, 122 64 + 3, 123 128 + 3, 124 256 + 27, 125 512 + 9, 126 1024 + 9, 127 2048 + 5, 128 4096 + 3, 129 8192 + 27, 130 16384 + 43, 131 32768 + 3, 132 65536 + 45, 133 131072 + 29, 134 262144 + 3, 135 524288 + 21, 136 1048576 + 7, 137 2097152 + 17, 138 4194304 + 15, 139 8388608 + 9, 140 16777216 + 43, 141 33554432 + 35, 142 67108864 + 15, 143 134217728 + 29, 144 268435456 + 3, 145 536870912 + 11, 146 1073741824 + 85, 147 0 148 }; 149 150 static int new_size(int size) 151 { 152 int i; 153 154 #if 0 155 for (i = 3; i < 31; i++) { 156 if ((1 << i) > size) 157 return 1 << i; 158 } 159 return -1; 160 #else 161 int newsize; 162 163 for (i = 0, newsize = MINSIZE; 164 i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) { 165 if (newsize > size) 166 return primes[i]; 167 } 168 /* Ran out of polynomials */ 169 return 0; /* should raise exception */ 170 #endif 171 } 172 173 #ifdef HASH_LOG 174 static int collision = 0; 175 static int init_st = 0; 176 177 static void stat_col() 178 { 179 FILE *f = fopen("/var/log/osm_st_col", "w"); 180 fprintf(f, "collision: %d\n", collision); 181 fclose(f); 182 } 183 #endif 184 185 st_table *st_init_table_with_size(type, size) 186 struct st_hash_type *type; 187 size_t size; 188 { 189 st_table *tbl; 190 191 #ifdef HASH_LOG 192 if (init_st == 0) { 193 init_st = 1; 194 atexit(stat_col); 195 } 196 #endif 197 198 size = new_size(size); /* round up to prime number */ 199 if (!size) 200 return NULL; 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 211 st_table *st_init_table(type) 212 struct st_hash_type *type; 213 { 214 return st_init_table_with_size(type, 0); 215 } 216 217 st_table *st_init_numtable(void) 218 { 219 return st_init_table(&type_numhash); 220 } 221 222 st_table *st_init_numtable_with_size(size) 223 size_t size; 224 { 225 return st_init_table_with_size(&type_numhash, size); 226 } 227 228 st_table *st_init_strtable(void) 229 { 230 return st_init_table(&type_strhash); 231 } 232 233 st_table *st_init_strtable_with_size(size) 234 size_t size; 235 { 236 return st_init_table_with_size(&type_strhash, size); 237 } 238 239 void st_free_table(table) 240 st_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 279 int st_lookup(table, key, value) 280 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 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)\ 300 do {\ 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 318 int st_insert(table, key, value) 319 register st_table *table; 320 register st_data_t key; 321 st_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 338 void st_add_direct(table, key, value) 339 st_table *table; 340 st_data_t key; 341 st_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 350 static void rehash(table) 351 register 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 if (!new_num_bins) 359 return; 360 361 new_bins = 362 (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *)); 363 364 for (i = 0; i < old_num_bins; i++) { 365 ptr = table->bins[i]; 366 while (ptr != 0) { 367 next = ptr->next; 368 hash_val = ptr->hash % new_num_bins; 369 ptr->next = new_bins[hash_val]; 370 new_bins[hash_val] = ptr; 371 ptr = next; 372 } 373 } 374 free(table->bins); 375 table->num_bins = new_num_bins; 376 table->bins = new_bins; 377 } 378 379 st_table *st_copy(old_table) 380 st_table *old_table; 381 { 382 st_table *new_table; 383 st_table_entry *ptr, *entry; 384 size_t i, num_bins = old_table->num_bins; 385 386 new_table = alloc(st_table); 387 if (new_table == 0) { 388 return 0; 389 } 390 391 *new_table = *old_table; 392 new_table->bins = (st_table_entry **) 393 Calloc(num_bins, sizeof(st_table_entry *)); 394 395 if (new_table->bins == 0) { 396 free(new_table); 397 return 0; 398 } 399 400 for (i = 0; i < num_bins; i++) { 401 new_table->bins[i] = 0; 402 ptr = old_table->bins[i]; 403 while (ptr != 0) { 404 entry = alloc(st_table_entry); 405 if (entry == 0) { 406 free(new_table->bins); 407 free(new_table); 408 return 0; 409 } 410 *entry = *ptr; 411 entry->next = new_table->bins[i]; 412 new_table->bins[i] = entry; 413 ptr = ptr->next; 414 } 415 } 416 return new_table; 417 } 418 419 int st_delete(table, key, value) 420 register st_table *table; 421 register st_data_t *key; 422 st_data_t *value; 423 { 424 unsigned int hash_val; 425 st_table_entry *tmp; 426 register st_table_entry *ptr; 427 428 hash_val = do_hash_bin(*key, table); 429 ptr = table->bins[hash_val]; 430 431 if (ptr == 0) { 432 if (value != 0) 433 *value = 0; 434 return 0; 435 } 436 437 if (EQUAL(table, *key, ptr->key)) { 438 table->bins[hash_val] = ptr->next; 439 table->num_entries--; 440 if (value != 0) 441 *value = ptr->record; 442 *key = ptr->key; 443 free(ptr); 444 return 1; 445 } 446 447 for (; ptr->next != 0; ptr = ptr->next) { 448 if (EQUAL(table, ptr->next->key, *key)) { 449 tmp = ptr->next; 450 ptr->next = ptr->next->next; 451 table->num_entries--; 452 if (value != 0) 453 *value = tmp->record; 454 *key = tmp->key; 455 free(tmp); 456 return 1; 457 } 458 } 459 460 return 0; 461 } 462 463 int st_delete_safe(table, key, value, never) 464 register st_table *table; 465 register st_data_t *key; 466 st_data_t *value; 467 st_data_t never; 468 { 469 unsigned int hash_val; 470 register st_table_entry *ptr; 471 472 hash_val = do_hash_bin(*key, table); 473 ptr = table->bins[hash_val]; 474 475 if (ptr == 0) { 476 if (value != 0) 477 *value = 0; 478 return 0; 479 } 480 481 for (; ptr != 0; ptr = ptr->next) { 482 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 483 table->num_entries--; 484 *key = ptr->key; 485 if (value != 0) 486 *value = ptr->record; 487 ptr->key = ptr->record = never; 488 return 1; 489 } 490 } 491 492 return 0; 493 } 494 495 static int delete_never(st_data_t key, st_data_t value, st_data_t never) 496 { 497 if (value == never) 498 return ST_DELETE; 499 return ST_CONTINUE; 500 } 501 502 void st_cleanup_safe(table, never) 503 st_table *table; 504 st_data_t never; 505 { 506 int num_entries = table->num_entries; 507 508 st_foreach(table, delete_never, never); 509 table->num_entries = num_entries; 510 } 511 512 void st_foreach(table, func, arg) 513 st_table *table; 514 int (*func) (st_data_t key, st_data_t val, st_data_t arg); 515 st_data_t arg; 516 { 517 st_table_entry *ptr, *last, *tmp; 518 enum st_retval retval; 519 int i; 520 521 for (i = 0; i < table->num_bins; i++) { 522 last = 0; 523 for (ptr = table->bins[i]; ptr != 0;) { 524 retval = (*func) (ptr->key, ptr->record, arg); 525 switch (retval) { 526 case ST_CONTINUE: 527 last = ptr; 528 ptr = ptr->next; 529 break; 530 case ST_STOP: 531 return; 532 case ST_DELETE: 533 tmp = ptr; 534 if (last == 0) { 535 table->bins[i] = ptr->next; 536 } else { 537 last->next = ptr->next; 538 } 539 ptr = ptr->next; 540 free(tmp); 541 table->num_entries--; 542 } 543 } 544 } 545 } 546 547 static int strhash(string) 548 register const char *string; 549 { 550 register int c; 551 552 #ifdef HASH_ELFHASH 553 register unsigned int h = 0, g; 554 555 while ((c = *string++) != '\0') { 556 h = (h << 4) + c; 557 if (g = h & 0xF0000000) 558 h ^= g >> 24; 559 h &= ~g; 560 } 561 return h; 562 #elif HASH_PERL 563 register int val = 0; 564 565 while ((c = *string++) != '\0') { 566 val = val * 33 + c; 567 } 568 569 return val + (val >> 5); 570 #else 571 register int val = 0; 572 573 while ((c = *string++) != '\0') { 574 val = val * 997 + c; 575 } 576 577 return val + (val >> 5); 578 #endif 579 } 580 581 static int numcmp(x, y) 582 void *x, *y; 583 { 584 return (st_ptr_t) x != (st_ptr_t) y; 585 } 586 587 static st_ptr_t numhash(n) 588 void *n; 589 { 590 return (st_ptr_t) n; 591 } 592