]> cvs.zerfleddert.de Git - micropolis/blame - src/tcl/tclhash.h
XINCLUDE: use /usr/X11R6/include everywhere
[micropolis] / src / tcl / tclhash.h
CommitLineData
6a5fa4e0
MG
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
32typedef 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
61typedef 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
95typedef 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
134extern void Tcl_DeleteHashEntry _ANSI_ARGS_((
135 Tcl_HashEntry *entryPtr));
136extern void Tcl_DeleteHashTable _ANSI_ARGS_((
137 Tcl_HashTable *tablePtr));
138extern Tcl_HashEntry * Tcl_FirstHashEntry _ANSI_ARGS_((
139 Tcl_HashTable *tablePtr,
140 Tcl_HashSearch *searchPtr));
141extern char * Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
142extern void Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
143 int keyType));
144extern Tcl_HashEntry * Tcl_NextHashEntry _ANSI_ARGS_((
145 Tcl_HashSearch *searchPtr));
146
147#endif /* _TCLHASH */
Impressum, Datenschutz