5 * A vector is a dynamic pointer array implemented as an access tree
6 * of index pages. The indexing is done using "unsigned long" indexes.
9 #ifndef VECTOR_LEVEL_BITS
11 * Macro: VECTOR_LEVEL_BITS
12 * This defines the number of bits in the indexing bit field.
14 #define VECTOR_LEVEL_BITS 8
19 * This is the general indexing used for vector access.
21 typedef unsigned long vector_index;
24 * Macro: VECTOR_INDEX_BITS
25 * This defines the number of bits of a vector index
27 #define VECTOR_INDEX_BITS ( sizeof( vector_index ) * 8 )
30 * Macro: VECTOR_INDEX_FIELDS
31 * This defines the number of bit fields in an vector index
33 #define VECTOR_INDEX_FIELDS \
34 ( ( VECTOR_INDEX_BITS - 1 ) / VECTOR_LEVEL_BITS + 1 )
38 * This defines the number of slots spanned by an index level
40 #define VECTOR_SLOTS ( 1 << VECTOR_LEVEL_BITS )
45 * A vector_page is an array of 16 void* items.
47 typedef void* vector_page[ VECTOR_SLOTS ];
52 * A vector is a compound of a size and a vector_page pointer, which
53 * when non-null points out the top-most page of the vector. The
54 * number of levels is derived from its size with level 0 being the
55 * leaf level of actual content. E.g., a vector larger than 16
56 * items, has at least two levels, and generally N levels may span up
57 * to 16^N content entries.
59 typedef struct _vector {
60 vector_index size; //!< Limit for the logical entries[]
61 vector_page *entries; //!< Pointer to entries indexing
65 * Find the nearest used (non-null) slot at given or higher index.
67 extern void **vector_next_used(vector *pv,vector_index *index);
70 * Find the nearest used (non-null) slot at given or lower index.
72 extern void **vector_prev_used(vector *pv,vector_index *index);
75 * Function: int vector_resize(
76 * vector *pv,vector_index new_size,
77 * int (*reclaim)(vector *,vector_index,void *item,void *data),
84 * Tries to resize the given vector to a new size. This may result in
85 * the introduction or removal of indexing pages, so that the leveling
86 * is consistent with the vector size. Thus, if it grows into a new
87 * 16^N level, then one or more new upper level pages are inserted as
88 * needed. If it shrinks below the current level, then top-level pages
91 * Also, if the new size is smaller than currently, then the now
92 * excess tail of entries is scanned for any used slots and the given
93 * reclaim function is invoked successively for these. The reclaim
94 * function must, in addition to memory-managing the entry, return 0
95 * upon success and non-zero to veto the attempted vector size
96 * change. The data argument is passed on to the reclaim function.
98 * The vector_resize function returns 0 on success, with the size
99 * duly changed. Otherwise the function retains the current size and
100 * returns -index-1 for the index of the veto-ed entry.
102 extern int vector_resize(
103 vector *pv, vector_index new_size,
104 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
108 * Function: void **vector_entry(vector *pv,vector_index index)
109 * \param pv - the vector record
110 * \param index - the slot index
112 * [pgix,epix] = modulo( index, pv->page );
114 * \returns a direct pointer to the slot of the given index in the
115 * array, or 0 if the index is beyond the array limits (0-limit). Note
116 * that slot pointers are only valid while the vector size is
119 extern void **vector_entry(vector *pv,vector_index index);
122 * Macro: vector_size(v)
123 * \param v - the vector record
124 * \returns the size of the vector.
126 #define vector_size(pv) ((vector_index) (pv)->size)
128 extern void vector_set(vector *pv,vector_index index,void *value);
130 // Set value at index but return the old value
131 extern void *vector_get_set(vector *pv,vector_index index,void *value);
133 extern void *vector_get(vector *pv,vector_index index);
135 extern void vector_append(vector *pv,void *value);
137 extern void vector_copy(
138 vector *dst,vector_index di,
139 vector *src,vector_index si,
143 * Invoking the itemdup function for all used (non-null) slots.
145 extern void vector_dump(
147 void (*itemdump)(const vector_index ,const void *));
149 extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
152 * Function: void vector_iterate(vector *pv,
153 * vector_index start,
154 * int (*itemfn)(vector_index,void*,void*),
157 * Steps through the vector item by item invoking the given function
158 * for each. Continues stepping while the item function returns 0.
160 extern void vector_iterate(
161 vector *pv, vector_index start,
162 int (*itemfn)(vector_index,void *item,void *data),
165 extern void *vector_bsearch(
166 vector *pv, vector_index *index, const void *key,
167 int (*compare)(const void *key, const void *item));