vector/vector.h

   1 #ifndef vector_H
   2 #define vector_H
   3
   4 /** \file vector.h
   5  *
   6  * A vector is a dynamic pointer array implemented as an access tree
   7  * of index pages. The indexing is done using "unsigned long" indexes,
   8  * and the level 0 index corresponds to actual items.
   9  *
  10  * Actual vectors are assigned a leveling variant which defines the
  11  * index page size for the vector. This must not be changed for a
  12  * vector with entries.
  13  *
  14  * \subsubsection variantlist Variants:
  15  *
  16  * - 0 is 8-bit indexing parts and index pages with 256 pointers
  17  * - 1 is 4-bit indexing parts and index pages with 16 pointers
  18  * - 2 is 2-bit indexing parts and index pages with 4 pointers
  19  * - 3 is for a single page sized as the vector.
  20  *
  21  * Variants 0-2 are managed by adding/removing full pages of the
  22  * indexing tree upon resize and access. Variant 3 is managed by using
  23  * realloc upon resize. In all cases shrinking a vector may mean to
  24  * reclaim "lost" items, if any, via a provided item reclaim callback
  25  * function which also may veto the shrinking.
  26  */
  27
  28 /**
  29  * \brief This is the general indexing used for vector access.
  30  * \related vector
  31  */
  32 typedef unsigned long vector_index;
  33
  34 /**
  35  * \brief A vector_page is an array of void* items. Its size depends
  36  * on the applicable vector variant.
  37  * \related vector
  38  */
  39 typedef void* vector_page[];
  40
  41 /**
  42  * A vector struct is the "foot part" of an actual containing the
  43  * applicable implementation variant for this vector, the intended
  44  * slot size and a root pointer for the indexing structure, which
  45  * consist of indexing pages according to the variant.
  46  *
  47  * Variant 0, 1 and 2, involves indexing pages of 256, 16 and 4
  48  * pointers respectively. Variant 3 involves a single indexing page of
  49  * the size of the vector.
  50  */
  51 typedef struct {
  52     /**
  53      * The indexing variant. 0 = 8-bit, 1 = 4-bit, and 2 = 2-bit
  54      * indexing parts. This gives 256, 16 or 4 slots per index page.
  55      * Note that variant should not be changed after initialization.
  56      */
  57     int variant;
  58
  59     /**
  60      * The size of the vector.
  61      */
  62     vector_index size;
  63
  64     /**
  65      * The root page of the indexing tree.
  66      */
  67     vector_page *entries;
  68 } vector;
  69
  70 /**
  71  * \brief Return the number of slots spanned by an index level for the
  72  * given vector variant.
  73  *
  74  * - 0 indicates 8-bit index parts, and 256 page slots
  75  * - 1 indicates 4-bit index parts, and 16 page slots
  76  * - 2 indicates 2-bit index parts, and 4 page slots
  77  * - 3 indicates 64-bit index parts, and 1 page level following the size
  78  *
  79  * The type 3 vector is managed by using realloc.
  80  * \related vector
  81  */
  82 extern unsigned long VECTOR_SLOTS(vector *pv);
  83
  84 /**
  85  * \brief Find the nearest used (non-null) slot at given or higher
  86  * index.
  87  *
  88  * \param pv is the vector concerned.
  89  *
  90  * \param index is the index to change.
  91  *
  92  * \returns a pointer to the first non-null vector slot from the given
  93  * index, and *index set accordingly. If no non-null slot is found,
  94  * the 0 is returned and *index is set to the vector size.
  95  *
  96  * \related vector
  97  */
  98 extern void **vector_next_used(vector *pv,vector_index *index);
  99
 100 /**
 101  * \brief Find the nearest used (non-null) slot at given or lower
 102  * index.
 103  *
 104  * \param pv is the vector concerned.
 105  *
 106  * \param index is the index to change.
 107  *
 108  * \returns a pointer to the first non-null vector slot from the given
 109  * index, and *index set accordingly. If no non-null slot is found,
 110  * the 0 is returned and *index is set to the vector size.
 111  *
 112  * \related vector
 113  */
 114 extern void **vector_prev_used(vector *pv,vector_index *index);
 115
 116 /**
 117  * \brief Resize a vector.
 118  *
 119  * \param pv is the vector concerned.
 120  *
 121  * \param new_size is the new size it should have,
 122  *
 123  * \param reclaim is used upon shrinking in size for handling any
 124  * current items above the new size, or vetoing the attempted resize.
 125  *
 126  * \param data is passed on the the reclaim function to use as context
 127  * as needed.
 128  *
 129  * \returns the index of a resizing veto any, or <0 otherwise, with -1
 130  * indicating success and -2 indicating OOM.
 131  *
 132  * This function attempts to resize the given vector to a new size.
 133  * This may result in the introduction or removal of indexing pages,
 134  * so that the index tree leveling is consistent with the vector size.
 135  * Thus, if it grows into a new level, then one or more new upper
 136  * level pages are inserted as needed. If it shrinks below the current
 137  * level, then top-level pages are removed.
 138  *
 139  * Also, if the new size is smaller than currently, then the now
 140  * excess tail of entries is scanned for any used slots and the given
 141  * reclaim function is invoked successively for these. The reclaim
 142  * function must, in addition to memory-managing the entry, return 0
 143  * upon success, or non-zero to veto the attempted vector size change.
 144  * The data argument is passed on to the reclaim function as given.
 145  *
 146  * \related vector
 147  */
 148 extern int vector_resize(
 149     vector *pv, vector_index new_size,
 150     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
 151     void *data );
 152
 153 /**
 154  * \brief Return pointer to the indexed page slot at the requested
 155  * level, and adding intermediate index pages if so requested.
 156  *
 157  * \param pv is the vector concerned.
 158  *
 159  * \param index is the slot index.
 160  *
 161  * \param level is the indexing level to access. Level 0 is the leaf
 162  * level that holds the slots for the items; level 1 is one level up,
 163  * for vectors larger than 256 items; ans so on.
 164  *
 165  * \param add is a flag to indicate (with 1) that missing index pages
 166  * should be added, or (with 0) that the function should simply return
 167  * null if an index page to access at any level is missing.
 168  *
 169  * \returns a pointer to the slot for the indexed item (level 0), or
 170  * (for higher levels) the slot for the index page on the access path
 171  * to the indexed item. The function returns 0 if the access path is
 172  * broken by a missing index page, or (with add==1) the allocation of
 173  * a new index page fails.
 174  *
 175  * \note The index tree for the vector is populated on demand only
 176  * where access has been requested.
 177  *
 178  * \related vector
 179  */
 180 extern void **vector_access(vector *pv,vector_index index,int level,int add);
 181
 182 /**
 183  * \brief Return the slot value at the given index.
 184  *
 185  * \param pv is the vector concerned.
 186  *
 187  * \param index is the slot index.
 188  *
 189  * \returns a direct pointer to the slot of the given index in the
 190  * array, or 0 if the index is beyond the array limits (0-limit).
 191  *
 192  * \note Note that slot pointers are only valid while the vector size
 193  * is unchanged.
 194  *
 195  * \related vector
 196  */
 197 extern void **vector_entry(vector *pv,vector_index index);
 198
 199 /**
 200  * \param pv - the vector concerned
 201  * \returns the size of the vector.
 202  * \related vector
 203  */
 204 #define vector_size(pv) ((vector_index) (pv)->size)
 205
 206 /**
 207  * \brief Set the vector value at the given index.
 208  *
 209  * \param pv is the vector concerned
 210  * \param index is the index for the slot to assign
 211  * \param value is the new slot value
 212  *
 213  * \note An assignment of 0 will be treated as an unused slot.
 214  *
 215  * \related vector
 216  */
 217 extern void vector_set(vector *pv,vector_index index,void *value);
 218
 219 /**
 220  * \brief Set the vector value at the given index and return the prior
 221  * value.
 222  *
 223  * \param pv is the vector concerned
 224  * \param index is the index for the slot to assign
 225  * \param value is the new slot value
 226  *
 227  * \note An assignment of 0 will be treated as an unused slot.
 228  *
 229  * \related vector
 230  */
 231 extern void *vector_get_set(vector *pv,vector_index index,void *value);
 232
 233 /**
 234  * \brief Get the vector value at the given index.
 235  *
 236  * \param pv is the vector concerned
 237  * \param index is the index for the slot to assign
 238  *
 239  * \note This function will allocate all traversed indeex tree pages
 240  * even for accessing an unassigned slot.
 241  *
 242  * \related vector
 243  */
 244 extern void *vector_get(vector *pv,vector_index index);
 245
 246 /**
 247  * \brief Grow the vector by one and assign the added slot.
 248  *
 249  * \param pv is the vector concerned
 250  * \param value is the new slot value
 251  *
 252  * \related vector
 253  */
 254 extern void vector_append(vector *pv,void *value);
 255
 256 /**
 257  * \brief Copy a consecutive region from one vector into another, or
 258  * possibly the same vector.
 259  *
 260  * \param pv is the vector concerned
 261  * \param value is the new slot value
 262  *
 263  * \note This transfers all slots from the source region to the
 264  * destination region, including zero slots. The vectors must be large
 265  * enough for the transfer, which is carried out from lowest to
 266  * highest or highest to lowest index depending on wther the move is
 267  * to higher index or to lower index respectively.
 268  *
 269  * \related vector
 270  */
 271 extern void vector_copy(
 272     vector *dst,vector_index di,
 273     vector *src,vector_index si,
 274     vector_index n);
 275
 276 /**
 277  * \brief Utility function that invokes the itemdump function for all
 278  * used (non-null) slots.
 279  *
 280  * \related vector
 281  * \seealso vector_iterate
 282  */
 283 extern void vector_dump(
 284     vector *pv,
 285     void (*itemdump)(const vector_index ,const void *));
 286
 287 /**
 288  * \brief Sort a vector with quicksort using the provided ordering
 289  * collback function.
 290  *
 291  * \related vector
 292  */
 293 extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
 294
 295 /**
 296  * Steps through the vector item by item invoking the given function
 297  * for each. Continues stepping while the item function returns 0.
 298  *
 299  * \related vector
 300  */
 301 extern void vector_iterate(
 302     vector *pv, vector_index start,
 303     int (*itemfn)(vector_index,void *item,void *data),
 304     void *data);
 305
 306 /**
 307  * \brief Binary search in a sorted vector for an item of the given
 308  * key, with a callback function providing the sorting order.
 309  *
 310  * \param pv is the vector concerned.
 311  *
 312  * \param index is a vector_index pointer for returning the index of
 313  * the found item.
 314  *
 315  * \param key is the lookup key to find.
 316  *
 317  * \param compare is a callback function that should return the search
 318  * direction given a key and an item. It should return 0 if the key is
 319  * a match for the item, <0 if the sought item is expected at a higher
 320  * index, and >0 if the sought item is expected at a lower index.
 321  *
 322  * \return a pointer to the found item and *index set to its index. If
 323  * there is no matching item, then 0 is returned, and the index is set
 324  * to the vector size.
 325  *
 326  * \related vector
 327  */
 328 extern void *vector_bsearch(
 329     vector *pv, vector_index *index, const void *key,
 330     int (*compare)(const void *key, const void *item));
 331
 332 /**
 333  * \brief Find the next used slot at or after the given index.
 334  *
 335  * \param pv the vector concerned.
 336  * \param index pointer to the index to advance.
 337  * \return the new index, or the vector size if no unused slot is
 338  * found.
 339  *
 340  * Scans forward in the vector for the first unused (null) vector slot
 341  * at or after the given index. Returns pv->size if full.
 342  *
 343  * \related vector
 344  */
 345 extern vector_index vector_next_unused(vector *pv,vector_index index);
 346
 347 #endif