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
50typedef struct st_table_entry st_table_entry;
51
52struct 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 */
71static int numcmp(void *, void *);
72static st_ptr_t numhash(void *);
73static struct st_hash_type type_numhash = {
74	numcmp,
75	numhash,
76};
77
78/* extern int strcmp(const char *, const char *); */
79static int strhash(const char *);
80
81static inline st_ptr_t st_strhash(void *key)
82{
83	return strhash((const char *)key);
84}
85
86static inline int st_strcmp(void *key1, void *key2)
87{
88	return strcmp((const char *)key1, (const char *)key2);
89}
90
91static 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
101static 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*/
120static 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
152static 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
176static int collision = 0;
177static int init_st = 0;
178
179static 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
187st_table *st_init_table_with_size(type, size)
188struct st_hash_type *type;
189size_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
211st_table *st_init_table(type)
212struct st_hash_type *type;
213{
214	return st_init_table_with_size(type, 0);
215}
216
217st_table *st_init_numtable(void)
218{
219	return st_init_table(&type_numhash);
220}
221
222st_table *st_init_numtable_with_size(size)
223size_t size;
224{
225	return st_init_table_with_size(&type_numhash, size);
226}
227
228st_table *st_init_strtable(void)
229{
230	return st_init_table(&type_strhash);
231}
232
233st_table *st_init_strtable_with_size(size)
234size_t size;
235{
236	return st_init_table_with_size(&type_strhash, size);
237}
238
239void st_free_table(table)
240st_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
279int st_lookup(table, key, value)
280st_table *table;
281register st_data_t key;
282st_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)\
300do {\
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
318int st_insert(table, key, value)
319register st_table *table;
320register st_data_t key;
321st_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
338void st_add_direct(table, key, value)
339st_table *table;
340st_data_t key;
341st_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
350static void rehash(table)
351register 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
376st_table *st_copy(old_table)
377st_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
416int st_delete(table, key, value)
417register st_table *table;
418register st_data_t *key;
419st_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
460int st_delete_safe(table, key, value, never)
461register st_table *table;
462register st_data_t *key;
463st_data_t *value;
464st_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
492static 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
499void st_cleanup_safe(table, never)
500st_table *table;
501st_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
509void st_foreach(table, func, arg)
510st_table *table;
511int (*func) (st_data_t key, st_data_t val, st_data_t arg);
512st_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
544static int strhash(string)
545register 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
578static int numcmp(x, y)
579void *x, *y;
580{
581	return (st_ptr_t) x != (st_ptr_t) y;
582}
583
584static st_ptr_t numhash(n)
585void *n;
586{
587	return (st_ptr_t) n;
588}
589