This is Unofficial EPICS BASE Doxygen Site
Classes | Macros | Typedefs | Functions
bucketLib.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include "epicsAssert.h"
#include "freeList.h"
#include "bucketLib.h"
+ Include dependency graph for bucketLib.c:

Go to the source code of this file.

Classes

struct  bucketSET
 

Macros

#define BUCKETID_BIT_WIDTH   (sizeof(BUCKETID)*CHAR_BIT)
 
#define BUCKET_MAX_WIDTH   12
 

Typedefs

typedef BUCKETID bucketHash(BUCKET *pb, const void *pId)
 
typedef ITEM ** bucketCompare(ITEM **ppi, const void *pId)
 

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 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 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...
 
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 int epicsStdCall bucketShow (BUCKET *pb)
 Display information about a hash table. More...
 

Macro Definition Documentation

#define BUCKET_MAX_WIDTH   12

Definition at line 70 of file bucketLib.c.

#define BUCKETID_BIT_WIDTH   (sizeof(BUCKETID)*CHAR_BIT)

Definition at line 65 of file bucketLib.c.

Typedef Documentation

typedef ITEM** bucketCompare(ITEM **ppi, const void *pId)

Definition at line 35 of file bucketLib.c.

typedef BUCKETID bucketHash(BUCKET *pb, const void *pId)

Definition at line 34 of file bucketLib.c.

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
*prbPointer to the hash table
*pIdPointer to the identifier
*pAppPointer to the payload
Returns
Status value

Definition at line 313 of file bucketLib.c.

314 {
315  return bucketAddItem(prb, &BSET[bidtPointer], pId, pApp);
316 }
LIBCOM_API int epicsStdCall bucketAddItemStringId ( BUCKET *  prb,
const char *  pId,
const void *  pApp 
)

Add an item identified by a string to the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
*pAppPointer to the payload
Returns
Status value

Definition at line 318 of file bucketLib.c.

319 {
320  return bucketAddItem(prb, &BSET[bidtString], pId, pApp);
321 }
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
*prbPointer to the hash table
*pIdPointer to the identifier
*pAppPointer to the payload
Returns
Status value

Definition at line 308 of file bucketLib.c.

309 {
310  return bucketAddItem(prb, &BSET[bidtUnsigned], pId, pApp);
311 }
LIBCOM_API BUCKET* epicsStdCall bucketCreate ( unsigned  nHashTableEntries)

Creates a new hash table.

Parameters
nHashTableEntriesTable size
Returns
Pointer to the newly created hash table, or NULL.

Definition at line 218 of file bucketLib.c.

219 {
220  BUCKETID mask;
221  unsigned nbits;
222  BUCKET *pb;
223 
224  /*
225  * no absurd sized buckets
226  */
227  if (nHashTableEntries<=1) {
228  fprintf (stderr, "Tiny bucket create failed\n");
229  return NULL;
230  }
231 
232  /*
233  * count the number of bits in the bucket id
234  */
235  if ( BUCKETID_BIT_WIDTH > 0 ) {
236  for (nbits=0; nbits<BUCKETID_BIT_WIDTH; nbits++) {
237  mask = (1<<nbits) - 1;
238  if ( ((nHashTableEntries-1) & ~mask) == 0){
239  break;
240  }
241  }
242  }
243  else {
244  mask = 0;
245  nbits = 0;
246  }
247 
248  /*
249  * indexWidth must be specified at least one
250  * bit less than the bit size of type BUCKETID
251  */
252  if (nbits>=BUCKETID_BIT_WIDTH) {
253  fprintf (
254  stderr,
255  "%s at %d: Requested index width=%d to large. max=%ld\n",
256  __FILE__,
257  __LINE__,
258  nbits,
259  (long)(BUCKETID_BIT_WIDTH-1));
260  return NULL;
261  }
262 
263  pb = (BUCKET *) calloc(1, sizeof(*pb));
264  if (!pb) {
265  return pb;
266  }
267 
268  pb->hashIdMask = mask;
269  pb->hashIdNBits = nbits;
270  freeListInitPvt(&pb->freeListPVT, sizeof(ITEM), 1024);
271 
272  pb->pTable = (ITEM **) calloc (mask+1, sizeof(*pb->pTable));
273  if (!pb->pTable) {
274  freeListCleanup(pb->freeListPVT);
275  free (pb);
276  return NULL;
277  }
278  return pb;
279 }
bucket::hashIdMask
unsigned hashIdMask
Definition: bucketLib.h:51
bucket::hashIdNBits
unsigned hashIdNBits
Definition: bucketLib.h:52
item
Internal: bucket item structure.
Definition: bucketLib.h:40
BUCKETID_BIT_WIDTH
#define BUCKETID_BIT_WIDTH
Definition: bucketLib.c:65
NULL
#define NULL
Definition: catime.c:38
bucket::pTable
ITEM ** pTable
Definition: bucketLib.h:49
freeListInitPvt
LIBCOM_API void epicsStdCall freeListInitPvt(void **ppvt, int size, int nmalloc)
Definition: freeListLib.c:44
bucket::freeListPVT
void * freeListPVT
Definition: bucketLib.h:50
freeListCleanup
LIBCOM_API void epicsStdCall freeListCleanup(void *pvt)
Definition: freeListLib.c:152
BUCKETID
unsigned BUCKETID
Internal: bucket identifier.
Definition: bucketLib.h:34
stderr
#define stderr
Definition: epicsStdio.h:32
bucket
Internal: Hash table structure.
Definition: bucketLib.h:48
LIBCOM_API int epicsStdCall bucketFree ( BUCKET *  prb)

Release memory used by a hash table.

Parameters
*prbPointer 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.

286 {
287  /*
288  * deleting a bucket with entries in use
289  * will cause memory leaks and is not allowed
290  */
291  assert (prb->nInUse==0);
292 
293  /*
294  * free the free list
295  */
296  freeListCleanup(prb->freeListPVT);
297  free (prb->pTable);
298  free (prb);
299 
300  return S_bucket_success;
301 }
bucket::nInUse
unsigned nInUse
Definition: bucketLib.h:53
assert
#define assert(exp)
Declare that a condition should be true.
Definition: epicsAssert.h:70
bucket::pTable
ITEM ** pTable
Definition: bucketLib.h:49
bucket::freeListPVT
void * freeListPVT
Definition: bucketLib.h:50
freeListCleanup
LIBCOM_API void epicsStdCall freeListCleanup(void *pvt)
Definition: freeListLib.c:152
S_bucket_success
#define S_bucket_success
Success, must be 0.
Definition: bucketLib.h:179
LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemPointerId ( BUCKET *  prb,
void *const *  pId 
)

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

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 401 of file bucketLib.c.

402 {
403  return bucketLookupAndRemoveItem(prb, &BSET[bidtPointer], pId);
404 }
LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemStringId ( BUCKET *  prb,
const char *  pId 
)

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

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 405 of file bucketLib.c.

406 {
407  return bucketLookupAndRemoveItem(prb, &BSET[bidtString], pId);
408 }
LIBCOM_API void* epicsStdCall bucketLookupAndRemoveItemUnsignedId ( BUCKET *  prb,
const unsigned *  pId 
)

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

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 397 of file bucketLib.c.

398 {
399  return bucketLookupAndRemoveItem(prb, &BSET[bidtUnsigned], pId);
400 }
LIBCOM_API void* epicsStdCall bucketLookupItemPointerId ( BUCKET *  prb,
void *const *  pId 
)

Find an item identified by a pointer in the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 440 of file bucketLib.c.

441 {
442  return bucketLookupItem(prb, &BSET[bidtPointer], pId);
443 }
LIBCOM_API void* epicsStdCall bucketLookupItemStringId ( BUCKET *  prb,
const char *  pId 
)

Find an item identified by a string in the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 445 of file bucketLib.c.

446 {
447  return bucketLookupItem(prb, &BSET[bidtString], pId);
448 }
LIBCOM_API void* epicsStdCall bucketLookupItemUnsignedId ( BUCKET *  prb,
const unsigned *  pId 
)

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

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Item's payload pointer, or NULL if not found

Definition at line 435 of file bucketLib.c.

436 {
437  return bucketLookupItem(prb, &BSET[bidtUnsigned], pId);
438 }
LIBCOM_API int epicsStdCall bucketRemoveItemPointerId ( BUCKET *  prb,
void *const *  pId 
)

Remove an item identified by a pointer from the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Status value

Definition at line 420 of file bucketLib.c.

421 {
422  return bucketLookupAndRemoveItem(prb, &BSET[bidtPointer], pId)?S_bucket_success:S_bucket_uknId;
423 }
S_bucket_uknId
#define S_bucket_uknId
Unknown identifier.
Definition: bucketLib.h:191
S_bucket_success
#define S_bucket_success
Success, must be 0.
Definition: bucketLib.h:179
LIBCOM_API int epicsStdCall bucketRemoveItemStringId ( BUCKET *  prb,
const char *  pId 
)

Remove an item identified by a string from the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Status value

Definition at line 425 of file bucketLib.c.

426 {
427  return bucketLookupAndRemoveItem(prb, &BSET[bidtString], pId)?S_bucket_success:S_bucket_uknId;
428 }
S_bucket_uknId
#define S_bucket_uknId
Unknown identifier.
Definition: bucketLib.h:191
S_bucket_success
#define S_bucket_success
Success, must be 0.
Definition: bucketLib.h:179
LIBCOM_API int epicsStdCall bucketRemoveItemUnsignedId ( BUCKET *  prb,
const unsigned *  pId 
)

Remove an item identified by a string from the table.

Parameters
*prbPointer to the hash table
*pIdPointer to the identifier
Returns
Status value

Definition at line 415 of file bucketLib.c.

416 {
417  return bucketLookupAndRemoveItem(prb, &BSET[bidtUnsigned], pId)?S_bucket_success:S_bucket_uknId;
418 }
S_bucket_uknId
#define S_bucket_uknId
Unknown identifier.
Definition: bucketLib.h:191
S_bucket_success
#define S_bucket_success
Success, must be 0.
Definition: bucketLib.h:179
LIBCOM_API int epicsStdCall bucketShow ( BUCKET *  prb)

Display information about a hash table.

Parameters
*prbPointer to the hash table
Returns
S_bucket_success

Definition at line 476 of file bucketLib.c.

477 {
478  ITEM **ppi;
479  ITEM *pi;
480  unsigned nElem;
481  double X;
482  double XX;
483  double mean;
484  double stdDev;
485  unsigned count;
486  unsigned maxEntries;
487 
488  printf( " Bucket entries in use = %d bytes in use = %ld\n",
489  pb->nInUse,
490  (long) (sizeof(*pb)+(pb->hashIdMask+1)*
491  sizeof(ITEM *)+pb->nInUse*sizeof(ITEM)));
492 
493  ppi = pb->pTable;
494  nElem = pb->hashIdMask+1;
495  X = 0.0;
496  XX = 0.0;
497  maxEntries = 0;
498  while (ppi < &pb->pTable[nElem]) {
499  pi = *ppi;
500  count = 0;
501  while (pi) {
502  count++;
503  pi = pi->pItem;
504  }
505  X += count;
506  XX += count*count;
507  if (count > maxEntries) maxEntries = count;
508  ppi++;
509  }
510 
511  mean = X/nElem;
512  stdDev = sqrt(XX/nElem - mean*mean);
513  printf( " Bucket entries/hash id - mean = %f std dev = %f max = %d\n",
514  mean,
515  stdDev,
516  maxEntries);
517 
518  return S_bucket_success;
519 }
item::pItem
struct item * pItem
Definition: bucketLib.h:41
bucket::nInUse
unsigned nInUse
Definition: bucketLib.h:53
bucket::hashIdMask
unsigned hashIdMask
Definition: bucketLib.h:51
item
Internal: bucket item structure.
Definition: bucketLib.h:40
printf
#define printf
Definition: epicsStdio.h:41
bucket::pTable
ITEM ** pTable
Definition: bucketLib.h:49
S_bucket_success
#define S_bucket_success
Success, must be 0.
Definition: bucketLib.h:179