| 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.5 2002/07/14 00:08:13 ghowlett 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 4
|
|---|
| 43 | #endif
|
|---|
| 44 | #ifndef SIZEOF_LONG_LONG
|
|---|
| 45 | #define SIZEOF_LONG_LONG 8
|
|---|
| 46 | #endif
|
|---|
| 47 | #ifndef SIZEOF_INT
|
|---|
| 48 | #define SIZEOF_INT 4
|
|---|
| 49 | #endif
|
|---|
| 50 | #ifndef SIZEOF_VOID_P
|
|---|
| 51 | #define SIZEOF_VOID_P 4
|
|---|
| 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 */
|
|---|
