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
st_strhash(void * key)79 static inline st_ptr_t st_strhash(void *key)
80 {
81 return strhash((const char *)key);
82 }
83
st_strcmp(void * key1,void * key2)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
new_size(int size)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
stat_col()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
st_init_table_with_size(type,size)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
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 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
st_copy(old_table)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
st_delete(table,key,value)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
st_delete_safe(table,key,value,never)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
delete_never(st_data_t key,st_data_t value,st_data_t never)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
st_cleanup_safe(table,never)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
st_foreach(table,func,arg)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
strhash(string)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
numcmp(x,y)581 static int numcmp(x, y)
582 void *x, *y;
583 {
584 return (st_ptr_t) x != (st_ptr_t) y;
585 }
586
numhash(n)587 static st_ptr_t numhash(n)
588 void *n;
589 {
590 return (st_ptr_t) n;
591 }
592