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 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 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 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 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 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 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 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 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 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 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