common/man/hash.3

.fp 5 CW
.de Af
.ds ;G \\*(;G\\f\\$1\\$3\\f\\$2
.if !\\$4 .Af \\$2 \\$1 "\\$4" "\\$5" "\\$6" "\\$7" "\\$8" "\\$9"
..
.de aF
.ie \\$3 .ft \\$1
.el \{\
.ds ;G \&
.nr ;G \\n(.f
.Af "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7" "\\$8" "\\$9"
\\*(;G
.ft \\n(;G \}
..
.de L
.aF 5 \\n(.f "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
..
.de LR
.aF 5 1 "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
..
.de RL
.aF 1 5 "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
..
.de EX		\" start example
.ta 1i 2i 3i 4i 5i 6i
.PP
.RS
.PD 0
.ft 5
.nf
..
.de EE		\" end example
.fi
.ft
.PD
.RE
.PP
..
.TH HASH 3
.SH NAME
hash \- hash table support (obsolete: use \fBcdt\fP instead)
.SH SYNOPSIS
.L "#include <hash.h>"
.SH DESCRIPTION
The
.I hash
routines manipulate collections of dynamic, scoped hash tables.
.PP
A hash table provides an association between a
.I key
and its
.IR value .
A
.I key
is a sequence of
.L char
elements and a
.I value
is a user supplied pointer to the value.
Each hash table has a dynamic number of slots,
each pointing to the head of a forward linked
.IR "collision chain" .
.PP
Hashing occurs as follows:
a
.I "hash function"
takes a
.I key
as an argument and returns a non-negative index.
The index modulo the table size produces a
slot that points to a
.IR "collision chain" .
The collision chain is sequentially searched until a match is found for
.IR key .
The hash tables are automatically resized as new entries are added.
.PP
Each hash table has one key type.
The default key type is a pointer to a null-terminated string.
The alternate key type is a pointer to a fixed length byte buffer,
declared for a given table by the
.L hashalloc()
function described below.
.PP
Hash table information is partitioned into two parts for efficient scoping.
The
.I root
part contains fixed information that is shared among a set of related
hash tables.
The remaining information is maintained on a per-table basis.
.PP
These basic types are defined in the header file
.B hash.h
(alternate names are listed in parenthesis):
.TP
.L "Hash_table_t (HASHTABLE)"
The per-table information.
The readonly public elements are:
.RS
.TP
.L "int buckets"
The number of table entries.
.TP
.L "char* name"
The hash table name.
.TP
.L "root"
The root information.
The public elements are:
.RS
.TP
.L "int root->accesses"
The number of lookups.
.TP
.L "int root->collisions"
The number of lookup collisions.
.RE
.TP
.L "Hash_table_t* scope"
The table that this scope covers,
.L NULL
if the table is not a scope.
.TP
.L "int size"
The current hash table size.
.RE
.TP
.L "Hash_bucket_t (HASHBUCKET)"
A collision chain hash bucket.
The public structure elements are:
.RS
.TP
.L "char* hashname(Hash_bucket_t*)"
Returns a pointer to the hash bucket key given the bucket pointer.
.TP
.L "char* value"
The value associated with the key.
.RE
.TP
.L "Hash_header_t (HASHHEADER)"
The hash bucket header that must be the first element in all user defined
buckets.
.L HASH_VALUE
may not be used with user defined buckets.
.TP
.L "Hash_position_t (HASHPOSITION)"
Stores the hash table position for
.LR hashscan .
The public elements are:
.RS
.TP
.L "Hash_bucket_t* bucket"
The current hash bucket pointer.
.RE
.PP
The routines are:
.TP
.L "Hash_table_t* hashalloc(Hash_table_t* ref, int op, ...)"
Creates a new hash table and returns a pointer to the table.
.IR malloc (3)
is used to allocate space for the table.
.L NULL
is returned if the table cannot be created.
.L ref
is a pointer to a reference hash table that provides
default values for unspecified information.
The new hash table and
.L ref
share the same root information.
If
.L ref
is
.L NULL
then new root information is created for the new table.
The remaining arguments appear in
.I op-arg
pairs, followed by a final
.L 0
argument.
The
.I op-arg
pairs are:
.RS
.TP
.L "HASH_alloc, (char(*)()) alloc"
.L alloc
is a function that is called to process
.L Hash_bucket_t
.L value
assignments.
The single argument is
.L "char* value"
and the processed
.L char*
value is returned.
.TP
.L "HASH_clear, int flags"
.L flags
are the
.L ref
flags to be cleared in the new hash table.
See
.L HASH_set
below.
.TP
.L "HASH_compare, (int(*)()) compare"
Specifies an alternate
.I key
comparison function.
The arguments and return value for
.L compare
are the same as for
.IR strncmp (3)
if
.L HASH_namesize
is specified and
.IR strcmp (3)
otherwise.
The first argument is the
.I key
from the current hash bucket on the
.I "collision chain"
and the second argument is the user supplied
.IR key .
.TP
.L "HASH_free, (int(*)()) free"
.L free
is a function that is called when a hash bucket is freed.
If
.L HASH_BUCKET
was set in
.L hashalloc
then the hash bucket pointer is passed, otherwise the bucket
.L value
pointer is passed.
.TP
.L "HASH_hash, (int(*)()) hash"
Specifies an alternate
.I key
hash function.
A
.L char*
key argument (and, if
.L HASH_namesize
is specified, an
.L int
key size argument) is passed to
.LR hash .
The return value must be a non-negative
.LR int .
.TP
.L "HASH_meanchain, int meanchain"
Specifies the mean collision chain length.
The hash table is automatically resized when this value is exceeded.
The default mean chain length is 2.
.TP
.L "HASH_name, char* name"
Associates
.L name
with the hash table.
Used by
.LR hashdump) .
.TP
.L "HASH_namesize, int namesize"
The fixed size in bytes for
.I keys
in the table.
If
.L namesize
is 0 (the default) then the
.I keys
are interpreted as null-terminated strings.
.TP
.L "HASH_set, int flags"
Changes the hash table flags by
.IR or ing
in
.LR flags .
The flags, which may be
.IR or ed
together, are:
.RS
.TP
.L HASH_ALLOCATE
Keys for new hash table entries are to be copied to data areas obtained from
.IR malloc (3).
.TP
.L HASH_FIXED
Fixes the hash table size, disabling any automatic table resizing.
.TP
.L HASH_SCOPE
The new hash table is a scope that is to be pushed on top of
.LR ref .
.L ref
must be
.RL non- NULL .
.RE
.TP
.L "HASH_va_list, va_list ap"
.L ap
is a
.L va_list
variable argument list pointer
(see
.LR <stdarg.h> ).
.RE
.TP
.L "Hash_table_t* hashfree(Hash_table_t* tab)"
The hash table
.L tab
is freed.
The scope covered table pointer is returned,
.L NULL
if
.L tab
is not a scope.
.TP
.L "char* hashlook(Hash_table_t* tab, char* name, int flags, char* value)"
Operates on the key
.L name
in the hash table
.L tab
according to
.L flags
and
.LR value .
A
.L Hash_bucket_t
pointer is returned unless otherwise noted.
There are three basic lookup operations:
.RS
.TP
.L HASH_CREATE
.L name
is entered into the top level scope if it does not already exist.
If
.L name
also appears in a lower scope and
.L HASH_ALLOC
is set for the table then the new bucket will share the
.L name
field value with the lower scope.
.TP
.L HASH_DELETE
.L name
is deleted from the top level scope if it exists.
.L NULL
is returned.
.TP
.L HASH_LOOKUP
The scopes are searched in order from top to bottom for
.L name .
The bucket pointer for the first occurrence is returned.
.L NULL
is returned if
.L name
is not found.
.RE
The basic operations may be qualified by the following
(the qualifiers are restricted to the basic operations in
the parenthesized list):
.RS
.TP
.L "HASH_BUCKET (HASH_CREATE,HASH_DELETE,HASH_LOOKUP)"
.L name
is a pointer to a bucket that has already been entered into the table.
.TP
.L "HASH_FIXED (HASH_CREATE)"
.L value
is taken to be the size of the hash bucket to be created for
.L name
in the top level scope.
The minimum bucket size is silently restricted to
.LR sizeof(Hash_header_t) .
.TP
.L "HASH_INSTALL (HASH_CREATE)"
.L name
is a pointer to a bucket that has not been entered into the table.
.TP
.L "HASH_NOSCOPE (HASH_LOOKUP)"
The lookup is restricted to the top level scope.
.TP
.L "HASH_OPAQUE (HASH_CREATE,HASH_DELETE)"
Sets
.L (HASH_CREATE)
or clears
.L (HASH_DELETE)
the
.I opaque
property for the bucket.
An opaque bucket is not visible in lower scopes.
.TP
.L "HASH_SCOPE (HASH_CREATE,HASH_DELETE)"
All scopes are searched for the bucket.
If the bucket is not found for
.L HASH_CREATE
then a new bucket is created in the lowest scope.
.TP
.L "HASH_VALUE (HASH_CREATE,HASH_LOOKUP)"
For
.L HASH_CREATE
the bucket
.L value
field is set to
.L value
and the bucket
.L name
value is returned.
For
.L HASH_LOOKUP
the bucket
.L value
field is returned,
.L NULL
if the bucket is not found.
.RE
If
.L name
.L NULL
then the name from the most recent
.L hashlook()
is used, avoiding recomputation of some internal parameters.
.TP
.L "char* hashget(Hash_table_t* tab, char* name)"
Returns the value
associated with the key
.L name
in the hash table
.LR tab .
If
.L name
is
.L NULL
then the name from the most recent
.L hashget()
is used, avoiding recomputation of some internal parameters.
.L NULL
is returned if
.L name
is not in the table.
All scope covered tables are searched.
.TP
.L "Hash_bucket_t* hashlast(Hash_table_t* tab)"
Returns a pointer to the most recent hash bucket for
.LR tab .
The value is set by
.LR hashlook() ,
.L hashscan()
and
.LR hashwalk() .
.TP
.L "char* hashput(Hash_table_t* tab, char* name, char* value)"
Set the value of the key
.L name
to
.L value
in the top level scope of the hash table
.LR tab .
.L name
is entered into the top level scope if necessary.
The (possibly re-allocated) key name pointer is returned
(see
.LR HASH_ALLOCATE ).
If
.L name
is 0 then the most recent lookup
.L name
to
.L hashlook()
or
.L hashget()
is used.
This eliminates a re-hash and re-lookup of
.LR name .
.TP
.L "int hashwalk(Hash_table_t* tab, int flags, (int(*)()) walker, char* handle)"
The function
.L walker
is applied to each entry (not covered by a scope starting at
.LR tab )
in the hash table
.LR tab .
If
.L flags
is
.L HASH_NOSCOPE
then only the top level hash table is used, otherwise the walk includes
all scope covered tables.
.L walker
is called with
.L char*
.I key
as the first argument,
.L char*
.I value
as the second argument, and
.L char*
.I handle
as the third argument.
.I handle
may be
.LR 0 .
The walk terminates after the last entry or when
.L walker
returns a negative value.
The return value of the last call to
.L walker
is returned.
Only one walk may be active within a collection of scoped tables.
.TP
.L "Hash_position_t* hashscan(Hash_table_t* tab, int flags)"
Returns a
.L Hash_position_t
pointer for a sequential scan on the hash table
.LR tab .
If
.L flags
is
.L HASH_NOSCOPE
then only the top level hash table is used, otherwise the scan includes
all scope covered tables.
Only one scan may be active within a collection of scoped tables.
.L hashdone()
must be called to terminate the scan.
.L 0
is returned on error.
.TP
.L "Hash_bucket_t* hashnext(Hash_position_t* pos)"
Returnes a pointer to the next bucket in the sequential scan set up by
.L hashscan()
on
.LR pos .
If no elements remain then
.L 0
is returned.
.TP
.L "void hashdone(Hash_position_t* pos)"
Completes a scan initiated by
.L hashscan()
on
.LR pos .
.TP
.L "int hashset(Hash_table_t* tab, int flags)"
Sets the flags for the hash table
.L tab
by
.IR or ing
in
.LR flags .
Only
.L HASH_ALLOCATE
and
.L HASH_FIXED
may be set.
.TP
.L "int hashclear(Hash_table_t* tab, int flags)"
Clears the flags for the hash table
.L tab
by masking out
.LR flags .
Only
.L HASH_ALLOCATE
and
.L HASH_FIXED
may be cleared.
.TP
.L "void hashdump(Hash_table_t* tab, int flags)"
Dumps hash table accounting info to standard error.
If
.L tab
is
.L NULL
then all allocated hash tables are dumped, otherwise only information on
.L tab
is dumped.
If
.L flags
is
.L HASH_BUCKET
then the hash bucket
.I key-value
pairs for each collision chain are also dumped.
.TP
.L "void hashsize(Hash_table_t* tab, int size)"
Changes the size of the hash table
.L tab
to
.L size
where
.L size
must be a power of 2.
Explicit calls to this routine are not necessary as hash tables
are automatically resized.
.TP
.L "int strhash(char* name)"
Hashes the null terminated character string
.L name
using a linear congruent pseudo-random number generator algorithm
and returns a non-negative
.L int
hash value.
.TP
.L "int memhash(char* buf, int siz)"
Hashes the buffer
.L buf
of
.L siz
bytes using a linear congruent pseudo-random number generator algorithm
and returns a non-negative
.L int
hash value.
.TP
.L "long strsum(char* name, long sum)"
Returns a running 31-bit checksum of the string
.L name
where
.L sum
is
.L 0
on the first call and
the return value from a previous
.L memsum
or
.L strsum
call otherwise.
The checksum value is consistent across all implementations.
.TP
.L "long memsum(char* buf, int siz, long sum)"
Returns a running 31-bit checksum of buffer
.L buf
of
.L siz
bytes where
.L sum
is
.L 0
on the first call and
the return value from a previous
.L memsum
or
.L strsum
call otherwise.
The checksum value is consistent across all implementations.
.SH "SEE ALSO"
sum(1)