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