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
st_strhash(void * key)81 static inline st_ptr_t st_strhash(void *key)
82 {
83 return strhash((const char *)key);
84 }
85
st_strcmp(void * key1,void * key2)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
new_size(int size)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
stat_col()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
st_init_table_with_size(type,size)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
st_init_table(type)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
st_init_numtable(void)217 st_table *st_init_numtable(void)
218 {
219 return st_init_table(&type_numhash);
220 }
221
st_init_numtable_with_size(size)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
st_init_strtable(void)228 st_table *st_init_strtable(void)
229 {
230 return st_init_table(&type_strhash);
231 }
232
st_init_strtable_with_size(size)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
st_free_table(table)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
st_lookup(table,key,value)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
st_insert(table,key,value)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
st_add_direct(table,key,value)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
rehash(table)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
st_copy(old_table)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
st_delete(table,key,value)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
st_delete_safe(table,key,value,never)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
delete_never(st_data_t key,st_data_t value,st_data_t never)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
st_cleanup_safe(table,never)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
st_foreach(table,func,arg)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
strhash(string)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
numcmp(x,y)578 static int numcmp(x, y)
579 void *x, *y;
580 {
581 return (st_ptr_t) x != (st_ptr_t) y;
582 }
583
numhash(n)584 static st_ptr_t numhash(n)
585 void *n;
586 {
587 return (st_ptr_t) n;
588 }
589