diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/Hash.3 | 113 |
1 files changed, 101 insertions, 12 deletions
@@ -5,19 +5,23 @@ '\" 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.4 2000/06/24 00:26:08 ericm Exp $ +'\" RCS: @(#) $Id: Hash.3,v 1.5 2000/07/19 22:15:28 ericm Exp $ '\" .so man.macros .TH Tcl_Hash 3 "" Tcl "Tcl Library Procedures" .BS .SH NAME -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 +Tcl_InitHashTable, Tcl_InitHashTableEx, 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 .SH SYNOPSIS .nf \fB#include <tcl.h>\fR .sp \fBTcl_InitHashTable\fR(\fItablePtr, keyType\fR) .sp +\fBTcl_InitHashTableEx\fR(\fItablePtr, keyType, typePtr\fR) +.sp +\fBTcl_InitObjHashTable\fR(\fItablePtr\fR) +.sp \fBTcl_DeleteHashTable\fR(\fItablePtr\fR) .sp Tcl_HashEntry * @@ -52,8 +56,10 @@ Address of hash table structure (for all procedures but 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_OBJ_KEYS, TCL_ONE_WORD_KEYS, or an integer value -greater than 1. +TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, TCL_CUSTOM_TYPE_KEYS, +TCL_CUSTOM_PTR_KEYS, or an integer value greater than 1. +.AP Tcl_HashKeyType *typePtr in +Address of structure which defines the behaviour of the hash table. .AP char *key in Key to use for probe into table. Exact form depends on \fIkeyType\fR used to create table. @@ -96,7 +102,10 @@ on average. This allows for fast lookups regardless of the number of entries in a table. .PP -\fBTcl_InitHashTable\fR initializes a structure that describes +\fBTcl_InitHashTable\fR calls the extended function +\fBTcl_InitHashTableEx\fR with a NULL \fItypePtr\fR. +.PP +\fBTcl_InitHashTableEx\fR initializes a structure that describes a new hash table. The space for the structure is provided by the caller, not by the hash module. @@ -107,18 +116,22 @@ one of the following values: Keys are null-terminated ASCII strings. They are passed to hashing routines using the address of the first character of the string. -.IP \fBTCL_OBJ_KEYS\fR 25 -Keys are Tcl_Obj *. Hashing and comparison are done on the string -representation of the object. The differences between this type and -TCL_STRING_KEYS are: the key is not copied, instead the reference -count is incremented; and the extra information associated with the -Tcl_Obj * is used to optimize comparisons. The string is only -compared if the two Tcl_Obj * are different and have the same length. .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) actually point to a string. +.IP \fBTCL_CUSTOM_TYPE_KEYS\fR 25 +Keys are of arbitrary type, and are stored in the entry. Hashing +and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType +structure is described in the section +\fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below. + +.IP \fBTCL_CUSTOM_TYPE_KEYS\fR 25 +Keys are pointers to arbitrary type, and the are stored in the entry. Hashing +and comparison is determined by \fItypePtr\fR. The Tcl_HashKeyType +structure is described in the section +\fBTHE TCL_HASHKEYTYPE STRUCTURE\fR below. .IP \fIother\fR 25 If \fIkeyType\fR is not one of the above, then it must be an integer value greater than 1. @@ -129,6 +142,9 @@ All keys must have the same size. Array keys are passed into hashing functions using the address of the first int in the array. .PP +\fBTcl_InitObjHashTable\fR uses \fBTcl_InitHashTableEx\fR to +initialize a hash table whose keys are Tcl_Obj *. +.PP \fBTcl_DeleteHashTable\fR deletes all of the entries in a hash table and frees up the memory associated with the table's bucket array and entries. @@ -211,5 +227,78 @@ However, users of the hashing routines should never refer directly 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 +procedure, initializing a Tcl_HashKeyType structure to describe +the type, and calling \fBTcl_InitHashTableEx\fR. +The \fBTcl_HashKeyType\fR structure is defined as follows: +.CS +typedef struct Tcl_HashKeyType { + int \fIversion\fR; + int \fIflags\fR; + Tcl_HashKeyProc *\fIhashKeyProc\fR; + Tcl_CompareHashKeysProc *\fIcompareKeysProc\fR; + Tcl_AllocHashEntryProc *\fIallocEntryProc\fR; + Tcl_FreeHashEntryProc *\fIfreeEntryProc\fR; +} 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. +.PP +The \fIflags\fR member is one or more of the following 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. +.PP +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); +.CE +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. +.CS +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. +.PP +The \fIallocEntryProc\fR member contains the address of a function +called to allocate space for an entry and initialise the key. +.CS +typedef Tcl_HashEntry *(Tcl_AllocHashEntryProc) ( + 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 +.PP +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. .SH KEYWORDS hash table, key, lookup, search, value |