vector/vector.h

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