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.
10 * Macro: VECTOR_LEVEL_BITS
11 * This defines the number of bits in the indexing bit field.
13 #define VECTOR_LEVEL_BITS 4
17 * This is the general indexing used for vector access.
19 typedef unsigned long vector_index;
22 * Macro: VECTOR_INDEX_BITS
23 * This defines the number of bits of a vector index
25 #define VECTOR_INDEX_BITS sizeof( vector_index )
28 * Macro: VECTOR_INDEX_FIELDS
29 * This defines the number of bit fields in an vector index
31 #define VECTOR_INDEX_FIELDS \
32 ( ( VECTOR_INDEX_BITS - 1 ) / VECTOR_LEVEL_BITS + 1 )
36 * This defines the number of slots spanned by an index level
38 #define VECTOR_SLOTS ( 1 << VECTOR_LEVEL_BITS )
43 * A vector_page is an array of 16 void* items.
45 typedef void* vector_page[ VECTOR_SLOTS ];
49 * This is VECTOR_LEVEL_BITS size bit field
51 typedef struct { int bits:VECTOR_LEVEL_BITS; } vector_field;
54 * Type: vector_indexing
56 * A vector index is ether viewed in whole as an VECTOR_INDEX_BITS wide
57 * unsigned, or in levels as a packed array of vector_field index
58 * parts. This implementation assumes LE integer layout.
61 vector_index whole; // as a whole
62 vector_field level[ VECTOR_INDEX_FIELDS ]; // qua bits fields
65 // The indexing part for level part p in index i
66 #define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->level[ p ].bits)
71 * A vector is a compound of a size and a vector_page pointer, which
72 * when non-null points out the top-most page of the vector. The
73 * number of levels is derived from its size with level 0 being the
74 * leaf level of actual content. E.g., a vector larger than 16
75 * items, has at least two levels, and generally N levels may span up
76 * to 16^N content entries.
78 typedef struct _vector {
79 vector_index size; //!< Limit for the logical entries[]
80 vector_page *entries; //!< Pointer to entries indexing
84 * Find the next used slot at given index or later. With a reclaim
85 * function, it will be invoked for verifying that the item is
86 * actually in use, in which case it returns 1. Otherwise it should
87 * reclaim any memory for the item and return 0;
89 void **vector_next_used(
90 vector *pv,vector_index *index,
91 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
95 * Function: int vector_resize(
96 * vector *pv,vector_index new_size,
97 * int (*reclaim)(vector *,vector_index,void *item,void *data),
104 * Tries to resize the given vector to a new size. This may result in
105 * the introduction or removal of indexing pages, so that the leveling
106 * is consistent with the vector size. Thus, if it grows into a new
107 * 16^N level, then one or more new upper level pages are inserted as
108 * needed. If it shrinks below the current level, then top-level pages
111 * Also, if the new size is smaller than currently, then the now
112 * excess tail of entries is scanned for any used slots and the given
113 * reclaim function is invoked successively for these. The reclaim
114 * function must, in addition to memory-managing the entry, return 0
115 * upon success and non-zero to veto the attempted vector size
116 * change. The data argument is passed on to the reclaim function.
118 * The vector_resize function returns 0 on success, with the size
119 * duly changed. Otherwise the function retains the current size and
120 * returns -index-1 for the index of the veto-ed entry.
123 vector *pv, vector_index new_size,
124 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
128 * Function: void **vector_entry(vector *pv,vector_index index)
129 * \param pv - the vector record
130 * \param index - the slot index
132 * [pgix,epix] = modulo( index, pv->page );
134 * \returns a direct pointer to the slot of the given index in the
135 * array, or 0 if the index is beyond the array limits (0-limit). Note
136 * that slot pointers are only valid while the vector size is
139 extern void **vector_entry(vector *pv,vector_index index);
142 * Function: vector_index vector_size(vector *pv)
143 * \param pv - the vector record
144 * \returns the size of the vector.
146 inline vector_index vector_size(vector *pv) {
150 void vector_set(vector *pv,vector_index index,void *value);
152 void *vector_get(vector *pv,vector_index index);
154 void vector_append(vector *pv,void *value);
156 void vector_copy(vector *dst,vector_index di,
157 vector *src,vector_index si,vector_index n);
159 void vector_dump(vector *pv,
160 int (*itemdump)(const vector_index ,const void *));
162 void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
164 void vector_iterate(vector *pv,
165 int (*itemfn)(vector_index,void*,void*),