pvector/qvector.h

   1 #ifndef qvector_H
   2 #define qvector_H
   3
   4 /**
   5  * A qvector is a dynamic pointer array implemented as an access tree
   6  * of index pages. The indexing is done using "unsigned long" indexes.
   7  */
   8
   9 /*!
  10  * Type: qvector_index
  11  * This is the general indexing used for qvector access.
  12  */
  13 typedef unsigned long qvector_index;
  14
  15 /*!
  16  * Macro: QV_INDEX_BITS
  17  * This defines the number of bits of a qvector index
  18  */
  19 #define QV_INDEX_BITS sizeof( qvector_index )
  20
  21 /*!
  22  * Macro: QV_LEVEL_BITS
  23  * This defines the number of bits in the indexing bit field.
  24  */
  25 #define QV_LEVEL_BITS 4
  26
  27 /*!
  28  * Macro: QV_INDEX_FIELDS
  29  * This defines the number of bit fields in an qvector index
  30  */
  31 #define QV_INDEX_FIELDS ( ( QV_INDEX_BITS - 1 ) / QV_LEVEL_BITS + 1 )
  32
  33 /*!
  34  * Macro: QV_SLOTS
  35  * This defines the number of slots spanned by an index level
  36  */
  37 #define QV_SLOTS ( 1 << QV_LEVEL_BITS )
  38
  39 /*!
  40  * Type: qvector_page
  41  *
  42  * A qvector_page is an array of 16 void* items.
  43  */
  44 typedef void* qvector_page[ QV_SLOTS ];
  45
  46 /*!
  47  * Type: qvector_field
  48  * This is QV_LEVEL_BITS size bit field
  49  */
  50 typedef struct { int bits:QV_LEVEL_BITS; } qvector_field;
  51
  52 /*!
  53  * Type: qvector_indexing
  54  *
  55  * A qvector index is ether viewed in whole as an QV_INDEX_BITS wide
  56  * unsigned, or in levels as a packed array of qvector_field index
  57  * parts. This implementation assumes LE integer layout.
  58  */
  59 typedef union {
  60     qvector_index whole;                     // as a whole
  61     qvector_field level[ QV_INDEX_FIELDS ];  // qua bits fields
  62 } qvector_indexing;
  63
  64 /*!
  65  * Type: qvector
  66  *
  67  * A qvector is a compound of a size and a qvector_page pointer, which
  68  * when non-null points out the top-most page of the qvector. The
  69  * number of levels is derived from its size with level 0 being the
  70  * leaf level of actual content. E.g., a qvector larger than 16
  71  * items, has at least two levels, and generally N levels may span up
  72  * to 16^N content entries.
  73  */
  74 typedef struct _qvector {
  75     qvector_index size;     //!< Limit for the logical entries[]
  76     qvector_page *entries; //!< Pointer to entries indexing
  77 } qvector;
  78
  79 // Number of slots for page S
  80 #define PV_LEVEL_SIZE(S) ((int)(exp( 16, (S) )))
  81
  82 // The indexing part for level part p in index i
  83 #define PV_PART(i,p) (((qvector_indexing*)(i))->level[ p ].bits)
  84
  85 /*!
  86  * Find the next used slot at given index or later. With a reclaim
  87  * function, it will be invoked for verifying that the item is
  88  * actually in use, in which case it returns 1. Otherwise it should
  89  * reclaim any memory for the item and return 0;
  90  */
  91 void **qvector_next_used(
  92     qvector *pv,qvector_index *index,
  93     int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
  94     void *data );
  95
  96 /*!
  97  * Function: int qvector_resize(
  98  *              qvector *pv,qvector_index new_size,
  99  *              int (*reclaim)(qvector *,qvector_index,void *item,void *data),
 100  *              void *data )
 101  * \param pv
 102  * \param new_size
 103  * \param reclaim
 104  * \param data
 105  *
 106  * Tries to resize the given qvector to a new size. This may result in
 107  * the introduction or removal of indexing pages, so that the leveling
 108  * is consistent with the qvector size. Thus, if it grows into a new
 109  * 16^N level, then one or more new upper level pages are inserted as
 110  * needed. If it shrinks below the current level, then top-level pages
 111  * are remove.
 112  *
 113  * Also, if the new size is smaller than currently, then the now
 114  * excess tail of entries is scanned for any used slots and the given
 115  * reclaim function is invoked successively for these. The reclaim
 116  * function must, in addition to memory-managing the entry, return 0
 117  * upon success and non-zero to veto the attempted qvector size
 118  * change. The data argument is passed on to the reclaim function.
 119  *
 120  * The qvector_resize function returns 0 on success, with the size
 121  * duly changed. Otherwise the function retains the current size and
 122  * returns -index-1 for the index of the veto-ed entry.
 123  */
 124 int qvector_resize(
 125     qvector *pv, qvector_index new_size,
 126     int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
 127     void *data );
 128
 129 /*!
 130  * Function: void **qvector_entry(qvector *pv,qvector_index index)
 131  * \param pv - the qvector record
 132  * \param index - the slot index
 133  *
 134  * [pgix,epix] = modulo( index, pv->page );
 135  *
 136  * \returns a direct pointer to the slot of the given index in the
 137  * array, or 0 if the index is beyond the array limits (0-limit). Note
 138  * that slot pointers are only valid while the qvector size is
 139  * unchanged.
 140  */
 141 extern void **qvector_entry(qvector *pv,qvector_index index);
 142
 143 /*!
 144  * Function: qvector_index qvector_size(qvector *pv)
 145  * \param pv - the qvector record
 146  * \returns the size of the qvector.
 147  */
 148 inline qvector_index qvector_size(qvector *pv) {
 149     return pv->size;
 150 }
 151
 152 void qvector_set(qvector *pv,qvector_index index,void *value);
 153
 154 void *qvector_get(qvector *pv,qvector_index index);
 155
 156 void qvector_append(qvector *pv,void *value);
 157
 158 void qvector_copy(qvector *dst,qvector_index di,
 159                   qvector *src,qvector_index si,qvector_index n);
 160
 161 void qvector_dump(qvector *pv,
 162                   int (*itemdump)(const qvector_index ,const void *));
 163
 164 void qvector_qsort(qvector *pv,int (*compar)(const void *,const void *));
 165
 166 void qvector_iterate(qvector *pv,
 167                      int (*itemfn)(qvector_index,void*,void*),
 168                      void*);
 169
 170 #endif