[25] | 1 | '\" |
---|
| 2 | '\" Copyright (c) 1989-1993 The Regents of the University of California. |
---|
| 3 | '\" Copyright (c) 1994-1996 Sun Microsystems, Inc. |
---|
| 4 | '\" |
---|
| 5 | '\" See the file "license.terms" for information on usage and redistribution |
---|
| 6 | '\" of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
---|
| 7 | '\" |
---|
| 8 | '\" RCS: @(#) $Id: Hash.3,v 1.26 2007/12/13 15:22:31 dgp Exp $ |
---|
| 9 | '\" |
---|
| 10 | .so man.macros |
---|
| 11 | .TH Tcl_Hash 3 "" Tcl "Tcl Library Procedures" |
---|
| 12 | .BS |
---|
| 13 | .SH NAME |
---|
| 14 | Tcl_InitHashTable, Tcl_InitCustomHashTable, Tcl_InitObjHashTable, Tcl_DeleteHashTable, Tcl_CreateHashEntry, Tcl_DeleteHashEntry, Tcl_FindHashEntry, Tcl_GetHashValue, Tcl_SetHashValue, Tcl_GetHashKey, Tcl_FirstHashEntry, Tcl_NextHashEntry, Tcl_HashStats \- procedures to manage hash tables |
---|
| 15 | .SH SYNOPSIS |
---|
| 16 | .nf |
---|
| 17 | \fB#include <tcl.h>\fR |
---|
| 18 | .sp |
---|
| 19 | \fBTcl_InitHashTable\fR(\fItablePtr, keyType\fR) |
---|
| 20 | .sp |
---|
| 21 | \fBTcl_InitCustomHashTable\fR(\fItablePtr, keyType, typePtr\fR) |
---|
| 22 | .sp |
---|
| 23 | \fBTcl_InitObjHashTable\fR(\fItablePtr\fR) |
---|
| 24 | .sp |
---|
| 25 | \fBTcl_DeleteHashTable\fR(\fItablePtr\fR) |
---|
| 26 | .sp |
---|
| 27 | Tcl_HashEntry * |
---|
| 28 | \fBTcl_CreateHashEntry\fR(\fItablePtr, key, newPtr\fR) |
---|
| 29 | .sp |
---|
| 30 | \fBTcl_DeleteHashEntry\fR(\fIentryPtr\fR) |
---|
| 31 | .sp |
---|
| 32 | Tcl_HashEntry * |
---|
| 33 | \fBTcl_FindHashEntry\fR(\fItablePtr, key\fR) |
---|
| 34 | .sp |
---|
| 35 | ClientData |
---|
| 36 | \fBTcl_GetHashValue\fR(\fIentryPtr\fR) |
---|
| 37 | .sp |
---|
| 38 | \fBTcl_SetHashValue\fR(\fIentryPtr, value\fR) |
---|
| 39 | .sp |
---|
| 40 | char * |
---|
| 41 | \fBTcl_GetHashKey\fR(\fItablePtr, entryPtr\fR) |
---|
| 42 | .sp |
---|
| 43 | Tcl_HashEntry * |
---|
| 44 | \fBTcl_FirstHashEntry\fR(\fItablePtr, searchPtr\fR) |
---|
| 45 | .sp |
---|
| 46 | Tcl_HashEntry * |
---|
| 47 | \fBTcl_NextHashEntry\fR(\fIsearchPtr\fR) |
---|
| 48 | .sp |
---|
| 49 | const char * |
---|
| 50 | \fBTcl_HashStats\fR(\fItablePtr\fR) |
---|
| 51 | .SH ARGUMENTS |
---|
| 52 | .AS Tcl_HashKeyType *searchPtr out |
---|
| 53 | .AP Tcl_HashTable *tablePtr in |
---|
| 54 | Address of hash table structure (for all procedures but |
---|
| 55 | \fBTcl_InitHashTable\fR, this must have been initialized by |
---|
| 56 | previous call to \fBTcl_InitHashTable\fR). |
---|
| 57 | .AP int keyType in |
---|
| 58 | Kind of keys to use for new hash table. Must be either |
---|
| 59 | \fBTCL_STRING_KEYS\fR, \fBTCL_ONE_WORD_KEYS\fR, \fBTCL_CUSTOM_TYPE_KEYS\fR, |
---|
| 60 | \fBTCL_CUSTOM_PTR_KEYS\fR, or an integer value greater than 1. |
---|
| 61 | .AP Tcl_HashKeyType *typePtr in |
---|
| 62 | Address of structure which defines the behaviour of the hash table. |
---|
| 63 | .AP "const char" *key in |
---|
| 64 | Key to use for probe into table. Exact form depends on |
---|
| 65 | \fIkeyType\fR used to create table. |
---|
| 66 | .AP int *newPtr out |
---|
| 67 | The word at \fI*newPtr\fR is set to 1 if a new entry was created |
---|
| 68 | and 0 if there was already an entry for \fIkey\fR. |
---|
| 69 | .AP Tcl_HashEntry *entryPtr in |
---|
| 70 | Pointer to hash table entry. |
---|
| 71 | .AP ClientData value in |
---|
| 72 | New value to assign to hash table entry. Need not have type |
---|
| 73 | ClientData, but must fit in same space as ClientData. |
---|
| 74 | .AP Tcl_HashSearch *searchPtr in |
---|
| 75 | Pointer to record to use to keep track of progress in enumerating |
---|
| 76 | all the entries in a hash table. |
---|
| 77 | .BE |
---|
| 78 | .SH DESCRIPTION |
---|
| 79 | .PP |
---|
| 80 | A hash table consists of zero or more entries, each consisting of a |
---|
| 81 | key and a value. Given the key for an entry, the hashing routines can |
---|
| 82 | very quickly locate the entry, and hence its value. There may be at |
---|
| 83 | most one entry in a hash table with a particular key, but many entries |
---|
| 84 | may have the same value. Keys can take one of four forms: strings, |
---|
| 85 | one-word values, integer arrays, or custom keys defined by a |
---|
| 86 | Tcl_HashKeyType structure (See section \fBTHE TCL_HASHKEYTYPE |
---|
| 87 | STRUCTURE\fR below). All of the keys in a given table have the same |
---|
| 88 | form, which is specified when the table is initialized. |
---|
| 89 | .PP |
---|
| 90 | The value of a hash table entry can be anything that fits in the same |
---|
| 91 | space as a |
---|
| 92 | .QW "char *" |
---|
| 93 | pointer. Values for hash table entries are |
---|
| 94 | managed entirely by clients, not by the hash module itself. Typically |
---|
| 95 | each entry's value is a pointer to a data structure managed by client |
---|
| 96 | code. |
---|
| 97 | .PP |
---|
| 98 | Hash tables grow gracefully as the number of entries increases, so |
---|
| 99 | that there are always less than three entries per hash bucket, on |
---|
| 100 | average. This allows for fast lookups regardless of the number of |
---|
| 101 | entries in a table. |
---|
| 102 | .PP |
---|
| 103 | The core provides three functions for the initialization of hash |
---|
| 104 | tables, Tcl_InitHashTable, Tcl_InitObjHashTable and |
---|
| 105 | Tcl_InitCustomHashTable. |
---|
| 106 | .PP |
---|
| 107 | \fBTcl_InitHashTable\fR initializes a structure that describes a new |
---|
| 108 | hash table. The space for the structure is provided by the caller, |
---|
| 109 | not by the hash module. The value of \fIkeyType\fR indicates what |
---|
| 110 | kinds of keys will be used for all entries in the table. All of the |
---|
| 111 | key types described later are allowed, with the exception of |
---|
| 112 | \fBTCL_CUSTOM_TYPE_KEYS\fR and \fBTCL_CUSTOM_PTR_KEYS\fR. |
---|
| 113 | .PP |
---|
| 114 | \fBTcl_InitObjHashTable\fR is a wrapper around |
---|
| 115 | \fBTcl_InitCustomHashTable\fR and initializes a hash table whose keys |
---|
| 116 | are Tcl_Obj *. |
---|
| 117 | .PP |
---|
| 118 | \fBTcl_InitCustomHashTable\fR initializes a structure that describes a |
---|
| 119 | new hash table. The space for the structure is provided by the |
---|
| 120 | caller, not by the hash module. The value of \fIkeyType\fR indicates |
---|
| 121 | what kinds of keys will be used for all entries in the table. |
---|
| 122 | \fIKeyType\fR must have one of the following values: |
---|
| 123 | .IP \fBTCL_STRING_KEYS\fR 25 |
---|
| 124 | Keys are null-terminated strings. |
---|
| 125 | They are passed to hashing routines using the address of the |
---|
| 126 | first character of the string. |
---|
| 127 | .IP \fBTCL_ONE_WORD_KEYS\fR 25 |
---|
| 128 | Keys are single-word values; they are passed to hashing routines |
---|
| 129 | and stored in hash table entries as |
---|
| 130 | .QW "char *" |
---|
| 131 | values. |
---|
| 132 | The pointer value is the key; it need not (and usually does not) |
---|
| 133 | actually point to a string. |
---|
| 134 | .IP \fBTCL_CUSTOM_TYPE_KEYS\fR 25 |
---|
| 135 | Keys are of arbitrary type, and are stored in the entry. Hashing |
---|
| 136 | and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType |
---|
| 137 | structure is described in the section |
---|
| 138 | \fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below. |
---|
| 139 | .IP \fBTCL_CUSTOM_PTR_KEYS\fR 25 |
---|
| 140 | Keys are pointers to an arbitrary type, and are stored in the entry. Hashing |
---|
| 141 | and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType |
---|
| 142 | structure is described in the section |
---|
| 143 | \fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below. |
---|
| 144 | .IP \fIother\fR 25 |
---|
| 145 | If \fIkeyType\fR is not one of the above, |
---|
| 146 | then it must be an integer value greater than 1. |
---|
| 147 | In this case the keys will be arrays of |
---|
| 148 | .QW int |
---|
| 149 | values, where |
---|
| 150 | \fIkeyType\fR gives the number of ints in each key. |
---|
| 151 | This allows structures to be used as keys. |
---|
| 152 | All keys must have the same size. |
---|
| 153 | Array keys are passed into hashing functions using the address |
---|
| 154 | of the first int in the array. |
---|
| 155 | .PP |
---|
| 156 | \fBTcl_DeleteHashTable\fR deletes all of the entries in a hash |
---|
| 157 | table and frees up the memory associated with the table's |
---|
| 158 | bucket array and entries. |
---|
| 159 | It does not free the actual table structure (pointed to |
---|
| 160 | by \fItablePtr\fR), since that memory is assumed to be managed |
---|
| 161 | by the client. |
---|
| 162 | \fBTcl_DeleteHashTable\fR also does not free or otherwise |
---|
| 163 | manipulate the values of the hash table entries. |
---|
| 164 | If the entry values point to dynamically-allocated memory, then |
---|
| 165 | it is the client's responsibility to free these structures |
---|
| 166 | before deleting the table. |
---|
| 167 | .PP |
---|
| 168 | \fBTcl_CreateHashEntry\fR locates the entry corresponding to a |
---|
| 169 | particular key, creating a new entry in the table if there |
---|
| 170 | was not already one with the given key. |
---|
| 171 | If an entry already existed with the given key then \fI*newPtr\fR |
---|
| 172 | is set to zero. |
---|
| 173 | If a new entry was created, then \fI*newPtr\fR is set to a non-zero |
---|
| 174 | value and the value of the new entry will be set to zero. |
---|
| 175 | The return value from \fBTcl_CreateHashEntry\fR is a pointer to |
---|
| 176 | the entry, which may be used to retrieve and modify the entry's |
---|
| 177 | value or to delete the entry from the table. |
---|
| 178 | .PP |
---|
| 179 | \fBTcl_DeleteHashEntry\fR will remove an existing entry from a |
---|
| 180 | table. |
---|
| 181 | The memory associated with the entry itself will be freed, but |
---|
| 182 | the client is responsible for any cleanup associated with the |
---|
| 183 | entry's value, such as freeing a structure that it points to. |
---|
| 184 | .PP |
---|
| 185 | \fBTcl_FindHashEntry\fR is similar to \fBTcl_CreateHashEntry\fR |
---|
| 186 | except that it does not create a new entry if the key doesn't exist; |
---|
| 187 | instead, it returns NULL as result. |
---|
| 188 | .PP |
---|
| 189 | \fBTcl_GetHashValue\fR and \fBTcl_SetHashValue\fR are used to |
---|
| 190 | read and write an entry's value, respectively. |
---|
| 191 | Values are stored and retrieved as type |
---|
| 192 | .QW ClientData , |
---|
| 193 | which is |
---|
| 194 | large enough to hold a pointer value. On almost all machines this is |
---|
| 195 | large enough to hold an integer value too. |
---|
| 196 | .PP |
---|
| 197 | \fBTcl_GetHashKey\fR returns the key for a given hash table entry, |
---|
| 198 | either as a pointer to a string, a one-word |
---|
| 199 | .PQ "char *" |
---|
| 200 | key, or |
---|
| 201 | as a pointer to the first word of an array of integers, depending |
---|
| 202 | on the \fIkeyType\fR used to create a hash table. |
---|
| 203 | In all cases \fBTcl_GetHashKey\fR returns a result with type |
---|
| 204 | .QW "char *" . |
---|
| 205 | When the key is a string or array, the result of \fBTcl_GetHashKey\fR |
---|
| 206 | points to information in the table entry; this information will |
---|
| 207 | remain valid until the entry is deleted or its table is deleted. |
---|
| 208 | .PP |
---|
| 209 | \fBTcl_FirstHashEntry\fR and \fBTcl_NextHashEntry\fR may be used |
---|
| 210 | to scan all of the entries in a hash table. |
---|
| 211 | A structure of type |
---|
| 212 | .QW Tcl_HashSearch , |
---|
| 213 | provided by the client, |
---|
| 214 | is used to keep track of progress through the table. |
---|
| 215 | \fBTcl_FirstHashEntry\fR initializes the search record and |
---|
| 216 | returns the first entry in the table (or NULL if the table is |
---|
| 217 | empty). |
---|
| 218 | Each subsequent call to \fBTcl_NextHashEntry\fR returns the |
---|
| 219 | next entry in the table or |
---|
| 220 | NULL if the end of the table has been reached. |
---|
| 221 | A call to \fBTcl_FirstHashEntry\fR followed by calls to |
---|
| 222 | \fBTcl_NextHashEntry\fR will return each of the entries in |
---|
| 223 | the table exactly once, in an arbitrary order. |
---|
| 224 | It is unadvisable to modify the structure of the table, e.g. |
---|
| 225 | by creating or deleting entries, while the search is in progress, |
---|
| 226 | with the exception of deleting the entry returned by |
---|
| 227 | \fBTcl_FirstHashEntry\fR or \fBTcl_NextHashEntry\fR. |
---|
| 228 | .PP |
---|
| 229 | \fBTcl_HashStats\fR returns a dynamically-allocated string with |
---|
| 230 | overall information about a hash table, such as the number of |
---|
| 231 | entries it contains, the number of buckets in its hash array, |
---|
| 232 | and the utilization of the buckets. |
---|
| 233 | It is the caller's responsibility to free the result string |
---|
| 234 | by passing it to \fBckfree\fR. |
---|
| 235 | .PP |
---|
| 236 | The header file \fBtcl.h\fR defines the actual data structures |
---|
| 237 | used to implement hash tables. |
---|
| 238 | This is necessary so that clients can allocate Tcl_HashTable |
---|
| 239 | structures and so that macros can be used to read and write |
---|
| 240 | the values of entries. |
---|
| 241 | However, users of the hashing routines should never refer directly |
---|
| 242 | to any of the fields of any of the hash-related data structures; |
---|
| 243 | use the procedures and macros defined here. |
---|
| 244 | .SH "THE TCL_HASHKEYTYPE STRUCTURE" |
---|
| 245 | .PP |
---|
| 246 | Extension writers can define new hash key types by defining four procedures, |
---|
| 247 | initializing a \fBTcl_HashKeyType\fR structure to describe the type, and |
---|
| 248 | calling \fBTcl_InitCustomHashTable\fR. The \fBTcl_HashKeyType\fR structure is |
---|
| 249 | defined as follows: |
---|
| 250 | .CS |
---|
| 251 | typedef struct Tcl_HashKeyType { |
---|
| 252 | int \fIversion\fR; |
---|
| 253 | int \fIflags\fR; |
---|
| 254 | Tcl_HashKeyProc *\fIhashKeyProc\fR; |
---|
| 255 | Tcl_CompareHashKeysProc *\fIcompareKeysProc\fR; |
---|
| 256 | Tcl_AllocHashEntryProc *\fIallocEntryProc\fR; |
---|
| 257 | Tcl_FreeHashEntryProc *\fIfreeEntryProc\fR; |
---|
| 258 | } Tcl_HashKeyType; |
---|
| 259 | .CE |
---|
| 260 | .PP |
---|
| 261 | The \fIversion\fR member is the version of the table. If this structure is |
---|
| 262 | extended in future then the version can be used to distinguish between |
---|
| 263 | different structures. It should be set to \fBTCL_HASH_KEY_TYPE_VERSION\fR. |
---|
| 264 | .PP |
---|
| 265 | The \fIflags\fR member is 0 or one or more of the following values OR'ed |
---|
| 266 | together: |
---|
| 267 | .IP \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR 25 |
---|
| 268 | There are some things, pointers for example which do not hash well because |
---|
| 269 | they do not use the lower bits. If this flag is set then the hash table will |
---|
| 270 | attempt to rectify this by randomizing the bits and then using the upper N |
---|
| 271 | bits as the index into the table. |
---|
| 272 | .IP \fBTCL_HASH_KEY_SYSTEM_HASH\fR 25 |
---|
| 273 | .VS 8.5 |
---|
| 274 | This flag forces Tcl to use the memory allocation procedures provided by the |
---|
| 275 | operating system when allocating and freeing memory used to store the hash |
---|
| 276 | table data structures, and not any of Tcl's own customized memory allocation |
---|
| 277 | routines. This is important if the hash table is to be used in the |
---|
| 278 | implementation of a custom set of allocation routines, or something that a |
---|
| 279 | custom set of allocation routines might depend on, in order to avoid any |
---|
| 280 | circular dependency. |
---|
| 281 | .VE 8.5 |
---|
| 282 | .PP |
---|
| 283 | The \fIhashKeyProc\fR member contains the address of a function called to |
---|
| 284 | calculate a hash value for the key. |
---|
| 285 | .CS |
---|
| 286 | typedef unsigned int (Tcl_HashKeyProc) ( |
---|
| 287 | Tcl_HashTable *\fItablePtr\fR, |
---|
| 288 | void *\fIkeyPtr\fR); |
---|
| 289 | .CE |
---|
| 290 | If this is NULL then \fIkeyPtr\fR is used and |
---|
| 291 | \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR is assumed. |
---|
| 292 | .PP |
---|
| 293 | The \fIcompareKeysProc\fR member contains the address of a function called to |
---|
| 294 | compare two keys. |
---|
| 295 | .CS |
---|
| 296 | typedef int (Tcl_CompareHashKeysProc) ( |
---|
| 297 | void *\fIkeyPtr\fR, |
---|
| 298 | Tcl_HashEntry *\fIhPtr\fR); |
---|
| 299 | .CE |
---|
| 300 | If this is NULL then the \fIkeyPtr\fR pointers are compared. If the keys do |
---|
| 301 | not match then the function returns 0, otherwise it returns 1. |
---|
| 302 | .PP |
---|
| 303 | The \fIallocEntryProc\fR member contains the address of a function called to |
---|
| 304 | allocate space for an entry and initialize the key and clientData. |
---|
| 305 | .CS |
---|
| 306 | typedef Tcl_HashEntry *(Tcl_AllocHashEntryProc) ( |
---|
| 307 | Tcl_HashTable *\fItablePtr\fR, |
---|
| 308 | void *\fIkeyPtr\fR); |
---|
| 309 | .CE |
---|
| 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 to |
---|
| 313 | allocate enough space for the entry and the key in one block, rather than |
---|
| 314 | doing it in two blocks. This saves space for a pointer to the key from the |
---|
| 315 | entry and another memory allocation. Tcl_Obj* keys use this function to |
---|
| 316 | allocate enough space for an entry and increment the reference count on the |
---|
| 317 | object. |
---|
| 318 | .PP |
---|
| 319 | The \fIfreeEntryProc\fR member contains the address of a function called to |
---|
| 320 | free space for an entry. |
---|
| 321 | .CS |
---|
| 322 | typedef void (Tcl_FreeHashEntryProc) (Tcl_HashEntry *\fIhPtr\fR); |
---|
| 323 | .CE |
---|
| 324 | If this is NULL then Tcl_Free is used to free the space for the entry. |
---|
| 325 | Tcl_Obj* keys use this function to decrement the reference count on the |
---|
| 326 | object. |
---|
| 327 | .SH KEYWORDS |
---|
| 328 | hash table, key, lookup, search, value |
---|