contrib/ofed/management/opensm/opensm/st.c

   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
  50 typedef struct st_table_entry st_table_entry;
  51
  52 struct 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  */
  71 static int numcmp(void *, void *);
  72 static st_ptr_t numhash(void *);
  73 static struct st_hash_type type_numhash = {
  74         numcmp,
  75         numhash,
  76 };
  77
  78 /* extern int strcmp(const char *, const char *); */
  79 static int strhash(const char *);
  80
  81 static inline st_ptr_t st_strhash(void *key)
  82 {
  83         return strhash((const char *)key);
  84 }
  85
  86 static inline int st_strcmp(void *key1, void *key2)
  87 {
  88         return strcmp((const char *)key1, (const char *)key2);
  89 }
  90
  91 static 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
 101 static 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 */
 120 static 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
 152 static 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
 176 static int collision = 0;
 177 static int init_st = 0;
 178
 179 static 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
 187 st_table *st_init_table_with_size(type, size)
 188 struct st_hash_type *type;
 189 size_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
 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         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
 376 st_table *st_copy(old_table)
 377 st_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
 416 int st_delete(table, key, value)
 417 register st_table *table;
 418 register st_data_t *key;
 419 st_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
 460 int st_delete_safe(table, key, value, never)
 461 register st_table *table;
 462 register st_data_t *key;
 463 st_data_t *value;
 464 st_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
 492 static 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
 499 void st_cleanup_safe(table, never)
 500 st_table *table;
 501 st_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
 509 void st_foreach(table, func, arg)
 510 st_table *table;
 511 int (*func) (st_data_t key, st_data_t val, st_data_t arg);
 512 st_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
 544 static int strhash(string)
 545 register 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
 578 static int numcmp(x, y)
 579 void *x, *y;
 580 {
 581         return (st_ptr_t) x != (st_ptr_t) y;
 582 }
 583
 584 static st_ptr_t numhash(n)
 585 void *n;
 586 {
 587         return (st_ptr_t) n;
 588 }