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