Initial revision

1 files changed, 208 insertions, 0 deletions

diff --git a/doc/Hash.3 b/doc/Hash.3
new file mode 100644
index 0000000..48835a3
--- /dev/null
+++ b/doc/Hash.3
@@ -0,0 +1,208 @@
+'\"
+'\" Copyright (c) 1989-1993 The Regents of the University of California.
+'\" Copyright (c) 1994-1996 Sun Microsystems, Inc.
+'\"
+'\" See the file "license.terms" for information on usage and redistribution
+'\" of this file, and for a DISCLAIMER OF ALL WARRANTIES.
+'\" 
+'\" SCCS: @(#) Hash.3 1.15 96/03/25 20:04:01
+'\" 
+.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
+.SH SYNOPSIS
+.nf
+\fB#include <tcl.h>\fR
+.sp
+\fBTcl_InitHashTable\fR(\fItablePtr, keyType\fR)
+.sp
+\fBTcl_DeleteHashTable\fR(\fItablePtr\fR)
+.sp
+Tcl_HashEntry *
+\fBTcl_CreateHashEntry\fR(\fItablePtr, key, newPtr\fR)
+.sp
+\fBTcl_DeleteHashEntry\fR(\fIentryPtr\fR)
+.sp
+Tcl_HashEntry *
+\fBTcl_FindHashEntry\fR(\fItablePtr, key\fR)
+.sp
+ClientData
+\fBTcl_GetHashValue\fR(\fIentryPtr\fR)
+.sp
+\fBTcl_SetHashValue\fR(\fIentryPtr, value\fR)
+.sp
+char *
+\fBTcl_GetHashKey\fR(\fItablePtr, entryPtr\fR)
+.sp
+Tcl_HashEntry *
+\fBTcl_FirstHashEntry\fR(\fItablePtr, searchPtr\fR)
+.sp
+Tcl_HashEntry *
+\fBTcl_NextHashEntry\fR(\fIsearchPtr\fR)
+.sp
+char *
+\fBTcl_HashStats\fR(\fItablePtr\fR)
+.SH ARGUMENTS
+.AS Tcl_HashSearch *searchPtr
+.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, or an integer value
+greater than 1.
+.AP char *key in
+Key to use for probe into table.  Exact form depends on
+\fIkeyType\fR used to create table.
+.AP int *newPtr out
+The word at \fI*newPtr\fR is set to 1 if a new entry was created
+and 0 if there was already an entry for \fIkey\fR.
+.AP Tcl_HashEntry *entryPtr in
+Pointer to hash table entry.
+.AP ClientData value in
+New value to assign to hash table entry.  Need not have type
+ClientData, but must fit in same space as ClientData.
+.AP Tcl_HashSearch *searchPtr in
+Pointer to record to use to keep track of progress in enumerating
+all the entries in a hash table.
+.BE
+
+.SH DESCRIPTION
+.PP
+A hash table consists of zero or more entries, each consisting of
+a key and a value.
+Given the key for an entry, the hashing routines can very quickly
+locate the entry, and hence its value.
+There may be at most one entry in a hash table with a
+particular key, but many entries may have the same value.
+Keys can take one of three forms:  strings,
+one-word values, or integer arrays.
+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 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.
+.PP
+Hash tables grow gracefully as the number of entries increases,
+so that there are always less than three entries per hash bucket,
+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
+a new hash table.
+The space for the structure is provided by the caller, not by
+the hash module.
+The value of \fIkeyType\fR indicates what kinds of keys will
+be used for all entries in the table.  \fIKeyType\fR must have
+one of the following values:
+.IP \fBTCL_STRING_KEYS\fR 25
+Keys are null-terminated ASCII strings.
+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)
+actually point to a string.
+.IP \fIother\fR 25
+If \fIkeyType\fR is not TCL_STRING_KEYS or TCL_ONE_WORD_KEYS,
+then it must be an integer value greater than 1.
+In this case the keys will be arrays of ``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.
+Array keys are passed into hashing functions using the address
+of the first int in the array.
+.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.
+It does not free the actual table structure (pointed to
+by \fItablePtr\fR), since that memory is assumed to be managed
+by the client.
+\fBTcl_DeleteHashTable\fR also does not free or otherwise
+manipulate the values of the hash table entries.
+If the entry values point to dynamically-allocated memory, then
+it is the client's responsibility to free these structures
+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.
+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
+value and the value of the new entry will be set to zero.
+The return value from \fBTcl_CreateHashEntry\fR is a pointer to
+the entry, which may be used to retrieve and modify the entry's
+value or to delete the entry from the table.
+.PP
+\fBTcl_DeleteHashEntry\fR will remove an existing entry from a
+table.
+The memory associated with the entry itself will be freed, but
+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;
+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
+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
+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 *''.
+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,
+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
+empty).
+Each subsequent call to \fBTcl_NextHashEntry\fR returns the
+next entry in the table or
+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.
+.PP
+\fBTcl_HashStats\fR returns a dynamically-allocated string with
+overall information about a hash table, such as the number of
+entries it contains, the number of buckets in its hash array,
+and the utilization of the buckets.
+It is the caller's responsibility to free the result string
+by passing it to \fBfree\fR.
+.PP
+The header file \fBtcl.h\fR defines the actual data structures
+used to implement hash tables.
+This is necessary so that clients can allocate Tcl_HashTable
+structures and so that macros can be used to read and write
+the values of entries.
+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 KEYWORDS
+hash table, key, lookup, search, value