2 '\" Copyright (c) 1989-1993 The Regents of the University of California.
3 '\" Copyright (c) 1994-1996 Sun Microsystems, Inc.
5 '\" See the file "license.terms" for information on usage and redistribution
6 '\" of this file, and for a DISCLAIMER OF ALL WARRANTIES.
8 '\" RCS: @(#) $Id: Hash.3,v 1.3 1999/12/21 23:57:33 hobbs Exp $
10 '\" The definitions below are for supplemental macros used in Tcl/Tk
13 '\" .AP type name in/out ?indent?
14 '\" Start paragraph describing an argument to a library procedure.
15 '\" type is type of argument (int, etc.), in/out is either "in", "out",
16 '\" or "in/out" to describe whether procedure reads or modifies arg,
17 '\" and indent is equivalent to second arg of .IP (shouldn't ever be
18 '\" needed; use .AS below instead)
21 '\" Give maximum sizes of arguments for setting tab stops. Type and
22 '\" name are examples of largest possible arguments that will be passed
23 '\" to .AP later. If args are omitted, default tab stops are used.
26 '\" Start box enclosure. From here until next .BE, everything will be
27 '\" enclosed in one large box.
30 '\" End of box enclosure.
33 '\" Begin code excerpt.
38 '\" .VS ?version? ?br?
39 '\" Begin vertical sidebar, for use in marking newly-changed parts
40 '\" of man pages. The first argument is ignored and used for recording
41 '\" the version when the .VS was added, so that the sidebars can be
42 '\" found and removed when they reach a certain age. If another argument
43 '\" is present, then a line break is forced before starting the sidebar.
46 '\" End of vertical sidebar.
49 '\" Begin an indented unfilled display.
52 '\" End of indented unfilled display.
55 '\" Start of list of standard options for a Tk widget. The
56 '\" options follow on successive lines, in four columns separated
60 '\" End of list of standard options for a Tk widget.
62 '\" .OP cmdName dbName dbClass
63 '\" Start of description of a specific option. cmdName gives the
64 '\" option's name as specified in the class command, dbName gives
65 '\" the option's name in the option database, and dbClass gives
66 '\" the option's class in the option database.
69 '\" Print arg1 underlined, then print arg2 normally.
71 '\" RCS: @(#) $Id: man.macros,v 1.3 1999/04/16 00:46:35 stanton Exp $
73 '\" # Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
77 '\" # Start an argument description
81 . ie !"\\$2"" .TP \\n()Cu
86 \&\\$1 \\fI\\$2\\fP (\\$3)
99 '\" # define tabbing values for .AP
102 .if !"\\$1"" .nr )A \\w'\\$1'u+3n
105 .if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
106 .nr )C \\n()Bu+\\w'(in/out)'u+2n
108 .AS Tcl_Interp Tcl_CreateInterp in/out
109 '\" # BS - start boxed text
110 '\" # ^y = starting y location
118 .if n \l'\\n(.lu\(ul'
121 '\" # BE - end boxed text (draw box now)
126 .ie n \l'\\n(^lu\(ul'
128 .\" Draw four-sided box normally, but don't draw top of
129 .\" box if the box started on an earlier page.
131 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
134 \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
141 '\" # VS - start vertical sidebar
142 '\" # ^Y = starting y location
143 '\" # ^v = 1 (for troff; for nroff this doesn't matter)
147 .ie n 'mc \s12\(br\s0
150 '\" # VE - end of vertical sidebar
158 \h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
165 '\" # Special macro to handle page bottom: finish off current
166 '\" # box/sidebar if in box/sidebar mode, then invoked standard
167 '\" # page bottom macro.
174 .\" Draw three-sided box if this is the box's first page,
175 .\" draw two sides but no top otherwise.
176 .ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
177 .el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
180 .nr ^x \\n(^tu+1v-\\n(^Yu
181 \kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
194 '\" # DS - begin display
200 '\" # DE - end display
206 '\" # SO - start of list of standard options
208 .SH "STANDARD OPTIONS"
214 '\" # SE - end of list of standard options
219 See the \\fBoptions\\fR manual entry for details on the standard options.
221 '\" # OP - start of full description for a single option
226 Command-Line Name: \\fB\\$1\\fR
227 Database Name: \\fB\\$2\\fR
228 Database Class: \\fB\\$3\\fR
232 '\" # CS - begin code excerpt
238 '\" # CE - end code excerpt
246 .TH Tcl_Hash 3 "" Tcl "Tcl Library Procedures"
249 Tcl_InitHashTable, 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
252 \fB#include <tcl.h>\fR
254 \fBTcl_InitHashTable\fR(\fItablePtr, keyType\fR)
256 \fBTcl_DeleteHashTable\fR(\fItablePtr\fR)
259 \fBTcl_CreateHashEntry\fR(\fItablePtr, key, newPtr\fR)
261 \fBTcl_DeleteHashEntry\fR(\fIentryPtr\fR)
264 \fBTcl_FindHashEntry\fR(\fItablePtr, key\fR)
267 \fBTcl_GetHashValue\fR(\fIentryPtr\fR)
269 \fBTcl_SetHashValue\fR(\fIentryPtr, value\fR)
272 \fBTcl_GetHashKey\fR(\fItablePtr, entryPtr\fR)
275 \fBTcl_FirstHashEntry\fR(\fItablePtr, searchPtr\fR)
278 \fBTcl_NextHashEntry\fR(\fIsearchPtr\fR)
281 \fBTcl_HashStats\fR(\fItablePtr\fR)
283 .AS Tcl_HashSearch *searchPtr
284 .AP Tcl_HashTable *tablePtr in
285 Address of hash table structure (for all procedures but
286 \fBTcl_InitHashTable\fR, this must have been initialized by
287 previous call to \fBTcl_InitHashTable\fR).
289 Kind of keys to use for new hash table. Must be either
290 TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, or an integer value
293 Key to use for probe into table. Exact form depends on
294 \fIkeyType\fR used to create table.
296 The word at \fI*newPtr\fR is set to 1 if a new entry was created
297 and 0 if there was already an entry for \fIkey\fR.
298 .AP Tcl_HashEntry *entryPtr in
299 Pointer to hash table entry.
300 .AP ClientData value in
301 New value to assign to hash table entry. Need not have type
302 ClientData, but must fit in same space as ClientData.
303 .AP Tcl_HashSearch *searchPtr in
304 Pointer to record to use to keep track of progress in enumerating
305 all the entries in a hash table.
310 A hash table consists of zero or more entries, each consisting of
312 Given the key for an entry, the hashing routines can very quickly
313 locate the entry, and hence its value.
314 There may be at most one entry in a hash table with a
315 particular key, but many entries may have the same value.
316 Keys can take one of three forms: strings,
317 one-word values, or integer arrays.
318 All of the keys in a given table have the same form, which is
319 specified when the table is initialized.
321 The value of a hash table entry can be anything that fits in
322 the same space as a ``char *'' pointer.
323 Values for hash table entries are managed entirely by clients,
324 not by the hash module itself.
325 Typically each entry's value is a pointer to a data structure
326 managed by client code.
328 Hash tables grow gracefully as the number of entries increases,
329 so that there are always less than three entries per hash bucket,
331 This allows for fast lookups regardless of the number of entries
334 \fBTcl_InitHashTable\fR initializes a structure that describes
336 The space for the structure is provided by the caller, not by
338 The value of \fIkeyType\fR indicates what kinds of keys will
339 be used for all entries in the table. \fIKeyType\fR must have
340 one of the following values:
341 .IP \fBTCL_STRING_KEYS\fR 25
342 Keys are null-terminated ASCII strings.
343 They are passed to hashing routines using the address of the
344 first character of the string.
345 .IP \fBTCL_ONE_WORD_KEYS\fR 25
346 Keys are single-word values; they are passed to hashing routines
347 and stored in hash table entries as ``char *'' values.
348 The pointer value is the key; it need not (and usually doesn't)
349 actually point to a string.
351 If \fIkeyType\fR is not TCL_STRING_KEYS or TCL_ONE_WORD_KEYS,
352 then it must be an integer value greater than 1.
353 In this case the keys will be arrays of ``int'' values, where
354 \fIkeyType\fR gives the number of ints in each key.
355 This allows structures to be used as keys.
356 All keys must have the same size.
357 Array keys are passed into hashing functions using the address
358 of the first int in the array.
360 \fBTcl_DeleteHashTable\fR deletes all of the entries in a hash
361 table and frees up the memory associated with the table's
362 bucket array and entries.
363 It does not free the actual table structure (pointed to
364 by \fItablePtr\fR), since that memory is assumed to be managed
366 \fBTcl_DeleteHashTable\fR also does not free or otherwise
367 manipulate the values of the hash table entries.
368 If the entry values point to dynamically-allocated memory, then
369 it is the client's responsibility to free these structures
370 before deleting the table.
372 \fBTcl_CreateHashEntry\fR locates the entry corresponding to a
373 particular key, creating a new entry in the table if there
374 wasn't already one with the given key.
375 If an entry already existed with the given key then \fI*newPtr\fR
377 If a new entry was created, then \fI*newPtr\fR is set to a non-zero
378 value and the value of the new entry will be set to zero.
379 The return value from \fBTcl_CreateHashEntry\fR is a pointer to
380 the entry, which may be used to retrieve and modify the entry's
381 value or to delete the entry from the table.
383 \fBTcl_DeleteHashEntry\fR will remove an existing entry from a
385 The memory associated with the entry itself will be freed, but
386 the client is responsible for any cleanup associated with the
387 entry's value, such as freeing a structure that it points to.
389 \fBTcl_FindHashEntry\fR is similar to \fBTcl_CreateHashEntry\fR
390 except that it doesn't create a new entry if the key doesn't exist;
391 instead, it returns NULL as result.
393 \fBTcl_GetHashValue\fR and \fBTcl_SetHashValue\fR are used to
394 read and write an entry's value, respectively.
395 Values are stored and retrieved as type ``ClientData'', which is
396 large enough to hold a pointer value. On almost all machines this is
397 large enough to hold an integer value too.
399 \fBTcl_GetHashKey\fR returns the key for a given hash table entry,
400 either as a pointer to a string, a one-word (``char *'') key, or
401 as a pointer to the first word of an array of integers, depending
402 on the \fIkeyType\fR used to create a hash table.
403 In all cases \fBTcl_GetHashKey\fR returns a result with type
405 When the key is a string or array, the result of \fBTcl_GetHashKey\fR
406 points to information in the table entry; this information will
407 remain valid until the entry is deleted or its table is deleted.
409 \fBTcl_FirstHashEntry\fR and \fBTcl_NextHashEntry\fR may be used
410 to scan all of the entries in a hash table.
411 A structure of type ``Tcl_HashSearch'', provided by the client,
412 is used to keep track of progress through the table.
413 \fBTcl_FirstHashEntry\fR initializes the search record and
414 returns the first entry in the table (or NULL if the table is
416 Each subsequent call to \fBTcl_NextHashEntry\fR returns the
417 next entry in the table or
418 NULL if the end of the table has been reached.
419 A call to \fBTcl_FirstHashEntry\fR followed by calls to
420 \fBTcl_NextHashEntry\fR will return each of the entries in
421 the table exactly once, in an arbitrary order.
422 It is unadvisable to modify the structure of the table, e.g.
423 by creating or deleting entries, while the search is in
426 \fBTcl_HashStats\fR returns a dynamically-allocated string with
427 overall information about a hash table, such as the number of
428 entries it contains, the number of buckets in its hash array,
429 and the utilization of the buckets.
430 It is the caller's responsibility to free the result string
431 by passing it to \fBckfree\fR.
433 The header file \fBtcl.h\fR defines the actual data structures
434 used to implement hash tables.
435 This is necessary so that clients can allocate Tcl_HashTable
436 structures and so that macros can be used to read and write
437 the values of entries.
438 However, users of the hashing routines should never refer directly
439 to any of the fields of any of the hash-related data structures;
440 use the procedures and macros defined here.
443 hash table, key, lookup, search, value