vector/vector.h

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