source: branches/blt4/src/objects/RpHash.h.in @ 2936

/*
 * 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 <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 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 */