util/src/TclTk/blt2.5/generic/bltHash.h

   1
   2 /*
   3  * bltHash.h --
   4  *
   5  * Copyright 2001 Silicon Metrics Corporation.
   6  *
   7  * Permission to use, copy, modify, and distribute this software and
   8  * its documentation for any purpose and without fee is hereby
   9  * granted, provided that the above copyright notice appear in all
  10  * copies and that both that the copyright notice and warranty
  11  * disclaimer appear in supporting documentation, and that the names
  12  * of Lucent Technologies any of their entities not be used in
  13  * advertising or publicity pertaining to distribution of the software
  14  * without specific, written prior permission.
  15  *
  16  * Silicon Metrics disclaims all warranties with regard to this
  17  * software, including all implied warranties of merchantability and
  18  * fitness.  In no event shall Lucent Technologies be liable for any
  19  * special, indirect or consequential damages or any damages
  20  * whatsoever resulting from loss of use, data or profits, whether in
  21  * an action of contract, negligence or other tortuous action, arising
  22  * out of or in connection with the use or performance of this
  23  * software.
  24  *
  25  * Bob Jenkins, 1996.  hash.c.  Public Domain.
  26  * Bob Jenkins, 1997.  lookup8.c.  Public Domain.
  27  *
  28  * Copyright (c) 1991-1993 The Regents of the University of California.
  29  * Copyright (c) 1994 Sun Microsystems, Inc.
  30  *
  31  * See the file "license.terms" for information on usage and redistribution
  32  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  33  *
  34  * RCS: @(#) $Id: bltHash.h.in,v 1.1.1.1 2009/05/09 16:27:17 pcmacdon Exp $
  35  */
  36
  37 #ifndef BLT_HASH_H
  38 #define BLT_HASH_H 1
  39
  40 #ifndef BLT_INT_H
  41 #ifndef SIZEOF_LONG
  42 #define SIZEOF_LONG 0
  43 #endif
  44 #ifndef SIZEOF_LONG_LONG
  45 #define SIZEOF_LONG_LONG 0
  46 #endif
  47 #ifndef SIZEOF_INT
  48 #define SIZEOF_INT 0
  49 #endif
  50 #ifndef SIZEOF_VOID_P
  51 #define SIZEOF_VOID_P 0
  52 #endif
  53 #ifndef HAVE_INTTYPES_H
  54 #if 1
  55 #define HAVE_INTTYPES_H 1
  56 #endif
  57 #endif
  58 #endif /* !BLT_INT_H */
  59
  60 #ifdef HAVE_INTTYPES_H
  61 #include <inttypes.h>
  62 #else
  63 #if (SIZEOF_VOID_P == 8)
  64 #if (SIZEOF_LONG == 8)
  65 typedef signed long int64_t;
  66 typedef unsigned long uint64_t;
  67 #else
  68 typedef signed long long int64_t;
  69 typedef unsigned long long uint64_t;
  70 #endif /* SIZEOF_LONG == 8 */
  71 #else
  72 #ifndef __CYGWIN__
  73 typedef signed int int32_t;
  74 #endif /* __CYGWIN__ */
  75 typedef unsigned int uint32_t;
  76 #endif /* SIZEOF_VOID_P == 8 */
  77 #endif /* HAVE_INTTYPES_H */
  78
  79 #if (SIZEOF_VOID_P == 8)
  80 typedef uint64_t Blt_Hash;
  81 #else
  82 typedef uint32_t Blt_Hash;
  83 #endif /* SIZEOF_VOID_P == 8 */
  84
  85 #include "bltPool.h"
  86
  87 /*
  88  * Acceptable key types for hash tables:
  89  */
  90 #define BLT_STRING_KEYS         0
  91 #define BLT_ONE_WORD_KEYS       ((size_t)-1)
  92
  93 /*
  94  * Forward declaration of Blt_HashTable.  Needed by some C++ compilers
  95  * to prevent errors when the forward reference to Blt_HashTable is
  96  * encountered in the Blt_HashEntry structure.
  97  */
  98
  99 #ifdef __cplusplus
 100 struct Blt_HashTable;
 101 #endif
 102
 103 typedef union {                 /* Key has one of these forms: */
 104     void *oneWordValue;         /* One-word value for key. */
 105     unsigned long words[1];     /* Multiple integer words for key.
 106                                  * The actual size will be as large
 107                                  * as necessary for this table's
 108                                  * keys. */
 109     char string[4];             /* String for key.  The actual size
 110                                  * will be as large as needed to hold
 111                                  * the key. */
 112 } Blt_HashKey;
 113
 114 /*
 115  * Structure definition for an entry in a hash table.  No-one outside
 116  * Blt should access any of these fields directly;  use the macros
 117  * defined below.
 118  */
 119 typedef struct Blt_HashEntry {
 120     struct Blt_HashEntry *nextPtr;      /* Pointer to next entry in this
 121                                          * hash bucket, or NULL for end of
 122                                          * chain. */
 123     Blt_Hash hval;
 124
 125     ClientData clientData;              /* Application stores something here
 126                                          * with Blt_SetHashValue. */
 127     Blt_HashKey key;                    /* MUST BE LAST FIELD IN RECORD!! */
 128 } Blt_HashEntry;
 129
 130 /*
 131  * Structure definition for a hash table.  Must be in blt.h so clients
 132  * can allocate space for these structures, but clients should never
 133  * access any fields in this structure.
 134  */
 135 #define BLT_SMALL_HASH_TABLE 4
 136 typedef struct Blt_HashTable {
 137     Blt_HashEntry **buckets;            /* Pointer to bucket array.  Each
 138                                          * element points to first entry in
 139                                          * bucket's hash chain, or NULL. */
 140     Blt_HashEntry *staticBuckets[BLT_SMALL_HASH_TABLE];
 141                                         /* Bucket array used for small tables
 142                                          * (to avoid mallocs and frees). */
 143     size_t numBuckets;                  /* Total number of buckets allocated
 144                                          * at **buckets. */
 145     size_t numEntries;                  /* Total number of entries present
 146                                          * in table. */
 147     size_t rebuildSize;                 /* Enlarge table when numEntries gets
 148                                          * to be this large. */
 149     Blt_Hash mask;                      /* Mask value used in hashing
 150                                          * function. */
 151     unsigned int downShift;             /* Shift count used in hashing
 152                                          * function.  Designed to use high-
 153                                          * order bits of randomized keys. */
 154     size_t keyType;                     /* Type of keys used in this table.
 155                                          * It's either BLT_STRING_KEYS,
 156                                          * BLT_ONE_WORD_KEYS, or an integer
 157                                          * giving the number of ints that
 158                                          * is the size of the key.
 159                                          */
 160     Blt_HashEntry *(*findProc) _ANSI_ARGS_((struct Blt_HashTable *tablePtr,
 161             CONST void *key));
 162     Blt_HashEntry *(*createProc) _ANSI_ARGS_((struct Blt_HashTable *tablePtr,
 163             CONST void *key, int *newPtr));
 164
 165     Blt_Pool hPool;             /* Pointer to the pool allocator used
 166                                  * for entries in this hash table. If
 167                                  * NULL, the standard Tcl_Alloc,
 168                                  * Tcl_Free routines will be used
 169                                  * instead.
 170                                  */
 171 } Blt_HashTable;
 172
 173 /*
 174  * Structure definition for information used to keep track of searches
 175  * through hash tables:
 176  */
 177
 178 typedef struct {
 179     Blt_HashTable *tablePtr;            /* Table being searched. */
 180     unsigned long nextIndex;            /* Index of next bucket to be
 181                                          * enumerated after present one. */
 182     Blt_HashEntry *nextEntryPtr;        /* Next entry to be enumerated in the
 183                                          * the current bucket. */
 184 } Blt_HashSearch;
 185
 186 /*
 187  * Macros for clients to use to access fields of hash entries:
 188  */
 189
 190 #define Blt_GetHashValue(h) ((h)->clientData)
 191 #define Blt_SetHashValue(h, value) ((h)->clientData = (ClientData)(value))
 192 #define Blt_GetHashKey(tablePtr, h) \
 193     ((void *) (((tablePtr)->keyType == BLT_ONE_WORD_KEYS) ? \
 194      (void *)(h)->key.oneWordValue : (h)->key.string))
 195
 196 /*
 197  * Macros to use for clients to use to invoke find and create procedures
 198  * for hash tables:
 199  */
 200 #define Blt_FindHashEntry(tablePtr, key) \
 201         (*((tablePtr)->findProc))(tablePtr, key)
 202 #define Blt_CreateHashEntry(tablePtr, key, newPtr) \
 203         (*((tablePtr)->createProc))(tablePtr, key, newPtr)
 204
 205 EXTERN void Blt_InitHashTable _ANSI_ARGS_((Blt_HashTable *tablePtr,
 206         size_t keyType));
 207
 208 EXTERN void Blt_InitHashTableWithPool _ANSI_ARGS_((Blt_HashTable *tablePtr,
 209         size_t keyType));
 210
 211 EXTERN void Blt_DeleteHashTable _ANSI_ARGS_((Blt_HashTable *tablePtr));
 212
 213 EXTERN void Blt_DeleteHashEntry _ANSI_ARGS_((Blt_HashTable *tablePtr,
 214         Blt_HashEntry *entryPtr));
 215
 216 EXTERN Blt_HashEntry *Blt_FirstHashEntry _ANSI_ARGS_((Blt_HashTable *tablePtr,
 217         Blt_HashSearch *searchPtr));
 218
 219 EXTERN Blt_HashEntry *Blt_NextHashEntry _ANSI_ARGS_((Blt_HashSearch *srchPtr));
 220
 221 EXTERN char *Blt_HashStats _ANSI_ARGS_((Blt_HashTable *tablePtr));
 222
 223 #endif /* BLT_HASH_H */