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.
14 * \subsubsection variantlist Variants:
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.
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.
29 * This is the general indexing used for vector access.
31 typedef unsigned long vector_index;
34 * A vector_page is an array of void* items. Its size depends on the
35 * applicable vector variant: 2^(8-variant)
37 typedef void* vector_page[];
40 * A vector is a compound of a size and a vector_page pointer, which
41 * when non-null points out the top-most page of the vector indexing
42 * tree. The number of levels is derived from its size with level 0
43 * being the leaf level of actual content. E.g., a vector larger than
44 * 256 items, has at least two levels, and generally N levels may span
45 * up to 256^N content entries.
49 * The indexing variant. 0 = 8-bit, 1 = 4-bit, and 2 = 2-bit
50 * indexing parts. This gives 256, 16 or 4 slots per index page.
51 * Note that variant should not be changed after initialization.
55 * The size of the vector.
59 * The root page of the indexing tree.
65 * \brief Return the number of slots spanned by an index level for the
66 * given vector variant.
68 * - 0 indicates 8-bit index parts, and 256 page slots
69 * - 1 indicates 4-bit index parts, and 16 page slots
70 * - 2 indicates 2-bit index parts, and 4 page slots
71 * - 3 indicates 64-bit index parts, and 1 page level following the size
73 * The type 3 vector is managed by using realloc.
75 extern unsigned long VECTOR_SLOTS(vector *pv);
78 * \brief Find the nearest used (non-null) slot at given or higher
81 * \param pv is the vector concerned.
83 * \param index is the index to change.
85 * \returns a pointer to the first non-null vector slot from the given
86 * index, and *index set accordingly. If no non-null slot is found,
87 * the 0 is returned and *index is set to the vector size.
91 extern void **vector_next_used(vector *pv,vector_index *index);
94 * \brief Find the nearest used (non-null) slot at given or lower
97 * \param pv is the vector concerned.
99 * \param index is the index to change.
101 * \returns a pointer to the first non-null vector slot from the given
102 * index, and *index set accordingly. If no non-null slot is found,
103 * the 0 is returned and *index is set to the vector size.
107 extern void **vector_prev_used(vector *pv,vector_index *index);
110 * \brief Resize a vector.
112 * \param pv is the vector concerned.
114 * \param new_size is the new size it should have,
116 * \param reclaim is used upon shrinking in size for handling any
117 * current items above the new size, or vetoing the attempted resize.
119 * \param data is passed on the the reclaim function to use as context
122 * \returns the index of a resizing veto any, or <0 otherwise, with -1
123 * indicating success and -2 indicating OOM.
125 * This function attempts to resize the given vector to a new size.
126 * This may result in the introduction or removal of indexing pages,
127 * so that the index tree leveling is consistent with the vector size.
128 * Thus, if it grows into a new level, then one or more new upper
129 * level pages are inserted as needed. If it shrinks below the current
130 * level, then top-level pages are removed.
132 * Also, if the new size is smaller than currently, then the now
133 * excess tail of entries is scanned for any used slots and the given
134 * reclaim function is invoked successively for these. The reclaim
135 * function must, in addition to memory-managing the entry, return 0
136 * upon success, or non-zero to veto the attempted vector size change.
137 * The data argument is passed on to the reclaim function as given.
141 extern int vector_resize(
142 vector *pv, vector_index new_size,
143 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
147 * \brief Return pointer to the indexed page slot at the requested
148 * level, and adding intermediate index pages if so requested.
150 * \param pv is the vector concerned.
152 * \param index is the slot index.
154 * \param level is the indexing level to access. Level 0 is the leaf
155 * level that holds the slots for the items; level 1 is one level up,
156 * for vectors larger than 256 items; ans so on.
158 * \param add is a flag to indicate (with 1) that missing index pages
159 * should be added, or (with 0) that the function should simply return
160 * null if an index page to access at any level is missing.
162 * \returns a pointer to the slot for the indexed item (level 0), or
163 * (for higher levels) the slot for the index page on the access path
164 * to the indexed item. The function returns 0 if the access path is
165 * broken by a missing index page, or (with add==1) the allocation of
166 * a new index page fails.
168 * \note The index tree for the vector is populated on demand only
169 * where access has been requested.
173 extern void **vector_access(vector *pv,vector_index index,int level,int add);
176 * \brief Return the slot value at the given index.
178 * \param pv is the vector concerned.
180 * \param index is the slot index.
182 * \returns a direct pointer to the slot of the given index in the
183 * array, or 0 if the index is beyond the array limits (0-limit).
185 * \note Note that slot pointers are only valid while the vector size
190 extern void **vector_entry(vector *pv,vector_index index);
193 * \param pv - the vector concerned
194 * \returns the size of the vector.
197 #define vector_size(pv) ((vector_index) (pv)->size)
200 * \brief Set the vector value at the given index.
202 * \param pv is the vector concerned
203 * \param index is the index for the slot to assign
204 * \param value is the new slot value
206 * \note An assignment of 0 will be treated as an unused slot.
210 extern void vector_set(vector *pv,vector_index index,void *value);
213 * \brief Set the vector value at the given index and return the prior
216 * \param pv is the vector concerned
217 * \param index is the index for the slot to assign
218 * \param value is the new slot value
220 * \note An assignment of 0 will be treated as an unused slot.
224 extern void *vector_get_set(vector *pv,vector_index index,void *value);
227 * \brief Get the vector value at the given index.
229 * \param pv is the vector concerned
230 * \param index is the index for the slot to assign
232 * \note This function will allocate all traversed indeex tree pages
233 * even for accessing an unassigned slot.
237 extern void *vector_get(vector *pv,vector_index index);
240 * \brief Grow the vector by one and assign the added slot.
242 * \param pv is the vector concerned
243 * \param value is the new slot value
247 extern void vector_append(vector *pv,void *value);
250 * \brief Copy a consecutive region from one vector into another, or
251 * possibly the same vector.
253 * \param pv is the vector concerned
254 * \param value is the new slot value
256 * \note This transfers all slots from the source region to the
257 * destination region, including zero slots. The vectors must be large
258 * enough for the transfer, which is carried out from lowest to
259 * highest or highest to lowest index depending on wther the move is
260 * to higher index or to lower index respectively.
264 extern void vector_copy(
265 vector *dst,vector_index di,
266 vector *src,vector_index si,
270 * \brief Utility function that invokes the itemdump function for all
271 * used (non-null) slots.
274 * \seealso vector_iterate
276 extern void vector_dump(
278 void (*itemdump)(const vector_index ,const void *));
280 extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
283 * Steps through the vector item by item invoking the given function
284 * for each. Continues stepping while the item function returns 0.
288 extern void vector_iterate(
289 vector *pv, vector_index start,
290 int (*itemfn)(vector_index,void *item,void *data),
294 * \brief Binary search in a sorted vector for an item of the given
295 * key, with a callback function providing the sorting order.
297 * \param pv is the vector concerned.
299 * \param index is a vector_index pointer for returning the index of
302 * \param key is the lookup key to find.
304 * \param compare is a callback function that should return the search
305 * direction given a key and an item. It should return 0 if the key is
306 * a match for the item, <0 if the sought item is expected at a higher
307 * index, and >0 if the sought item is expected at a lower index.
309 * \return a pointer to the found item and *index set to its index. If
310 * there is no matching item, then 0 is returned, and the index is set
311 * to the vector size.
315 extern void *vector_bsearch(
316 vector *pv, vector_index *index, const void *key,
317 int (*compare)(const void *key, const void *item));
320 * \brief Find the next used slot at or after the given index.
322 * \param pv the vector concerned.
323 * \param index pointer to the index to advance.
324 * \return the new index, or the vector size if no unused slot is
327 * Scans forward in the vector for the first unused (null) vector slot
328 * at or after the given index. Returns pv->size if full.
332 extern vector_index vector_next_unused(vector *pv,vector_index index);