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(void)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
st_init_table_with_size(struct st_hash_type * type,size_t size)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
st_init_table(struct st_hash_type * type)209 st_table *st_init_table(struct st_hash_type *type)
210 {
211 return st_init_table_with_size(type, 0);
212 }
213
st_init_numtable(void)214 st_table *st_init_numtable(void)
215 {
216 return st_init_table(&type_numhash);
217 }
218
st_init_numtable_with_size(size_t size)219 st_table *st_init_numtable_with_size(size_t size)
220 {
221 return st_init_table_with_size(&type_numhash, size);
222 }
223
st_init_strtable(void)224 st_table *st_init_strtable(void)
225 {
226 return st_init_table(&type_strhash);
227 }
228
st_init_strtable_with_size(size_t size)229 st_table *st_init_strtable_with_size(size_t size)
230 {
231 return st_init_table_with_size(&type_strhash, size);
232 }
233
st_free_table(st_table * table)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
st_lookup(st_table * table,st_data_t key,st_data_t * value)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
st_insert(st_table * table,st_data_t key,st_data_t value)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
st_add_direct(st_table * table,st_data_t key,st_data_t value)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
rehash(st_table * table)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
st_copy(st_table * old_table)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
st_delete(st_table * table,st_data_t * key,st_data_t * value)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
st_delete_safe(st_table * table,st_data_t * key,st_data_t * value,st_data_t never)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
delete_never(st_data_t key,st_data_t value,st_data_t never)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
st_cleanup_safe(st_table * table,st_data_t never)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
st_foreach(st_table * table,int (* func)(st_data_t key,st_data_t val,st_data_t arg),st_data_t arg)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
strhash(const char * string)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
numcmp(void * x,void * y)554 static int numcmp(void *x, void *y)
555 {
556 return (st_ptr_t) x != (st_ptr_t) y;
557 }
558
numhash(void * n)559 static st_ptr_t numhash(void *n)
560 {
561 return (st_ptr_t) n;
562 }
563