Show tclHash.h syntax highlighted
/*
*
* Copyright (c) 2003 The Regents of the University of California. All
* rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Neither the name of the University nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
/*
* tclHash.h --
*
* This header file declares the facilities provided by the
* Tcl hash table procedures.
*
* Copyright 1991 Regents of the University of California
* 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. The University of California
* makes no representations about the suitability of this
* software for any purpose. It is provided "as is" without
* express or implied warranty.
*
* $Id: tclHash.h,v 1.3 2003/07/11 22:30:02 cerpa Exp $
*/
#ifndef _TCLHASH
#define _TCLHASH
#ifndef _TCL
#include "tcl.h"
#endif
/*
* Structure definition for an entry in a hash table. No-one outside
* Tcl should access any of these fields directly; use the macros
* defined below.
*/
typedef struct Tcl_HashEntry {
struct Tcl_HashEntry *nextPtr; /* Pointer to next entry in this
* hash bucket, or NULL for end of
* chain. */
struct Tcl_HashTable *tablePtr; /* Pointer to table containing entry. */
struct Tcl_HashEntry **bucketPtr; /* Pointer to bucket that points to
* first entry in this entry's chain:
* used for deleting the entry. */
ClientData clientData; /* Application stores something here
* with Tcl_SetHashValue. */
union { /* Key has one of these forms: */
char *oneWordValue; /* One-word value for key. */
int 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. */
} key; /* MUST BE LAST FIELD IN RECORD!! */
} Tcl_HashEntry;
/*
* Structure definition for a hash table. Must be in tcl.h so clients
* can allocate space for these structures, but clients should never
* access any fields in this structure.
*/
#define TCL_SMALL_HASH_TABLE 4
typedef struct Tcl_HashTable {
Tcl_HashEntry **buckets; /* Pointer to bucket array. Each
* element points to first entry in
* bucket's hash chain, or NULL. */
Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
/* Bucket array used for small tables
* (to avoid mallocs and frees). */
int numBuckets; /* Total number of buckets allocated
* at **bucketPtr. */
int numEntries; /* Total number of entries present
* in table. */
int rebuildSize; /* Enlarge table when numEntries gets
* to be this large. */
int downShift; /* Shift count used in hashing
* function. Designed to use high-
* order bits of randomized keys. */
int mask; /* Mask value used in hashing
* function. */
int keyType; /* Type of keys used in this table.
* It's either TCL_STRING_KEYS,
* TCL_ONE_WORD_KEYS, or an integer
* giving the number of ints in a
*/
Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
char *key));
Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
char *key, int *newPtr));
} Tcl_HashTable;
/*
* Structure definition for information used to keep track of searches
* through hash tables:
*/
typedef struct Tcl_HashSearch {
Tcl_HashTable *tablePtr; /* Table being searched. */
int nextIndex; /* Index of next bucket to be
* enumerated after present one. */
Tcl_HashEntry *nextEntryPtr; /* Next entry to be enumerated in the
* the current bucket. */
} Tcl_HashSearch;
/*
* Acceptable key types for hash tables:
*/
#define TCL_STRING_KEYS 0
#define TCL_ONE_WORD_KEYS 1
/*
* Macros for clients to use to access fields of hash entries:
*/
#define Tcl_GetHashValue(h) ((h)->clientData)
#define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
#define Tcl_GetHashKey(tablePtr, h) \
((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
: (h)->key.string))
/*
* Macros to use for clients to use to invoke find and create procedures
* for hash tables:
*/
#define Tcl_FindHashEntry(tablePtr, key) \
(*((tablePtr)->findProc))(tablePtr, key)
#define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
(*((tablePtr)->createProc))(tablePtr, key, newPtr)
/*
* Exported procedures:
*/
extern void Tcl_DeleteHashEntry _ANSI_ARGS_((
Tcl_HashEntry *entryPtr));
extern void Tcl_DeleteHashTable _ANSI_ARGS_((
Tcl_HashTable *tablePtr));
extern Tcl_HashEntry * Tcl_FirstHashEntry _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
Tcl_HashSearch *searchPtr));
extern char * Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
extern void Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
int keyType));
extern Tcl_HashEntry * Tcl_NextHashEntry _ANSI_ARGS_((
Tcl_HashSearch *searchPtr));
#endif /* _TCLHASH */
See more files for this project here