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 .TH Tcl_Hash 3 "" Tcl "Tcl Library Procedures"
9 .\" The -*- nroff -*- definitions below are for supplemental macros used
10 .\" in Tcl/Tk manual entries.
12 .\" .AP type name in/out ?indent?
13 .\" Start paragraph describing an argument to a library procedure.
14 .\" type is type of argument (int, etc.), in/out is either "in", "out",
15 .\" or "in/out" to describe whether procedure reads or modifies arg,
16 .\" and indent is equivalent to second arg of .IP (shouldn't ever be
17 .\" needed; use .AS below instead)
20 .\" Give maximum sizes of arguments for setting tab stops. Type and
21 .\" name are examples of largest possible arguments that will be passed
22 .\" to .AP later. If args are omitted, default tab stops are used.
25 .\" Start box enclosure. From here until next .BE, everything will be
26 .\" enclosed in one large box.
29 .\" End of box enclosure.
32 .\" Begin code excerpt.
37 .\" .VS ?version? ?br?
38 .\" Begin vertical sidebar, for use in marking newly-changed parts
39 .\" of man pages. The first argument is ignored and used for recording
40 .\" the version when the .VS was added, so that the sidebars can be
41 .\" found and removed when they reach a certain age. If another argument
42 .\" is present, then a line break is forced before starting the sidebar.
45 .\" End of vertical sidebar.
48 .\" Begin an indented unfilled display.
51 .\" End of indented unfilled display.
54 .\" Start of list of standard options for a Tk widget. The manpage
55 .\" argument defines where to look up the standard options; if
56 .\" omitted, defaults to "options". The options follow on successive
57 .\" lines, in three columns separated by tabs.
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.
72 .\" Print arg1 in quotes, then arg2 normally (for trailing punctuation).
75 .\" Print an open parenthesis, arg1 in quotes, then arg2 normally
76 .\" (for trailing punctuation) and then a closing parenthesis.
78 .\" # Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
82 .\" # Start an argument description
86 . ie !"\\$2"" .TP \\n()Cu
91 \&\\$1 \\fI\\$2\\fP (\\$3)
104 .\" # define tabbing values for .AP
107 .if !"\\$1"" .nr )A \\w'\\$1'u+3n
110 .if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
111 .nr )C \\n()Bu+\\w'(in/out)'u+2n
113 .AS Tcl_Interp Tcl_CreateInterp in/out
114 .\" # BS - start boxed text
115 .\" # ^y = starting y location
123 .if n \l'\\n(.lu\(ul'
126 .\" # BE - end boxed text (draw box now)
131 .ie n \l'\\n(^lu\(ul'
133 .\" Draw four-sided box normally, but don't draw top of
134 .\" box if the box started on an earlier page.
136 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
139 \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
146 .\" # VS - start vertical sidebar
147 .\" # ^Y = starting y location
148 .\" # ^v = 1 (for troff; for nroff this doesn't matter)
152 .ie n 'mc \s12\(br\s0
155 .\" # VE - end of vertical sidebar
163 \h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
170 .\" # Special macro to handle page bottom: finish off current
171 .\" # box/sidebar if in box/sidebar mode, then invoked standard
172 .\" # page bottom macro.
179 .\" Draw three-sided box if this is the box's first page,
180 .\" draw two sides but no top otherwise.
181 .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
182 .el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
185 .nr ^x \\n(^tu+1v-\\n(^Yu
186 \kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
199 .\" # DS - begin display
205 .\" # DE - end display
211 .\" # SO - start of list of standard options
213 'ie '\\$1'' .ds So \\fBoptions\\fR
214 'el .ds So \\fB\\$1\\fR
215 .SH "STANDARD OPTIONS"
221 .\" # SE - end of list of standard options
226 See the \\*(So manual entry for details on the standard options.
228 .\" # OP - start of full description for a single option
233 Command-Line Name: \\fB\\$1\\fR
234 Database Name: \\fB\\$2\\fR
235 Database Class: \\fB\\$3\\fR
239 .\" # CS - begin code excerpt
245 .\" # CE - end code excerpt
250 .\" # UL - underline word
254 .\" # QW - apply quotation marks to word
256 .ie '\\*(lq'"' ``\\$1''\\$2
257 .\"" fix emacs highlighting
258 .el \\*(lq\\$1\\*(rq\\$2
260 .\" # PQ - apply parens and quotation marks to word
262 .ie '\\*(lq'"' (``\\$1''\\$2)\\$3
263 .\"" fix emacs highlighting
264 .el (\\*(lq\\$1\\*(rq\\$2)\\$3
266 .\" # QR - quoted range
268 .ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
269 .\"" fix emacs highlighting
270 .el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
272 .\" # MT - "empty" string
278 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
281 \fB#include <tcl.h>\fR
283 \fBTcl_InitHashTable\fR(\fItablePtr, keyType\fR)
285 \fBTcl_InitCustomHashTable\fR(\fItablePtr, keyType, typePtr\fR)
287 \fBTcl_InitObjHashTable\fR(\fItablePtr\fR)
289 \fBTcl_DeleteHashTable\fR(\fItablePtr\fR)
292 \fBTcl_CreateHashEntry\fR(\fItablePtr, key, newPtr\fR)
294 \fBTcl_DeleteHashEntry\fR(\fIentryPtr\fR)
297 \fBTcl_FindHashEntry\fR(\fItablePtr, key\fR)
300 \fBTcl_GetHashValue\fR(\fIentryPtr\fR)
302 \fBTcl_SetHashValue\fR(\fIentryPtr, value\fR)
305 \fBTcl_GetHashKey\fR(\fItablePtr, entryPtr\fR)
308 \fBTcl_FirstHashEntry\fR(\fItablePtr, searchPtr\fR)
311 \fBTcl_NextHashEntry\fR(\fIsearchPtr\fR)
314 \fBTcl_HashStats\fR(\fItablePtr\fR)
316 .AS "const Tcl_HashKeyType" *searchPtr out
317 .AP Tcl_HashTable *tablePtr in
318 Address of hash table structure (for all procedures but
319 \fBTcl_InitHashTable\fR, this must have been initialized by
320 previous call to \fBTcl_InitHashTable\fR).
322 Kind of keys to use for new hash table. Must be either
323 \fBTCL_STRING_KEYS\fR, \fBTCL_ONE_WORD_KEYS\fR, \fBTCL_CUSTOM_TYPE_KEYS\fR,
324 \fBTCL_CUSTOM_PTR_KEYS\fR, or an integer value greater than 1.
325 .AP Tcl_HashKeyType *typePtr in
326 Address of structure which defines the behavior of the hash table.
327 .AP "const void" *key in
328 Key to use for probe into table. Exact form depends on
329 \fIkeyType\fR used to create table.
331 The word at \fI*newPtr\fR is set to 1 if a new entry was created
332 and 0 if there was already an entry for \fIkey\fR.
333 .AP Tcl_HashEntry *entryPtr in
334 Pointer to hash table entry.
335 .AP ClientData value in
336 New value to assign to hash table entry. Need not have type
337 ClientData, but must fit in same space as ClientData.
338 .AP Tcl_HashSearch *searchPtr in
339 Pointer to record to use to keep track of progress in enumerating
340 all the entries in a hash table.
344 A hash table consists of zero or more entries, each consisting of a
345 key and a value. Given the key for an entry, the hashing routines can
346 very quickly locate the entry, and hence its value. There may be at
347 most one entry in a hash table with a particular key, but many entries
348 may have the same value. Keys can take one of four forms: strings,
349 one-word values, integer arrays, or custom keys defined by a
350 Tcl_HashKeyType structure (See section \fBTHE TCL_HASHKEYTYPE STRUCTURE\fR
351 below). All of the keys in a given table have the same
352 form, which is specified when the table is initialized.
354 The value of a hash table entry can be anything that fits in the same
357 pointer. Values for hash table entries are
358 managed entirely by clients, not by the hash module itself. Typically
359 each entry's value is a pointer to a data structure managed by client
362 Hash tables grow gracefully as the number of entries increases, so
363 that there are always less than three entries per hash bucket, on
364 average. This allows for fast lookups regardless of the number of
367 The core provides three functions for the initialization of hash
368 tables, Tcl_InitHashTable, Tcl_InitObjHashTable and
369 Tcl_InitCustomHashTable.
371 \fBTcl_InitHashTable\fR initializes a structure that describes a new
372 hash table. The space for the structure is provided by the caller,
373 not by the hash module. The value of \fIkeyType\fR indicates what
374 kinds of keys will be used for all entries in the table. All of the
375 key types described later are allowed, with the exception of
376 \fBTCL_CUSTOM_TYPE_KEYS\fR and \fBTCL_CUSTOM_PTR_KEYS\fR.
378 \fBTcl_InitObjHashTable\fR is a wrapper around
379 \fBTcl_InitCustomHashTable\fR and initializes a hash table whose keys
382 \fBTcl_InitCustomHashTable\fR initializes a structure that describes a
383 new hash table. The space for the structure is provided by the
384 caller, not by the hash module. The value of \fIkeyType\fR indicates
385 what kinds of keys will be used for all entries in the table.
386 \fIKeyType\fR must have one of the following values:
387 .IP \fBTCL_STRING_KEYS\fR 25
388 Keys are null-terminated strings.
389 They are passed to hashing routines using the address of the
390 first character of the string.
391 .IP \fBTCL_ONE_WORD_KEYS\fR 25
392 Keys are single-word values; they are passed to hashing routines
393 and stored in hash table entries as
396 The pointer value is the key; it need not (and usually does not)
397 actually point to a string.
398 .IP \fBTCL_CUSTOM_TYPE_KEYS\fR 25
399 Keys are of arbitrary type, and are stored in the entry. Hashing
400 and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType
401 structure is described in the section
402 \fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below.
403 .IP \fBTCL_CUSTOM_PTR_KEYS\fR 25
404 Keys are pointers to an arbitrary type, and are stored in the entry. Hashing
405 and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType
406 structure is described in the section
407 \fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below.
409 If \fIkeyType\fR is not one of the above,
410 then it must be an integer value greater than 1.
411 In this case the keys will be arrays of
414 \fIkeyType\fR gives the number of ints in each key.
415 This allows structures to be used as keys.
416 All keys must have the same size.
417 Array keys are passed into hashing functions using the address
418 of the first int in the array.
420 \fBTcl_DeleteHashTable\fR deletes all of the entries in a hash
421 table and frees up the memory associated with the table's
422 bucket array and entries.
423 It does not free the actual table structure (pointed to
424 by \fItablePtr\fR), since that memory is assumed to be managed
426 \fBTcl_DeleteHashTable\fR also does not free or otherwise
427 manipulate the values of the hash table entries.
428 If the entry values point to dynamically-allocated memory, then
429 it is the client's responsibility to free these structures
430 before deleting the table.
432 \fBTcl_CreateHashEntry\fR locates the entry corresponding to a
433 particular key, creating a new entry in the table if there
434 was not already one with the given key.
435 If an entry already existed with the given key then \fI*newPtr\fR
437 If a new entry was created, then \fI*newPtr\fR is set to a non-zero
438 value and the value of the new entry will be set to zero.
439 The return value from \fBTcl_CreateHashEntry\fR is a pointer to
440 the entry, which may be used to retrieve and modify the entry's
441 value or to delete the entry from the table.
443 \fBTcl_DeleteHashEntry\fR will remove an existing entry from a
445 The memory associated with the entry itself will be freed, but
446 the client is responsible for any cleanup associated with the
447 entry's value, such as freeing a structure that it points to.
449 \fBTcl_FindHashEntry\fR is similar to \fBTcl_CreateHashEntry\fR
450 except that it does not create a new entry if the key doesn't exist;
451 instead, it returns NULL as result.
453 \fBTcl_GetHashValue\fR and \fBTcl_SetHashValue\fR are used to
454 read and write an entry's value, respectively.
455 Values are stored and retrieved as type
458 large enough to hold a pointer value. On almost all machines this is
459 large enough to hold an integer value too.
461 \fBTcl_GetHashKey\fR returns the key for a given hash table entry,
462 either as a pointer to a string, a one-word
465 as a pointer to the first word of an array of integers, depending
466 on the \fIkeyType\fR used to create a hash table.
467 In all cases \fBTcl_GetHashKey\fR returns a result with type
469 When the key is a string or array, the result of \fBTcl_GetHashKey\fR
470 points to information in the table entry; this information will
471 remain valid until the entry is deleted or its table is deleted.
473 \fBTcl_FirstHashEntry\fR and \fBTcl_NextHashEntry\fR may be used
474 to scan all of the entries in a hash table.
477 provided by the client,
478 is used to keep track of progress through the table.
479 \fBTcl_FirstHashEntry\fR initializes the search record and
480 returns the first entry in the table (or NULL if the table is
482 Each subsequent call to \fBTcl_NextHashEntry\fR returns the
483 next entry in the table or
484 NULL if the end of the table has been reached.
485 A call to \fBTcl_FirstHashEntry\fR followed by calls to
486 \fBTcl_NextHashEntry\fR will return each of the entries in
487 the table exactly once, in an arbitrary order.
488 It is inadvisable to modify the structure of the table, e.g.
489 by creating or deleting entries, while the search is in progress,
490 with the exception of deleting the entry returned by
491 \fBTcl_FirstHashEntry\fR or \fBTcl_NextHashEntry\fR.
493 \fBTcl_HashStats\fR returns a dynamically-allocated string with
494 overall information about a hash table, such as the number of
495 entries it contains, the number of buckets in its hash array,
496 and the utilization of the buckets.
497 It is the caller's responsibility to free the result string
498 by passing it to \fBckfree\fR.
500 The header file \fBtcl.h\fR defines the actual data structures
501 used to implement hash tables.
502 This is necessary so that clients can allocate Tcl_HashTable
503 structures and so that macros can be used to read and write
504 the values of entries.
505 However, users of the hashing routines should never refer directly
506 to any of the fields of any of the hash-related data structures;
507 use the procedures and macros defined here.
508 .SH "THE TCL_HASHKEYTYPE STRUCTURE"
510 Extension writers can define new hash key types by defining four procedures,
511 initializing a \fBTcl_HashKeyType\fR structure to describe the type, and
512 calling \fBTcl_InitCustomHashTable\fR. The \fBTcl_HashKeyType\fR structure is
516 typedef struct Tcl_HashKeyType {
519 Tcl_HashKeyProc *\fIhashKeyProc\fR;
520 Tcl_CompareHashKeysProc *\fIcompareKeysProc\fR;
521 Tcl_AllocHashEntryProc *\fIallocEntryProc\fR;
522 Tcl_FreeHashEntryProc *\fIfreeEntryProc\fR;
523 } \fBTcl_HashKeyType\fR;
526 The \fIversion\fR member is the version of the table. If this structure is
527 extended in future then the version can be used to distinguish between
528 different structures. It should be set to \fBTCL_HASH_KEY_TYPE_VERSION\fR.
530 The \fIflags\fR member is 0 or one or more of the following values OR'ed
532 .IP \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR 25
533 There are some things, pointers for example which do not hash well because
534 they do not use the lower bits. If this flag is set then the hash table will
535 attempt to rectify this by randomizing the bits and then using the upper N
536 bits as the index into the table.
537 .IP \fBTCL_HASH_KEY_SYSTEM_HASH\fR 25
538 This flag forces Tcl to use the memory allocation procedures provided by the
539 operating system when allocating and freeing memory used to store the hash
540 table data structures, and not any of Tcl's own customized memory allocation
541 routines. This is important if the hash table is to be used in the
542 implementation of a custom set of allocation routines, or something that a
543 custom set of allocation routines might depend on, in order to avoid any
546 The \fIhashKeyProc\fR member contains the address of a function called to
547 calculate a hash value for the key.
550 typedef unsigned int \fBTcl_HashKeyProc\fR(
551 Tcl_HashTable *\fItablePtr\fR,
555 If this is NULL then \fIkeyPtr\fR is used and
556 \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR is assumed.
558 The \fIcompareKeysProc\fR member contains the address of a function called to
562 typedef int \fBTcl_CompareHashKeysProc\fR(
564 Tcl_HashEntry *\fIhPtr\fR);
567 If this is NULL then the \fIkeyPtr\fR pointers are compared. If the keys do
568 not match then the function returns 0, otherwise it returns 1.
570 The \fIallocEntryProc\fR member contains the address of a function called to
571 allocate space for an entry and initialize the key and clientData.
574 typedef Tcl_HashEntry *\fBTcl_AllocHashEntryProc\fR(
575 Tcl_HashTable *\fItablePtr\fR,
579 If this is NULL then \fBTcl_Alloc\fR is used to allocate enough space for a
580 Tcl_HashEntry, the key pointer is assigned to key.oneWordValue and the
581 clientData is set to NULL. String keys and array keys use this function to
582 allocate enough space for the entry and the key in one block, rather than
583 doing it in two blocks. This saves space for a pointer to the key from the
584 entry and another memory allocation. Tcl_Obj* keys use this function to
585 allocate enough space for an entry and increment the reference count on the
588 The \fIfreeEntryProc\fR member contains the address of a function called to
589 free space for an entry.
592 typedef void \fBTcl_FreeHashEntryProc\fR(
593 Tcl_HashEntry *\fIhPtr\fR);
596 If this is NULL then \fBTcl_Free\fR is used to free the space for the entry.
597 Tcl_Obj* keys use this function to decrement the reference count on the
600 hash table, key, lookup, search, value
OSDN Git Service
