cvs.zerfleddert.de Git - micropolis/blame_incremental - src/tcl/tclhash.h

/*
 * 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.
 *
 * $Header: /sprite/src/lib/tcl/RCS/tclHash.h,v 1.3 91/08/27 11:36:04 ouster Exp $ SPRITE (Berkeley)
 */

#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 */
Commit	Line	Data
	1	/*
	2	* tclHash.h --
	3	*
	4	* This header file declares the facilities provided by the
	5	* Tcl hash table procedures.
	6	*
	7	* Copyright 1991 Regents of the University of California
	8	* Permission to use, copy, modify, and distribute this
	9	* software and its documentation for any purpose and without
	10	* fee is hereby granted, provided that the above copyright
	11	* notice appear in all copies. The University of California
	12	* makes no representations about the suitability of this
	13	* software for any purpose. It is provided "as is" without
	14	* express or implied warranty.
	15	*
	16	* $Header: /sprite/src/lib/tcl/RCS/tclHash.h,v 1.3 91/08/27 11:36:04 ouster Exp $ SPRITE (Berkeley)
	17	*/
	18
	19	#ifndef _TCLHASH
	20	#define _TCLHASH
	21
	22	#ifndef _TCL
	23	#include <tcl.h>
	24	#endif
	25
	26	/*
	27	* Structure definition for an entry in a hash table. No-one outside
	28	* Tcl should access any of these fields directly; use the macros
	29	* defined below.
	30	*/
	31
	32	typedef struct Tcl_HashEntry {
	33	struct Tcl_HashEntry nextPtr; / Pointer to next entry in this
	34	* hash bucket, or NULL for end of
	35	* chain. */
	36	struct Tcl_HashTable tablePtr; / Pointer to table containing entry. */
	37	struct Tcl_HashEntry *bucketPtr; / Pointer to bucket that points to
	38	* first entry in this entry's chain:
	39	* used for deleting the entry. */
	40	ClientData clientData; /* Application stores something here
	41	* with Tcl_SetHashValue. */
	42	union { /* Key has one of these forms: */
	43	char oneWordValue; / One-word value for key. */
	44	int words[1]; /* Multiple integer words for key.
	45	* The actual size will be as large
	46	* as necessary for this table's
	47	* keys. */
	48	char string[4]; /* String for key. The actual size
	49	* will be as large as needed to hold
	50	* the key. */
	51	} key; /* MUST BE LAST FIELD IN RECORD!! */
	52	} Tcl_HashEntry;
	53
	54	/*
	55	* Structure definition for a hash table. Must be in tcl.h so clients
	56	* can allocate space for these structures, but clients should never
	57	* access any fields in this structure.
	58	*/
	59
	60	#define TCL_SMALL_HASH_TABLE 4
	61	typedef struct Tcl_HashTable {
	62	Tcl_HashEntry *buckets; / Pointer to bucket array. Each
	63	* element points to first entry in
	64	* bucket's hash chain, or NULL. */
	65	Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
	66	/* Bucket array used for small tables
	67	* (to avoid mallocs and frees). */
	68	int numBuckets; /* Total number of buckets allocated
	69	* at *bucketPtr. /
	70	int numEntries; /* Total number of entries present
	71	* in table. */
	72	int rebuildSize; /* Enlarge table when numEntries gets
	73	* to be this large. */
	74	int downShift; /* Shift count used in hashing
	75	* function. Designed to use high-
	76	* order bits of randomized keys. */
	77	int mask; /* Mask value used in hashing
	78	* function. */
	79	int keyType; /* Type of keys used in this table.
	80	* It's either TCL_STRING_KEYS,
	81	* TCL_ONE_WORD_KEYS, or an integer
	82	* giving the number of ints in a
	83	*/
	84	Tcl_HashEntry (findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
	85	char *key));
	86	Tcl_HashEntry (createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
	87	char key, int newPtr));
	88	} Tcl_HashTable;
	89
	90	/*
	91	* Structure definition for information used to keep track of searches
	92	* through hash tables:
	93	*/
	94
	95	typedef struct Tcl_HashSearch {
	96	Tcl_HashTable tablePtr; / Table being searched. */
	97	int nextIndex; /* Index of next bucket to be
	98	* enumerated after present one. */
	99	Tcl_HashEntry nextEntryPtr; / Next entry to be enumerated in the
	100	* the current bucket. */
	101	} Tcl_HashSearch;
	102
	103	/*
	104	* Acceptable key types for hash tables:
	105	*/
	106
	107	#define TCL_STRING_KEYS 0
	108	#define TCL_ONE_WORD_KEYS 1
	109
	110	/*
	111	* Macros for clients to use to access fields of hash entries:
	112	*/
	113
	114	#define Tcl_GetHashValue(h) ((h)->clientData)
	115	#define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
	116	#define Tcl_GetHashKey(tablePtr, h) \
	117	((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
	118	: (h)->key.string))
	119
	120	/*
	121	* Macros to use for clients to use to invoke find and create procedures
	122	* for hash tables:
	123	*/
	124
	125	#define Tcl_FindHashEntry(tablePtr, key) \
	126	(*((tablePtr)->findProc))(tablePtr, key)
	127	#define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
	128	(*((tablePtr)->createProc))(tablePtr, key, newPtr)
	129
	130	/*
	131	* Exported procedures:
	132	*/
	133
	134	extern void Tcl_DeleteHashEntry _ANSI_ARGS_((
	135	Tcl_HashEntry *entryPtr));
	136	extern void Tcl_DeleteHashTable _ANSI_ARGS_((
	137	Tcl_HashTable *tablePtr));
	138	extern Tcl_HashEntry * Tcl_FirstHashEntry _ANSI_ARGS_((
	139	Tcl_HashTable *tablePtr,
	140	Tcl_HashSearch *searchPtr));
	141	extern char * Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
	142	extern void Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
	143	int keyType));
	144	extern Tcl_HashEntry * Tcl_NextHashEntry _ANSI_ARGS_((
	145	Tcl_HashSearch *searchPtr));
	146
	147	#endif /* _TCLHASH */