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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
36 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
40 #endif /* HAVE_CONFIG_H */
44 #include <opensm/st.h>
50 typedef struct st_table_entry st_table_entry;
52 struct st_table_entry {
59 #define ST_DEFAULT_MAX_DENSITY 5
60 #define ST_DEFAULT_INIT_TABLE_SIZE 11
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
67 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
71 static int numcmp(void *, void *);
72 static st_ptr_t numhash(void *);
73 static struct st_hash_type type_numhash = {
78 /* extern int strcmp(const char *, const char *); */
79 static int strhash(const char *);
81 static inline st_ptr_t st_strhash(void *key)
83 return strhash((const char *)key);
86 static inline int st_strcmp(void *key1, void *key2)
88 return strcmp((const char *)key1, (const char *)key2);
91 static struct st_hash_type type_strhash = {
96 #define xmalloc malloc
97 #define xcalloc calloc
98 #define xrealloc realloc
101 static void rehash(st_table *);
103 #define alloc(type) (type*)xmalloc(sizeof(type))
104 #define Calloc(n,s) (char*)xcalloc((n), (s))
106 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)(((void*)x),((void *)y)) == 0)
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)
112 * MINSIZE is the minimum size of a dictionary.
118 Table of prime numbers 2^n+a, 2<=n<=30.
120 static long primes[] = {
152 static int new_size(int size)
157 for (i = 3; i < 31; i++) {
165 for (i = 0, newsize = MINSIZE;
166 i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) {
170 /* Ran out of polynomials */
171 return -1; /* should raise exception */
176 static int collision = 0;
177 static int init_st = 0;
179 static void stat_col()
181 FILE *f = fopen("/var/log/osm_st_col", "w");
182 fprintf(f, "collision: %d\n", collision);
187 st_table *st_init_table_with_size(type, size)
188 struct st_hash_type *type;
200 size = new_size(size); /* round up to prime number */
202 tbl = alloc(st_table);
204 tbl->num_entries = 0;
205 tbl->num_bins = size;
206 tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *));
211 st_table *st_init_table(type)
212 struct st_hash_type *type;
214 return st_init_table_with_size(type, 0);
217 st_table *st_init_numtable(void)
219 return st_init_table(&type_numhash);
222 st_table *st_init_numtable_with_size(size)
225 return st_init_table_with_size(&type_numhash, size);
228 st_table *st_init_strtable(void)
230 return st_init_table(&type_strhash);
233 st_table *st_init_strtable_with_size(size)
236 return st_init_table_with_size(&type_strhash, size);
239 void st_free_table(table)
242 register st_table_entry *ptr, *next;
245 for (i = 0; i < table->num_bins; i++) {
246 ptr = table->bins[i];
257 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
258 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
261 #define COLLISION collision++
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)) \
272 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
279 int st_lookup(table, key, value)
281 register st_data_t key;
284 unsigned int hash_val, bin_pos;
285 register st_table_entry *ptr;
287 hash_val = do_hash(key, table);
288 FIND_ENTRY(table, ptr, hash_val, bin_pos);
294 *value = ptr->record;
299 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
301 st_table_entry *entry;\
302 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) \
305 bin_pos = hash_val % table->num_bins;\
308 entry = alloc(st_table_entry);\
310 entry->hash = hash_val;\
312 entry->record = value;\
313 entry->next = table->bins[bin_pos];\
314 table->bins[bin_pos] = entry;\
315 table->num_entries++;\
318 int st_insert(table, key, value)
319 register st_table *table;
320 register st_data_t key;
323 unsigned int hash_val, bin_pos;
324 register st_table_entry *ptr;
326 hash_val = do_hash(key, table);
327 FIND_ENTRY(table, ptr, hash_val, bin_pos);
330 ADD_DIRECT(table, key, value, hash_val, bin_pos);
338 void st_add_direct(table, key, value)
343 unsigned int hash_val, bin_pos;
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);
350 static void rehash(table)
351 register st_table *table;
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;
357 new_num_bins = new_size(old_num_bins + 1);
359 (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *));
361 for (i = 0; i < old_num_bins; i++) {
362 ptr = table->bins[i];
365 hash_val = ptr->hash % new_num_bins;
366 ptr->next = new_bins[hash_val];
367 new_bins[hash_val] = ptr;
372 table->num_bins = new_num_bins;
373 table->bins = new_bins;
376 st_table *st_copy(old_table)
380 st_table_entry *ptr, *entry;
381 size_t i, num_bins = old_table->num_bins;
383 new_table = alloc(st_table);
384 if (new_table == 0) {
388 *new_table = *old_table;
389 new_table->bins = (st_table_entry **)
390 Calloc(num_bins, sizeof(st_table_entry *));
392 if (new_table->bins == 0) {
397 for (i = 0; i < num_bins; i++) {
398 new_table->bins[i] = 0;
399 ptr = old_table->bins[i];
401 entry = alloc(st_table_entry);
403 free(new_table->bins);
408 entry->next = new_table->bins[i];
409 new_table->bins[i] = entry;
416 int st_delete(table, key, value)
417 register st_table *table;
418 register st_data_t *key;
421 unsigned int hash_val;
423 register st_table_entry *ptr;
425 hash_val = do_hash_bin(*key, table);
426 ptr = table->bins[hash_val];
434 if (EQUAL(table, *key, ptr->key)) {
435 table->bins[hash_val] = ptr->next;
436 table->num_entries--;
438 *value = ptr->record;
444 for (; ptr->next != 0; ptr = ptr->next) {
445 if (EQUAL(table, ptr->next->key, *key)) {
447 ptr->next = ptr->next->next;
448 table->num_entries--;
450 *value = tmp->record;
460 int st_delete_safe(table, key, value, never)
461 register st_table *table;
462 register st_data_t *key;
466 unsigned int hash_val;
467 register st_table_entry *ptr;
469 hash_val = do_hash_bin(*key, table);
470 ptr = table->bins[hash_val];
478 for (; ptr != 0; ptr = ptr->next) {
479 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
480 table->num_entries--;
483 *value = ptr->record;
484 ptr->key = ptr->record = never;
492 static int delete_never(st_data_t key, st_data_t value, st_data_t never)
499 void st_cleanup_safe(table, never)
503 int num_entries = table->num_entries;
505 st_foreach(table, delete_never, never);
506 table->num_entries = num_entries;
509 void st_foreach(table, func, arg)
511 int (*func) (st_data_t key, st_data_t val, st_data_t arg);
514 st_table_entry *ptr, *last, *tmp;
515 enum st_retval retval;
518 for (i = 0; i < table->num_bins; i++) {
520 for (ptr = table->bins[i]; ptr != 0;) {
521 retval = (*func) (ptr->key, ptr->record, arg);
532 table->bins[i] = ptr->next;
534 last->next = ptr->next;
538 table->num_entries--;
544 static int strhash(string)
545 register const char *string;
550 register unsigned int h = 0, g;
552 while ((c = *string++) != '\0') {
554 if (g = h & 0xF0000000)
560 register int val = 0;
562 while ((c = *string++) != '\0') {
566 return val + (val >> 5);
568 register int val = 0;
570 while ((c = *string++) != '\0') {
574 return val + (val >> 5);
578 static int numcmp(x, y)
581 return (st_ptr_t) x != (st_ptr_t) y;
584 static st_ptr_t numhash(n)