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