1/* ***************************************************************************** 2 3libcsc: Hash Table Subsystem 4 5 ---------------------------------------------------------------- 6 7Copyright (c) 1999, 2001, 2002 Douglas R. Jerome, Peoria, AZ USA 8 9 This program is free software; you can redistribute it and/or modify 10 it under the terms of the GNU Library General Public License as 11 published by the Free Software Foundation; either version 2 of the 12 License, or (at your option) any later version. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU Library General Public 20 License along with this program; if not, write to the Free Software 21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 22 23 ---------------------------------------------------------------- 24 25FILE NAME 26 27 $RCSfile: csc_hash.c,v $ 28 $Revision: 1.4 $ 29 $Date: 2003/03/26 02:03:23 $ 30 31PROGRAM INFORMATION 32 33 Developed by: libcsc project 34 Developer: Douglas R. Jerome, drj, <jerome@primenet.com> 35 36FILE DESCRIPTION 37 38<SUBSYSTEM NAME="csc_hash"> 39 40NAME 41 csc_hash 42 43DESCRIPTION 44 Hash table Subsystem 45 46FUNCTIONS 47 CSChashNew - create a new libcsc hash table 48 CSChashDel - remove a libcsc hash table 49 CSChashStat - query statistics of a libcsc hash table 50 CSChashEntryPut - put an entry into a libcsc hash table 51 CSChashEntryGet - get an item from a libcsc hash table 52 CSChashEntryDel - remove an entry from a libcsc hash table 53 CSChashEntryNext - find next entry in a libcsc hash table 54 CSChashEntryStat - query the fields of a libcsc hash table entry 55 CSChashRead - read an ASCII format libcsc hash table 56 CSChashWrite - write a libcsc hash table in an ASCII format 57 CSChashDump - write a formatted dump of a libcsc hash table 58</SUBSYSTEM> 59 60CHANGE LOG 61 62 25mar03 drj Fixed bucket allocation problem in initHashTab(). 63 Corrected previous improvement in CSChashEntryGet(). 64 65 23mar03 drj Added a CSCmemListType argument to CSChashEntryGet(). 66 67 22apr02 drj Added internal documentation. 68 69 13apr02 drj Converted to libcsc: renamed everything from rt to csc, 70 removed some debug message printing code. 71 72 11may00 drj Tracked changes to rtsMem*. 73 74 15apr00 drj Moved the hash union structure definition into rts.h. 75 Made the hash structures more opaque and simplified the 76 functions that returns pointers. 77 Fixed buggy rebuild. 78 Fixed buggy entry deletion. 79 Fixed up unused stats in rtsHashWrite. 80 Fixed bug in rtsHashEntryGet(). 81 82 28nov99 drj Fixed bug in rtsHashEntryNext(); bad return value. 83 Added more output text to rtsHashWrite(). Fixed up 84 rtsHashWrite() to not crash with empty hash tables. 85 Fixed rtsHashNew() to accept zero size indicating a 86 growing hash table. 87 88 26nov99 drj Fixed bug in rtsHashEntryPut(); address operator 89 missing. 90 91 29apr99 drj Rebaselined from librt version 0.3.1. 92 93***************************************************************************** */ 94 95 96/* ************************************************************************* */ 97/* */ 98/* F e a t u r e S w i t c h e s */ 99/* */ 100/* ************************************************************************* */ 101 102/* 103 * Select these feature by moving them from the `if UNDEF' into the `else' 104 * section. 105 */ 106#ifdef UNDEF 107# define _BSD_SOURCE 1 /* 4.3+bsd subsystems */ 108# define _POSIX_SOURCE 1 /* posix.1 */ 109# define _POSIX_C_SOURCE 199309L /* posix.1 and posix.4 */ 110#else 111# define _POSIX_C_SOURCE 199506L /* posix.1 and posix.4 and MORE */ 112# ifndef _REENTRANT 113# define _REENTRANT /* thread-safe for glibc */ 114# endif 115#endif 116 117 118/* ************************************************************************* */ 119/* */ 120/* I n c l u d e d F i l e s */ 121/* */ 122/* ************************************************************************* */ 123 124/* 125 * OS Specific Header Files 126 */ 127/* (None.) */ 128 129/* 130 * Standard C (ANSI) Header Files 131 */ 132#include <stdio.h> 133#include <stdlib.h> 134#include <string.h> 135 136/* 137 * Posix Header Files 138 */ 139#include <unistd.h> 140 141/* 142 * 4.3+BSD Header Files 143 */ 144/* (None.) */ 145 146/* 147 * Project Specific Header Files 148 */ 149#include "libcsc_debug.h" 150#include "libcsc.h" 151 152 153/* ************************************************************************* */ 154/* */ 155/* M a n i f e s t C o n s t a n t s */ 156/* */ 157/* ************************************************************************* */ 158 159#define HASH_SIG (0x48415348) 160 161#define PRED(x) ((x)->pred) 162#define SUCC(x) ((x)->succ) 163 164#define COSMOLOGICAL_CONSTANT (7) 165#define CSC_HASH_GROWS (0) 166 167#define MON_ENTER(x) {if(x->monFunc!=NULL)(*x->monFunc)\ 168 (CSC_IN,(void*)x->monData);} 169 170#define MON_EXIT(x) {if(x->monFunc!=NULL)(*x->monFunc)\ 171 (CSC_OUT,(void*)x->monData);} 172 173 174/* ************************************************************************* */ 175/* */ 176/* E x t e r n a l R e f e r e n c e s */ 177/* */ 178/* ************************************************************************* */ 179 180/* (None.) */ 181 182 183/* ************************************************************************* */ 184/* */ 185/* S c a l a r D a t a T y p e s */ 186/* */ 187/* ************************************************************************* */ 188 189typedef unsigned long CSChashType; 190 191 192/* ************************************************************************* */ 193/* */ 194/* N o n - S c a l a r D a t a S t r u c t u r e s */ 195/* */ 196/* ************************************************************************* */ 197 198typedef struct S_hashEntryType 199 { 200#ifdef DEBUG 201 long sig_lo; 202#endif 203 struct S_hashEntryType* succ; 204 struct S_hashEntryType* pred; 205 S_hashKeyUnion key; 206 void* data; 207 size_t size; 208#ifdef DEBUG 209 long sig_hi; 210#endif 211 } S_hashEntryType; 212 213typedef struct S_hashTableType 214 { 215#ifdef DEBUG 216 long sig_lo; 217#endif 218 const char* name; 219 S_hashEntryType** hash; 220 CSChashKeyType keySpec; 221 CSCmemListType memLst; 222 CSCmonFnType monFunc; 223 const void* monData; 224 CSCprofileType profiling; 225 size_t count; 226 size_t nhash; 227 CSCboolean grows; 228 unsigned long downShift; 229 unsigned long mask; 230 size_t resizes; 231 size_t deletions; 232 size_t insertions; 233 size_t collisions; 234#ifdef DEBUG 235 long sig_hi; 236#endif 237 } S_hashTableType; 238 239 240/* ************************************************************************* */ 241/* */ 242/* P u b l i c G l o b a l V a r i a b l e s */ 243/* */ 244/* ************************************************************************* */ 245 246/* (None.) */ 247 248 249/* ************************************************************************* */ 250/* */ 251/* P r i v a t e G l o b a l V a r i a b l e s */ 252/* */ 253/* ************************************************************************* */ 254 255/* (None.) */ 256 257 258/* ************************************************************************* */ 259/* */ 260/* E x e c u t a b l e C o d e (Locally Used Functions) */ 261/* */ 262/* ************************************************************************* */ 263 264 265/************************************************************************** 266 * Private Function Prototypes 267 **************************************************************************/ 268 269PRIVATE CSChashType CSChashStr ( 270 const size_t nhash, 271 const char* const keyPtr 272 ); 273 274PRIVATE int CSChash ( 275 const CSChashKeyUnion* const keyPtr, 276 const CSChashTableType hashTablePtr, 277 CSChashType* const hashValPtr 278 ); 279 280PRIVATE int hashMatch ( 281 const CSChashKeyType keySpec, 282 const CSChashKeyUnion* const key1Ptr, 283 const CSChashKeyUnion* const key2Ptr 284 ); 285 286PRIVATE int initHashTab ( 287 CSChashTableType const hashTablePtr, 288 const CSChashKeyType keySpec, 289 const size_t size 290 ); 291 292PRIVATE int clearHashTab ( 293 const CSChashTableType hashTablePtr 294 ); 295 296PRIVATE int hashEntryNew ( 297 CSChashEntryType* const entryPtrPtr, 298 CSCmemListType const memLst, 299 const CSChashKeyType keySpec, 300 const CSChashKeyUnion* const keyPtr, 301 const void* const itemPtr, 302 const size_t itemSize 303 ); 304 305PRIVATE int hashEntryDel ( 306 CSChashEntryType const oldEntryPtr, 307 CSCmemListType const memLst, 308 const CSChashKeyType keySpec 309 ); 310 311PRIVATE int hashLinkAdd ( 312 CSChashEntryType* const hashListPtrPtr, 313 CSChashEntryType const newEntryPtr 314 ); 315 316PRIVATE int hashLinkSub ( 317 CSChashEntryType* const hashListPtrPtr, 318 CSChashEntryType const oldEntryPtr 319 ); 320 321PRIVATE int hashEntryFind ( 322 const CSChashEntryType hashListPtr, 323 const CSChashKeyUnion* const keyPtr, 324 const CSChashKeyType keySpec, 325 CSChashEntryType* const hashEntryPtrPtr, 326 void** const itemPtrPtr, 327 size_t* const itemSizePtr 328 ); 329 330PRIVATE int rebuild ( 331 const CSChashTableType hashTablePtr 332 ); 333 334 335/* ---------------------------------------------------------------------- */ 336 337 338/************************************************************************** 339 * Private Function CSChashStr 340 **************************************************************************/ 341 342PRIVATE CSChashType CSChashStr ( 343 const size_t nhash, 344 const char* const keyPtr 345 ) 346 { 347 CSChashType hashVal; 348 CSChashType hashG; 349 char* bufPtr; 350 char ch; 351 int index; 352 353 ASSERT_RTN (keyPtr != NULL, "CSChashStr: null keyPtr", 0); 354 355 hashVal = 0; 356 for ( bufPtr = (char*) keyPtr, index = 1 ; (ch = *bufPtr++) ; index++ ) 357 { 358 hashVal = (hashVal << 4) + ((CSChashType)ch * 13); 359 if ((hashG = hashVal & 0xF0000000)) 360 { 361 hashVal = hashVal ^ (hashG >> 24); 362 hashVal = hashVal ^ hashG; 363 } 364 } 365 hashVal %= (CSChashType)nhash; 366 367 return (hashVal); 368 } 369 370 371/************************************************************************** 372 * Private Function CSChash 373 **************************************************************************/ 374 375PRIVATE int CSChash ( 376 const CSChashKeyUnion* const keyPtr, 377 const CSChashTableType hashTablePtr, 378 CSChashType* const hashValuePtr 379 ) 380 { 381 int hashStat = CSC_OK; 382 CSChashType tmpHash = 0; 383 384 ASSERT_RTN (keyPtr != NULL, "CSChash: null keyPtr", CSC_BADARG); 385 ASSERT_RTN (hashTablePtr != NULL, "CSChash: null hashTablePtr", CSC_BADARG); 386 ASSERT_RTN (hashValuePtr != NULL, "CSChash: null hashTablePtr", CSC_BADARG); 387 388 switch (hashTablePtr->keySpec) 389 { 390 default: 391 hashStat = CSC_CORRUPT; 392 break; 393 394 case CSC_HASH_ASCIIZ_KEY: 395 tmpHash = CSChashStr (hashTablePtr->nhash, keyPtr->asciiz); 396 break; 397 398 case CSC_HASH_INT32_KEY: 399 tmpHash = ((long)(keyPtr->integer) * 1103515245L); 400 tmpHash = tmpHash >> hashTablePtr->downShift; 401 tmpHash = tmpHash & hashTablePtr->mask; 402 break; 403 } 404 405 if (hashStat == CSC_OK) *hashValuePtr = tmpHash; 406 407 return (hashStat); 408 } 409 410 411/************************************************************************** 412 * Private Function hashMatch 413 **************************************************************************/ 414 415PRIVATE int hashMatch ( 416 const CSChashKeyType keySpec, 417 const CSChashKeyUnion* const key1Ptr, 418 const CSChashKeyUnion* const key2Ptr 419 ) 420 { 421 int matchStat = CSC_NOTFOUND; 422 423 ASSERT_RTN (key1Ptr != NULL, "hashMatch: null key1Ptr", CSC_BADARG); 424 ASSERT_RTN (key2Ptr != NULL, "hashMatch: null key2Ptr", CSC_BADARG); 425 426 switch (keySpec) 427 { 428 default: 429 matchStat = CSC_CORRUPT; 430 break; 431 432 case CSC_HASH_ASCIIZ_KEY: 433 if (CSC_STREQ(key1Ptr->asciiz,key2Ptr->asciiz)) matchStat = CSC_OK; 434 break; 435 436 case CSC_HASH_INT32_KEY: 437 if (key1Ptr->integer == key2Ptr->integer) matchStat = CSC_OK; 438 break; 439 } 440 441 return (matchStat); 442 } 443 444 445/************************************************************************** 446 * Private Function initHashTab 447 **************************************************************************/ 448 449PRIVATE int initHashTab ( 450 CSChashTableType const hashTable, 451 const CSChashKeyType keySpec, 452 const size_t size 453 ) 454 { 455 int initStat = CSC_OK; 456 int tableSize; 457 int index; 458 459 ASSERT_RTN (hashTable != NULL, "initHashTab: null hashTab", CSC_BADARG); 460 ASSERT_RTN ( \ 461 keySpec==CSC_HASH_ASCIIZ_KEY || keySpec==CSC_HASH_INT32_KEY,\ 462 "initHashTab: invalid keySpec", \ 463 CSC_BADARG \ 464 ); 465 466 hashTable->hash = NULL; 467 hashTable->keySpec = -1; 468 hashTable->count = -1; 469 hashTable->nhash = -1; 470 hashTable->resizes = -1; 471 hashTable->deletions = -1; 472 hashTable->insertions = -1; 473 hashTable->collisions = -1; 474 hashTable->grows = CSC_INDETERMINATE; 475 hashTable->downShift = -1; 476 hashTable->mask = -1; 477 478 if (size == CSC_HASH_GROWS) 479 tableSize = (int)4; 480 else 481 tableSize = (int)size; 482 483 initStat = CSCmemAlloc ( 484 hashTable->memLst, 485 (void**)&hashTable->hash, 486 tableSize, 487 sizeof(S_hashEntryType), 488 0 489 ); 490 491 if (initStat == CSC_OK) 492 { 493 for ( index = 0 ; index < tableSize ; index++ ) 494 { 495 hashTable->hash[index] = NULL; 496 } 497 hashTable->keySpec = keySpec; 498 hashTable->count = 0; 499 hashTable->nhash = tableSize; 500 hashTable->resizes = 0; 501 hashTable->deletions = 0; 502 hashTable->insertions = 0; 503 hashTable->collisions = 0; 504 if (size == CSC_HASH_GROWS) 505 { 506 hashTable->grows = CSC_TRUE; 507 hashTable->downShift = 28; 508 hashTable->mask = 3; 509 } 510 else 511 { 512 hashTable->grows = CSC_FALSE; 513 } 514 } 515 else 516 { 517 hashTable->hash = NULL; 518 hashTable->memLst = NULL; 519 initStat = CSC_NOMEM; 520 } 521 522 return (initStat); 523 } 524 525 526/************************************************************************** 527 * Private Function clearHashTab 528 **************************************************************************/ 529 530PRIVATE int clearHashTab ( 531 CSChashTableType const hashTable 532 ) 533 { 534 int clrStat = CSC_OK; 535 536 ASSERT_RTN (hashTable != NULL, "clearHashTab: null hashTable", CSC_BADARG); 537 ASSERT_RTN ( \ 538 hashTable->sig_lo == HASH_SIG, \ 539 "clearHashTab: bad signature in hashTable", \ 540 CSC_CORRUPT \ 541 ); 542 ASSERT_RTN ( \ 543 hashTable->sig_hi == HASH_SIG, \ 544 "clearHashTab: bad signature in hashTable", \ 545 CSC_CORRUPT \ 546 ); 547 548 ASSERT (hashTable->hash != NULL); 549 (void)CSCmemFree (hashTable->memLst, (void**)&hashTable->hash, 0); 550 551 hashTable->hash = NULL; 552 hashTable->keySpec = -1; 553 hashTable->count = -1; 554 hashTable->nhash = -1; 555 hashTable->resizes = -1; 556 hashTable->deletions = -1; 557 hashTable->insertions = -1; 558 hashTable->collisions = -1; 559 hashTable->grows = CSC_INDETERMINATE; 560 hashTable->downShift = -1; 561 hashTable->mask = -1; 562 563 return (clrStat); 564 } 565 566 567/************************************************************************** 568 * Private Function hashEntryNew 569 **************************************************************************/ 570 571PRIVATE int hashEntryNew ( 572 CSChashEntryType* const entryPtrPtr, 573 CSCmemListType const memLst, 574 const CSChashKeyType keySpec, 575 const CSChashKeyUnion* const keyPtr, 576 const void* const itemPtr, 577 const size_t itemSize 578 ) 579 { 580 int newStat = CSC_OK; 581 CSChashEntryType newEntryPtr = NULL; 582 583 ASSERT_RTN (entryPtrPtr!=NULL, "hashEntryNew: null entryPtrPtr", CSC_BADARG); 584 ASSERT_RTN (keyPtr != NULL, "hashEntryNew: null keyPtr", CSC_BADARG); 585 ASSERT_RTN (itemPtr != NULL, "hashEntryNew: null itemPtr", CSC_BADARG); 586 ASSERT_RTN (itemSize > 0, "hashEntryNew: no itemSize", CSC_BADARG); 587 ASSERT_RTN ( \ 588 keySpec==CSC_HASH_ASCIIZ_KEY || keySpec==CSC_HASH_INT32_KEY,\ 589 "hashEntryNew: invalid keySpec", \ 590 CSC_BADARG \ 591 ); 592 593 newStat = CSCmemAlloc ( 594 memLst, 595 (void**)&newEntryPtr, 596 1, 597 sizeof(S_hashEntryType), 598 0 599 ); 600 601 if (newStat == CSC_OK) 602 { 603 newEntryPtr->pred = NULL; 604 newEntryPtr->succ = NULL; 605 newEntryPtr->size = itemSize; 606#ifdef DEBUG 607 newEntryPtr->sig_lo = HASH_SIG; 608 newEntryPtr->sig_hi = HASH_SIG; 609#endif 610 611 (void)CSCmemDup ( 612 memLst, (void**)&newEntryPtr->data, itemPtr, itemSize, 0 613 ); 614 if (newEntryPtr->data != NULL) 615 { 616 switch (keySpec) 617 { 618 default: 619 (void)CSCmemFree (memLst, (void**)&newEntryPtr->data, 0); 620 (void)CSCmemFree (memLst, (void**)&newEntryPtr, 0); 621 newStat = CSC_BADARG; 622 break; 623 624 case CSC_HASH_ASCIIZ_KEY: 625 (void)CSCmemDup ( 626 memLst, 627 (void**)&newEntryPtr->key.asciiz, 628 keyPtr->asciiz, 629 strlen(keyPtr->asciiz)+1, 630 0 631 ); 632 if (newEntryPtr->key.asciiz == NULL) 633 { 634 (void)CSCmemFree (memLst, (void**)&newEntryPtr->data, 0); 635 (void)CSCmemFree (memLst, (void**)&newEntryPtr, 0); 636 newStat = CSC_NOMEM; 637 } 638 break; 639 640 case CSC_HASH_INT32_KEY: 641 newEntryPtr->key.integer = keyPtr->integer; 642 break; 643 } 644 *entryPtrPtr = newEntryPtr; 645 } 646 else 647 { 648 (void)CSCmemFree (memLst, (void**)&newEntryPtr, 0); 649 newStat = CSC_NOMEM; 650 } 651 } 652 653 return (newStat); 654 } 655 656 657/************************************************************************** 658 * Private Function hashEntryDel 659 **************************************************************************/ 660 661PRIVATE int hashEntryDel ( 662 CSChashEntryType const oldEntry, 663 CSCmemListType const memLst, 664 const CSChashKeyType keySpec 665 ) 666 { 667 int delStat = CSC_OK; 668 669 ASSERT_RTN (oldEntry != NULL, "hashEntryDel: null oldEntry", CSC_BADARG); 670 ASSERT_RTN ( \ 671 oldEntry->sig_lo == HASH_SIG, \ 672 "hashEntryDel: bad signature in oldEntry", \ 673 CSC_CORRUPT \ 674 ); 675 ASSERT_RTN ( \ 676 oldEntry->sig_hi == HASH_SIG, \ 677 "hashEntryDel: bad signature in oldEntry", \ 678 CSC_CORRUPT \ 679 ); 680 ASSERT_RTN ( \ 681 keySpec==CSC_HASH_ASCIIZ_KEY || keySpec==CSC_HASH_INT32_KEY,\ 682 "hashEntryDel: invalid keySpec", \ 683 CSC_BADARG \ 684 ); 685 686 if (oldEntry != NULL) 687 { 688 ASSERT (oldEntry->data != NULL); 689 (void)CSCmemFree (memLst, (void**)&oldEntry->data, 0); 690 if (keySpec == CSC_HASH_ASCIIZ_KEY) 691 { 692 ASSERT (oldEntry->key.asciiz != NULL); 693 (void)CSCmemFree (memLst, (void**)&oldEntry->key.asciiz, 0); 694 } 695 (void)CSCmemFree (memLst, (void**)&oldEntry, 0); 696 } 697 else 698 { 699 delStat = CSC_NOTFOUND; 700 } 701 702 return (delStat); 703 } 704 705 706/************************************************************************** 707 * Private Function hashLinkAdd 708 **************************************************************************/ 709 710PRIVATE int hashLinkAdd ( 711 CSChashEntryType* const hashListPtrPtr, 712 CSChashEntryType const newEntryPtr 713 ) 714 { 715 int addStat = CSC_OK; 716 717 ASSERT_RTN ( \ 718 hashListPtrPtr != NULL, \ 719 "hashLinkAdd: null hashListPtrPtr", \ 720 CSC_BADARG \ 721 ); 722 ASSERT_RTN ( \ 723 newEntryPtr != NULL, \ 724 "hashLinkAdd: null newEntryPtr", \ 725 CSC_BADARG \ 726 ); 727 ASSERT_RTN ( \ 728 newEntryPtr->sig_lo == HASH_SIG, \ 729 "hashLinkAdd: bad signature in newEntryPtr", \ 730 CSC_CORRUPT \ 731 ); 732 ASSERT_RTN ( \ 733 newEntryPtr->sig_hi == HASH_SIG, \ 734 "hashLinkAdd: bad signature in newEntryPtr", \ 735 CSC_CORRUPT \ 736 ); 737 738 if (*hashListPtrPtr != NULL) 739 { 740 ASSERT_RTN ( \ 741 (*hashListPtrPtr)->sig_lo == HASH_SIG, \ 742 "hashLinkAdd: bad signature in hash", \ 743 CSC_CORRUPT \ 744 ); 745 ASSERT_RTN ( \ 746 (*hashListPtrPtr)->sig_hi == HASH_SIG, \ 747 "hashLinkAdd: bad signature in hash", \ 748 CSC_CORRUPT \ 749 ); 750 PRED(*hashListPtrPtr) = newEntryPtr; 751 SUCC(newEntryPtr) = *hashListPtrPtr; 752 } 753 *hashListPtrPtr = newEntryPtr; 754 755 return (addStat); 756 } 757 758 759/************************************************************************** 760 * Private Function hashLinkSub 761 **************************************************************************/ 762 763PRIVATE int hashLinkSub ( 764 CSChashEntryType* const hashListPtrPtr, 765 CSChashEntryType const oldEntryPtr 766 ) 767 { 768 int subStat = CSC_OK; 769 770 ASSERT_RTN ( \ 771 hashListPtrPtr != NULL, \ 772 "hashLinkSub: null hashListPtrPtr", \ 773 CSC_BADARG \ 774 ); 775 ASSERT_RTN ( \ 776 oldEntryPtr != NULL, \ 777 "hashLinkSub: null oldEntryPtr", \ 778 CSC_BADARG \ 779 ); 780 ASSERT_RTN ( \ 781 oldEntryPtr->sig_lo == HASH_SIG, \ 782 "hashLinkSub: bad signature in oldEntryPtr", \ 783 CSC_CORRUPT \ 784 ); 785 ASSERT_RTN ( \ 786 oldEntryPtr->sig_hi == HASH_SIG, \ 787 "hashLinkSub: bad signature in oldEntryPtr", \ 788 CSC_CORRUPT \ 789 ); 790 791 if (oldEntryPtr == *hashListPtrPtr) 792 { 793 /* -- DE-LINK FIRST ENTRY -- */ 794 /* -- DE-LINK SINGLE ENTRY -- */ 795 *hashListPtrPtr = SUCC(oldEntryPtr); 796 if (*hashListPtrPtr != NULL) 797 PRED(*hashListPtrPtr) = NULL; 798 } 799 else 800 { 801 if (SUCC(oldEntryPtr) == NULL) 802 { 803 /* -- DE-LINK LAST ENTRY -- */ 804 ASSERT_RTN ( \ 805 (PRED(oldEntryPtr))->sig_lo == HASH_SIG, \ 806 "hashLinkSub: bad signature in PRED(oldEntryPtr)", \ 807 CSC_CORRUPT \ 808 ); 809 ASSERT_RTN ( \ 810 (PRED(oldEntryPtr))->sig_hi == HASH_SIG, \ 811 "hashLinkSub: bad signature in PRED(oldEntryPtr)", \ 812 CSC_CORRUPT \ 813 ); 814 SUCC(PRED(oldEntryPtr)) = NULL; 815 } 816 else 817 { 818 /* -- DE-LINK INNER ENTRY -- */ 819 ASSERT_RTN ( \ 820 (PRED(oldEntryPtr))->sig_lo == HASH_SIG, \ 821 "hashLinkSub: bad signature in PRED(oldEntryPtr)", \ 822 CSC_CORRUPT \ 823 ); 824 ASSERT_RTN ( \ 825 (PRED(oldEntryPtr))->sig_hi == HASH_SIG, \ 826 "hashLinkSub: bad signature in PRED(oldEntryPtr)", \ 827 CSC_CORRUPT \ 828 ); 829 ASSERT_RTN ( \ 830 (SUCC(oldEntryPtr))->sig_lo == HASH_SIG, \ 831 "hashLinkSub: bad signature in SUCC(oldEntryPtr)", \ 832 CSC_CORRUPT \ 833 ); 834 ASSERT_RTN ( \ 835 (SUCC(oldEntryPtr))->sig_hi == HASH_SIG, \ 836 "hashLinkSub: bad signature in SUCC(oldEntryPtr)", \ 837 CSC_CORRUPT \ 838 ); 839 SUCC(PRED(oldEntryPtr)) = SUCC(oldEntryPtr); 840 PRED(SUCC(oldEntryPtr)) = PRED(oldEntryPtr); 841 } 842 } 843 844 return (subStat); 845 } 846 847 848/************************************************************************** 849 * Private Function hashEntryFind 850 **************************************************************************/ 851 852PRIVATE int hashEntryFind ( 853 const CSChashEntryType hashListPtr, 854 const CSChashKeyUnion* const keyPtr, 855 const CSChashKeyType keySpec, 856 CSChashEntryType* const hashEntryPtrPtr, 857 void** const itemPtrPtr, 858 size_t* const itemSizePtr 859 ) 860 { 861 int findStat = CSC_NOTFOUND; 862 CSChashEntryType entryPtr = NULL; 863 864 entryPtr = (CSChashEntryType)hashListPtr; 865 while ((entryPtr != NULL) && (findStat == CSC_NOTFOUND)) 866 { 867 ASSERT_RTN ( \ 868 entryPtr->sig_lo == HASH_SIG, \ 869 "hashEntryFind: bad signature in entryPtr", \ 870 CSC_CORRUPT \ 871 ); 872 ASSERT_RTN ( \ 873 entryPtr->sig_hi == HASH_SIG, \ 874 "hashEntryFind: bad signature in entryPtr", \ 875 CSC_CORRUPT \ 876 ); 877 findStat = hashMatch (keySpec, &entryPtr->key, keyPtr); 878 if (findStat == CSC_NOTFOUND) entryPtr = SUCC(entryPtr); 879 } 880 881 if (findStat == CSC_OK) 882 { 883 if (hashEntryPtrPtr != NULL) *hashEntryPtrPtr = entryPtr; 884 if (itemPtrPtr != NULL) *itemPtrPtr = entryPtr->data; 885 if (itemSizePtr != NULL) *itemSizePtr = entryPtr->size; 886 } 887 888 return (findStat); 889 } 890 891 892/************************************************************************** 893 * Private Function rebuild 894 **************************************************************************/ 895 896PRIVATE int rebuild ( 897 CSChashTableType const hashTablePtr 898 ) 899 { 900 int rebuildStat = CSC_OK; 901 CSChashEntryType* oldHashPtr = NULL; 902 CSChashEntryType oldHashPtr2 = NULL; 903 CSChashEntryType oldHashPtr3 = NULL; 904 size_t oldNhash = 0; 905 int index = 0; 906 CSChashType hashVal; 907 908 ASSERT_RTN (hashTablePtr != NULL, "rebuild: null hashTablePtr", CSC_BADARG); 909 ASSERT_RTN ( \ 910 hashTablePtr->sig_lo == HASH_SIG, \ 911 "rebuild: bad signature in hashTablePtr", \ 912 CSC_CORRUPT \ 913 ); 914 ASSERT_RTN ( \ 915 hashTablePtr->sig_hi == HASH_SIG, \ 916 "rebuild: bad signature in hashTablePtr", \ 917 CSC_CORRUPT \ 918 ); 919 920 oldHashPtr = hashTablePtr->hash; 921 oldNhash = hashTablePtr->nhash; 922 923 hashTablePtr->hash = NULL; 924 rebuildStat = CSCmemAlloc ( 925 hashTablePtr->memLst, 926 (void**)&hashTablePtr->hash, 927 hashTablePtr->nhash*4, 928 sizeof(S_hashEntryType), 929 0 930 ); 931 932 if (rebuildStat == CSC_OK) 933 { 934 hashTablePtr->nhash *= 4; 935 hashTablePtr->downShift -= 2; 936 hashTablePtr->mask = (hashTablePtr->mask << 2) + 3; 937 hashTablePtr->resizes += 1; 938 939 hashTablePtr->deletions = 0; 940 hashTablePtr->insertions = 0; 941 hashTablePtr->collisions = 0; 942 943 for ( index = 0 ; index < (int)hashTablePtr->nhash ; index++ ) 944 hashTablePtr->hash[index] = NULL; 945 946 for ( index = 0 ; index < (int)oldNhash ; index++ ) 947 { 948 oldHashPtr2 = oldHashPtr[index]; 949 while (oldHashPtr2 != NULL) 950 { 951 oldHashPtr3 = SUCC(oldHashPtr2); 952 (void)CSChash (&(oldHashPtr2->key), hashTablePtr, &hashVal); 953 (void)hashLinkSub (&(oldHashPtr[index]), oldHashPtr2); 954 SUCC(oldHashPtr2) = NULL; 955 PRED(oldHashPtr2) = NULL; 956 (void)hashLinkAdd (&(hashTablePtr->hash[hashVal]), oldHashPtr2); 957 oldHashPtr2 = oldHashPtr3; 958 } 959 } 960 961 (void)CSCmemFree (hashTablePtr->memLst, (void**)&oldHashPtr, 0); 962 } 963 else 964 { 965 hashTablePtr->hash = oldHashPtr; 966 } 967 968 return (rebuildStat); 969 } 970 971 972/* ************************************************************************* */ 973/* */ 974/* E x e c u t a b l e C o d e (External Interface Functions) */ 975/* */ 976/* ************************************************************************* */ 977 978 979/************************************************************************** 980 * Public Function CSChashNew 981 ************************************************************************** 982 983<SUBROUTINE NAME="CSChashNew"> 984 985NAME 986 CSChashNew - create a new libcsc hash table 987 988SYNOPSYS 989 #include "libcsc.h" 990 991 CSChashTableType CSChashNew ( 992 const char* const name, 993 CSChashKeyType keySpec, 994 size_t size, 995 CSCmonFnType monFunc, 996 const void* monData, 997 CSCprofileType profiling 998 ); 999 1000RETURN VALUE 1001 CSChashNew(), if successful, returns an opaque data type representing 1002 a new libcsc hash table, or NULL if otherwise not successful. 1003 1004DESCRIPTION 1005 CSChashNew() creates a new libcsc hash table with several attributes: 1006 name, type of key, and number of hash locations. 1007 1008 `name' points to an arbitrary string that is used as the name of the 1009 new libcsc hash table. 1010 1011 `keySpec' specifies the type of keys used by the new hash table; it is 1012 one of: 1013 1014 CSC_HASH_ASCIIZ_KEY ... hash keys for this table will be ASCII 1015 NULL-terminated (ASCIIZ) strings. 1016 1017 CSC_HASH_INT32_KEY .... hash keys for this table will be 1018 integers of the type int32. 1019 1020 `size' specifies the number of hash locations, or buckets, in the new 1021 libcsc hash table. If size is zero, then the new libcsc hash table 1022 will begin life with four hash locations and will quadruple whenever the 1023 number of hash locations is some mysterious factor of the total number 1024 of hashed items (gets overfull). 1025 1026 `profiling' can be CSC_DO_PROFILING or CSC_NO_PROFILING; it specifies 1027 whether alocate/free, insertion/deletion, etc. statistics should 1028 actually be generated and kept in the hash table. 1029 1030SEE ALSO 1031 CSChashDel(3) 1032 CSChashStat(3) 1033 CSChashEntryPut(3) 1034 CSChashEntryGet(3) 1035 CSChashEntryDel(3) 1036 CSChashEntryNext(3) 1037 CSChashEntryStat(3) 1038 CSChashRead(3) 1039 CSChashWrite(3) 1040 CSChashDump(3) 1041</SUBROUTINE> 1042 1043 **************************************************************************/ 1044 1045PUBLIC CSChashTableType (CSChashNew) ( 1046 const char* const name, 1047 CSChashKeyType keySpec, 1048 size_t size, 1049 CSCmonFnType monFunc, 1050 const void* monData, 1051 CSCprofileType profiling 1052 ) 1053 { 1054 CSChashTableType newHash = NULL; 1055 CSCmemListType memList = NULL; 1056 int hashStat; 1057 1058 ASSERT_RTN (name != NULL, "CSChashNew: no hash name", NULL); 1059 ASSERT_RTN ( \ 1060 keySpec==CSC_HASH_ASCIIZ_KEY || keySpec==CSC_HASH_INT32_KEY,\ 1061 "CSChashNew: invalid keySpec", \ 1062 NULL \ 1063 ); 1064 ASSERT_RTN ( \ 1065 ((profiling==CSC_DO_PROFILING)||(profiling==CSC_NO_PROFILING)),\ 1066 "CSChashNew: illegal profile value", \ 1067 NULL \ 1068 ); 1069 1070 memList = CSCmemInit (name, NULL, monFunc, monData, CSC_NO_PROFILING); 1071 if (memList != NULL) 1072 { 1073 (void)CSCmemAlloc (memList,(void**)&newHash,1,sizeof(S_hashTableType),0); 1074 if (newHash != NULL) 1075 { 1076 newHash->name = name; 1077 newHash->memLst = memList; 1078 newHash->profiling = profiling; 1079 newHash->monFunc = monFunc; 1080 newHash->monData = monData; 1081#ifdef DEBUG 1082 newHash->sig_lo = HASH_SIG; 1083 newHash->sig_hi = HASH_SIG; 1084#endif 1085 hashStat = initHashTab (newHash, keySpec, size); 1086 if (hashStat != CSC_OK) 1087 { 1088 (void)CSCmemFree (memList, (void**)&newHash, 0); 1089 (void)CSCmemDone (memList); 1090 newHash = NULL; 1091 } 1092 } 1093 else 1094 { 1095 (void)CSCmemDone (memList); 1096 } 1097 } 1098 1099 return (newHash); 1100 } 1101 1102 1103/************************************************************************** 1104 * Public Function CSChashDel 1105 ************************************************************************** 1106 1107<SUBROUTINE NAME="CSChashDel"> 1108 1109NAME 1110 CSChashDel - remove a libcsc hash table 1111 1112SYNOPSYS 1113 #include "libcsc.h" 1114 1115 int CSChashDel ( 1116 CSChashTableType const hashTable 1117 ); 1118 1119RETURN VALUE 1120 CSChashDel(), if successful, returns CSC_OK; otherwise, CSC_NOTFOUND, 1121 CSC_BADARG, and CSC_CORRUPT can be returned corresponding to NULL 1122 pointers, bad function arguments, and internal data errors, 1123 respectively. 1124 1125DESCRIPTION 1126 The libcsc hash table represented by the opaque `hashTable' is 1127 completely removed. 1128 1129SEE ALSO 1130 CSChashNew(3) 1131 CSChashStat(3) 1132 CSChashEntryPut(3) 1133 CSChashEntryGet(3) 1134 CSChashEntryDel(3) 1135 CSChashEntryNext(3) 1136 CSChashEntryStat(3) 1137 CSChashRead(3) 1138 CSChashWrite(3) 1139 CSChashDump(3) 1140</SUBROUTINE> 1141 1142 **************************************************************************/ 1143 1144PUBLIC int (CSChashDel) ( 1145 CSChashTableType const hashTable 1146 ) 1147 { 1148 int delStat = CSC_OK; 1149 CSChashEntryType entry = NULL; 1150 CSChashEntryType nextEntry = NULL; 1151 CSChashKeyType keySpec = 0; 1152 size_t* countPtr = NULL; 1153 int nhash; 1154 int index; 1155 1156 ASSERT_RTN (hashTable != NULL, "CSChashDel: null hashTable", CSC_BADARG); 1157 ASSERT_RTN ( \ 1158 hashTable->sig_lo == HASH_SIG, \ 1159 "CSChashDel: bad signature in hashTable", \ 1160 CSC_CORRUPT \ 1161 ); 1162 ASSERT_RTN ( \ 1163 hashTable->sig_hi == HASH_SIG, \ 1164 "CSChashDel: bad signature in hashTable", \ 1165 CSC_CORRUPT \ 1166 ); 1167 1168 MON_ENTER(hashTable); 1169 1170 keySpec = hashTable->keySpec; 1171 countPtr = &hashTable->count; 1172 nhash = (int)hashTable->nhash; 1173 1174 for ( index = 0 ; index < nhash ; ++index ) 1175 { 1176 int tmpStat = CSC_OK; 1177 entry = hashTable->hash[ index ]; 1178 while (entry != NULL) 1179 { 1180 nextEntry = SUCC(entry); 1181 tmpStat = hashEntryDel (entry, hashTable->memLst, keySpec); 1182 if (tmpStat == CSC_OK) 1183 { 1184 --(*countPtr); 1185 } 1186 else 1187 { 1188 delStat = tmpStat; 1189 } 1190 entry = nextEntry; 1191 } 1192 } 1193 ASSERT (hashTable->count == 0); 1194 1195 if (delStat == CSC_OK) 1196 { 1197 CSCmemListType memList = hashTable->memLst; 1198 CSCmonFnType monFunc = hashTable->monFunc; 1199 const void* monData = hashTable->monData; 1200 delStat = clearHashTab (hashTable); 1201 hashTable->name = NULL; 1202 hashTable->memLst = NULL; 1203 hashTable->profiling = -1; 1204 hashTable->monFunc = NULL; 1205 hashTable->monData = NULL; 1206#ifdef DEBUG 1207 hashTable->sig_lo = -1; 1208 hashTable->sig_hi = -1; 1209#endif 1210 (void)CSCmemFree (memList, (void**)&hashTable, 0); 1211 (void)CSCmemDone (memList); 1212 if (monFunc != NULL) (*monFunc) (CSC_OUT, (void*)monData); 1213 } 1214 else 1215 { 1216 MON_EXIT(hashTable); 1217 } 1218 1219 return (delStat); 1220 } 1221 1222 1223/************************************************************************** 1224 * Public Function CSChashStat 1225 ************************************************************************** 1226 1227<SUBROUTINE NAME="CSChashStat"> 1228 1229NAME 1230 CSChashStat - query statistics of a libcsc hash table 1231 1232SYNOPSYS 1233 #include "libcsc.h" 1234 1235 int CSChashStat ( 1236 CSChashTableType const hashTable, 1237 CSChashStatType* const statStruct 1238 ); 1239 1240RETURN VALUE 1241 CSChashStat(), if successful, returns a pointer to a structure of 1242 queried data, or NULL if otherwise not successful. 1243 CSChashStat(), returns CSC_OK, or CSC_BADARG and CSC_CORRUPT can be 1244 returned corresponding to NULL pointers, bad function arguments, and 1245 internal data errors, respectively. 1246 1247DESCRIPTION 1248 CSChashStat() queries the libcsc hash table represented by the opaque 1249 `hashTable' and fills a CSChashStatType structure. The CSChashStatType 1250 structure is 1251 1252 typedef struct CSChashStatType 1253 { 1254 char name[80]; // name of hash table 1255 CSCprofileType profiling; // profiling flag 1256 size_t count; // count of items in table 1257 size_t nhash; // number of hash locations 1258 CSCboolean grows; // CSC_TRUE or CSC_FALSE 1259 size_t resizes; // num of resizes, if table grows 1260 size_t deletions; // num of deletions since resize 1261 size_t insertions; // num of insertions since resize 1262 size_t collisions; // num of collisions since resize 1263 } CSChashStatType; 1264 1265 Only up to seventy nine characters of the table name are retrieved. 1266 1267 If the table size was specified a zero when it was created with 1268 CSChashNew() then the table quadruples its hash locations as it gets 1269 full. In this case the grows flag will be CSC_TRUE, otherwise it will 1270 be CSC_FALSE. 1271 1272 If the table grows, then the deletions, insertions, and collisions 1273 fields of the CSChashStatType structure will represent those 1274 statistics only since the last time the table resized itself i.e., the 1275 deletions, insertions, and collisions are reset to zero when the table 1276 resizes itself. 1277 1278EXAMPLE 1279 CSChashTableType myTable; 1280 CSChashQueryType statStruct; 1281 int stat 1282 1283 . 1284 . 1285 . 1286 stat = CSChashStat (myTable, &statStruct); 1287 . 1288 // do something with the statistics 1289 . 1290 . 1291 . 1292 1293SEE ALSO 1294 CSChashNew(3) 1295 CSChashDel(3) 1296 CSChashEntryPut(3) 1297 CSChashEntryGet(3) 1298 CSChashEntryDel(3) 1299 CSChashEntryNext(3) 1300 CSChashEntryStat(3) 1301 CSChashRead(3) 1302 CSChashWrite(3) 1303 CSChashDump(3) 1304</SUBROUTINE> 1305 1306 **************************************************************************/ 1307 1308PUBLIC int (CSChashStat) ( 1309 CSChashTableType const hashTable, 1310 CSChashStatType* const statStruct 1311 ) 1312 { 1313 ASSERT_RTN (hashTable != NULL, "CSChashStat: null hashTable", CSC_BADARG); 1314 ASSERT_RTN ( \ 1315 hashTable->sig_lo == HASH_SIG, \ 1316 "CSChashStat: bad signature in hashTable", \ 1317 CSC_CORRUPT \ 1318 ); 1319 ASSERT_RTN ( \ 1320 hashTable->sig_hi == HASH_SIG, \ 1321 "CSChashStat: bad signature in hashTable", \ 1322 CSC_CORRUPT \ 1323 ); 1324 1325 MON_ENTER(hashTable); 1326 1327 (void)memset (statStruct->name, '\0', 80); 1328 (void)strncpy (statStruct->name, hashTable->name, 79); 1329 statStruct->profiling = hashTable->profiling; 1330 statStruct->count = hashTable->count; 1331 statStruct->nhash = hashTable->nhash; 1332 statStruct->grows = hashTable->grows; 1333 statStruct->resizes = hashTable->resizes; 1334 statStruct->deletions = hashTable->deletions; 1335 statStruct->insertions = hashTable->insertions; 1336 statStruct->collisions = hashTable->collisions; 1337 1338 MON_EXIT(hashTable); 1339 1340 return (CSC_OK); 1341 } 1342 1343 1344/************************************************************************** 1345 * Public Function CSChashEntryPut 1346 ************************************************************************** 1347 1348<SUBROUTINE NAME="CSChashEntryPut"> 1349 1350NAME 1351 CSChashEntryPut - put an entry into a libcsc hash table 1352 1353SYNOPSYS 1354 #include "libcsc.h" 1355 1356 int CSChashEntryPut ( 1357 CSChashTableType const hashTable, 1358 CSChashKeyUnion* const keyPtr, 1359 void* const itemPtr, 1360 size_t itemSize 1361 ); 1362 1363RETURN VALUE 1364 CSChashEntryPut(), if successful, returns CSC_OK. If the key is 1365 already in use in the table, then CSChashEntryPut() will return 1366 CSC_DUPKEY. Other values, CSC_NOTFOUND, CSC_BADARG, and CSC_CORRUPT can 1367 be returned corresponding to NULL pointers, bad function arguments, and 1368 internal data errors, respectively. 1369 1370DESCRIPTION 1371 CSChashEntryPut() puts the data pointed to by `itemPtr', whose key is 1372 pointed to by `keyPtr' and size in bytes is `itemSize', into the libcsc 1373 hash table represented by the opaque `hashTable'. 1374 1375 The data that goes into the table is a duplicate of `itemSize' bytes 1376 from the address `itemPtr'. To avoid duplicating static data, put a 1377 pointer of the client data into the table. If the item being put into 1378 the table contains a pointer, beware of aliasing errors if the pointer 1379 is to allocated memory that becomes deallocated while the item is in the 1380 table. 1381 1382 Of course, the type of the key pointed to by `keyPtr' must match the 1383 type of keys (CSC_HASH_INT32_KEY or CSC_HASH_ASCIIZ_KEY) used by 1384 `hashTable'. 1385 1386SEE ALSO 1387 CSChashNew(3) 1388 CSChashDel(3) 1389 CSChashStat(3) 1390 CSChashEntryGet(3) 1391 CSChashEntryDel(3) 1392 CSChashEntryNext(3) 1393 CSChashEntryStat(3) 1394 CSChashRead(3) 1395 CSChashWrite(3) 1396 CSChashDump(3) 1397</SUBROUTINE> 1398 1399 **************************************************************************/ 1400 1401PUBLIC int (CSChashEntryPut) ( 1402 CSChashTableType const hashTable, 1403 CSChashKeyUnion* const keyPtr, 1404 void* const itemPtr, 1405 size_t itemSize 1406 ) 1407 { 1408 int putStat = CSC_OK; 1409 CSChashEntryType* newListPtr = NULL; 1410 CSChashEntryType newHEntry = NULL; 1411 CSChashType hashVal; 1412 1413 ASSERT_RTN (hashTable != NULL, "CSChashEntryPut: no hashTable", CSC_BADARG); 1414 ASSERT_RTN (keyPtr != NULL, "CSChashEntryPut: no keyPtr", CSC_BADARG); 1415 ASSERT_RTN (itemPtr != NULL, "CSChashEntryPut: no itemPtr", CSC_BADARG); 1416 ASSERT_RTN (itemSize > 0, "CSChashEntryPut: no itemSize", CSC_BADARG); 1417 ASSERT_RTN ( \ 1418 hashTable->sig_lo == HASH_SIG, \ 1419 "CSChashEntryPut: bad signature in hashTable", \ 1420 CSC_CORRUPT \ 1421 ); 1422 ASSERT_RTN ( \ 1423 hashTable->sig_hi == HASH_SIG, \ 1424 "CSChashEntryPut: bad signature in hashTable", \ 1425 CSC_CORRUPT \ 1426 ); 1427 1428 MON_ENTER(hashTable); 1429 1430 (void)CSChash (keyPtr, hashTable, &hashVal); 1431 ASSERT (hashVal < hashTable->nhash); 1432 1433 newListPtr = &(hashTable->hash[hashVal]); 1434 1435 putStat = hashEntryFind ( 1436 *newListPtr, 1437 keyPtr, 1438 hashTable->keySpec, 1439 NULL, 1440 NULL, 1441 NULL 1442 ); 1443 1444 if (putStat == CSC_OK) 1445 { 1446 putStat = CSC_DUPKEY; 1447 } 1448 else 1449 { 1450 if (putStat == CSC_NOTFOUND) 1451 { 1452 putStat = hashEntryNew ( 1453 &newHEntry, 1454 hashTable->memLst, 1455 hashTable->keySpec, 1456 keyPtr, 1457 itemPtr, 1458 itemSize 1459 ); 1460 if (putStat == CSC_OK) 1461 { 1462 if (*newListPtr != NULL) ++(hashTable->collisions); 1463 (void)hashLinkAdd (newListPtr, newHEntry); 1464 ++(hashTable->count); 1465 ++(hashTable->insertions); 1466 } 1467 1468 if (hashTable->grows == CSC_TRUE) 1469 if (hashTable->count > COSMOLOGICAL_CONSTANT * hashTable->nhash) 1470 rebuild (hashTable); 1471 } 1472 } 1473 1474 MON_EXIT(hashTable); 1475 1476 return (putStat); 1477 } 1478 1479 1480/************************************************************************** 1481 * Public Function CSChashEntryGet 1482 ************************************************************************** 1483 1484<SUBROUTINE NAME="CSChashEntryGet"> 1485 1486NAME 1487 CSChashEntryGet - get an item from a libcsc hash table 1488 1489SYNOPSYS 1490 #include "libcsc.h" 1491 1492 int CSChashEntryGet ( 1493 CSChashTableType const hashTable, 1494 CSChashKeyUnion* const keyPtr, 1495 void** const itemPtrPtr, 1496 size_t* const itemSizePtr, 1497 CSCmemListType const memLst 1498 ); 1499 1500RETURN VALUE 1501 CSChashEntryGet(), if successful, returns CSC_OK; otherwise, 1502 CSC_NOTFOUND, CSC_BADARG, and CSC_CORRUPT can be returned corresponding 1503 to NULL pointers, bad function arguments, and internal data errors, 1504 respectively. 1505 1506DESCRIPTION 1507 CSChashEntryGet() looks up the key pointed to by `keyPtr' in the libcsc 1508 hash table represented by the opaque `hashTable'. 1509 1510 If the item corresponding to the key is found in the table, then a copy 1511 of the the data is allocated with CSCmemDup(), or malloc() if `memLst' 1512 is NULL, and the pointer of the newly allocated data it is written to 1513 the void pointer that is pointed to by `itemPtrPtr', and its size in 1514 bytes is written to the size_t pointed to by `itemSizePtr'. 1515 1516 Since CSChashEntryGet(), if successful, allocates storage for the 1517 retrieved item. If `memLst' is not null then CSCmemDup() is used with 1518 the value of `memLst'; the data should be removed with CSCmemFree(), 1519 using "tagData" value of zero, to avoid leaking this memory. If `memLst' 1520 is NULL, then malloc() is use to allocate storage, and free() should be 1521 used to remove the data to avoid leaking this memory. 1522 1523SEE ALSO 1524 CSChashNew(3) 1525 CSChashDel(3) 1526 CSChashStat(3) 1527 CSChashEntryPut(3) 1528 CSChashEntryDel(3) 1529 CSChashEntryNext(3) 1530 CSChashEntryStat(3) 1531 CSChashRead(3) 1532 CSChashWrite(3) 1533 CSChashDump(3) 1534</SUBROUTINE> 1535 1536 **************************************************************************/ 1537 1538PUBLIC int (CSChashEntryGet) ( 1539 CSChashTableType const hashTable, 1540 CSChashKeyUnion* const keyPtr, 1541 void** const itemPtrPtr, 1542 size_t* const itemSizePtr, 1543 CSCmemListType const memLst 1544 ) 1545 { 1546 int hashTabGetStat = CSC_OK; 1547 CSChashType hashVal = 0; 1548 CSChashEntryType hashList = NULL; 1549 void* localItemPtr = NULL; 1550 size_t localSize; 1551 1552 ASSERT_RTN (hashTable!=NULL, "CSChashEntryGet: null hashTable", CSC_BADARG); 1553 ASSERT_RTN (keyPtr!=NULL, "CSChashEntryGet: null keyPtr", CSC_BADARG); 1554 ASSERT_RTN ( \ 1555 hashTable->sig_lo == HASH_SIG, \ 1556 "CSChashEntryGet: bad signature in hashTable", \ 1557 CSC_CORRUPT \ 1558 ); 1559 ASSERT_RTN ( \ 1560 hashTable->sig_hi == HASH_SIG, \ 1561 "CSChashEntryGet: bad signature in hashTable", \ 1562 CSC_CORRUPT \ 1563 ); 1564 1565 MON_ENTER(hashTable); 1566 1567 (void)CSChash (keyPtr, hashTable, &hashVal); 1568 ASSERT (hashVal < hashTable->nhash); 1569 1570 hashList = hashTable->hash[hashVal]; 1571 hashTabGetStat = hashEntryFind ( 1572 hashList, 1573 keyPtr, 1574 hashTable->keySpec, 1575 NULL, 1576 &localItemPtr, 1577 &localSize 1578 ); 1579 1580 if (hashTabGetStat == CSC_OK) 1581 { 1582 if (memLst != NULL) 1583 { 1584 hashTabGetStat = CSCmemDup ( 1585 memLst, 1586 itemPtrPtr, 1587 localItemPtr, 1588 localSize, 1589 0 1590 ); 1591 *itemSizePtr = localSize; 1592 } 1593 else 1594 { 1595 *itemPtrPtr = calloc (localSize, sizeof(char)); 1596 if (*itemPtrPtr != NULL) 1597 { 1598 hashTabGetStat = CSC_OK; 1599 (void)memcpy (*itemPtrPtr, localItemPtr, localSize); 1600 *itemSizePtr = localSize; 1601 } 1602 else 1603 { 1604 hashTabGetStat = CSC_NOMEM; 1605 *itemSizePtr = 0; 1606 } 1607 } 1608 if (hashTabGetStat != CSC_OK) 1609 { 1610 *itemPtrPtr = NULL; 1611 *itemSizePtr = 0; 1612 } 1613 } 1614 1615 MON_EXIT(hashTable); 1616 1617 return (hashTabGetStat); 1618 } 1619 1620 1621/************************************************************************** 1622 * Public Function CSChashEntryDel 1623 ************************************************************************** 1624 1625<SUBROUTINE NAME="CSChashEntryDel"> 1626 1627NAME 1628 CSChashEntryDel - remove an entry from a libcsc hash table 1629 1630SYNOPSYS 1631 #include "lib.h" 1632 1633 int CSChashEntryDel ( 1634 CSChashTableType const hashTable, 1635 CSChashKeyUnion* const keyPtr 1636 ); 1637 1638RETURN VALUE 1639 CSChashEntryDel(), if successful, returns CSC_OK; otherwise, 1640 CSC_NOTFOUND, CSC_BADARG, and CSC_CORRUPT can be returned corresponding 1641 to NULL pointers, bad function arguments, and internal data errors, 1642 respectively. 1643 1644DESCRIPTION 1645 The hash table entry with the key value that is pointed to by `keyPtr' 1646 is removed from the hash table represented by the opaque `hashTable'. 1647 1648 Of course, the type of the key pointed to by `keyPtr' must match the 1649 type of keys (CSC_HASH_INT32_KEY or CSC_HASH_ASCIIZ_KEY) used by 1650 `hashTable'. 1651 1652SEE ALSO 1653 CSChashNew(3) 1654 CSChashDel(3) 1655 CSChashStat(3) 1656 CSChashEntryPut(3) 1657 CSChashEntryGet(3) 1658 CSChashEntryNext(3) 1659 CSChashEntryStat(3) 1660 CSChashRead(3) 1661 CSChashWrite(3) 1662 CSChashDump(3) 1663</SUBROUTINE> 1664 1665 **************************************************************************/ 1666 1667PUBLIC int (CSChashEntryDel) ( 1668 CSChashTableType const hashTable, 1669 CSChashKeyUnion* const keyPtr 1670 ) 1671 { 1672 int delStat = CSC_OK; 1673 CSChashType hashVal = 0; 1674 CSChashEntryType* oldListPtr = NULL; 1675 CSChashEntryType oldEntry = NULL; 1676 1677 ASSERT_RTN (hashTable!=NULL, "CSChashEntryDel: null hashTable", CSC_BADARG); 1678 ASSERT_RTN (keyPtr!=NULL, "CSChashEntryDel: null keyPtr", CSC_BADARG); 1679 ASSERT_RTN ( \ 1680 hashTable->sig_lo == HASH_SIG, \ 1681 "CSChashEntryDel: bad signature in hashTable", \ 1682 CSC_CORRUPT \ 1683 ); 1684 ASSERT_RTN ( \ 1685 hashTable->sig_hi == HASH_SIG, \ 1686 "CSChashEntryDel: bad signature in hashTable", \ 1687 CSC_CORRUPT \ 1688 ); 1689 1690 MON_ENTER(hashTable); 1691 1692 (void)CSChash (keyPtr, hashTable, &hashVal); 1693 ASSERT (hashVal < hashTable->nhash); 1694 1695 oldListPtr = &(hashTable->hash[hashVal]); 1696 1697 delStat = hashEntryFind ( 1698 *oldListPtr, 1699 keyPtr, 1700 hashTable->keySpec, 1701 &oldEntry, 1702 NULL, 1703 NULL 1704 ); 1705 if (delStat == CSC_OK) 1706 { 1707 delStat = hashLinkSub (oldListPtr, oldEntry); 1708 if (delStat == CSC_OK) 1709 { 1710 delStat = hashEntryDel ( 1711 oldEntry, hashTable->memLst, hashTable->keySpec 1712 ); 1713 ASSERT (hashTable->count >= 1); 1714 --(hashTable->count); 1715 ++(hashTable->deletions); 1716 } 1717 } 1718 1719 MON_EXIT(hashTable); 1720 1721 return (delStat); 1722 } 1723 1724 1725/************************************************************************** 1726 * Public Function CSChashEntryNext 1727 ************************************************************************** 1728 1729<SUBROUTINE NAME="CSChashEntryNext"> 1730 1731NAME 1732 CSChashEntryNext - find next entry in a libcsc hash table 1733 1734SYNOPSYS 1735 #include "libcsc.h" 1736 1737 CSChashEntryType CSChashEntryNext ( 1738 CSChashTableType const hashTable, 1739 CSChashEntryType const entry 1740 ); 1741 1742RETURN VALUE 1743 CSChashEntryNext(), if successful, returns an opaque libcsc hash table 1744 entry. If not successful, CSChashEntryNext() returns NULL. 1745 1746DESCRIPTION 1747 CSChashEntryNext() uses the libcsc hash table referred to by the opaque 1748 `hashTable' and returns the next consecutive entry following the entry 1749 indicated by the opaque `entry'. This next consecutive entry is the 1750 entry physically following `entry', its key may hash to the save value 1751 as `entry''s key, or it may be some larger hash value. 1752 1753 If `entry' is NULL, then the first item in the table is returned. 1754 1755 If `hashTable' is a table with no entries, or there are no more entries 1756 following entry, then NULL is returned. 1757 1758BUGS 1759 This function provides one of the few ways to get direct access to a 1760 libcsc hash table's internal data. Avoid using this function. 1761 1762SEE ALSO 1763 CSChashNew(3) 1764 CSChashDel(3) 1765 CSChashStat(3) 1766 CSChashEntryPut(3) 1767 CSChashEntryGet(3) 1768 CSChashEntryDel(3) 1769 CSChashEntryStat(3) 1770 CSChashRead(3) 1771 CSChashWrite(3) 1772 CSChashDump(3) 1773</SUBROUTINE> 1774 1775 **************************************************************************/ 1776 1777PUBLIC CSChashEntryType (CSChashEntryNext) ( 1778 CSChashTableType const hashTable, 1779 CSChashEntryType const entry 1780 ) 1781 { 1782 int nextStat = CSC_OK; 1783 CSChashEntryType nextEntry = NULL; 1784 CSChashType hashVal = 0; 1785 1786 ASSERT_RTN (hashTable != NULL, "CSChashEntryNext: null hashTable", NULL); 1787 ASSERT_RTN ( \ 1788 hashTable->sig_lo == HASH_SIG, \ 1789 "CSChashEntryNext: bad signature in hashTable", \ 1790 NULL \ 1791 ); 1792 ASSERT_RTN ( \ 1793 hashTable->sig_hi == HASH_SIG, \ 1794 "CSChashEntryNext: bad signature in hashTable", \ 1795 NULL \ 1796 ); 1797 1798 MON_ENTER(hashTable); 1799 1800 if (entry != NULL) 1801 { 1802 ASSERT_RTN ( \ 1803 entry->sig_lo == HASH_SIG, \ 1804 "CSChashEntryNext: bad signature in entry", \ 1805 NULL \ 1806 ); 1807 ASSERT_RTN ( \ 1808 entry->sig_hi == HASH_SIG, \ 1809 "CSChashEntryNext: bad signature in entry", \ 1810 NULL \ 1811 ); 1812 if (SUCC(entry) != NULL) 1813 nextEntry = SUCC(entry); 1814 else 1815 { 1816 nextStat = CSChash (&entry->key, hashTable, &hashVal); 1817 hashVal += 1; 1818 } 1819 } 1820 1821 while ((nextEntry == NULL) && (hashVal < hashTable->nhash)) 1822 nextEntry = hashTable->hash[hashVal++]; 1823 1824 MON_EXIT(hashTable); 1825 1826 return (nextEntry); 1827 } 1828 1829 1830/************************************************************************** 1831 * Public Function CSChashEntryStat 1832 ************************************************************************** 1833 1834<SUBROUTINE NAME="CSChashEntryStat"> 1835 1836NAME 1837 CSChashEntryStat - query the fields of a libcsc hash table entry 1838 1839SYNOPSYS 1840 #include "libcsc.h" 1841 1842 int CSChashEntryStat ( 1843 CSChashEntryType const entry, 1844 CSChashKeyUnion** const keyPtrPtr, 1845 void** const itemPtrPtr, 1846 size_t* const itemSizePtr 1847 ); 1848 1849RETURN VALUE 1850 If successful, CSChashEntryStat() returns CSC_OK. If entry is NULL, 1851 then CSC_BADARG is returned. If libcsc was compiled with the DEBUG 1852 macro and the libcsc hash entry at entry is munged up, then CSC_CORRUPT 1853 is returned. 1854 1855DESCRIPTION 1856 CSChashEntryStat() queries the libcsc hash table entry represented by 1857 the opaque `entry'. 1858 1859 If `keyPtrPtr' is not NULL, then the a pointer to `entry''s key is 1860 written to the CSChashKeyUnion pointer that is pointed to by 1861 `keyPtrPtr'. 1862 1863 If `itemPtrPtr' is not NULL, then `entry''s item pointer is written to 1864 the void pointer that is pointed to by `itemPtrPtr'. 1865 1866 If `itemSizePtr' is not NULL, then the size, in bytes, of `entry''s 1867 item is written to the size_t pointed to by `itemSizePtr'. 1868 1869BUGS 1870 This function provides one of the few ways to get direct access to a 1871 libcsc hash table's internal data. Avoid using this function. 1872 1873SEE ALSO 1874 CSChashNew(3) 1875 CSChashDel(3) 1876 CSChashStat(3) 1877 CSChashEntryPut(3) 1878 CSChashEntryGet(3) 1879 CSChashEntryDel(3) 1880 CSChashEntryNext(3) 1881 CSChashRead(3) 1882 CSChashWrite(3) 1883 CSChashDump(3) 1884</SUBROUTINE> 1885 1886 **************************************************************************/ 1887 1888PUBLIC int (CSChashEntryStat) ( 1889 CSChashEntryType const entry, 1890 CSChashKeyUnion** const keyPtrPtr, 1891 void** const itemPtrPtr, 1892 size_t* const itemSizePtr 1893 ) 1894 { 1895 int queryStat = CSC_OK; 1896 1897 ASSERT_RTN (entry != NULL, "CSChashEntryStat: null entry", CSC_BADARG); 1898 ASSERT_RTN ( \ 1899 entry->sig_lo == HASH_SIG, \ 1900 "CSChashEntryStat: bad signature in entry", \ 1901 CSC_CORRUPT \ 1902 ); 1903 ASSERT_RTN ( \ 1904 entry->sig_hi == HASH_SIG, \ 1905 "CSChashEntryStat: bad signature in entry", \ 1906 CSC_CORRUPT \ 1907 ); 1908 1909 if (entry != NULL) 1910 { 1911 if (keyPtrPtr != NULL) *keyPtrPtr = (CSChashKeyUnion*)&entry->key; 1912 if (itemPtrPtr != NULL) *itemPtrPtr = entry->data; 1913 if (itemSizePtr != NULL) *itemSizePtr = entry->size; 1914 } 1915 else 1916 queryStat = CSC_BADARG; 1917 1918 return (queryStat); 1919 } 1920 1921 1922/************************************************************************** 1923 * Public Function CSChashRead 1924 ************************************************************************** 1925 1926<SUBROUTINE NAME="CSChashRead"> 1927 1928NAME 1929 CSChashRead - read an ASCII format libcsc hash table 1930 1931SYNOPSYS 1932 #include "libcsc.h" 1933 1934 int CSChashRead ( 1935 int fd, 1936 CSChashTableType* const hashTablePtr, 1937 CSCmonFnType monFunc, 1938 const void* monData, 1939 CSCprofileType profiling 1940 ); 1941 1942RETURN VALUE 1943 CSChashRead() always returns CSC_OK. Lame. 1944 1945DESCRIPTION 1946 CSChashRead() reads from `fd' a libcsc hash table in ASCII format that 1947 was written with CSChashWrite(). 1948 1949 `hashTablePtr' should point to a CSChashTableType that is set to NULL; a 1950 new libcsc hash table will be created. 1951 1952BUGS 1953 There is no error checking in this function. 1954 1955SEE ALSO 1956 CSChashNew(3) 1957 CSChashDel(3) 1958 CSChashStat(3) 1959 CSChashEntryPut(3) 1960 CSChashEntryGet(3) 1961 CSChashEntryDel(3) 1962 CSChashEntryNext(3) 1963 CSChashEntryStat(3) 1964 CSChashWrite(3) 1965 CSChashDump(3) 1966</SUBROUTINE> 1967 1968 **************************************************************************/ 1969 1970PUBLIC int (CSChashRead) ( 1971 int fd, 1972 CSChashTableType* const hashTablePtr, 1973 CSCmonFnType monFunc, 1974 const void* monData, 1975 CSCprofileType profiling 1976 ) 1977 { 1978 int readStat = CSC_OK; 1979 CSCmemListType memList = NULL; 1980 char* objectName = NULL; 1981 char* tableName = NULL; 1982 char* keySpecStr = NULL; 1983 char* tableSize = NULL; 1984 char* tableCount = NULL; 1985 int index = 0; 1986 CSChashKeyType keySpec = 0; 1987 size_t nhash = 0; 1988 int count = 0; 1989 void* bufPtr = NULL; 1990 size_t bufSize = 0; 1991 char* keyValPtr = NULL; 1992 CSChashKeyUnion key; 1993 1994 memList = CSCmemInit ("TEMP", NULL, NULL, NULL, CSC_NO_PROFILING); 1995 if (memList == NULL) return (CSC_NOMEM); 1996 1997 (void)CSCioReadLine (fd, &objectName, memList, 0); 1998 (void)CSCioReadLine (fd, &tableName, memList, 0); 1999 (void)CSCioReadLine (fd, &keySpecStr, memList, 0); 2000 (void)CSCioReadLine (fd, &tableSize, memList, 0); 2001 (void)CSCioReadLine (fd, &tableCount, memList, 0); 2002 2003 keySpec = (CSChashKeyType)atoi(keySpecStr); 2004 nhash = (size_t)atoi(tableSize); 2005 count = (size_t)atoi(tableCount); 2006 2007 *hashTablePtr = CSChashNew ( 2008 tableName, 2009 keySpec, 2010 nhash, 2011 monFunc, 2012 monData, 2013 profiling 2014 ); 2015 for ( index = 0 ; index < count ; index++) 2016 { 2017 (void)CSCioReadLine (fd, &keyValPtr, memList, 0); 2018 switch (keySpec) 2019 { 2020 default: break; 2021 case CSC_HASH_ASCIIZ_KEY: (void)CSCmemDup ( 2022 (*hashTablePtr)->memLst, 2023 (void**)&key.asciiz, 2024 keyValPtr, 2025 strlen(keyValPtr)+1, 2026 0 2027 ); 2028 break; 2029 case CSC_HASH_INT32_KEY: key.integer = atoi(keyValPtr); break; 2030 } 2031 (void)CSCioBufRead (fd, &bufPtr, &bufSize, memList, 0); 2032 (void)CSChashEntryPut (*hashTablePtr, &key, bufPtr, bufSize); 2033 if (keySpec == CSC_HASH_ASCIIZ_KEY) 2034 { 2035 (void)CSCmemFree ((*hashTablePtr)->memLst, (void**)&key.asciiz, 0); 2036 } 2037 (void)CSCmemFree (memList, (void**)&keyValPtr, 0); 2038 (void)CSCmemFree (memList, (void**)&bufPtr, 0); 2039 } 2040 2041 (void)CSCmemFree (memList, (void**)&objectName, 0); 2042 (void)CSCmemFree (memList, (void**)&tableName, 0); 2043 (void)CSCmemFree (memList, (void**)&keySpecStr, 0); 2044 (void)CSCmemFree (memList, (void**)&tableSize, 0); 2045 (void)CSCmemFree (memList, (void**)&tableCount, 0); 2046 2047 (void)CSCmemDone (memList); 2048 2049 return (readStat); 2050 } 2051 2052 2053/************************************************************************** 2054 * Public Function CSChashWrite 2055 ************************************************************************** 2056 2057<SUBROUTINE NAME="CSChashWrite"> 2058 2059NAME 2060 CSChashWrite - write a libcsc hash table in an ASCII format 2061 2062SYNOPSYS 2063 #include "libcsc.h" 2064 2065 int CSChashWrite ( 2066 int fd, 2067 CSChashTableType const hashTable 2068 ); 2069 2070RETURN VALUE 2071 CSChashWrite() always returns CSC_OK. Lame. 2072 2073DESCRIPTION 2074 CSChashWrite() writes to `fd' the libcsc hash table represented by the 2075 opaque `hashTable' in an ASCII format. Small, simple tables will be 2076 human-readable by patient humans, but CSChashRead() will be happy to 2077 read it and create another duplicate libcsc hash table. In this way, 2078 libcsc hash tables can be transported between processes, in space or 2079 time. 2080 2081 Caution: client pointers stored in the table will be severe aliasing 2082 bugs when they are read by a different process. 2083 2084BUGS 2085 There is no error checking in this function. 2086 2087SEE ALSO 2088 CSChashNew(3) 2089 CSChashDel(3) 2090 CSChashStat(3) 2091 CSChashEntryPut(3) 2092 CSChashEntryGet(3) 2093 CSChashEntryDel(3) 2094 CSChashEntryNext(3) 2095 CSChashEntryStat(3) 2096 CSChashRead(3) 2097 CSChashDump(3) 2098</SUBROUTINE> 2099 2100 **************************************************************************/ 2101 2102PUBLIC int (CSChashWrite) ( 2103 int fd, 2104 CSChashTableType const hashTable 2105 ) 2106 { 2107 int writeStat = CSC_OK; 2108 CSChashEntryType entry = NULL; 2109 char ioLine[ 80 ]; 2110 CSChashKeyType keySpec; 2111 2112 MON_ENTER(hashTable); 2113 2114 (void)write (fd, "HASH TABLE => ", 14); 2115 (void)write (fd, hashTable->name, strlen(hashTable->name)); 2116 (void)write (fd, "\n", 1); 2117 2118 switch ((int)hashTable->keySpec) 2119 { 2120 default: 2121 (void)write (fd, "unknown key type => ", 20); 2122 break; 2123 2124 case CSC_HASH_ASCIIZ_KEY: 2125 (void)write (fd, "key type: CSC_HASH_ASCIIZ_KEY => ", 34); 2126 break; 2127 2128 case CSC_HASH_INT32_KEY: 2129 (void)write (fd, "key type: CSC_HASH_INT32_KEY => ", 34); 2130 break; 2131 } 2132 (void)sprintf (ioLine, "%d\n", (int)hashTable->keySpec); 2133 (void)write (fd, ioLine, strlen(ioLine)); 2134 2135 (void)write (fd, "nhash => ", 9); 2136 (void)sprintf (ioLine, "%d\n", (int)hashTable->nhash); 2137 (void)write (fd, ioLine, strlen(ioLine)); 2138 2139 (void)write (fd, "count => ", 9); 2140 (void)sprintf (ioLine, "%d\n", (int)hashTable->count); 2141 (void)write (fd, ioLine, strlen(ioLine)); 2142 2143 keySpec = hashTable->keySpec; 2144 while ((entry=CSChashEntryNext(hashTable,entry)) != NULL) 2145 { 2146 (void)write (fd, "--\n", 3); 2147 switch (keySpec) 2148 { 2149 default: 2150 break; 2151 2152 case CSC_HASH_ASCIIZ_KEY: 2153 (void)write (fd, entry->key.asciiz, strlen(entry->key.asciiz)); 2154 (void)write (fd, "\n", 1); 2155 break; 2156 2157 case CSC_HASH_INT32_KEY: 2158 (void)sprintf (ioLine, "%d\n", (int)entry->key.integer); 2159 (void)write (fd, ioLine, strlen(ioLine)); 2160 break; 2161 } 2162 CSCioBufWrite (fd, entry->data, entry->size); 2163 } 2164 2165 MON_EXIT(hashTable); 2166 2167 return (writeStat); 2168 } 2169 2170 2171/************************************************************************** 2172 * Public Function CSChashDump 2173 ************************************************************************** 2174 2175<SUBROUTINE NAME="CSChashDump"> 2176 2177NAME 2178 CSChashDump - write a formatted dump of a libcsc hash table 2179 2180SYNOPSYS 2181 #include "libcsc.h" 2182 2183 int CSChashDump ( 2184 int fd, 2185 CSChashTableType const hashTable 2186 ); 2187 2188RETURN VALUE 2189 CSChashDump() always returns CSC_OK. Lame. 2190 2191DESCRIPTION 2192 CSChashDump() writes to `fd' a formatted dump of the entire hash table 2193 represented by the opaque `hashTable'. 2194 2195 This formatted dump of the hash table is for visual inspection of the 2196 hash table. After a short header, each item's hash value, key, data 2197 size, and data dump is written. 2198 2199 Don't do this with large hash tables, even if they are sparsely 2200 populated; nobody would read it. 2201 2202SEE ALSO 2203 CSChashNew(3) 2204 CSChashDel(3) 2205 CSChashStat(3) 2206 CSChashEntryPut(3) 2207 CSChashEntryGet(3) 2208 CSChashEntryDel(3) 2209 CSChashEntryNext(3) 2210 CSChashEntryStat(3) 2211 CSChashRead(3) 2212 CSChashWrite(3) 2213</SUBROUTINE> 2214 2215 **************************************************************************/ 2216 2217PUBLIC int (CSChashDump) ( 2218 int fd, 2219 CSChashTableType const hashTable 2220 ) 2221 { 2222 int dumpStat = CSC_OK; 2223 CSCmemListType memList = NULL; 2224 int index = 0; 2225 char* msgBufPtr = NULL; 2226 CSChashEntryType entry = NULL; 2227 CSChashKeyType keySpec; 2228 2229 memList = CSCmemInit ("TEMP", NULL, NULL, NULL, CSC_NO_PROFILING); 2230 if (memList == NULL) return (CSC_NOMEM); 2231 2232 MON_ENTER(hashTable); 2233 2234#define SIGNON "\nRTHASHSYS-I-DUMP, hash table dump follows.\n\n" 2235 (void)write (fd, SIGNON, strlen(SIGNON)); 2236#undef SIGNON 2237 2238#define FMT_STR "Hash table `%s' has %d hash positions and %d items.\n" 2239#define FMT_SZ (strlen(FMT_STR)+strlen(hashTable->name)+20+1) 2240 2241 (void)CSCmemAlloc (memList, (void**)&msgBufPtr, 1, FMT_SZ, 0); 2242 (void)sprintf ( 2243 msgBufPtr, 2244 FMT_STR, 2245 hashTable->name, 2246 hashTable->nhash, 2247 hashTable->count 2248 ); 2249 (void)write (fd, msgBufPtr, strlen(msgBufPtr)); 2250 (void)CSCmemFree (memList, (void**)&msgBufPtr, 0); 2251#undef FMT_STR 2252#undef FMT_SZ 2253 2254#define MSG_STR "hash\t\tkey\tsize\n----\t\t---\t----\n\n" 2255 (void)write (fd, MSG_STR, strlen(MSG_STR)); 2256#undef MSG_STR 2257 2258 keySpec = hashTable->keySpec; 2259 for ( index = 0 ; index < (int)hashTable->nhash ; ++index ) 2260 { 2261 entry = hashTable->hash[index]; 2262#define FMT_STR "%05d" 2263#define FMT_SZ (strlen(FMT_STR)+20+1) 2264 (void)CSCmemAlloc (memList, (void**)&msgBufPtr, 1, FMT_SZ, 0); 2265 (void)sprintf (msgBufPtr, FMT_STR, index); 2266 (void)write (fd, msgBufPtr, strlen(msgBufPtr)); 2267 (void)CSCmemFree (memList, (void**)&msgBufPtr, 0); 2268#undef FMT_STR 2269#undef FMT_SZ 2270 if (entry != NULL) 2271 { 2272 while (entry != NULL) 2273 { 2274 2275#define FMT_STR_A "\t\t%s\t%ld (%08lX hex)\n" 2276#define FMT_STR_I "\t\t%ld\t%ld (%08lX hex)\n" 2277 2278 switch (keySpec) 2279 { 2280 default: 2281 break; 2282 case CSC_HASH_ASCIIZ_KEY: 2283#define FMT_STR "\t\t%s\t%d (%08X hex)\n" 2284#define FMT_SZ (strlen(FMT_STR)+strlen(entry->key.asciiz)+20+1) 2285 (void)CSCmemAlloc (memList, (void**)&msgBufPtr, 1, FMT_SZ, 0); 2286 (void)sprintf ( 2287 msgBufPtr, 2288 FMT_STR, 2289 entry->key.asciiz, 2290 entry->size, 2291 entry->size 2292 ); 2293#undef FMT_STR 2294#undef FMT_SZ 2295 break; 2296 case CSC_HASH_INT32_KEY: 2297#define FMT_STR "\t\t%d\t%d (%08X hex)\n" 2298#define FMT_SZ (strlen(FMT_STR)+sizeof(entry->key.integer)+20+1) 2299 (void)CSCmemAlloc (memList, (void**)&msgBufPtr, 1, FMT_SZ, 0); 2300 (void)sprintf ( 2301 msgBufPtr, 2302 FMT_STR, 2303 entry->key.integer, 2304 entry->size, 2305 entry->size 2306 ); 2307#undef FMT_STR 2308#undef FMT_SZ 2309 break; 2310 } 2311 (void)write (fd, msgBufPtr, strlen(msgBufPtr)); 2312 (void)CSCmemFree (memList, (void**)&msgBufPtr, 0); 2313/* 2314 (void)rtsMemDump (fd, entry->data, entry->size, NULL); 2315*/ 2316 entry = SUCC(entry); 2317 } 2318 } 2319 else 2320 { 2321#define MSG_STR "\t\tEMPTY\n" 2322 (void)write (fd, MSG_STR, strlen(MSG_STR)); 2323#undef MSG_STR 2324 } 2325 } 2326 2327 write (fd, "\n", 1); 2328 2329 (void)CSCmemDone (memList); 2330 2331 return (dumpStat); 2332 } 2333 2334 2335/* End of the file. */ 2336