diff options
Diffstat (limited to 'doc/Hash.3')
| -rw-r--r-- | doc/Hash.3 | 143 |
1 files changed, 83 insertions, 60 deletions
@@ -5,7 +5,7 @@ '\" See the file "license.terms" for information on usage and redistribution '\" of this file, and for a DISCLAIMER OF ALL WARRANTIES. '\" -'\" RCS: @(#) $Id: Hash.3,v 1.10.2.1 2003/07/18 16:56:24 dgp Exp $ +'\" RCS: @(#) $Id: Hash.3,v 1.26.2.2 2009/11/27 14:53:54 dkf Exp $ '\" .so man.macros .TH Tcl_Hash 3 "" Tcl "Tcl Library Procedures" @@ -46,21 +46,21 @@ Tcl_HashEntry * Tcl_HashEntry * \fBTcl_NextHashEntry\fR(\fIsearchPtr\fR) .sp -CONST char * +char * \fBTcl_HashStats\fR(\fItablePtr\fR) .SH ARGUMENTS -.AS Tcl_HashSearch *searchPtr +.AS Tcl_HashKeyType *searchPtr out .AP Tcl_HashTable *tablePtr in Address of hash table structure (for all procedures but \fBTcl_InitHashTable\fR, this must have been initialized by previous call to \fBTcl_InitHashTable\fR). .AP int keyType in Kind of keys to use for new hash table. Must be either -TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, TCL_CUSTOM_TYPE_KEYS, -TCL_CUSTOM_PTR_KEYS, or an integer value greater than 1. +\fBTCL_STRING_KEYS\fR, \fBTCL_ONE_WORD_KEYS\fR, \fBTCL_CUSTOM_TYPE_KEYS\fR, +\fBTCL_CUSTOM_PTR_KEYS\fR, or an integer value greater than 1. .AP Tcl_HashKeyType *typePtr in Address of structure which defines the behaviour of the hash table. -.AP "CONST char" *key in +.AP "const char" *key in Key to use for probe into table. Exact form depends on \fIkeyType\fR used to create table. .AP int *newPtr out @@ -88,7 +88,9 @@ STRUCTURE\fR below). All of the keys in a given table have the same form, which is specified when the table is initialized. .PP The value of a hash table entry can be anything that fits in the same -space as a ``char *'' pointer. Values for hash table entries are +space as a +.QW "char *" +pointer. Values for hash table entries are managed entirely by clients, not by the hash module itself. Typically each entry's value is a pointer to a data structure managed by client code. @@ -124,8 +126,10 @@ They are passed to hashing routines using the address of the first character of the string. .IP \fBTCL_ONE_WORD_KEYS\fR 25 Keys are single-word values; they are passed to hashing routines -and stored in hash table entries as ``char *'' values. -The pointer value is the key; it need not (and usually doesn't) +and stored in hash table entries as +.QW "char *" +values. +The pointer value is the key; it need not (and usually does not) actually point to a string. .IP \fBTCL_CUSTOM_TYPE_KEYS\fR 25 Keys are of arbitrary type, and are stored in the entry. Hashing @@ -140,7 +144,9 @@ structure is described in the section .IP \fIother\fR 25 If \fIkeyType\fR is not one of the above, then it must be an integer value greater than 1. -In this case the keys will be arrays of ``int'' values, where +In this case the keys will be arrays of +.QW int +values, where \fIkeyType\fR gives the number of ints in each key. This allows structures to be used as keys. All keys must have the same size. @@ -161,7 +167,7 @@ before deleting the table. .PP \fBTcl_CreateHashEntry\fR locates the entry corresponding to a particular key, creating a new entry in the table if there -wasn't already one with the given key. +was not already one with the given key. If an entry already existed with the given key then \fI*newPtr\fR is set to zero. If a new entry was created, then \fI*newPtr\fR is set to a non-zero @@ -177,28 +183,34 @@ the client is responsible for any cleanup associated with the entry's value, such as freeing a structure that it points to. .PP \fBTcl_FindHashEntry\fR is similar to \fBTcl_CreateHashEntry\fR -except that it doesn't create a new entry if the key doesn't exist; +except that it does not create a new entry if the key doesn't exist; instead, it returns NULL as result. .PP \fBTcl_GetHashValue\fR and \fBTcl_SetHashValue\fR are used to read and write an entry's value, respectively. -Values are stored and retrieved as type ``ClientData'', which is +Values are stored and retrieved as type +.QW ClientData , +which is large enough to hold a pointer value. On almost all machines this is large enough to hold an integer value too. .PP \fBTcl_GetHashKey\fR returns the key for a given hash table entry, -either as a pointer to a string, a one-word (``char *'') key, or +either as a pointer to a string, a one-word +.PQ "char *" +key, or as a pointer to the first word of an array of integers, depending on the \fIkeyType\fR used to create a hash table. In all cases \fBTcl_GetHashKey\fR returns a result with type -``char *''. +.QW "char *" . When the key is a string or array, the result of \fBTcl_GetHashKey\fR points to information in the table entry; this information will remain valid until the entry is deleted or its table is deleted. .PP \fBTcl_FirstHashEntry\fR and \fBTcl_NextHashEntry\fR may be used to scan all of the entries in a hash table. -A structure of type ``Tcl_HashSearch'', provided by the client, +A structure of type +.QW Tcl_HashSearch , +provided by the client, is used to keep track of progress through the table. \fBTcl_FirstHashEntry\fR initializes the search record and returns the first entry in the table (or NULL if the table is @@ -209,9 +221,10 @@ NULL if the end of the table has been reached. A call to \fBTcl_FirstHashEntry\fR followed by calls to \fBTcl_NextHashEntry\fR will return each of the entries in the table exactly once, in an arbitrary order. -It is unadvisable to modify the structure of the table, e.g. -by creating or deleting entries, while the search is in -progress. +It is inadvisable to modify the structure of the table, e.g. +by creating or deleting entries, while the search is in progress, +with the exception of deleting the entry returned by +\fBTcl_FirstHashEntry\fR or \fBTcl_NextHashEntry\fR. .PP \fBTcl_HashStats\fR returns a dynamically-allocated string with overall information about a hash table, such as the number of @@ -230,10 +243,10 @@ to any of the fields of any of the hash-related data structures; use the procedures and macros defined here. .SH "THE TCL_HASHKEYTYPE STRUCTURE" .PP -Extension writers can define new hash key types by defining four -procedures, initializing a Tcl_HashKeyType structure to describe -the type, and calling \fBTcl_InitCustomHashTable\fR. -The \fBTcl_HashKeyType\fR structure is defined as follows: +Extension writers can define new hash key types by defining four procedures, +initializing a \fBTcl_HashKeyType\fR structure to describe the type, and +calling \fBTcl_InitCustomHashTable\fR. The \fBTcl_HashKeyType\fR structure is +defined as follows: .CS typedef struct Tcl_HashKeyType { int \fIversion\fR; @@ -245,61 +258,71 @@ typedef struct Tcl_HashKeyType { } Tcl_HashKeyType; .CE .PP -The \fIversion\fR member is the version of the table. If this -structure is extended in future then the version can be used -to distinguish between different structures. It should be set -to \fBTCL_HASH_KEY_TYPE_VERSION\fR. +The \fIversion\fR member is the version of the table. If this structure is +extended in future then the version can be used to distinguish between +different structures. It should be set to \fBTCL_HASH_KEY_TYPE_VERSION\fR. .PP -The \fIflags\fR member is one or more of the following values OR'ed together: +The \fIflags\fR member is 0 or one or more of the following values OR'ed +together: .IP \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR 25 -There are some things, pointers for example which don't hash well -because they do not use the lower bits. If this flag is set then the -hash table will attempt to rectify this by randomising the bits and -then using the upper N bits as the index into the table. +There are some things, pointers for example which do not hash well because +they do not use the lower bits. If this flag is set then the hash table will +attempt to rectify this by randomizing the bits and then using the upper N +bits as the index into the table. +.IP \fBTCL_HASH_KEY_SYSTEM_HASH\fR 25 +.VS 8.5 +This flag forces Tcl to use the memory allocation procedures provided by the +operating system when allocating and freeing memory used to store the hash +table data structures, and not any of Tcl's own customized memory allocation +routines. This is important if the hash table is to be used in the +implementation of a custom set of allocation routines, or something that a +custom set of allocation routines might depend on, in order to avoid any +circular dependency. +.VE 8.5 .PP -The \fIhashKeyProc\fR member contains the address of a function -called to calculate a hash value for the key. +The \fIhashKeyProc\fR member contains the address of a function called to +calculate a hash value for the key. .CS typedef unsigned int (Tcl_HashKeyProc) ( - Tcl_HashTable *\fItablePtr\fR, - VOID *\fIkeyPtr\fR); + Tcl_HashTable *\fItablePtr\fR, + void *\fIkeyPtr\fR); .CE -If this is NULL then \fIkeyPtr\fR is used and +If this is NULL then \fIkeyPtr\fR is used and \fBTCL_HASH_KEY_RANDOMIZE_HASH\fR is assumed. .PP -The \fIcompareKeysProc\fR member contains the address of a function -called to compare two keys. +The \fIcompareKeysProc\fR member contains the address of a function called to +compare two keys. .CS -typedef int (Tcl_CompareHashKeysProc) (VOID *\fIkeyPtr\fR, - Tcl_HashEntry *\fIhPtr\fR); +typedef int (Tcl_CompareHashKeysProc) ( + void *\fIkeyPtr\fR, + Tcl_HashEntry *\fIhPtr\fR); .CE -If this is NULL then the \fIkeyPtr\fR pointers are compared. -If the keys don't match then the function returns 0, otherwise -it returns 1. +If this is NULL then the \fIkeyPtr\fR pointers are compared. If the keys do +not match then the function returns 0, otherwise it returns 1. .PP -The \fIallocEntryProc\fR member contains the address of a function -called to allocate space for an entry and initialise the key. +The \fIallocEntryProc\fR member contains the address of a function called to +allocate space for an entry and initialize the key and clientData. .CS typedef Tcl_HashEntry *(Tcl_AllocHashEntryProc) ( - Tcl_HashTable *\fItablePtr\fR, VOID *\fIkeyPtr\fR); + Tcl_HashTable *\fItablePtr\fR, + void *\fIkeyPtr\fR); .CE If this is NULL then Tcl_Alloc is used to allocate enough space for a -Tcl_HashEntry and the key pointer is assigned to key.oneWordValue. -String keys and array keys use this function to allocate enough -space for the entry and the key in one block, rather than doing -it in two blocks. This saves space for a pointer to the key from -the entry and another memory allocation. Tcl_Obj * keys use this -function to allocate enough space for an entry and increment the -reference count on the object. -If +Tcl_HashEntry, the key pointer is assigned to key.oneWordValue and the +clientData is set to NULL. String keys and array keys use this function to +allocate enough space for the entry and the key in one block, rather than +doing it in two blocks. This saves space for a pointer to the key from the +entry and another memory allocation. Tcl_Obj* keys use this function to +allocate enough space for an entry and increment the reference count on the +object. .PP -The \fIfreeEntryProc\fR member contains the address of a function -called to free space for an entry. +The \fIfreeEntryProc\fR member contains the address of a function called to +free space for an entry. .CS typedef void (Tcl_FreeHashEntryProc) (Tcl_HashEntry *\fIhPtr\fR); .CE -If this is NULL then Tcl_Free is used to free the space for the -entry. Tcl_Obj * keys use this function to decrement the -reference count on the object. +If this is NULL then Tcl_Free is used to free the space for the entry. +Tcl_Obj* keys use this function to decrement the reference count on the +object. .SH KEYWORDS hash table, key, lookup, search, value |