DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH
 

hash(3)





NAME

       hash - hash table support - obsolete - use cdt


SYNOPSIS

       #include <hash.h>


DESCRIPTION

       The  hash  routines  manipulate  collections  of  dynamic,  scoped hash
       tables.

       A hash table provides an association between a key and  its  value.   A
       key  is  a  sequence  of  char  elements and a 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 collision chain.

       Hashing  occurs  as follows: a hash function takes a key as an argument
       and returns a non-negative index.  The index modulo the table size pro-
       duces  a slot that points to a collision chain.  The collision chain is
       sequentially searched until a match is found for key.  The hash  tables
       are automatically resized as new entries are added.

       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 hashalloc()
       function described below.

       Hash table information is partitioned  into  two  parts  for  efficient
       scoping.  The 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.

       These  basic  types  are  defined  in the header file hash.h (alternate
       names are listed in parenthesis):

       Hash_table_t (HASHTABLE)
              The per-table information.  The readonly public elements are:

              int buckets
                     The number of table entries.

              char* name
                     The hash table name.

              root   The root information.  The public elements are:

                     int root->accesses
                            The number of lookups.

                     int root->collisions
                            The number of lookup collisions.

              Hash_table_t* scope
                     The table that this scope covers, NULL if  the  table  is
                     not a scope.

              int size
                     The current hash table size.

       Hash_bucket_t (HASHBUCKET)
              A  collision  chain  hash bucket.  The public structure elements
              are:

              char* hashname(Hash_bucket_t*)
                     Returns a pointer to the hash bucket key given the bucket
                     pointer.

              char* value
                     The value associated with the key.

       Hash_header_t (HASHHEADER)
              The  hash  bucket  header  that must be the first element in all
              user defined buckets.  HASH_VALUE may  not  be  used  with  user
              defined buckets.

       Hash_position_t (HASHPOSITION)
              Stores  the  hash  table position for hashscan.  The public ele-
              ments are:

              Hash_bucket_t* bucket
                     The current hash bucket pointer.

       The routines are:

       Hash_table_t* hashalloc(Hash_table_t* ref, int op, ...)
              Creates a new hash table and returns a  pointer  to  the  table.
              malloc(3)  is  used  to  allocate  space for the table.  NULL is
              returned if the table cannot be created.  ref is a pointer to  a
              reference  hash  table that provides default values for unspeci-
              fied information.  The new hash table and  ref  share  the  same
              root  information.   If ref is NULL then new root information is
              created for the new table.  The remaining  arguments  appear  in
              op-arg  pairs, followed by a final 0 argument.  The op-arg pairs
              are:

              HASH_alloc, (char(*)()) alloc
                     alloc  is  a  function  that   is   called   to   process
                     Hash_bucket_t  value assignments.  The single argument is
                     char* value and the processed char* value is returned.

              HASH_clear, int flags
                     flags are the ref flags to be cleared in the new hash ta-
                     ble.  See HASH_set below.

              HASH_compare, (int(*)()) compare
                     Specifies  an  alternate  key  comparison  function.  The
                     arguments and return value for compare are  the  same  as
                     for  strncmp(3)  if  HASH_namesize  is specified and str-
                     cmp(3) otherwise.  The first argument is the key from the
                     current hash bucket on the collision chain and the second
                     argument is the user supplied key.

              HASH_free, (int(*)()) free
                     free is a function that is called when a hash  bucket  is
                     freed.  If HASH_BUCKET was set in hashalloc then the hash
                     bucket pointer is  passed,  otherwise  the  bucket  value
                     pointer is passed.

              HASH_hash, (int(*)()) hash
                     Specifies  an  alternate  key hash function.  A char* key
                     argument (and, if HASH_namesize is specified, an int  key
                     size  argument) is passed to hash.  The return value must
                     be a non-negative int.

              HASH_meanchain, int meanchain
                     Specifies the mean collision chain length.  The hash  ta-
                     ble is automatically resized when this value is exceeded.
                     The default mean chain length is 2.

              HASH_name, char* name
                     Associates name with the hash table.  Used by  hashdump).

              HASH_namesize, int namesize
                     The  fixed size in bytes for keys in the table.  If name-
                     size is 0 (the default) then the keys are interpreted  as
                     null-terminated strings.

              HASH_set, int flags
                     Changes  the  hash  table  flags  by oring in flags.  The
                     flags, which may be ored together, are:

                     HASH_ALLOCATE
                            Keys for new hash table entries are to  be  copied
                            to data areas obtained from malloc(3).

                     HASH_FIXED
                            Fixes the hash table size, disabling any automatic
                            table resizing.

                     HASH_SCOPE
                            The new hash table is a scope that is to be pushed
                            on top of ref.  ref must be non-NULL.

              HASH_va_list, va_list ap
                     ap  is  a  va_list  variable  argument  list pointer (see
                     <stdarg.h>).

       Hash_table_t* hashfree(Hash_table_t* tab)
              The hash table tab is freed.  The scope covered table pointer is
              returned, NULL if tab is not a scope.

       char* hashlook(Hash_table_t* tab, char* name, int flags, char* value)
              Operates  on  the  key  name  in the hash table tab according to
              flags and value.  A Hash_bucket_t  pointer  is  returned  unless
              otherwise noted.  There are three basic lookup operations:

              HASH_CREATE
                     name  is  entered into the top level scope if it does not
                     already exist.  If name also appears in a lower scope and
                     HASH_ALLOC  is set for the table then the new bucket will
                     share the name field value with the lower scope.

              HASH_DELETE
                     name is deleted from the top level scope  if  it  exists.
                     NULL is returned.

              HASH_LOOKUP
                     The  scopes  are searched in order from top to bottom for
                     name.  The bucket pointer for  the  first  occurrence  is
                     returned.  NULL is returned if name is not found.
       The  basic operations may be qualified by the following (the qualifiers
       are restricted to the basic operations in the parenthesized list):

              HASH_BUCKET (HASH_CREATE,HASH_DELETE,HASH_LOOKUP)
                     name is a pointer to  a  bucket  that  has  already  been
                     entered into the table.

              HASH_FIXED (HASH_CREATE)
                     value  is  taken  to be the size of the hash bucket to be
                     created for name in the top  level  scope.   The  minimum
                     bucket     size     is     silently     restricted     to
                     sizeof(Hash_header_t).

              HASH_INSTALL (HASH_CREATE)
                     name is a pointer to a bucket that has not  been  entered
                     into the table.

              HASH_NOSCOPE (HASH_LOOKUP)
                     The lookup is restricted to the top level scope.

              HASH_OPAQUE (HASH_CREATE,HASH_DELETE)
                     Sets  (HASH_CREATE)  or  clears  (HASH_DELETE) the opaque
                     property for the bucket.  An opaque bucket is not visible
                     in lower scopes.

              HASH_SCOPE (HASH_CREATE,HASH_DELETE)
                     All scopes are searched for the bucket.  If the bucket is
                     not found for HASH_CREATE then a new bucket is created in
                     the lowest scope.

              HASH_VALUE (HASH_CREATE,HASH_LOOKUP)
                     For  HASH_CREATE  the  bucket value field is set to value
                     and the bucket name value is returned.   For  HASH_LOOKUP
                     the bucket value field is returned, NULL if the bucket is
                     not found.
       If name NULL then the name from the most  recent  hashlook()  is  used,
       avoiding recomputation of some internal parameters.

       char* hashget(Hash_table_t* tab, char* name)
              Returns the value associated with the key name in the hash table
              tab.  If name is  NULL  then  the  name  from  the  most  recent
              hashget()  is  used,  avoiding  recomputation  of  some internal
              parameters.  NULL is returned if name is not in the table.   All
              scope covered tables are searched.

       Hash_bucket_t* hashlast(Hash_table_t* tab)
              Returns  a  pointer to the most recent hash bucket for tab.  The
              value is set by hashlook(), hashscan() and hashwalk().

       char* hashput(Hash_table_t* tab, char* name, char* value)
              Set the value of the key name to value in the top level scope of
              the hash table tab.  name is entered into the top level scope if
              necessary.  The (possibly  re-allocated)  key  name  pointer  is
              returned (see HASH_ALLOCATE).  If name is 0 then the most recent
              lookup name to hashlook() or hashget() is used.  This eliminates
              a re-hash and re-lookup of name.

       int  hashwalk(Hash_table_t*  tab,  int  flags, (int(*)()) walker, char*
       handle)
              The  function  walker is applied to each entry (not covered by a
              scope starting at tab) in the  hash  table  tab.   If  flags  is
              HASH_NOSCOPE  then only the top level hash table is used, other-
              wise the walk includes all  scope  covered  tables.   walker  is
              called  with char* key as the first argument, char* value as the
              second argument, and char* handle as the third argument.  handle
              may  be  0.   The  walk  terminates after the last entry or when
              walker returns a negative value.  The return value of  the  last
              call  to walker is returned.  Only one walk may be active within
              a collection of scoped tables.

       Hash_position_t* hashscan(Hash_table_t* tab, int flags)
              Returns a Hash_position_t pointer for a sequential scan  on  the
              hash  table  tab.   If  flags  is 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.  hashdone() must be called  to  terminate  the
              scan.  0 is returned on error.

       Hash_bucket_t* hashnext(Hash_position_t* pos)
              Returnes a pointer to the next bucket in the sequential scan set
              up by hashscan() on pos.   If  no  elements  remain  then  0  is
              returned.

       void hashdone(Hash_position_t* pos)
              Completes a scan initiated by hashscan() on pos.

       int hashset(Hash_table_t* tab, int flags)
              Sets  the  flags for the hash table tab by oring in flags.  Only
              HASH_ALLOCATE and HASH_FIXED may be set.

       int hashclear(Hash_table_t* tab, int flags)
              Clears the flags for the hash table tab by  masking  out  flags.
              Only HASH_ALLOCATE and HASH_FIXED may be cleared.

       void hashdump(Hash_table_t* tab, int flags)
              Dumps  hash  table accounting info to standard error.  If tab is
              NULL then all allocated hash tables are dumped,  otherwise  only
              information  on tab is dumped.  If flags is HASH_BUCKET then the
              hash bucket key-value pairs for each collision  chain  are  also
              dumped.

       void hashsize(Hash_table_t* tab, int size)
              Changes  the  size of the hash table tab to size where size must
              be a power of 2.  Explicit calls to this routine are not  neces-
              sary as hash tables are automatically resized.

       int strhash(char* name)
              Hashes  the null terminated character string name using a linear
              congruent pseudo-random number generator algorithm and returns a
              non-negative int hash value.

       int memhash(char* buf, int siz)
              Hashes  the  buffer  buf  of  siz bytes using a linear congruent
              pseudo-random number generator algorithm and returns a non-nega-
              tive int hash value.

       long strsum(char* name, long sum)
              Returns  a  running 31-bit checksum of the string name where sum
              is 0 on the first call and the return value from a previous mem-
              sum  or strsum call otherwise.  The checksum value is consistent
              across all implementations.

       long memsum(char* buf, int siz, long sum)
              Returns a running 31-bit checksum of buffer  buf  of  siz  bytes
              where  sum  is  0  on the first call and the return value from a
              previous memsum or strsum call otherwise.  The checksum value is
              consistent across all implementations.


SEE ALSO

       sum(1)

                                                                       HASH(3)

Man(1) output converted with man2html