bucketLib.h File Reference

A hash table. Do not use for new code. More...

#include "errMdef.h"
#include "epicsTypes.h"
#include "libComAPI.h"

Include dependency graph for bucketLib.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	item
	Internal: bucket item structure. More...
struct	bucket
	Internal: Hash table structure. More...

Macros
Status values returned by some bucketLib functions
#define	BUCKET_SUCCESS   S_bucket_success
	A synonym for S_bucket_success. More...
#define	S_bucket_success   0
	Success, must be 0. More...
#define	S_bucket_noMemory   (M_bucket | 1) /*Memory allocation failed*/
	Memory allocation failed. More...
#define	S_bucket_idInUse   (M_bucket | 2) /*Identifier already in use*/
	Identifier already in use. More...
#define	S_bucket_uknId   (M_bucket | 3) /*Unknown identifier*/
	Unknown identifier. More...

Typedefs
typedef unsigned	BUCKETID
	Internal: bucket identifier. More...
typedef struct item	ITEM
	Internal: bucket item structure. More...
typedef struct bucket	BUCKET
	Internal: Hash table structure. More...

Enumerations
enum	buckTypeOfId { bidtUnsigned, bidtPointer, bidtString }
	Internal: bucket key type. More...

Functions
LIBCOM_API BUCKET *epicsStdCall	bucketCreate (unsigned nHashTableEntries)
	Creates a new hash table. More...
LIBCOM_API int epicsStdCall	bucketFree (BUCKET *prb)
	Release memory used by a hash table. More...
LIBCOM_API int epicsStdCall	bucketShow (BUCKET *prb)
	Display information about a hash table. More...
LIBCOM_API int epicsStdCall	bucketAddItemUnsignedId (BUCKET *prb, const unsigned *pId, const void *pApp)
	Add an item identified by an unsigned int to the table. More...
LIBCOM_API int epicsStdCall	bucketAddItemPointerId (BUCKET *prb, void *const *pId, const void *pApp)
	Add an item identified by a pointer to the table. More...
LIBCOM_API int epicsStdCall	bucketAddItemStringId (BUCKET *prb, const char *pId, const void *pApp)
	Add an item identified by a string to the table. More...
LIBCOM_API int epicsStdCall	bucketRemoveItemUnsignedId (BUCKET *prb, const unsigned *pId)
	Remove an item identified by a string from the table. More...
LIBCOM_API int epicsStdCall	bucketRemoveItemPointerId (BUCKET *prb, void *const *pId)
	Remove an item identified by a pointer from the table. More...
LIBCOM_API int epicsStdCall	bucketRemoveItemStringId (BUCKET *prb, const char *pId)
	Remove an item identified by a string from the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupItemUnsignedId (BUCKET *prb, const unsigned *pId)
	Find an item identified by an unsigned int in the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupItemPointerId (BUCKET *prb, void *const *pId)
	Find an item identified by a pointer in the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupItemStringId (BUCKET *prb, const char *pId)
	Find an item identified by a string in the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupAndRemoveItemUnsignedId (BUCKET *prb, const unsigned *pId)
	Find and delete an item identified by an unsigned int from the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupAndRemoveItemPointerId (BUCKET *prb, void *const *pId)
	Find and delete an item identified by a pointer from the table. More...
LIBCOM_API void *epicsStdCall	bucketLookupAndRemoveItemStringId (BUCKET *prb, const char *pId)
	Find and delete an item identified by a string from the table. More...

Detailed Description

A hash table. Do not use for new code.

Author

Jeffrey O. Hill

A hash table for which keys may be unsigned integers, pointers, or strings. This API is used by the IOC's Channel Access Server, but it should not be used by other code.

Note

Storage for identifiers must persist until an item is deleted

Definition in file bucketLib.h.

Macro Definition Documentation

#define BUCKET_SUCCESS   S_bucket_success

A synonym for S_bucket_success.

Definition at line 175 of file bucketLib.h.

#define S_bucket_idInUse   (M_bucket | 2) /*Identifier already in use*/

Identifier already in use.

Definition at line 187 of file bucketLib.h.

#define S_bucket_noMemory   (M_bucket | 1) /*Memory allocation failed*/

Memory allocation failed.

Definition at line 183 of file bucketLib.h.

#define S_bucket_success   0

Success, must be 0.

Definition at line 179 of file bucketLib.h.

#define S_bucket_uknId   (M_bucket | 3) /*Unknown identifier*/

Unknown identifier.

Definition at line 191 of file bucketLib.h.

Typedef Documentation

typedef struct bucket BUCKET

Internal: Hash table structure.

typedef unsigned BUCKETID

Internal: bucket identifier.

Definition at line 34 of file bucketLib.h.

typedef struct item ITEM

Internal: bucket item structure.

Enumeration Type Documentation

enum buckTypeOfId

Internal: bucket key type.

Enumerator
bidtUnsigned
bidtPointer
bidtString

Definition at line 37 of file bucketLib.h.

{bidtUnsigned, bidtPointer, bidtString} buckTypeOfId;

Function Documentation

LIBCOM_API int epicsStdCall bucketAddItemPointerId	(	BUCKET *	prb,
		void *const *	pId,
		const void *	pApp
	)

Add an item identified by a pointer to the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier
*pApp	Pointer to the payload

Returns

Status value

Definition at line 313 of file bucketLib.c.

{
    return bucketAddItem(prb, &BSET[bidtPointer], pId, pApp);
}

LIBCOM_API int epicsStdCall bucketAddItemStringId	(	BUCKET *	prb,
		const char *	pId,
		const void *	pApp
	)

Add an item identified by a string to the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier
*pApp	Pointer to the payload

Returns

Status value

Definition at line 318 of file bucketLib.c.

{
    return bucketAddItem(prb, &BSET[bidtString], pId, pApp);
}

LIBCOM_API int epicsStdCall bucketAddItemUnsignedId	(	BUCKET *	prb,
		const unsigned *	pId,
		const void *	pApp
	)

Add an item identified by an unsigned int to the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier
*pApp	Pointer to the payload

Returns

Status value

Definition at line 308 of file bucketLib.c.

{
    return bucketAddItem(prb, &BSET[bidtUnsigned], pId, pApp);
}

LIBCOM_API BUCKET* epicsStdCall bucketCreate

(

unsigned

nHashTableEntries

)

Creates a new hash table.

Parameters

nHashTableEntries

Table size

Returns

Pointer to the newly created hash table, or NULL.

Definition at line 218 of file bucketLib.c.

{
    BUCKETID    mask;
    unsigned    nbits;
    BUCKET      *pb;

    /*
     * no absurd sized buckets
     */
    if (nHashTableEntries<=1) {
        fprintf (stderr, "Tiny bucket create failed\n");
        return NULL;
    }

    /*
     * count the number of bits in the bucket id
     */
    if ( BUCKETID_BIT_WIDTH > 0 ) {
        for (nbits=0; nbits<BUCKETID_BIT_WIDTH; nbits++) {
            mask = (1<<nbits) - 1;
            if ( ((nHashTableEntries-1) & ~mask) == 0){
                break;
            }
        }
    }
    else {
        mask = 0;
        nbits = 0;
    }

    /*
     * indexWidth must be specified at least one
     * bit less than the bit size of type BUCKETID
     */
    if (nbits>=BUCKETID_BIT_WIDTH) {
        fprintf (
            stderr,
        "%s at %d: Requested index width=%d to large. max=%ld\n",
            __FILE__,
            __LINE__,
            nbits,
            (long)(BUCKETID_BIT_WIDTH-1));
        return NULL;
    }

    pb = (BUCKET *) calloc(1, sizeof(*pb));
    if (!pb) {
        return pb;
    }

    pb->hashIdMask = mask;
    pb->hashIdNBits = nbits;
    freeListInitPvt(&pb->freeListPVT, sizeof(ITEM), 1024);

    pb->pTable = (ITEM **) calloc (mask+1, sizeof(*pb->pTable));
    if (!pb->pTable) {
        freeListCleanup(pb->freeListPVT);
        free (pb);
        return NULL;
    }
    return pb;
}

LIBCOM_API int epicsStdCall bucketFree

(

BUCKET *

prb

)

Release memory used by a hash table.

Parameters

*prb	Pointer to the hash table

Returns

S_bucket_success

Note

All items must be deleted from the hash table before calling this.

Definition at line 285 of file bucketLib.c.

{
    /*
     * deleting a bucket with entries in use
     * will cause memory leaks and is not allowed
     */
    assert (prb->nInUse==0);

    /*
     * free the free list
     */
    freeListCleanup(prb->freeListPVT);
    free (prb->pTable);
    free (prb);

    return S_bucket_success;
}

LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemPointerId	(	BUCKET *	prb,
		void *const *	pId
	)

Find and delete an item identified by a pointer from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 401 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtPointer], pId);
}

LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemStringId	(	BUCKET *	prb,
		const char *	pId
	)

Find and delete an item identified by a string from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 405 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtString], pId);
}

LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemUnsignedId	(	BUCKET *	prb,
		const unsigned *	pId
	)

Find and delete an item identified by an unsigned int from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 397 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtUnsigned], pId);
}

LIBCOM_API void* epicsStdCall bucketLookupItemPointerId	(	BUCKET *	prb,
		void *const *	pId
	)

Find an item identified by a pointer in the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 440 of file bucketLib.c.

{
    return bucketLookupItem(prb, &BSET[bidtPointer], pId);
}

LIBCOM_API void* epicsStdCall bucketLookupItemStringId	(	BUCKET *	prb,
		const char *	pId
	)

Find an item identified by a string in the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 445 of file bucketLib.c.

{
    return bucketLookupItem(prb, &BSET[bidtString], pId);
}

LIBCOM_API void* epicsStdCall bucketLookupItemUnsignedId	(	BUCKET *	prb,
		const unsigned *	pId
	)

Find an item identified by an unsigned int in the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Item's payload pointer, or NULL if not found

Definition at line 435 of file bucketLib.c.

{
    return bucketLookupItem(prb, &BSET[bidtUnsigned], pId);
}

LIBCOM_API int epicsStdCall bucketRemoveItemPointerId	(	BUCKET *	prb,
		void *const *	pId
	)

Remove an item identified by a pointer from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Status value

Definition at line 420 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtPointer], pId)?S_bucket_success:S_bucket_uknId;
}

LIBCOM_API int epicsStdCall bucketRemoveItemStringId	(	BUCKET *	prb,
		const char *	pId
	)

Remove an item identified by a string from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Status value

Definition at line 425 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtString], pId)?S_bucket_success:S_bucket_uknId;
}

LIBCOM_API int epicsStdCall bucketRemoveItemUnsignedId	(	BUCKET *	prb,
		const unsigned *	pId
	)

Remove an item identified by a string from the table.

Parameters

*prb	Pointer to the hash table
*pId	Pointer to the identifier

Returns

Status value

Definition at line 415 of file bucketLib.c.

{
    return bucketLookupAndRemoveItem(prb, &BSET[bidtUnsigned], pId)?S_bucket_success:S_bucket_uknId;
}

LIBCOM_API int epicsStdCall bucketShow

(

BUCKET *

prb

)

Display information about a hash table.

Parameters

*prb	Pointer to the hash table

Returns

S_bucket_success

Definition at line 476 of file bucketLib.c.

{
    ITEM        **ppi;
    ITEM        *pi;
    unsigned    nElem;
    double      X;
    double      XX;
    double      mean;
    double      stdDev;
    unsigned    count;
    unsigned    maxEntries;

    printf( "    Bucket entries in use = %d bytes in use = %ld\n",
        pb->nInUse,
        (long) (sizeof(*pb)+(pb->hashIdMask+1)*
            sizeof(ITEM *)+pb->nInUse*sizeof(ITEM)));

    ppi = pb->pTable;
    nElem = pb->hashIdMask+1;
    X = 0.0;
    XX = 0.0;
    maxEntries = 0;
    while (ppi < &pb->pTable[nElem]) {
        pi = *ppi;
        count = 0;
        while (pi) {
            count++;
            pi = pi->pItem;
        }
        X += count;
        XX += count*count;
        if (count > maxEntries) maxEntries = count;
        ppi++;
    }

    mean = X/nElem;
    stdDev = sqrt(XX/nElem - mean*mean);
    printf( "    Bucket entries/hash id - mean = %f std dev = %f max = %d\n",
        mean,
        stdDev,
        maxEntries);

    return S_bucket_success;
}