|
HTML rendering created 2025-02-02 by Michael Kerrisk, author of The Linux Programming Interface. For details of in-depth Linux/UNIX system programming training courses that I teach, look here. Hosting by jambit GmbH. |
|
|
NAME | C SYNOPSIS | CAVEAT | DESCRIPTION | HASH CONTROL | HASH NODE | DIAGNOSTICS AND RETURN VALUES | SEE ALSO | COLOPHON |
|
|
|
PMHASH(3) Library Functions Manual PMHASH(3)
__pmHashInit, __pmHashPreAlloc, __pmHashAdd, __pmHashDel,
__pmHashSearch, __pmHashWalk, __pmHashWalkCB, __pmHashFree,
__pmHashClear - general purpose hashing routines
#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
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.
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 keys 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);
}
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.
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.
__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.
PMAPI(3), calloc(3), free(3) and pmErrStr(3).
This page is part of the PCP (Performance Co-Pilot) project. In‐
formation about the project can be found at ⟨http://www.pcp.io/⟩.
If you have a bug report for this manual page, send it to
pcp@groups.io. This page was obtained from the project's upstream
Git repository ⟨https://github.com/performancecopilot/pcp.git⟩ on
2025-02-02. (At that time, the date of the most recent commit
that was found in the repository was 2025-01-30.) If you discover
any rendering problems in this HTML version of the page, or you
believe there is a better or more up-to-date source for the page,
or you have corrections or improvements to the information in this
COLOPHON (which is not part of the original manual page), send a
mail to man-pages@man7.org
Performance Co-Pilot PCP PMHASH(3)
|
HTML rendering created 2025-02-02 by Michael Kerrisk, author of The Linux Programming Interface. For details of in-depth Linux/UNIX system programming training courses that I teach, look here. Hosting by jambit GmbH. |
|