source: trunk/kitgen/8.x/blt/generic/bltHash.h.in@ 187

Last change on this file since 187 was 175, checked in by demin, 12 years ago

initial commit

File size: 7.1 KB
RevLine 
[175]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 @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 ((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
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 */
Note: See TracBrowser for help on using the repository browser.