xref: /freebsd/contrib/ofed/opensm/opensm/st.c (revision bf7830d79dd02a84225c93130c2dce68e0a541d6)
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