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.
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.
16 * \brief This is the general indexing used for Vector access.
20 typedef unsigned long VectorIndex;
23 * \brief A VectorPage is an array of void* items. Its size depends
24 * on the applicable Vector variant.
28 typedef void* VectorPage[];
31 * \brief The implementation variants.
33 * - Byte_index_levels (0) has 8-bit indexing parts and index pages
36 * - Nibble_index_levels (1) has 4-bit indexing parts and index pages
39 * - BitPair_index_levels (2) has 2-bit indexing parts and index pages
42 * - Single_index_level (3) has a single page that is sized as the
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.
55 Byte_index_levels = 0,
56 Nibble_index_levels = 1,
57 BitPair_index_levels = 2,
58 Single_index_level = 3
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.
70 * The indexing variant.
72 enum VectorVariant variant;
75 * The size of the Vector.
80 * The root page of the indexing tree.
86 * \brief Return the number of slots spanned by an index level for the
87 * given Vector variant.
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
94 * The type 3 Vector is managed by using realloc.
97 extern unsigned long VECTOR_SLOTS(Vector *pv);
100 * \brief Find the nearest used (non-null) slot at given or higher
103 * \param pv is the Vector concerned.
105 * \param index is the index to change.
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.
113 extern void **Vector_next_used(Vector *pv,VectorIndex *index);
116 * \brief Find the nearest used (non-null) slot at given or lower
119 * \param pv is the Vector concerned.
121 * \param index is the index to change.
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.
129 extern void **Vector_prev_used(Vector *pv,VectorIndex *index);
132 * \brief Resize a Vector.
134 * \param pv is the Vector concerned.
136 * \param new_size is the new size it should have,
138 * \param reclaim is used upon shrinking in size for handling any
139 * current items above the new size, or vetoing the attempted resize.
141 * \param data is passed on the the reclaim function to use as context
144 * \returns the index of a resizing veto any, or <0 otherwise, with -1
145 * indicating success and -2 indicating OOM.
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.
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.
163 extern int Vector_resize(
164 Vector *pv, VectorIndex new_size,
165 int (*reclaim)(Vector *pv,VectorIndex index,void *item,void *data),
169 * \brief Return pointer to the indexed page slot at the requested
170 * level, and adding intermediate index pages if so requested.
172 * \param pv is the Vector concerned.
174 * \param index is the slot index.
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.
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.
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.
190 * \note The index tree for the Vector is populated on demand only
191 * where access has been requested.
195 extern void **Vector_access(Vector *pv,VectorIndex index,int level,int add);
198 * \brief Return the slot value at the given index.
200 * \param pv is the Vector concerned.
202 * \param index is the slot index.
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).
207 * \note Note that slot pointers are only valid while the Vector size
212 extern void **Vector_entry(Vector *pv,VectorIndex index);
215 * \param pv - the Vector concerned
216 * \returns the size of the Vector.
219 #define Vector_size(pv) ((VectorIndex) (pv)->size)
222 * \brief Set the Vector value at the given index.
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
228 * \note An assignment of 0 will be treated as an unused slot.
232 extern void Vector_set(Vector *pv,VectorIndex index,void *value);
235 * \brief Set the Vector value at the given index and return the prior
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
242 * \note An assignment of 0 will be treated as an unused slot.
246 extern void *Vector_get_set(Vector *pv,VectorIndex index,void *value);
249 * \brief Get the Vector value at the given index.
251 * \param pv is the Vector concerned
252 * \param index is the index for the slot to assign
254 * \note This function will allocate all traversed indeex tree pages
255 * even for accessing an unassigned slot.
259 extern void *Vector_get(Vector *pv,VectorIndex index);
262 * \brief Grow the Vector by one and assign the added slot.
264 * \param pv is the Vector concerned
265 * \param value is the new slot value
269 extern void Vector_append(Vector *pv,void *value);
272 * \brief Copy a consecutive region from one Vector into another, or
273 * possibly the same Vector.
275 * \param pv is the Vector concerned
276 * \param value is the new slot value
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.
286 extern void Vector_copy(
287 Vector *dst,VectorIndex di,
288 Vector *src,VectorIndex si,
292 * \brief Allocate a copy of a Vector into one in the given variant.
294 extern Vector *Vector_clone(enum VectorVariant variant,Vector *src);
297 * \brief Utility function that invokes the itemdump function for all
298 * used (non-null) slots.
301 * \seealso Vector_iterate
303 extern void Vector_dump(
305 void (*itemdump)(const VectorIndex ,const void *));
308 * \brief Sort a Vector with quicksort using the provided ordering
313 extern void Vector_qsort(Vector *pv,int (*compar)(const void *,const void *));
316 * Steps through the Vector item by item invoking the given function
317 * for each. Continues stepping while the item function returns 0.
321 extern void Vector_iterate(
322 Vector *pv, VectorIndex start,
323 int (*itemfn)(VectorIndex,void *item,void *data),
327 * \brief Binary search in a sorted Vector for an item of the given
328 * key, with a callback function providing the sorting order.
330 * \param pv is the Vector concerned.
332 * \param index is a VectorIndex pointer for returning the index of
335 * \param key is the lookup key to find.
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.
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.
348 extern void *Vector_bsearch(
349 Vector *pv, VectorIndex *index, const void *key,
350 int (*compare)(const void *key, const void *item));
353 * \brief Find the index for a given value
355 * \param pv is the Vector concerned
356 * \param is the value to find
358 * This function scans the Vector for the first, if any, occurrence of
359 * the value, or returns pv->size if not found.
363 extern VectorIndex Vector_find(Vector *pv,void *value);
366 * \brief Find the next used slot at or after the given index.
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
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.
378 extern VectorIndex Vector_next_unused(Vector *pv,VectorIndex index);
381 * \brief Convenience callback function for Vector shrinking to free
382 * any existing slot assignment.
386 extern int Vector_free_any(Vector *pv,VectorIndex ix,void *item,void *data);
389 * \brief Convenience callback function for Vector shrinking to ignore
390 * any existing slot assignment (without free-ing them).
394 extern int Vector_clear_any(Vector *pv,VectorIndex ix,void *item,void *data);