'\"macro stdmacro
.\"
.\" Copyright (c) 2024 Ken McDonell.  All Rights Reserved.
.\"
.\" This program is free software; you can redistribute it and/or modify it
.\" under the terms of the GNU General Public License as published by the
.\" Free Software Foundation; either version 2 of the License, or (at your
.\" option) any later version.
.\"
.\" This program is distributed in the hope that it will be useful, but
.\" WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
.\" or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
.\" for more details.
.\"
.\"
.TH PMHASH 3 "PCP" "Performance Co-Pilot"
.ds xM pmhash
.SH NAME
\f3__pmHashInit\f1,
\f3__pmHashPreAlloc\f1,
\f3__pmHashAdd\f1,
\f3__pmHashDel\f1,
\f3__pmHashSearch\f1,
\f3__pmHashWalk\f1,
\f3__pmHashWalkCB\f1,
\f3__pmHashFree\f1,
\f3__pmHashClear\f1 \- general purpose hashing routines
.SH "C SYNOPSIS"
.ft 3
#include <pcp/pmapi.h>
.br
#include <pcp/libpcp.h>
.hy 0
.ad l
.sp
void __pmHashInit(__pmHashCtl *\fIhcp\fP);
.br
int __pmHashPreAlloc(int \fIhsize\fP, __pmHashCtl *\fIhcp\fP);
.br
int __pmHashAdd(unsigned int \fIkey\fP, void *\fIdata\fP, __pmHashCtl *\fIhcp\fP);
.br
int __pmHashDel(unsigned int \fIkey\fP, void *\fIdata\fP, __pmHashCtl *\fIhcp\fP);
.br
__pmHashNode *__pmHashSearch(unsigned int \fIkey\fP, __pmHashCtl *\fIhcp\fP);
.br
__pmHashNode *__pmHashWalk(__pmHashCtl *\fIhcp\fP, __pmHashWalkState \fIstate\fP);
.br
void __pmHashWalkCB(__pmHashWalkCallback \fIcb\fP, void *\fIcdata\fP, const __pmHashCtl *\fIhcp\fP);
.br
void __pmHashFree(__pmHashCtl *\fIhcp\fP);
.br
void __pmHashClear(__pmHashCtl *\fIhcp\fP);
.hy
.ad
.sp
cc ... \-lpcp
.ft 1
.SH CAVEAT
This documentation is intended for internal Performance Co-Pilot
(PCP) developer use.
.PP
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.
.SH DESCRIPTION
.de CR
.ie t \f(CR\\$1\fR\\$2
.el \fI\\$1\fR\\$2
..
The
.B __pmHash
group of routines implement a generalized suite of linear hashing services
based on a
.I key
that is an unsigned int and
.I data
that is an opaque pointer to information the caller wishes to associate
with
.IR key .
.PP
The data type of
.I key
makes is suitable for hashed access based on metric identifier (\c
.BR pmID ),
instance domain number (\c
.BR pmInDom )
or internal instance identifiers within an instance domain.
.PP
Multiple hash tables may exist, each identified by a hash control
struct (\c
.BR __pmHashCtl )
.B hcp
which is declared by the caller and initialized by calling
.BR __pmHashInit .
Refer to the
.B "HASH CONTROL"
and
.B "HASH NODE"
sections below for more information on the hash table internal data
structures.
.PP
The hash table is initially empty but
dynamically grows by approximate 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
.B __pmHashPreAlloc
with an initial hash table size of
.I hsize
entries, but this must be done after calling
.B __pmHashInit
and before any entries are added.
.PP
Entries are added to a hash table by calling
.BR __pmHashAdd .
The opaque
.I data
is typically a pointer to a block of additional information to be associated
with the
.IR key ,
although it may be
.B NULL
if there is no additional information required or currently available.
.PP
Although usually not required, duplicate
.I key
values can be stored in a hash table and
.B __pmHashAdd
will silently add these (presumably with a different
.I data
pointer).
If uniqueness of
.IR key s
is required, it is necessary to call
.B __pmHashSearch
first to determine that there is no entry for
.IR key ,
before calling
.BR __pmHashAdd .
.PP
Entries may be removed from a hash table using
.B __pmHashDel
where the entry to be deleted is the
.I first
one with a matching
.I key
and
.I data
pointer.
See the note above about duplicate keys to understand why
the
.I data
parameter is needed.
.PP
.B __pmHashSearch
finds the
.I first
entry with a matching
.IR key .
If duplicate keys are being stored, then the caller will
have to follow the
.IR hp -> next
chain looking for additional entries with the same
.IR key .
Refer to the
.B "HASH CONTROL"
and
.B "HASH NODE"
sections below for more information on the hash table internal data
structures.
.PP
.B __pmHashWalk
provides a stateful interface to walk each node in the hash table.
It is first called with
.I state
set to
.B PM_HASH_WALK_START
to retrieve the first entry
and then repeatedly called with
.I state
set to
.B PM_HASH_WALK_NEXT
to retrieve subsequent entries.
.PP
.B __pmHashWalkCB
provides an alternative method to traverse the hash table.
The callback function
.I cb
is called with two arguments, a pointer to the current hash entry and
.I cdata
(the latter allows the caller to pass auxiliary
information into the callback function, but can be
.B NULL
if this is not required).
The callback function must return one of the following
.B __pmHashWalkState
values:
.PD 0
.IP \fBPM_HASH_WALK_NEXT\fP 4n
continue the traversal
.IP \fBPM_HASH_WALK_STOP\fP
terminate the traversal
.IP \fBPM_HASH_DELETE_NEXT\fP
delete the current node from the hash table and continue the traversal
.IP \fBPM_HASH_DELETE_STOP\fP
delete the current node from the hash table and terminate the traversal
.PD
.PP
.B __pmHashFree
will release all storage associated with the hash table
and return the hash table to the empty state, just like after
.B __pmHashInit
has been called.
But
.B __pmHashFree
cannot free any storage attached via the
.I data
argument to
.B __pmHashAdd
calls.
So the most appropriate way to clean up the hash table is to first
traverse the table releasing any
.I data
and then call
.B __pmHashFree
as the example below shows.
.PP
.ft CR
.in +4n
.nf
__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);
}

.fi
.in -4n
.ft
.PP
.B __pmHashClear
returns the hash table to the empty state, just like after
.B __pmHashInit
has been called.
Beware that
.B __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
.B __pmHashWalkCB
before calling
.BR __pmHashClear .
.PP
.ft CR
.in +4n
.nf
__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);
}

.fi
.in -4n
.ft
.SH HASH CONTROL
The
.B __pmHashCtl
struct is defined as:
.PP
.ft CR
.in +4n
.nf
typedef struct __pmHashCtl {
    int                 nodes;
    int                 hsize;
    __pmHashNode        **hash;
    __pmHashNode        *next;
    unsigned int        index;
} __pmHashCtl;
.fi
.in -4n
.ft
.PP
The hash table
.I hash
contains
.I hsize
entries, each of which may point to a linked list of hash nodes.
The total number of hash nodes is held in
.IR nodes .
The
.I index
and
.I next
fields are used to maintain state during hash table walk operations.
.SH HASH NODE
The
.B __pmHashNode
struct is defined as:
.PP
.ft CR
.in +4n
.nf
typedef struct __pmHashNode {
    struct __pmHashNode *next;
    unsigned int        key;
    void                *data;
} __pmHashNode;
.fi
.in -4n
.ft
.PP
Each node holds the
.IR key ,
the opaque pointer (\c
.IR data )
and
.I next
implements the linked list of hash nodes from each entry in the hash table.
.SH DIAGNOSTICS AND RETURN VALUES
.B __pmHashPreAlloc
returns -1 if the hash table is not empty, else a value < 0 to
indicate an error, probably from
.BR calloc (3),
that can be turned into an error message by calling
.BR pmErrStr (3).
.PP
.B __pmHashAdd
returns 1 for success, else a value < 0 to
indicate an error, probably from
.BR calloc (3).
.PP
Return values from
.B __pmHashDel
are 0 if no matching entry is found, else 1 if a matching entry
was deleted.
.PP
.B __pmHashSearch
returns with a pointer to the entry if found, else
.BR NULL .
.PP
.B __pmHashWalk
returns with a pointer to the next entry if found, else
.B NULL
when all entries have been traversed.
.SH SEE ALSO
.BR PMAPI (3),
.BR calloc (3),
.BR free (3)
and
.BR pmErrStr (3).

.\" control lines for scripts/man-spell
.\" +ok+ stateful
.\" +ok+ __pmHash {from The __pmHash group ...} pmhash {from .xM}
.\" +ok+ hp mycallback {from example}