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(void) 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(struct st_hash_type *type, size_t size) 186 { 187 st_table *tbl; 188 189 #ifdef HASH_LOG 190 if (init_st == 0) { 191 init_st = 1; 192 atexit(stat_col); 193 } 194 #endif 195 196 size = new_size(size); /* round up to prime number */ 197 if (!size) 198 return NULL; 199 200 tbl = alloc(st_table); 201 tbl->type = type; 202 tbl->num_entries = 0; 203 tbl->num_bins = size; 204 tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *)); 205 206 return tbl; 207 } 208 209 st_table *st_init_table(struct st_hash_type *type) 210 { 211 return st_init_table_with_size(type, 0); 212 } 213 214 st_table *st_init_numtable(void) 215 { 216 return st_init_table(&type_numhash); 217 } 218 219 st_table *st_init_numtable_with_size(size_t size) 220 { 221 return st_init_table_with_size(&type_numhash, size); 222 } 223 224 st_table *st_init_strtable(void) 225 { 226 return st_init_table(&type_strhash); 227 } 228 229 st_table *st_init_strtable_with_size(size_t size) 230 { 231 return st_init_table_with_size(&type_strhash, size); 232 } 233 234 void st_free_table(st_table *table) 235 { 236 register st_table_entry *ptr, *next; 237 int i; 238 239 for (i = 0; i < table->num_bins; i++) { 240 ptr = table->bins[i]; 241 while (ptr != 0) { 242 next = ptr->next; 243 free(ptr); 244 ptr = next; 245 } 246 } 247 free(table->bins); 248 free(table); 249 } 250 251 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 252 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 253 254 #ifdef HASH_LOG 255 #define COLLISION collision++ 256 #else 257 #define COLLISION 258 #endif 259 260 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 261 bin_pos = hash_val%(table)->num_bins;\ 262 ptr = (table)->bins[bin_pos];\ 263 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) \ 264 {\ 265 COLLISION;\ 266 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 267 ptr = ptr->next;\ 268 }\ 269 ptr = ptr->next;\ 270 }\ 271 } while (0) 272 273 int st_lookup(st_table *table, st_data_t key, st_data_t *value) 274 { 275 unsigned int hash_val, bin_pos; 276 register st_table_entry *ptr; 277 278 hash_val = do_hash(key, table); 279 FIND_ENTRY(table, ptr, hash_val, bin_pos); 280 281 if (ptr == 0) { 282 return 0; 283 } else { 284 if (value != 0) 285 *value = ptr->record; 286 return 1; 287 } 288 } 289 290 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 291 do {\ 292 st_table_entry *entry;\ 293 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) \ 294 {\ 295 rehash(table);\ 296 bin_pos = hash_val % table->num_bins;\ 297 }\ 298 \ 299 entry = alloc(st_table_entry);\ 300 \ 301 entry->hash = hash_val;\ 302 entry->key = key;\ 303 entry->record = value;\ 304 entry->next = table->bins[bin_pos];\ 305 table->bins[bin_pos] = entry;\ 306 table->num_entries++;\ 307 } while (0); 308 309 int st_insert(st_table *table, st_data_t key, st_data_t value) 310 { 311 unsigned int hash_val, bin_pos; 312 register st_table_entry *ptr; 313 314 hash_val = do_hash(key, table); 315 FIND_ENTRY(table, ptr, hash_val, bin_pos); 316 317 if (ptr == 0) { 318 ADD_DIRECT(table, key, value, hash_val, bin_pos); 319 return 0; 320 } else { 321 ptr->record = value; 322 return 1; 323 } 324 } 325 326 void st_add_direct(st_table *table, st_data_t key, st_data_t value) 327 { 328 unsigned int hash_val, bin_pos; 329 330 hash_val = do_hash(key, table); 331 bin_pos = hash_val % table->num_bins; 332 ADD_DIRECT(table, key, value, hash_val, bin_pos); 333 } 334 335 static void rehash(st_table *table) 336 { 337 register st_table_entry *ptr, *next, **new_bins; 338 int i, old_num_bins = table->num_bins, new_num_bins; 339 unsigned int hash_val; 340 341 new_num_bins = new_size(old_num_bins + 1); 342 if (!new_num_bins) 343 return; 344 345 new_bins = 346 (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *)); 347 348 for (i = 0; i < old_num_bins; i++) { 349 ptr = table->bins[i]; 350 while (ptr != 0) { 351 next = ptr->next; 352 hash_val = ptr->hash % new_num_bins; 353 ptr->next = new_bins[hash_val]; 354 new_bins[hash_val] = ptr; 355 ptr = next; 356 } 357 } 358 free(table->bins); 359 table->num_bins = new_num_bins; 360 table->bins = new_bins; 361 } 362 363 st_table *st_copy(st_table *old_table) 364 { 365 st_table *new_table; 366 st_table_entry *ptr, *entry; 367 size_t i, num_bins = old_table->num_bins; 368 369 new_table = alloc(st_table); 370 if (new_table == 0) { 371 return 0; 372 } 373 374 *new_table = *old_table; 375 new_table->bins = (st_table_entry **) 376 Calloc(num_bins, sizeof(st_table_entry *)); 377 378 if (new_table->bins == 0) { 379 free(new_table); 380 return 0; 381 } 382 383 for (i = 0; i < num_bins; i++) { 384 new_table->bins[i] = 0; 385 ptr = old_table->bins[i]; 386 while (ptr != 0) { 387 entry = alloc(st_table_entry); 388 if (entry == 0) { 389 free(new_table->bins); 390 free(new_table); 391 return 0; 392 } 393 *entry = *ptr; 394 entry->next = new_table->bins[i]; 395 new_table->bins[i] = entry; 396 ptr = ptr->next; 397 } 398 } 399 return new_table; 400 } 401 402 int st_delete(st_table *table, st_data_t *key, st_data_t *value) 403 { 404 unsigned int hash_val; 405 st_table_entry *tmp; 406 register st_table_entry *ptr; 407 408 hash_val = do_hash_bin(*key, table); 409 ptr = table->bins[hash_val]; 410 411 if (ptr == 0) { 412 if (value != 0) 413 *value = 0; 414 return 0; 415 } 416 417 if (EQUAL(table, *key, ptr->key)) { 418 table->bins[hash_val] = ptr->next; 419 table->num_entries--; 420 if (value != 0) 421 *value = ptr->record; 422 *key = ptr->key; 423 free(ptr); 424 return 1; 425 } 426 427 for (; ptr->next != 0; ptr = ptr->next) { 428 if (EQUAL(table, ptr->next->key, *key)) { 429 tmp = ptr->next; 430 ptr->next = ptr->next->next; 431 table->num_entries--; 432 if (value != 0) 433 *value = tmp->record; 434 *key = tmp->key; 435 free(tmp); 436 return 1; 437 } 438 } 439 440 return 0; 441 } 442 443 int st_delete_safe(st_table *table, st_data_t *key, st_data_t *value, 444 st_data_t never) 445 { 446 unsigned int hash_val; 447 register st_table_entry *ptr; 448 449 hash_val = do_hash_bin(*key, table); 450 ptr = table->bins[hash_val]; 451 452 if (ptr == 0) { 453 if (value != 0) 454 *value = 0; 455 return 0; 456 } 457 458 for (; ptr != 0; ptr = ptr->next) { 459 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 460 table->num_entries--; 461 *key = ptr->key; 462 if (value != 0) 463 *value = ptr->record; 464 ptr->key = ptr->record = never; 465 return 1; 466 } 467 } 468 469 return 0; 470 } 471 472 static int delete_never(st_data_t key, st_data_t value, st_data_t never) 473 { 474 if (value == never) 475 return ST_DELETE; 476 return ST_CONTINUE; 477 } 478 479 void st_cleanup_safe(st_table *table, st_data_t never) 480 { 481 int num_entries = table->num_entries; 482 483 st_foreach(table, delete_never, never); 484 table->num_entries = num_entries; 485 } 486 487 void st_foreach(st_table *table, 488 int (*func)(st_data_t key, st_data_t val, st_data_t arg), 489 st_data_t arg) 490 { 491 st_table_entry *ptr, *last, *tmp; 492 enum st_retval retval; 493 int i; 494 495 for (i = 0; i < table->num_bins; i++) { 496 last = 0; 497 for (ptr = table->bins[i]; ptr != 0;) { 498 retval = (*func) (ptr->key, ptr->record, arg); 499 switch (retval) { 500 case ST_CONTINUE: 501 last = ptr; 502 ptr = ptr->next; 503 break; 504 case ST_STOP: 505 return; 506 case ST_DELETE: 507 tmp = ptr; 508 if (last == 0) { 509 table->bins[i] = ptr->next; 510 } else { 511 last->next = ptr->next; 512 } 513 ptr = ptr->next; 514 free(tmp); 515 table->num_entries--; 516 } 517 } 518 } 519 } 520 521 static int strhash(const char *string) 522 { 523 register int c; 524 525 #ifdef HASH_ELFHASH 526 register unsigned int h = 0, g; 527 528 while ((c = *string++) != '\0') { 529 h = (h << 4) + c; 530 if (g = h & 0xF0000000) 531 h ^= g >> 24; 532 h &= ~g; 533 } 534 return h; 535 #elif HASH_PERL 536 register int val = 0; 537 538 while ((c = *string++) != '\0') { 539 val = val * 33 + c; 540 } 541 542 return val + (val >> 5); 543 #else 544 register int val = 0; 545 546 while ((c = *string++) != '\0') { 547 val = val * 997 + c; 548 } 549 550 return val + (val >> 5); 551 #endif 552 } 553 554 static int numcmp(void *x, void *y) 555 { 556 return (st_ptr_t) x != (st_ptr_t) y; 557 } 558 559 static st_ptr_t numhash(void *n) 560 { 561 return (st_ptr_t) n; 562 } 563