1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
24  */
25 
26 /*
27  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
28  * Use is subject to license terms.
29  */
30 
31 /*
32  *
33  * MODULE: dapl_hash.c
34  *
35  * PURPOSE: Hash Table
36  * Description:
37  *
38  * Provides a generic hash table with chaining.
39  *
40  * $Id: dapl_hash.c,v 1.10 2003/07/11 18:42:17 hobie16 Exp $
41  */
42 
43 #include "dapl_hash.h"
44 
45 /*
46  *
47  * Structures
48  *
49  */
50 
51 /*
52  * A hash table element
53  */
54 typedef struct DAPL_HASH_ELEM
55 {
56 	struct DAPL_HASH_ELEM	*next_element;
57 	DAPL_HASH_KEY		key;
58 	void			*datum;
59 } DAPL_HASH_ELEM;
60 
61 /*
62  * The hash table
63  */
64 struct dapl_hash_table
65 {
66 	unsigned long		num_entries;
67 	unsigned long		tbl_size;
68 	DAPL_HASH_ELEM		*table;
69 	DAT_BOOLEAN		locking_required; /* internal locking reqd */
70 	DAPL_OS_LOCK		lock;
71 	unsigned long		iterator_bucket;
72 	DAPL_HASH_ELEM		*iterator;
73 	/*
74 	 * statistics - we tally on insert operations, counting
75 	 * the number of entries in the whole hash table, as
76 	 * well as the length of chains we walk to insert.  This
77 	 * ignores empty buckets, giving us data on overall table
78 	 * occupancy, as well as max/average chain length for
79 	 * the buckets used.  If our hash function results in
80 	 * hot buckets, this will show it.
81 	 */
82 	uint64_t		hash_tbl_inserts;   /* total inserts ops    */
83 	uint64_t		hash_tbl_max;	/* max in entire table  */
84 	uint64_t		hash_tbl_total;	/* total in table	*/
85 	uint64_t		hash_chn_max;	/* longest chain	*/
86 	uint64_t		hash_chn_total;	/* total non-0 lenghts  */
87 };
88 
89 
90 /*
91  *
92  * Defines
93  *
94  */
95 
96 /* The hash function */
97 #define	DAPL_DOHASH(key, hashsize)   ((uint64_t)((key) % (hashsize)))
98 
99 /* datum value in empty table slots  (use 0UL or ~0UL as appropriate) */
100 #define	NO_DATUM_VALUE		((void *) 0UL)
101 #define	NO_DATUM(value)		((value) == NO_DATUM_VALUE)
102 
103 /* Lookup macro (which falls back to function to rehash) */
104 #define	DAPL_HASHLOOKUP(p_table, in_key, out_datum, bucket_head) \
105 	{ \
106 		DAPL_HASH_ELEM *element = \
107 		&((p_table)->table)[DAPL_DOHASH(in_key, (p_table)->tbl_size)]; \
108 		if (NO_DATUM(element->datum)) { \
109 			(bucket_head) = (void *)0; \
110 		} else if (element->key == (DAPL_HASH_KEY) (in_key)) { \
111 			(out_datum) = element->datum; \
112 			(bucket_head) = (void *)element; \
113 		} else if (element->next_element) { \
114 			dapli_hash_rehash(element, \
115 					(in_key), \
116 					(void **)&(out_datum), \
117 					(DAPL_HASH_ELEM **)&(bucket_head)); \
118 		} else { \
119 			(bucket_head) = (void *)0; \
120 		}\
121 	}
122 
123 
124 /*
125  *
126  * Internal Functions
127  *
128  */
129 
130 /*
131  * Rehash the key (used by add and lookup functions)
132  *
133  * Inputs:  element	element to rehash key
134  *	    key, datum	datum for key head
135  *	    head	head for list
136  */
137 static void
dapli_hash_rehash(DAPL_HASH_ELEM * element,DAPL_HASH_KEY key,void ** datum,DAPL_HASH_ELEM ** head)138 dapli_hash_rehash(
139 	DAPL_HASH_ELEM	*element,
140 	DAPL_HASH_KEY	key,
141 	void		**datum,
142 	DAPL_HASH_ELEM	** head)
143 {
144 	/*
145 	 * assume we looked at the contents of element already,
146 	 * and start with the next element.
147 	 */
148 	dapl_os_assert(element->next_element);
149 	dapl_os_assert(!NO_DATUM(element->datum));
150 
151 	*head = element;
152 	/*CONSTCOND*/
153 	while (1) {
154 		element = element->next_element;
155 		if (!element) {
156 			break;
157 		}
158 		if (element->key == key) {
159 			*datum = element->datum;
160 			return;
161 		}
162 	}
163 	*head = 0;
164 }
165 
166 /*
167  * Add a new key to the hash table
168  *
169  * Inputs:
170  *          table, key and datum to be added
171  *          allow_dup   - DAT_TRUE if dups are allowed
172  * Outputs:
173  *          report_dup  - should you care to know
174  * Returns:
175  *          DAT_TRUE on success
176  */
177 static DAT_BOOLEAN
dapli_hash_add(DAPL_HASH_TABLEP p_table,DAPL_HASH_KEY key,void * datum,DAT_BOOLEAN allow_dup,DAT_BOOLEAN * report_dup)178 dapli_hash_add(
179 	DAPL_HASH_TABLEP	p_table,
180 	DAPL_HASH_KEY		key,
181 	void			*datum,
182 	DAT_BOOLEAN		allow_dup,
183 	DAT_BOOLEAN		*report_dup)
184 {
185 	void		*olddatum;
186 	DAPL_HASH_KEY   hashValue;
187 	DAPL_HASH_ELEM *found;
188 	DAT_BOOLEAN	status = DAT_FALSE;
189 	unsigned int    chain_len = 0;
190 
191 	if (report_dup) {
192 		(*report_dup) = DAT_FALSE;
193 	}
194 
195 	if (NO_DATUM(datum)) {
196 		/*
197 		 * Reserved value used for datum
198 		 */
199 		dapl_dbg_log(
200 		    DAPL_DBG_TYPE_ERR,
201 		    "dapli_hash_add () called with magic NO_DATA value "
202 		    "(%p) used as datum!\n", datum);
203 		return (DAT_FALSE);
204 	}
205 
206 	DAPL_HASHLOOKUP(p_table, key, olddatum, found);
207 
208 	if (found) {
209 		/*
210 		 * key exists already
211 		 */
212 		if (report_dup) {
213 			*report_dup = DAT_TRUE;
214 		}
215 
216 		if (!allow_dup) {
217 			dapl_dbg_log(DAPL_DBG_TYPE_ERR,
218 			    "dapli_hash_add () called with duplicate key "
219 			    "(" F64x ")\n", key);
220 			return (DAT_FALSE);
221 		}
222 	}
223 
224 	hashValue = DAPL_DOHASH(key, p_table->tbl_size);
225 	if (NO_DATUM(p_table->table[hashValue].datum)) {
226 		/*
227 		 * Empty head - just fill it in
228 		 */
229 		p_table->table[hashValue].key = key;
230 		p_table->table[hashValue].datum = datum;
231 		p_table->table[hashValue].next_element = 0;
232 		p_table->num_entries++;
233 		status = DAT_TRUE;
234 	} else {
235 		DAPL_HASH_ELEM *newelement = (DAPL_HASH_ELEM *)
236 		    dapl_os_alloc(sizeof (DAPL_HASH_ELEM));
237 		/*
238 		 * Add an element to the end of the chain
239 		 */
240 		if (newelement) {
241 			DAPL_HASH_ELEM *lastelement;
242 			newelement->key = key;
243 			newelement->datum = datum;
244 			newelement->next_element = 0;
245 			for (lastelement = &p_table->table[hashValue];
246 			    lastelement->next_element;
247 			    lastelement = lastelement->next_element) {
248 				/* Walk to the end of the chain */
249 				chain_len++;
250 			}
251 			lastelement->next_element = newelement;
252 			p_table->num_entries++;
253 			status = DAT_TRUE;
254 		} else {
255 			/* allocation failed - should not happen */
256 			status = DAT_FALSE;
257 		}
258 	}
259 
260 	/*
261 	 * Tally up our counters. chain_len is one less than current chain
262 	 * length.
263 	 */
264 	chain_len++;
265 	p_table->hash_tbl_inserts++;
266 	p_table->hash_tbl_total += p_table->num_entries;
267 	p_table->hash_chn_total += chain_len;
268 	if (p_table->num_entries > p_table->hash_tbl_max) {
269 		p_table->hash_tbl_max = p_table->num_entries;
270 	}
271 	if (chain_len > p_table->hash_chn_max) {
272 		p_table->hash_chn_max = chain_len;
273 	}
274 
275 	return (status);
276 }
277 
278 
279 /*
280  * Remove element from hash bucket
281  *
282  * Inputs:
283  *          element, key        to be deleted
284  * Returns:
285  *          DAT_TRUE on success
286  */
287 static DAT_BOOLEAN
dapl_hash_delete_element(DAPL_HASH_ELEM * element,DAPL_HASH_KEY key,DAPL_HASH_DATA * p_datum)288 dapl_hash_delete_element(DAPL_HASH_ELEM * element,
289 			DAPL_HASH_KEY key,
290 			DAPL_HASH_DATA *p_datum)
291 {
292 	DAPL_HASH_ELEM *curelement;
293 	DAPL_HASH_ELEM *lastelement;
294 
295 	lastelement = NULL;
296 	for (curelement = element; curelement;
297 	    lastelement = curelement,
298 	    curelement = curelement->next_element) {
299 		if (curelement->key == key) {
300 			if (p_datum) {
301 				*p_datum = curelement->datum;
302 			}
303 			if (lastelement) {
304 				/*
305 				 * curelement was malloc'd; free it
306 				 */
307 				lastelement->next_element =
308 				    curelement->next_element;
309 				dapl_os_free((void *) curelement,
310 				    sizeof (DAPL_HASH_ELEM));
311 			} else {
312 				/*
313 				 * curelement is static list head
314 				 */
315 				DAPL_HASH_ELEM *n = curelement->next_element;
316 				if (n) {
317 					/*
318 					 * If there is a next element, copy its
319 					 * contents into the head and free the
320 					 * original next element.
321 					 */
322 					curelement->key = n->key;
323 					curelement->datum = n->datum;
324 					curelement->next_element =
325 					    n->next_element;
326 					dapl_os_free((void *) n,
327 					    sizeof (DAPL_HASH_ELEM));
328 				} else {
329 					curelement->datum = NO_DATUM_VALUE;
330 				}
331 			}
332 			break;
333 		}
334 	}
335 
336 	return (curelement != NULL ? DAT_TRUE : DAT_FALSE);
337 }
338 
339 
340 /*
341  *
342  * External Functions
343  *
344  */
345 
346 
347 /*
348  * Create a new hash table with at least 'table_size' hash buckets.
349  */
350 DAT_RETURN
dapls_hash_create(IN DAT_COUNT table_size,IN DAT_BOOLEAN locking_required,OUT DAPL_HASH_TABLE ** pp_table)351 dapls_hash_create(
352 	IN DAT_COUNT	table_size,
353 	IN DAT_BOOLEAN	locking_required,
354 	OUT DAPL_HASH_TABLE **pp_table)
355 {
356 	DAPL_HASH_TABLE *p_table;
357 	DAT_COUNT	table_length = table_size * sizeof (DAPL_HASH_ELEM);
358 	DAT_RETURN	dat_status;
359 	DAT_COUNT	i;
360 
361 	dapl_os_assert(pp_table);
362 	dat_status = DAT_SUCCESS;
363 
364 	/* Allocate hash table */
365 	p_table = dapl_os_alloc(sizeof (DAPL_HASH_TABLE));
366 	if (NULL == p_table) {
367 		dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
368 		    DAT_RESOURCE_MEMORY);
369 		goto bail;
370 	}
371 
372 	/* Init hash table, allocate and init and buckets */
373 	(void) dapl_os_memzero(p_table, sizeof (DAPL_HASH_TABLE));
374 	p_table->tbl_size = table_size;
375 	p_table->table = (DAPL_HASH_ELEM *)dapl_os_alloc(table_length);
376 	if (NULL == p_table->table) {
377 		dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
378 		dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
379 		    DAT_RESOURCE_MEMORY);
380 		goto bail;
381 	}
382 	/* Init the lock anyways */
383 	dapl_os_lock_init(&p_table->lock);
384 	p_table->locking_required = locking_required;
385 
386 	for (i = 0; i < table_size; i++) {
387 		p_table->table[i].datum = NO_DATUM_VALUE;
388 		p_table->table[i].key   = 0;
389 		p_table->table[i].next_element = 0;
390 	}
391 
392 	*pp_table = p_table;
393 
394 bail:
395 	return (dat_status);
396 }
397 
398 
399 /*
400  * Destroy a hash table
401  */
402 DAT_RETURN
dapls_hash_free(IN DAPL_HASH_TABLE * p_table)403 dapls_hash_free(
404 	IN DAPL_HASH_TABLE *p_table)
405 {
406 	dapl_os_assert(p_table && p_table->table);
407 
408 	dapl_os_lock_destroy(&p_table->lock);
409 	dapl_os_free(p_table->table,
410 	    sizeof (DAPL_HASH_ELEM) * p_table->tbl_size);
411 	dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
412 
413 	return (DAT_SUCCESS);
414 }
415 
416 
417 /*
418  * Returns the number of elements stored in the table
419  */
420 
421 DAT_RETURN
dapls_hash_size(IN DAPL_HASH_TABLE * p_table,OUT DAT_COUNT * p_size)422 dapls_hash_size(
423     IN DAPL_HASH_TABLE  *p_table,
424     OUT DAT_COUNT	*p_size)
425 {
426 	dapl_os_assert(p_table && p_size);
427 
428 	*p_size = p_table->num_entries;
429 
430 	return (DAT_SUCCESS);
431 }
432 
433 
434 /*
435  * Inserts the specified data into the table with the given key.
436  * Duplicates are not expected, and return in error, having done nothing.
437  */
438 
439 DAT_RETURN
dapls_hash_insert(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,IN DAPL_HASH_DATA data)440 dapls_hash_insert(
441     IN DAPL_HASH_TABLE  *p_table,
442     IN DAPL_HASH_KEY    key,
443     IN DAPL_HASH_DATA   data)
444 {
445 	DAT_RETURN	dat_status;
446 
447 	dapl_os_assert(p_table);
448 	dat_status = DAT_SUCCESS;
449 
450 	if (p_table->locking_required) {
451 		dapl_os_lock(&p_table->lock);
452 	}
453 
454 	if (!dapli_hash_add(p_table, key, data, DAT_FALSE, NULL)) {
455 		dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
456 		    DAT_RESOURCE_MEMORY);
457 	}
458 
459 	if (p_table->locking_required) {
460 		dapl_os_unlock(&p_table->lock);
461 	}
462 
463 	return (dat_status);
464 }
465 
466 
467 /*
468  * Searches for the given key.  If found,
469  * DAT_SUCCESS is returned and the associated
470  * data is returned in the DAPL_HASH_DATA
471  * pointer if that pointer is not NULL.
472  */
473 DAT_RETURN
dapls_hash_search(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,OUT DAPL_HASH_DATA * p_data)474 dapls_hash_search(
475     IN DAPL_HASH_TABLE *p_table,
476     IN DAPL_HASH_KEY    key,
477     OUT DAPL_HASH_DATA *p_data)
478 {
479 	DAT_RETURN	dat_status;
480 	void		*olddatum;
481 	DAPL_HASH_ELEM	*found;
482 
483 	dapl_os_assert(p_table);
484 	dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
485 
486 	if (p_table->locking_required) {
487 		dapl_os_lock(&p_table->lock);
488 		DAPL_HASHLOOKUP(p_table, key, olddatum, found);
489 		dapl_os_unlock(&p_table->lock);
490 	} else {
491 		DAPL_HASHLOOKUP(p_table, key, olddatum, found);
492 	}
493 
494 	if (found) {
495 		if (p_data) {
496 			*p_data = olddatum;
497 		}
498 		dat_status = DAT_SUCCESS;
499 	}
500 
501 	return (dat_status);
502 }
503 
504 
505 DAT_RETURN
dapls_hash_remove(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,OUT DAPL_HASH_DATA * p_data)506 dapls_hash_remove(
507     IN DAPL_HASH_TABLE *p_table,
508     IN DAPL_HASH_KEY key,
509     OUT DAPL_HASH_DATA *p_data)
510 {
511 	DAT_RETURN	dat_status;
512 	DAPL_HASH_KEY   hashValue;
513 
514 	dapl_os_assert(p_table);
515 	dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
516 
517 	if (p_table->num_entries == 0) {
518 		dapl_dbg_log(DAPL_DBG_TYPE_ERR,
519 		    "dapls_hash_remove () called on empty hash table!\n");
520 		return (dat_status);
521 	}
522 
523 	hashValue = DAPL_DOHASH(key, p_table->tbl_size);
524 	if (p_table->locking_required) {
525 		dapl_os_lock(&p_table->lock);
526 	}
527 	if (dapl_hash_delete_element(&p_table->table[hashValue], key, p_data)) {
528 		p_table->num_entries--;
529 		dat_status = DAT_SUCCESS;
530 	}
531 	if (p_table->locking_required) {
532 		dapl_os_unlock(&p_table->lock);
533 	}
534 	return (dat_status);
535 }
536 /*
537  * Iterates through the entire hash table return one element at a time.
538  * Note: this is not a threadsafe routine and hence consumers that
539  * rely on the hash-tables internal locking are not allowed to use this.
540  */
541 DAT_RETURN
dapls_hash_iterate(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_ITERATOR op,OUT DAPL_HASH_DATA * p_data)542 dapls_hash_iterate(
543     IN DAPL_HASH_TABLE		*p_table,
544     IN DAPL_HASH_ITERATOR	op,
545     OUT DAPL_HASH_DATA		*p_data)
546 {
547 	DAPL_HASH_ELEM *curr;
548 
549 	dapl_os_assert(p_table);
550 	/*
551 	 * sorry iterate is supported only for consumers that do their
552 	 * own locking
553 	 */
554 	if (p_table->locking_required) {
555 		return (DAT_ERROR(DAT_INVALID_PARAMETER, 0));
556 	}
557 	if (op == DAPL_HASH_ITERATE_INIT) {
558 		/* the hash table is empty */
559 		if (p_table->num_entries == 0) {
560 			*p_data = NULL;
561 			return (DAT_SUCCESS);
562 		}
563 		/* find the first bucket with valid data */
564 		p_table->iterator_bucket = 0;
565 		while (p_table->iterator_bucket < p_table->tbl_size) {
566 			curr = &p_table->table[p_table->iterator_bucket];
567 			if (NO_DATUM(curr->datum)) {
568 				/* empty bucket - move on */
569 				p_table->iterator_bucket++;
570 			} else {
571 				break;
572 			}
573 		}
574 		/* should not be empty if num_entries is non-zero */
575 		dapl_os_assert(!NO_DATUM(curr->datum));
576 		if (p_table->iterator_bucket == p_table->tbl_size) {
577 			p_table->iterator = NULL;
578 		} else {
579 			p_table->iterator = curr;
580 		}
581 	} else {
582 		dapl_os_assert(op == DAPL_HASH_ITERATE_NEXT);
583 	}
584 	/* iterator points to the element to be returned */
585 	if (p_table->iterator == NULL) {
586 		/* nothing more left in the hashtable */
587 		*p_data = NULL;
588 		return (DAT_SUCCESS);
589 	}
590 
591 	dapl_dbg_log(DAPL_DBG_TYPE_EP,
592 	    "dapls_hash_iterate: entry found=(%p), bucket(%d)\n",
593 	    p_table->iterator, p_table->iterator_bucket);
594 	*p_data = p_table->iterator->datum;
595 	curr = p_table->iterator;
596 
597 	/* re-position iterator to point to the next valid element */
598 	if (curr->next_element != NULL) { /* found the next element */
599 		p_table->iterator = curr->next_element;
600 		dapl_os_assert(!NO_DATUM(p_table->iterator->datum));
601 	} else {
602 		p_table->iterator = NULL;
603 		/*
604 		 * We are here means we've hit the end of the current bucket,
605 		 * so start searching for next bucket with a valid entry -
606 		 * we only need to look at the head of the bucket
607 		 */
608 		p_table->iterator_bucket++;
609 		while (p_table->iterator_bucket < p_table->tbl_size) {
610 			curr = &p_table->table[p_table->iterator_bucket];
611 			if (NO_DATUM(curr->datum)) {
612 				p_table->iterator_bucket++;
613 			} else {
614 				p_table->iterator = curr;
615 				break;
616 			}
617 		}
618 	}
619 	return (DAT_SUCCESS);
620 }
621