/* * 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 RP_HASH_H #define RP_HASH_H 1 #ifndef RP_INT_H #ifndef SIZEOF_LONG #define SIZEOF_LONG @SIZEOF_LONG@ #endif #ifndef SIZEOF_LONG_LONG #define SIZEOF_LONG_LONG @SIZEOF_LONG_LONG@ #endif #ifndef SIZEOF_INT #define SIZEOF_INT @SIZEOF_INT@ #endif #ifndef SIZEOF_VOID_P #define SIZEOF_VOID_P @SIZEOF_VOID_P@ #endif #ifndef HAVE_INTTYPES_H #if @HAVE_INTTYPES_H@ #define HAVE_INTTYPES_H 1 #endif #endif #endif /* !RP_INT_H */ #ifdef HAVE_INTTYPES_H #include #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 Rp_Hash; #else typedef uint32_t Rp_Hash; #endif /* SIZEOF_VOID_P == 8 */ #include "RpPool.h" /* * Acceptable key types for hash tables: */ #define RP_STRING_KEYS 0 #define RP_ONE_WORD_KEYS ((size_t)-1) /* * Forward declaration of Rp_HashTable. Needed by some C++ compilers * to prevent errors when the forward reference to Rp_HashTable is * encountered in the Rp_HashEntry structure. */ #ifdef __cplusplus struct Rp_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. */ } Rp_HashKey; /* * Structure definition for an entry in a hash table. No-one outside * Rp should access any of these fields directly; use the macros * defined below. */ typedef struct Rp_HashEntry { struct Rp_HashEntry *nextPtr; /* Pointer to next entry in this * hash bucket, or NULL for end of * chain. */ Rp_Hash hval; ClientData clientData; /* Application stores something here * with Rp_SetHashValue. */ Rp_HashKey key; /* MUST BE LAST FIELD IN RECORD!! */ } Rp_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 RP_SMALL_HASH_TABLE 4 typedef struct Rp_HashTable { Rp_HashEntry **buckets; /* Pointer to bucket array. Each * element points to first entry in * bucket's hash chain, or NULL. */ Rp_HashEntry *staticBuckets[RP_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. */ Rp_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 RP_STRING_KEYS, * RP_ONE_WORD_KEYS, or an integer * giving the number of ints that * is the size of the key. */ Rp_HashEntry *(*findProc) _ANSI_ARGS_((struct Rp_HashTable *tablePtr, CONST void *key)); Rp_HashEntry *(*createProc) _ANSI_ARGS_((struct Rp_HashTable *tablePtr, CONST void *key, int *newPtr)); Rp_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. */ } Rp_HashTable; /* * Structure definition for information used to keep track of searches * through hash tables: */ typedef struct { Rp_HashTable *tablePtr; /* Table being searched. */ unsigned long nextIndex; /* Index of next bucket to be * enumerated after present one. */ Rp_HashEntry *nextEntryPtr; /* Next entry to be enumerated in the * the current bucket. */ } Rp_HashSearch; /* * Macros for clients to use to access fields of hash entries: */ #define Rp_GetHashValue(h) ((h)->clientData) #define Rp_SetHashValue(h, value) ((h)->clientData = (ClientData)(value)) #define Rp_GetHashKey(tablePtr, h) \ ((void *) (((tablePtr)->keyType == RP_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 Rp_FindHashEntry(tablePtr, key) \ (*((tablePtr)->findProc))(tablePtr, key) #define Rp_CreateHashEntry(tablePtr, key, newPtr) \ (*((tablePtr)->createProc))(tablePtr, key, newPtr) EXTERN void Rp_InitHashTable _ANSI_ARGS_((Rp_HashTable *tablePtr, size_t keyType)); EXTERN void Rp_InitHashTableWithPool _ANSI_ARGS_((Rp_HashTable *tablePtr, size_t keyType)); EXTERN void Rp_DeleteHashTable _ANSI_ARGS_((Rp_HashTable *tablePtr)); EXTERN void Rp_DeleteHashEntry _ANSI_ARGS_((Rp_HashTable *tablePtr, Rp_HashEntry *entryPtr)); EXTERN Rp_HashEntry *Rp_FirstHashEntry _ANSI_ARGS_((Rp_HashTable *tablePtr, Rp_HashSearch *searchPtr)); EXTERN Rp_HashEntry *Rp_NextHashEntry _ANSI_ARGS_((Rp_HashSearch *srchPtr)); EXTERN char *Rp_HashStats _ANSI_ARGS_((Rp_HashTable *tablePtr)); #endif /* RP_HASH_H */