1Tcl_Hash(3)                 Tcl Library Procedures                 Tcl_Hash(3)
2
3
4
5______________________________________________________________________________
6

NAME

8       Tcl_InitHashTable,    Tcl_InitCustomHashTable,    Tcl_InitObjHashTable,
9       Tcl_DeleteHashTable,     Tcl_CreateHashEntry,      Tcl_DeleteHashEntry,
10       Tcl_FindHashEntry,  Tcl_GetHashValue, Tcl_SetHashValue, Tcl_GetHashKey,
11       Tcl_FirstHashEntry, Tcl_NextHashEntry, Tcl_HashStats  -  procedures  to
12       manage hash tables
13

SYNOPSIS

15       #include <tcl.h>
16
17       Tcl_InitHashTable(tablePtr, keyType)
18
19       Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
20
21       Tcl_InitObjHashTable(tablePtr)
22
23       Tcl_DeleteHashTable(tablePtr)
24
25       Tcl_HashEntry *
26       Tcl_CreateHashEntry(tablePtr, key, newPtr)
27
28       Tcl_DeleteHashEntry(entryPtr)
29
30       Tcl_HashEntry *
31       Tcl_FindHashEntry(tablePtr, key)
32
33       ClientData
34       Tcl_GetHashValue(entryPtr)
35
36       Tcl_SetHashValue(entryPtr, value)
37
38       char *
39       Tcl_GetHashKey(tablePtr, entryPtr)
40
41       Tcl_HashEntry *
42       Tcl_FirstHashEntry(tablePtr, searchPtr)
43
44       Tcl_HashEntry *
45       Tcl_NextHashEntry(searchPtr)
46
47       char *
48       Tcl_HashStats(tablePtr)
49

ARGUMENTS

51       Tcl_HashTable *tablePtr (in)             Address  of  hash table struc‐
52                                                ture (for all  procedures  but
53                                                Tcl_InitHashTable,  this  must
54                                                have been initialized by  pre‐
55                                                vious          call         to
56                                                Tcl_InitHashTable).
57
58       int keyType (in)                         Kind of keys to  use  for  new
59                                                hash  table.   Must  be either
60                                                TCL_STRING_KEYS,
61                                                TCL_ONE_WORD_KEYS,    TCL_CUS‐
62                                                TOM_TYPE_KEYS,        TCL_CUS‐
63                                                TOM_PTR_KEYS,  or  an  integer
64                                                value greater than 1.
65
66       Tcl_HashKeyType *typePtr (in)            Address  of  structure   which
67                                                defines  the  behaviour of the
68                                                hash table.
69
70       const char *key (in)                     Key to use for probe into  ta‐
71                                                ble.   Exact  form  depends on
72                                                keyType used to create table.
73
74       int *newPtr (out)                        The word at *newPtr is set  to
75                                                1  if  a new entry was created
76                                                and 0 if there was already  an
77                                                entry for key.
78
79       Tcl_HashEntry *entryPtr (in)             Pointer to hash table entry.
80
81       ClientData value (in)                    New  value  to  assign to hash
82                                                table entry.   Need  not  have
83                                                type  ClientData, but must fit
84                                                in same space as ClientData.
85
86       Tcl_HashSearch *searchPtr (in)           Pointer to record  to  use  to
87                                                keep track of progress in enu‐
88                                                merating all the entries in  a
89                                                hash table.
90_________________________________________________________________
91

DESCRIPTION

93       A hash table consists of zero or more entries, each consisting of a key
94       and a value.  Given the key for an entry, the hashing routines can very
95       quickly locate the entry, and hence its value. There may be at most one
96       entry in a hash table with a particular key, but many entries may  have
97       the  same  value.   Keys  can take one of four forms: strings, one-word
98       values, integer arrays, or custom keys  defined  by  a  Tcl_HashKeyType
99       structure (See section THE TCL_HASHKEYTYPE STRUCTURE below). All of the
100       keys in a given table have the same form, which is specified  when  the
101       table is initialized.
102
103       The  value  of a hash table entry can be anything that fits in the same
104       space as a “char *” pointer.  Values for hash table entries are managed
105       entirely  by  clients,  not  by the hash module itself.  Typically each
106       entry's value is a pointer to a data structure managed by client code.
107
108       Hash tables grow gracefully as the number of entries increases, so that
109       there  are  always less than three entries per hash bucket, on average.
110       This allows for fast lookups regardless of the number of entries  in  a
111       table.
112
113       The  core  provides  three  functions  for  the  initialization of hash
114       tables,  Tcl_InitHashTable,   Tcl_InitObjHashTable   and   Tcl_InitCus‐
115       tomHashTable.
116
117       Tcl_InitHashTable initializes a structure that describes a new hash ta‐
118       ble.  The space for the structure is provided by the caller, not by the
119       hash module.  The value of keyType indicates what kinds of keys will be
120       used for all entries in the table. All of the key types described later
121       are  allowed,  with  the exception of TCL_CUSTOM_TYPE_KEYS and TCL_CUS‐
122       TOM_PTR_KEYS.
123
124       Tcl_InitObjHashTable is a wrapper  around  Tcl_InitCustomHashTable  and
125       initializes a hash table whose keys are Tcl_Obj *.
126
127       Tcl_InitCustomHashTable  initializes  a  structure that describes a new
128       hash table. The space for the structure is provided by the caller,  not
129       by  the hash module.  The value of keyType indicates what kinds of keys
130       will be used for all entries in the table.  KeyType must  have  one  of
131       the following values:
132
133       TCL_STRING_KEYS          Keys  are  null-terminated  strings.  They are
134                                passed to hashing routines using  the  address
135                                of the first character of the string.
136
137       TCL_ONE_WORD_KEYS        Keys  are single-word values;  they are passed
138                                to hashing routines and stored in  hash  table
139                                entries as “char *” values.  The pointer value
140                                is the key;  it need  not  (and  usually  does
141                                not) actually point to a string.
142
143       TCL_CUSTOM_TYPE_KEYS     Keys  are of arbitrary type, and are stored in
144                                the entry. Hashing and  comparison  is  deter‐
145                                mined  by  typePtr. The Tcl_HashKeyType struc‐
146                                ture  is  described   in   the   section   THE
147                                TCL_HASHKEYTYPE STRUCTURE below.
148
149       TCL_CUSTOM_PTR_KEYS      Keys  are  pointers  to an arbitrary type, and
150                                are stored in the entry. Hashing and  compari‐
151                                son is determined by typePtr. The Tcl_HashKey‐
152                                Type structure is described in the section THE
153                                TCL_HASHKEYTYPE STRUCTURE below.
154
155       other                    If  keyType  is  not one of the above, then it
156                                must be an integer value greater than  1.   In
157                                this  case  the  keys  will be arrays of “int”
158                                values, where keyType gives the number of ints
159                                in  each  key.   This  allows structures to be
160                                used as keys.  All keys  must  have  the  same
161                                size.   Array  keys  are  passed  into hashing
162                                functions using the address of the  first  int
163                                in the array.
164
165       Tcl_DeleteHashTable  deletes  all  of  the  entries in a hash table and
166       frees up the memory  associated  with  the  table's  bucket  array  and
167       entries.   It  does  not free the actual table structure (pointed to by
168       tablePtr), since that memory is assumed to be managed  by  the  client.
169       Tcl_DeleteHashTable also does not free or otherwise manipulate the val‐
170       ues of the hash table entries.  If the entry values  point  to  dynami‐
171       cally-allocated  memory, then it is the client's responsibility to free
172       these structures before deleting the table.
173
174       Tcl_CreateHashEntry locates the entry  corresponding  to  a  particular
175       key,  creating  a  new  entry in the table if there was not already one
176       with the given key.  If an entry already existed  with  the  given  key
177       then  *newPtr is set to zero.  If a new entry was created, then *newPtr
178       is set to a non-zero value and the value of the new entry will  be  set
179       to zero.  The return value from Tcl_CreateHashEntry is a pointer to the
180       entry, which may be used to retrieve and modify the entry's value or to
181       delete the entry from the table.
182
183       Tcl_DeleteHashEntry  will  remove  an existing entry from a table.  The
184       memory associated with the entry itself will be freed, but  the  client
185       is  responsible for any cleanup associated with the entry's value, such
186       as freeing a structure that it points to.
187
188       Tcl_FindHashEntry is similar to Tcl_CreateHashEntry except that it does
189       not  create  a  new entry if the key doesn't exist; instead, it returns
190       NULL as result.
191
192       Tcl_GetHashValue and Tcl_SetHashValue are used to  read  and  write  an
193       entry's  value,  respectively.  Values are stored and retrieved as type
194       “ClientData”, which is large enough to hold a pointer value.  On almost
195       all machines this is large enough to hold an integer value too.
196
197       Tcl_GetHashKey  returns the key for a given hash table entry, either as
198       a pointer to a string, a one-word (“char *”) key, or as  a  pointer  to
199       the  first  word of an array of integers, depending on the keyType used
200       to create a hash table.  In all cases Tcl_GetHashKey returns  a  result
201       with  type  “char *”.  When the key is a string or array, the result of
202       Tcl_GetHashKey points to information in the table entry;  this informa‐
203       tion  will  remain  valid  until  the  entry is deleted or its table is
204       deleted.
205
206       Tcl_FirstHashEntry and Tcl_NextHashEntry may be used to scan all of the
207       entries  in  a  hash table.  A structure of type “Tcl_HashSearch”, pro‐
208       vided by the client, is used to keep track of progress through the  ta‐
209       ble.   Tcl_FirstHashEntry initializes the search record and returns the
210       first entry in the table (or NULL if the table is empty).  Each  subse‐
211       quent  call to Tcl_NextHashEntry returns the next entry in the table or
212       NULL  if  the  end  of  the  table  has  been  reached.   A   call   to
213       Tcl_FirstHashEntry  followed  by calls to Tcl_NextHashEntry will return
214       each of the entries in the table exactly once, in an  arbitrary  order.
215       It is inadvisable to modify the structure of the table, e.g.  by creat‐
216       ing or deleting entries, while the search  is  in  progress,  with  the
217       exception  of  deleting  the  entry  returned  by Tcl_FirstHashEntry or
218       Tcl_NextHashEntry.
219
220       Tcl_HashStats  returns  a  dynamically-allocated  string  with  overall
221       information  about  a hash table, such as the number of entries it con‐
222       tains, the number of buckets in its hash array, and the utilization  of
223       the  buckets.   It  is  the  caller's responsibility to free the result
224       string by passing it to ckfree.
225
226       The header file tcl.h defines the actual data structures used to imple‐
227       ment  hash  tables.   This  is  necessary  so that clients can allocate
228       Tcl_HashTable structures and so that macros can be  used  to  read  and
229       write  the  values  of entries.  However, users of the hashing routines
230       should never refer directly to any of the fields of any  of  the  hash-
231       related data structures; use the procedures and macros defined here.
232

THE TCL_HASHKEYTYPE STRUCTURE

234       Extension writers can define new hash key types by defining four proce‐
235       dures, initializing a Tcl_HashKeyType structure to describe  the  type,
236       and  calling  Tcl_InitCustomHashTable. The Tcl_HashKeyType structure is
237       defined as follows:
238              typedef struct Tcl_HashKeyType {
239                  int version;
240                  int flags;
241                  Tcl_HashKeyProc *hashKeyProc;
242                  Tcl_CompareHashKeysProc *compareKeysProc;
243                  Tcl_AllocHashEntryProc *allocEntryProc;
244                  Tcl_FreeHashEntryProc *freeEntryProc;
245              } Tcl_HashKeyType;
246
247       The version member is the version of the table. If  this  structure  is
248       extended  in future then the version can be used to distinguish between
249       different structures. It should be set to TCL_HASH_KEY_TYPE_VERSION.
250
251       The flags member is 0 or one or more  of  the  following  values  OR'ed
252       together:
253
254       TCL_HASH_KEY_RANDOMIZE_HASH
255                                There  are  some  things, pointers for example
256                                which do not hash well because they do not use
257                                the  lower  bits. If this flag is set then the
258                                hash table will attempt  to  rectify  this  by
259                                randomizing  the bits and then using the upper
260                                N bits as the index into the table.
261
262       TCL_HASH_KEY_SYSTEM_HASH This flag forces Tcl to use the memory alloca‐ │
263                                tion procedures provided by the operating sys‐ │
264                                tem when allocating and freeing memory used to │
265                                store  the hash table data structures, and not │
266                                any of Tcl's own customized memory  allocation │
267                                routines.  This is important if the hash table │
268                                is to be used in the implementation of a  cus‐ │
269                                tom  set  of allocation routines, or something │
270                                that a custom set of allocation routines might │
271                                depend  on,  in  order  to  avoid any circular │
272                                dependency.
273
274       The hashKeyProc member contains the address of  a  function  called  to
275       calculate a hash value for the key.
276              typedef unsigned int (Tcl_HashKeyProc) (
277                      Tcl_HashTable *tablePtr,
278                      void *keyPtr);
279       If  this is NULL then keyPtr is used and TCL_HASH_KEY_RANDOMIZE_HASH is
280       assumed.
281
282       The compareKeysProc member contains the address of a function called to
283       compare two keys.
284              typedef int (Tcl_CompareHashKeysProc) (
285                      void *keyPtr,
286                      Tcl_HashEntry *hPtr);
287       If  this  is NULL then the keyPtr pointers are compared. If the keys do
288       not match then the function returns 0, otherwise it returns 1.
289
290       The allocEntryProc member contains the address of a function called  to
291       allocate space for an entry and initialize the key and clientData.
292              typedef Tcl_HashEntry *(Tcl_AllocHashEntryProc) (
293                      Tcl_HashTable *tablePtr,
294                      void *keyPtr);
295       If  this  is NULL then Tcl_Alloc is used to allocate enough space for a
296       Tcl_HashEntry, the key pointer is assigned to key.oneWordValue and  the
297       clientData is set to NULL. String keys and array keys use this function
298       to allocate enough space for the entry and the key in one block, rather
299       than  doing it in two blocks. This saves space for a pointer to the key
300       from the entry and another memory allocation. Tcl_Obj*  keys  use  this
301       function to allocate enough space for an entry and increment the refer‐
302       ence count on the object.
303
304       The freeEntryProc member contains the address of a function  called  to
305       free space for an entry.
306              typedef void (Tcl_FreeHashEntryProc) (Tcl_HashEntry *hPtr);
307       If  this is NULL then Tcl_Free is used to free the space for the entry.
308       Tcl_Obj* keys use this function to decrement the reference count on the
309       object.
310

KEYWORDS

312       hash table, key, lookup, search, value
313
314
315
316Tcl                                                                Tcl_Hash(3)
Impressum