]> git.zerfleddert.de Git - micropolis/blob - src/tcl/tclhash.h
projects / micropolis / blob
? search:


b390573211e4c3e1d2bbc02bf00ee596a6a19799
[micropolis] / src / tcl / tclhash.h
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 */
Micropolis
Impressum, Datenschutz