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