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