# pmhash

## NAME



           **__pmHashInit** , **__pmHashPreAlloc** , **__pmHashAdd** , **__pmHashDel** ,
           **__pmHashSearch** , **__pmHashWalk** , **__pmHashWalkCB** , **__pmHashFree** ,
           **__pmHashClear** - general purpose hashing routines
    


## C SYNOPSIS



           **#include <pcp/pmapi.h>**
           **#include <pcp/libpcp.h>**
    
           **void __pmHashInit(__pmHashCtl ***_hcp_**);**
           **int __pmHashPreAlloc(int** _hsize_**, __pmHashCtl ***_hcp_**);**
           **int __pmHashAdd(unsigned int** _key_**, void ***_data_**, __pmHashCtl ***_hcp_**);**
           **int __pmHashDel(unsigned int** _key_**, void ***_data_**, __pmHashCtl ***_hcp_**);**
           **__pmHashNode *__pmHashSearch(unsigned int** _key_**, __pmHashCtl ***_hcp_**);**
           **__pmHashNode *__pmHashWalk(__pmHashCtl ***_hcp_**,**
                                      **__pmHashWalkState** _state_**);**
           **void __pmHashWalkCB(__pmHashWalkCallback** _cb_**, void ***_cdata_**,**
                               **const __pmHashCtl ***_hcp_**);**
           **void __pmHashFree(__pmHashCtl ***_hcp_**);**
           **void __pmHashClear(__pmHashCtl ***_hcp_**);**
    
           **cc ... -lpcp**
    


## CAVEAT



           This  documentation  is intended for internal Performance Co-Pilot
           (PCP) developer use.
    
           These interfaces are not part of the PCP APIs that are  guaranteed
           to  remain  fixed across releases, and at some point in the future
           they may not work or may provide different semantics.
    


## DESCRIPTION



           The **__pmHash** group of routines implement a  generalized  suite  of
           linear hashing services based on a _key_ that is an unsigned int and
           _data_ that is an opaque pointer to information the caller wishes to
           associate with _key_.
    
           The  data type of _key_ makes is suitable for hashed access based on
           metric identifier (**pmID**), instance domain number (**pmInDom**) or  in‐
           ternal instance identifiers within an instance domain.
    
           Multiple  hash tables may exist, each identified by a hash control
           struct (**__pmHashCtl**) **hcp** which is declared by the caller and  ini‐
           tialized  by  calling **__pmHashInit**.  Refer to the **HASH CONTROL** and
           **HASH NODE** sections below for more information on  the  hash  table
           internal data structures.
    
           The hash table is initially empty but dynamically grows by approx‐
           imate  doubling  in  size as entries are added, and this may cause
           some organizational overhead in relinking the hash chains when the
           hash table grows.  This overhead  can  be  avoided  by  optionally
           calling  **__pmHashPreAlloc** with an initial hash table size of _hsize_
           entries, but this must be done after calling **__pmHashInit** and  be‐
           fore any entries are added.
    
           Entries  are  added  to  a hash table by calling **__pmHashAdd**.  The
           opaque _data_ is typically a pointer to a block of additional infor‐
           mation to be associated with the _key_ , although it may be  **NULL** if
           there  is  no  additional information required or currently avail‐
           able.
    
           Although usually not required, duplicate _key_ values can be  stored
           in  a  hash table and **__pmHashAdd** will silently add these (presum‐
           ably with a different _data_ pointer).  If uniqueness of _key_ s is re‐
           quired, it is necessary to call **__pmHashSearch** first to  determine
           that there is no entry for _key_ , before calling **__pmHashAdd**.
    
           Entries  may  be removed from a hash table using **__pmHashDel** where
           the entry to be deleted is the _first_ one with a matching  _key_  and
           _data_  pointer.   See the note above about duplicate keys to under‐
           stand why the _data_ parameter is needed.
    
           **__pmHashSearch** finds the _first_ entry with a matching _key_.  If  du‐
           plicate keys are being stored, then the caller will have to follow
           the  _hp_ ->_next_  chain  looking for additional entries with the same
           _key_.  Refer to the **HASH CONTROL** and **HASH NODE** sections  below  for
           more information on the hash table internal data structures.
    
           **__pmHashWalk** provides  a  stateful interface to walk each node in
           the  hash  table.   It  is  first  called  with   _state_   set   to
           **PM_HASH_WALK_START** to retrieve the first entry and then repeatedly
           called  with _state_ set to **PM_HASH_WALK_NEXT** to retrieve subsequent
           entries.
    
           **__pmHashWalkCB** provides an alternative method to traverse the hash
           table.  The callback function _cb_ is called with two  arguments,  a
           pointer to the current hash entry and _cdata_ (the latter allows the
           caller  to  pass auxiliary information into the callback function,
           but can be **NULL** if this is not required).  The  callback  function
           must return one of the following **__pmHashWalkState** values:
           **PM_HASH_WALK_NEXT**
               continue the traversal
           **PM_HASH_WALK_STOP**
               terminate the traversal
           **PM_HASH_DELETE_NEXT**
               delete the current node from the hash table and continue the
               traversal
           **PM_HASH_DELETE_STOP**
               delete the current node from the hash table and terminate the
               traversal
    
           **__pmHashFree** will release all storage associated with the hash ta‐
           ble and return the hash table to the empty state, just like after
           **__pmHashInit** has been called.  But **__pmHashFree** cannot free any
           storage attached via the _data_ argument to **__pmHashAdd** calls.  So
           the most appropriate way to clean up the hash table is to first
           traverse the table releasing any _data_ and then call **__pmHashFree**
           as the example below shows.
    
               __pmHashCtl    hash;
    
               __pmHashWalkState
               mycallback(const __pmHashNode *hp, void *cp)
               {
                   (void)cp;
                   if (hp->data) {
                    /*
                     * free() if malloc'd or some datum-specific
                     * method, e.g. __pmFreeProfile()
                     */
                       free(hp->data);
                   }
                   return PM_HASH_WALK_NEXT;
               }
    
               ...
                   __pmHashWalkCB(mycallback, NULL, &hash);
                   __pmHashFree(&hash);
               }
    
           **__pmHashClear** returns the hash table to the empty state, just like
           after **__pmHashInit** has been called.  Beware that **__pmHashClear**
           does not release any storage associated with hash entries, and so
           risks leaking memory, however the following example shows how to
           release all memory in a single traversal of the hash table with
           **__pmHashWalkCB** before calling **__pmHashClear**.
    
               __pmHashCtl    hash;
    
               __pmHashWalkState
               mycallback(const __pmHashNode *hp, void *cp)
               {
                   (void)cp;
                   if (hp->data) {
                    /*
                     * free() if malloc'd or some datum-specific
                     * method, e.g. __pmFreeProfile()
                     */
                       free(hp->data);
                   }
                   /*
                    * compared to the previous example, this difference
                    * is important and frees each hash node
                    */
                   return PM_HASH_DELETE_NEXT;
               }
    
               ...
                   __pmHashWalkCB(mycallback, NULL, &hash);
                   __pmHashClear(&hash);
               }
    


## HASH CONTROL



           The **__pmHashCtl** struct is defined as:
    
               typedef struct __pmHashCtl {
                   int                 nodes;
                   int                 hsize;
                   __pmHashNode        **hash;
                   __pmHashNode        *next;
                   unsigned int        index;
               } __pmHashCtl;
    
           The hash table _hash_ contains _hsize_ entries, each of which may
           point to a linked list of hash nodes.  The total number of hash
           nodes is held in _nodes_.  The _index_ and _next_ fields are used to
           maintain state during hash table walk operations.
    


## HASH NODE



           The **__pmHashNode** struct is defined as:
    
               typedef struct __pmHashNode {
                   struct __pmHashNode *next;
                   unsigned int        key;
                   void                *data;
               } __pmHashNode;
    
           Each node holds the _key_ , the opaque pointer (_data_) and _next_ imple‐
           ments the linked list of hash nodes from each entry in the hash
           table.
    


## DIAGNOSTICS AND RETURN VALUES



           **__pmHashPreAlloc** returns -1 if the hash table is not empty, else a
           value < 0 to indicate an error, probably from calloc(3), that can
           be turned into an error message by calling pmErrStr(3).
    
           **__pmHashAdd** returns 1 for success, else a value < 0 to indicate an
           error, probably from calloc(3).
    
           Return values from **__pmHashDel** are 0 if no matching entry is
           found, else 1 if a matching entry was deleted.
    
           **__pmHashSearch** returns with a pointer to the entry if found, else
           **NULL**.
    
           **__pmHashWalk** returns with a pointer to the next entry if found,
           else **NULL** when all entries have been traversed.
    


* * *