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       void *
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
52                                                      structure (for all  pro‐
53                                                      cedures              but
54                                                      Tcl_InitHashTable,  this
55                                                      must  have been initial‐
56                                                      ized by previous call to
57                                                      Tcl_InitHashTable).
58
59       int keyType (in)                               Kind  of keys to use for
60                                                      new hash table.  Must be
61                                                      either  TCL_STRING_KEYS,
62                                                      TCL_ONE_WORD_KEYS,
63                                                      TCL_CUSTOM_TYPE_KEYS,
64                                                      TCL_CUSTOM_PTR_KEYS,  or
65                                                      an integer value greater
66                                                      than 1.
67
68       Tcl_HashKeyType *typePtr (in)                  Address   of   structure
69                                                      which defines the behav‐
70                                                      ior of the hash table.
71
72       const void *key (in)                           Key  to  use  for  probe
73                                                      into  table.  Exact form
74                                                      depends on keyType  used
75                                                      to create table.
76
77       int *newPtr (out)                              The  word  at *newPtr is
78                                                      set to 1 if a new  entry
79                                                      was  created  and  0  if
80                                                      there  was  already   an
81                                                      entry for key.
82
83       Tcl_HashEntry *entryPtr (in)                   Pointer  to  hash  table
84                                                      entry.
85
86       ClientData value (in)                          New value to  assign  to
87                                                      hash  table entry.  Need
88                                                      not  have  type  Client‐
89                                                      Data,  but  must  fit in
90                                                      same  space  as  Client‐
91                                                      Data.
92
93       Tcl_HashSearch *searchPtr (in)                 Pointer to record to use
94                                                      to   keep    track    of
95                                                      progress  in enumerating
96                                                      all  the  entries  in  a
97                                                      hash table.
98______________________________________________________________________________
99

DESCRIPTION

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

THE TCL_HASHKEYTYPE STRUCTURE

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

KEYWORDS

330       hash table, key, lookup, search, value
331
332
333
334Tcl                                                                Tcl_Hash(3)
Impressum