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 @SIZEOF_LONG@ 43#endif 44#ifndef SIZEOF_LONG_LONG 45#define SIZEOF_LONG_LONG @SIZEOF_LONG_LONG@ 46#endif 47#ifndef SIZEOF_INT 48#define SIZEOF_INT @SIZEOF_INT@ 49#endif 50#ifndef SIZEOF_VOID_P 51#define SIZEOF_VOID_P @SIZEOF_VOID_P@ 52#endif 53#ifndef HAVE_INTTYPES_H 54#if @HAVE_INTTYPES_H@ 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) 65typedef signed long int64_t; 66typedef unsigned long uint64_t; 67#else 68typedef signed long long int64_t; 69typedef unsigned long long uint64_t; 70#endif /* SIZEOF_LONG == 8 */ 71#else 72#ifndef __CYGWIN__ 73typedef signed int int32_t; 74#endif /* __CYGWIN__ */ 75typedef unsigned int uint32_t; 76#endif /* SIZEOF_VOID_P == 8 */ 77#endif /* HAVE_INTTYPES_H */ 78 79#if (SIZEOF_VOID_P == 8) 80typedef uint64_t Blt_Hash; 81#else 82typedef 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 (-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 100struct Blt_HashTable; 101#endif 102 103typedef 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 */ 119typedef 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 136typedef 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 178typedef 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 205EXTERN void Blt_InitHashTable _ANSI_ARGS_((Blt_HashTable *tablePtr, 206 size_t keyType)); 207 208EXTERN void Blt_InitHashTableWithPool _ANSI_ARGS_((Blt_HashTable *tablePtr, 209 size_t keyType)); 210 211EXTERN void Blt_DeleteHashTable _ANSI_ARGS_((Blt_HashTable *tablePtr)); 212 213EXTERN void Blt_DeleteHashEntry _ANSI_ARGS_((Blt_HashTable *tablePtr, 214 Blt_HashEntry *entryPtr)); 215 216EXTERN Blt_HashEntry *Blt_FirstHashEntry _ANSI_ARGS_((Blt_HashTable *tablePtr, 217 Blt_HashSearch *searchPtr)); 218 219EXTERN Blt_HashEntry *Blt_NextHashEntry _ANSI_ARGS_((Blt_HashSearch *srchPtr)); 220 221EXTERN char *Blt_HashStats _ANSI_ARGS_((Blt_HashTable *tablePtr)); 222 223#endif /* BLT_HASH_H */ 224