5 * Representing a vector of void* accessible via an indexing structure
6 * as levels of same-size pages. A "vector_page" is a contiguous array
7 * void*, and an index is "unsigned long" (64 bits).
10 #if VECTOR_LEVEL_BITS == 4
12 vector_index as_whole;
14 unsigned int msb:4; unsigned int lsb:4;
15 } __attribute__ ((__packed__)) as_byte[8];
18 #define VECTOR_PART_BYTE(i,p) ((vector_indexing*)(i))->as_byte[ (p)/2 ]
20 static int VECTOR_INDEX_PART(vector_index *index,int part) {
22 return VECTOR_PART_BYTE(index,part).lsb;
24 return VECTOR_PART_BYTE(index,part).msb;
27 static int VECTOR_INDEX_PART_INC(vector_index *index,int part) {
29 return ++VECTOR_PART_BYTE(index,part).lsb;
31 return ++VECTOR_PART_BYTE(index,part).msb;
36 * Advances a vector index to the next used slot at or below the
37 * given level, starting from the indexed entry (inclusive) and up.
38 * The function will free any empty pages it discovers, and then
39 * update the index slots accordingly. The given index is advanced
40 * cyclically to match the found slot. The function returns a slot
41 * pointer to the used slot, if any, and 0 otherwise.
43 static void **vector_level_next_used(
44 vector_page *page,vector_index *index,int level,vector_index end) {
45 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( index, level ) ];
46 for( ; *index < end; p++ ) {
49 return p; // This is a used entry
51 // *p is an index that needs to be inspected recursively
52 int whole = VECTOR_INDEX_PART( index, level - 1 ) == 0;
53 void **x = vector_level_next_used( *p, index, level - 1, end );
55 return x; // Used slot was found; return it.
57 // The page *p is all empty, so can/should be reclaimed.
63 if ( VECTOR_INDEX_PART_INC( index, level ) == 0 ) {
64 break; // cycling this level => nothing found
70 // The least number of levels to span index S (typically the size of a
72 static unsigned int vector_levels(vector_index S) {
81 // Find the next used slot at given index or later. Returns pointer to
83 void **vector_next_used(
84 vector *pv,vector_index *index,
85 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
88 if ( pv->entries == 0 ) {
92 int levels = vector_levels( pv->size );
93 for ( ; *index < pv->size; (*index)++ ) {
94 void **slot = vector_level_next_used(
95 pv->entries, index, levels - 1, pv->size ) ;
97 // reached the end of the vector
102 // Try reclaiming the slot,
103 if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
113 // Reclaim tree of unused pages
114 static void vector_reclaim(vector_page *page,unsigned int level) {
117 for ( ; i < VECTOR_SLOTS; i++ ) {
119 vector_reclaim( (vector_page *) (*page)[i], level - 1 );
126 // Resize vector, using the reclaim function as needed, to handle any
127 // excess items or to veto the resize. Returns the index of the veto, if
128 // any, or <0 otherwise, with -1 indicating success and -2 indicating
129 // OOM while growing.
131 // Nothe that resizing may result in the introduction/removal of
132 // indexing levels and pages, so as to keep the leveling accurate for
135 vector *pv,vector_index new_size,
136 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
139 // Table of number of slots for a level above that of the number
140 // at the prior lower level. The first level (i.e., level 0) adds
141 // 15 slots to the one slot of no index page. Level 1 adds 15*16
142 // slots, level 2 adds 15*(16^2), and generically level i adds
144 static int level_delta[ VECTOR_INDEX_FIELDS ];
145 if ( level_delta[ 0 ] == 0 ) {
148 for ( i = 0; i < VECTOR_INDEX_FIELDS; i++ ) {
149 level_delta[ i ] = ( VECTOR_SLOTS - 1 ) * d;
150 d = VECTOR_SLOTS * d;
157 vector_levels( pv->size ),
158 vector_levels( new_size )
160 if ( pv->entries == 0 ) {
164 // A shrinking vector might be veto-ed
165 if ( new_size < pv->size ) {
166 vector_index index = new_size;
167 void **slot = vector_next_used( pv, &index, reclaim, data );
171 // At this point we know that there are no slots used after
172 // the new_size size, so now it's time to remove and reclaim
173 // any superflouous top level pages.
174 vector_page *entries;
175 vector_page **pp = &pv->entries;
176 while ( level.old-- > level.new ) {
178 pp = (vector_page **)(*pp)[0];
181 if ( pp != &pv->entries ) {
182 entries = pv->entries;
185 *pp = 0; // Detach subtree
189 vector_reclaim( entries, level.old );
191 if ( new_size == 0 && pv->entries ) {
196 // vector is growing. Maybe insert levels.
197 while ( level.old < level.new ) {
198 vector_page *p = (vector_page *)
199 calloc( 1, sizeof( vector_page ) );
203 (*p)[0] = pv->entries;
205 pv->size += level_delta[ level.old++ ];
206 // Note that the last level addition might make the size
207 // larger than requested, which gets corrected below.
214 // Return a pointer to the indexed item the given page level, adding
215 // intermediate pages if requested. Returns 0 if addition fails (OOM),
216 // or if not requested and page is missing.
217 // Level 0 = pointer to the item entry itself.
218 // Level VECTORLEVELS( pv->size ) - 1 =
219 static void **vector_access(
220 vector *pv,vector_index index,int level,int add)
222 if ( index >= pv->size ) {
225 void **page = (void**) &pv->entries;
226 int i = vector_levels( pv->size );
227 while ( i-- > level ) {
228 if ( add && (*page) == 0 ) {
229 (*page) = calloc( VECTOR_SLOTS, sizeof( void* ) );
235 page += VECTOR_INDEX_PART( &index, i );
240 // Map index into a value slot
241 void **vector_entry(vector *pv,vector_index index) {
242 return vector_access( pv, index, 0, 1 );
245 inline void vector_set(vector *pv,vector_index index,void *value) {
246 void **p = vector_entry( pv, index );
250 inline void *vector_get(vector *pv,vector_index index) {
251 return *(vector_entry( pv, index ));
254 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
259 void vector_append(vector *pv,void *value) {
260 vector_resize( pv, pv->size + 1, 0, 0 );
261 vector_set( pv, pv->size - 1, value );
264 // copy block of n items from src[si] to dst[di]
265 // no efficiency hacks
266 void vector_copy(vector *dst,vector_index di,
267 vector *src,vector_index si,vector_index n) {
268 if ( dst != src || di < si ) {
270 vector_set( dst, di++, vector_get( src, si++ ) );
272 } else if ( di > si ){
276 vector_set( dst, di--, vector_get( src, si-- ) );
281 void vector_dump(vector *pv,
282 int (*itemdump)(const vector_index,const void *)) {
283 vector_index index = 0;
284 for ( ; index < pv->size; index++ ) {
285 void **slot = vector_next_used( pv, &index, 0, 0 );
289 itemdump( index, *slot );
295 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
296 typedef int (*comparfn)(const void *,const void *);
298 static void vector_qsort_part(
299 vector *pv,comparfn compar,
300 vector_index low,vector_index high)
305 vector_index lo = low;
306 vector_index m = high - 1;
312 vector_index hi = m - 1;
313 void **mp = vector_entry( pv, m );
316 // Find index of first item "above" mp scanning from lo and up
317 for ( ; lo < m; lo++ ) {
318 lop = vector_entry( pv, lo );
319 if ( compar( *lop, *mp ) < 0 ) {
323 // if lo == m, then lop is wrong!!
324 // Find index of first item "below" mp scanning from hi and down
325 for ( ; hi > lo; hi-- ) {
326 hip = vector_entry( pv, hi );
327 if ( compar( *mp, *hip ) < 0 ) {
344 vector_qsort_part( pv, compar, low, m );
345 vector_qsort_part( pv, compar, m+1, high );
348 void vector_qsort(vector *pv,comparfn compar) {
349 vector_qsort_part( pv, compar, 0, pv->size );
352 void vector_iterate(vector *pv,
353 int (*itemfn)(vector_index,void*,void*),
356 vector_index index = 0;
357 while ( index < pv->size ) {
358 void **slot = vector_next_used( pv, &index, 0, 0 );
362 int i = index & 0xff;
363 for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) {
364 if ( itemfn( index, *slot, data ) ) {