pvector/pvector.h

   1 #ifndef pvector_H
   2 #define pvector_H
   3
   4 /**
   5  * A pvector is a dynamic pointer array implemented as an access tree
   6  * of index pages of 256 pointers.
   7  */
   8
   9 //#include <stdint.h>
  10
  11 /*!
  12  * Type: pvector_page
  13  *
  14  * A pvector_page is an array of 256 void* items.
  15  */
  16 typedef void* pvector_page[256];
  17
  18 /*!
  19  * Type: pvector_index
  20  *
  21  * A pvector index is ether viewed in whole as an unsigned 64-bit
  22  * integer, or in levels as 8 unsigned char level indexes. This
  23  * implementation assumes LE integer layout.
  24  */
  25 typedef union {
  26     unsigned int whole;
  27     unsigned char level[4];
  28 } pvector_index;
  29
  30 /*!
  31  * Type: pvector
  32  *
  33  * A pvector is a compound of a size and a pvector_page pointer, which
  34  * when non-null points out the top-most page of the pvector. The
  35  * number of levels is derived from its size with level 0 being the
  36  * leaf level of actual content. E.g., a pvector larger than 256
  37  * items, has at least two levels, and generally N levels may span up
  38  * to 256^N content entries.
  39  */
  40 typedef struct _pvector {
  41     unsigned int size;     //!< Limit for the logical entries[]
  42     pvector_page *entries; //!< Pointer to entries indexing
  43 } pvector;
  44
  45 // Number of page levels for size S
  46 #define PV_LEVELS(S) ((int)(( 39 - __builtin_clz( ((S)-1) | 1) ) / 8 ))
  47
  48 #define PV_LEVEL_SIZE(S) ((int)(exp( 256, (S) )))
  49
  50 // The indexing part for level part p in index i
  51 #define PV_PART(p,i) (((unsigned char*)&i)[p])
  52
  53 /*!
  54  * Function: int pvector_resize( pvector *pv,unsigned int new_size,
  55  *                               int (*reclaim)(pvector *,int,void*) )
  56  * \param pv
  57  * \param new_size
  58  * \param reclaim
  59  *
  60  * Tries to resize the given pvector to a new size. This may result in
  61  * the introduction or removal of indexing pages, so that the leveling
  62  * is consistent with the pvector size. Thus, if it grows into a new
  63  * 256^N level, then one or more new upper level pages are inserted as
  64  * needed. If it shrinks below the current level, then top-level pages
  65  * are remove.
  66  *
  67  * Also, if the new size is smaller than currently, then the now
  68  * excess tail of entries is scanned for any used slots and the given
  69  * reclaim function is invoked successively for these. The reclaim
  70  * function must, in addition to memory-managing the entry, return 0
  71  * upon success and non-zero to veto the attempted pvector size
  72  * change.
  73  *
  74  * The pvector_resize function returns 0 on success, with the size
  75  * duly changed. Otherwise the function retains the current size and
  76  * returns -index-1 for the index of the veto-ed entry.
  77  */
  78 int pvector_resize(
  79     pvector *pv,unsigned int new_size,
  80     int (*reclaim)(pvector *,int,void*) );
  81
  82 /*!
  83  * Function: void **pvector_entry(pvector *pv,unsigned int index)
  84  * \param pv - the pvector record
  85  * \param index - the slot index
  86  *
  87  * [pgix,epix] = modulo( index, pv->page );
  88  *
  89  * \returns a direct pointer to the slot of the given index in the
  90  * array, or 0 if the index is beyond the array limits (0-limit). Note
  91  * that slot pointers are only valid while the pvector size is
  92  * unchanged.
  93  */
  94 extern void **pvector_entry(pvector *pv,unsigned int index);
  95
  96 /*!
  97  * Function: unsigned int pvector_size(pvector *pv)
  98  * \param pv - the pvector record
  99  * \returns the size of the pvector.
 100  */
 101 inline unsigned int pvector_size(pvector *pv) {
 102     return pv->size;
 103 }
 104
 105 void pvector_set(pvector *pv,unsigned int index,void *value);
 106
 107 void *pvector_get(pvector *pv,unsigned int index);
 108
 109 #endif