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