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
48typedef struct st_table_entry st_table_entry;
49
50struct 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 */
69static int numcmp(void *, void *);
70static st_ptr_t numhash(void *);
71static struct st_hash_type type_numhash = {
72	numcmp,
73	numhash,
74};
75
76/* extern int strcmp(const char *, const char *); */
77static int strhash(const char *);
78
79static inline st_ptr_t st_strhash(void *key)
80{
81	return strhash((const char *)key);
82}
83
84static inline int st_strcmp(void *key1, void *key2)
85{
86	return strcmp((const char *)key1, (const char *)key2);
87}
88
89static 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
99static 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*/
118static 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
150static 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
174static int collision = 0;
175static int init_st = 0;
176
177static 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
185st_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
209st_table *st_init_table(struct st_hash_type *type)
210{
211	return st_init_table_with_size(type, 0);
212}
213
214st_table *st_init_numtable(void)
215{
216	return st_init_table(&type_numhash);
217}
218
219st_table *st_init_numtable_with_size(size_t size)
220{
221	return st_init_table_with_size(&type_numhash, size);
222}
223
224st_table *st_init_strtable(void)
225{
226	return st_init_table(&type_strhash);
227}
228
229st_table *st_init_strtable_with_size(size_t size)
230{
231	return st_init_table_with_size(&type_strhash, size);
232}
233
234void 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
273int 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)\
291do {\
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
309int 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
326void 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
335static 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
363st_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
402int 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
443int 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
472static 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
479void 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
487void 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
521static 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
554static int numcmp(void *x, void *y)
555{
556	return (st_ptr_t) x != (st_ptr_t) y;
557}
558
559static st_ptr_t numhash(void *n)
560{
561	return (st_ptr_t) n;
562}
563