6 * Representing a vector of void* accessible via an indexing structure
7 * as levels of same-size pages. A "vector_page" is a contiguous array
8 * void*, and an index is "unsigned long" (64 bits).
11 /** ============================================================ **/
12 #if VECTOR_LEVEL_BITS == 4
14 vector_index as_whole;
16 unsigned int msb:4; unsigned int lsb:4;
17 } __attribute__ ((__packed__)) as_byte[8];
20 #define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 )
22 #define VECTOR_PART_BYTE(i,p) ((vector_indexing*)(i))->as_byte[ (p)/2 ]
24 static int VECTOR_INDEX_PART(vector_index *index,int part) {
26 return VECTOR_PART_BYTE(index,part).lsb;
28 return VECTOR_PART_BYTE(index,part).msb;
31 static int VECTOR_INDEX_PART_INC(vector_index *index,int part) {
33 return ++VECTOR_PART_BYTE(index,part).lsb;
35 return ++VECTOR_PART_BYTE(index,part).msb;
38 static int VECTOR_INDEX_PART_INC(vector_index *index,int part) {
40 return VECTOR_PART_BYTE(index,part).lsb--;
42 return VECTOR_PART_BYTE(index,part).msb--;
45 /** ============================================================ **/
46 #elif VECTOR_LEVEL_BITS == 8
48 #define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 )
51 vector_index as_whole;
52 unsigned char as_byte[8];
55 #define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->as_byte[p])
57 #define VECTOR_INDEX_PART_INC(i,p) (++VECTOR_INDEX_PART(i,p))
59 #define VECTOR_INDEX_PART_DEC(i,p) (VECTOR_INDEX_PART(i,p)--)
62 /** ============================================================ **/
65 * Advances a vector index to the next used slot at or below the
66 * given level, starting from the indexed entry (inclusive) and up.
67 * The function will free any empty pages it discovers, and then
68 * update the index slots accordingly. The given index is advanced
69 * cyclically to match the found slot. The function returns a slot
70 * pointer to the used slot, if any, and 0 otherwise.
72 static void **vector_level_next_used(
73 vector_page *page,vector_index *index,int level,vector_index end) {
74 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( index, level ) ];
75 for( ; *index < end; p++ ) {
78 return p; // This is a used entry
80 // *p is an index that needs to be inspected recursively
81 int whole = VECTOR_INDEX_PART( index, level - 1 ) == 0;
82 void **x = vector_level_next_used( *p, index, level - 1, end );
84 return x; // Used slot was found; return it.
86 // The page *p is all empty, so can/should be reclaimed.
92 if ( VECTOR_INDEX_PART_INC( index, level ) == 0 ) {
93 break; // cycling this level => nothing found
100 // The least number of levels to span index S (typically the size of a
102 static unsigned int vector_levels(vector_index S) {
111 // Find the next used slot at given index or later. Returns pointer to
112 // the slot. This allows for a reclaim function that may reclaim slot
113 // items on the way to next used slot.
114 void **vector_next_used(vector *pv,vector_index *index) {
115 if ( pv->entries == 0 || *index >= pv->size ) {
119 int levels = vector_levels( pv->size );
120 for ( ; *index < pv->size; (*index)++ ) {
121 void **slot = vector_level_next_used(
122 pv->entries, index, levels - 1, pv->size ) ;
124 *index = pv->size; // reached the end of the vector
125 } else if ( *slot == 0 ) {
133 // Reclaim tree of unused pages
134 static void vector_reclaim(vector_page *page,unsigned int level) {
137 for ( ; i < VECTOR_SLOTS; i++ ) {
139 vector_reclaim( (vector_page *) (*page)[i], level - 1 );
146 // Resize vector, using the reclaim function as needed, to handle any
147 // excess items or to veto the resize. Returns the index of the veto,
148 // if any, or <0 otherwise, with -1 indicating success and -2
151 // Note that resizing may result in the introduction/removal of
152 // indexing levels and pages, so as to keep the leveling accurate for
155 vector *pv,vector_index new_size,
156 int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
159 // Table of number of slots for a level above that of the number
160 // at the prior lower level. The first level (i.e., level 0) adds
161 // 15 slots to the one slot of no index page. Level 1 adds 15*16
162 // slots, level 2 adds 15*(16^2), and generically level i adds
164 static int level_delta[ VECTOR_INDEX_FIELDS ];
165 if ( level_delta[ 0 ] == 0 ) {
168 for ( i = 0; i < VECTOR_INDEX_FIELDS; i++ ) {
169 level_delta[ i ] = ( VECTOR_SLOTS - 1 ) * d;
170 d = VECTOR_SLOTS * d;
177 vector_levels( pv->size ),
178 vector_levels( new_size )
180 if ( pv->entries == 0 ) {
184 // A shrinking vector might be veto-ed
185 if ( new_size < pv->size ) {
186 vector_index index = new_size;
187 void **slot = vector_next_used( pv, &index );
189 if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
191 slot = vector_next_used( pv, &index );
196 // At this point we know that there are no slots used after
197 // the new_size size, so now it's time to remove and reclaim
198 // any superflouous top level pages.
199 vector_page *entries;
200 vector_page **pp = &pv->entries;
201 while ( level.old-- > level.new ) {
203 pp = (vector_page **)(*pp)[0];
206 if ( pp != &pv->entries ) {
207 entries = pv->entries;
210 *pp = 0; // Detach subtree
214 vector_reclaim( entries, level.old );
216 if ( new_size == 0 && pv->entries ) {
221 // vector is growing. Maybe insert levels.
222 while ( level.old < level.new ) {
223 vector_page *p = (vector_page *)
224 calloc( 1, sizeof( vector_page ) );
228 (*p)[0] = pv->entries;
230 pv->size += level_delta[ level.old++ ];
231 // Note that the last level addition might make the size
232 // larger than requested, which gets corrected below.
239 // Return pointer to the indexed page slot at the requested level, and
240 // adding intermediate index pages if so requested. Returns 0 if
241 // addition fails (OOM), or if not requested and page is missing.
242 static void **vector_access(
243 vector *pv,vector_index index,int level,int add)
245 if ( index >= pv->size ) {
248 void **page = (void**) &pv->entries;
249 int i = vector_levels( pv->size );
250 while ( i-- > level ) {
251 if ( add && (*page) == 0 ) {
252 (*page) = calloc( VECTOR_SLOTS, sizeof( void* ) );
258 page += VECTOR_INDEX_PART( &index, i );
263 // Find the first in-use slot at or before the index, at the level
264 static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) {
265 void **slot = vector_access( pv, *index, lv, 0 );
274 void **sub = vector_prev_used_level( pv, index, lv - 1 );
280 } while ( VECTOR_INDEX_PART_DEC( index, lv ) != 0 );
284 // Find nearest used slot at or prior to the given index.
285 void **vector_prev_used(vector *pv,vector_index *index) {
286 if ( pv->entries == 0 || *index >= pv->size ) {
290 void **slot = vector_prev_used_level(
291 pv, index, vector_levels( pv->size ) - 1 );
298 // Map index into a value slot
299 void **vector_entry(vector *pv,vector_index index) {
300 return vector_access( pv, index, 0, 1 );
303 inline void vector_set(vector *pv,vector_index index,void *value) {
304 void **p = vector_entry( pv, index );
309 // Set value at index but return the old value
310 void *vector_get_set(vector *pv,vector_index index,void *value) {
311 void **p = vector_entry( pv, index );
317 inline void *vector_get(vector *pv,vector_index index) {
318 void **p = vector_entry( pv, index );
322 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
327 void vector_append(vector *pv,void *value) {
328 vector_resize( pv, pv->size + 1, 0, 0 );
329 vector_set( pv, pv->size - 1, value );
332 // copy block of n items from src[si] to dst[di]
333 // no efficiency hacks
334 void vector_copy(vector *dst,vector_index di,
335 vector *src,vector_index si,vector_index n) {
336 if ( dst != src || di < si ) {
338 vector_set( dst, di++, vector_get( src, si++ ) );
340 } else if ( di > si ){
344 vector_set( dst, di--, vector_get( src, si-- ) );
349 void vector_dump(vector *pv,
350 void (*itemdump)(const vector_index,const void *)) {
351 vector_index index = 0;
352 for ( ; index < pv->size; index++ ) {
353 void **slot = vector_next_used( pv, &index );
357 itemdump( index, *slot );
363 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
364 typedef int (*comparfn)(const void *,const void *);
366 static void vector_qsort_part(
367 vector *pv,comparfn compar,
368 vector_index low,vector_index high)
373 vector_index lo = low;
374 vector_index m = high - 1;
380 vector_index hi = m - 1;
381 void **mp = vector_entry( pv, m );
384 // Find index of first item "above" mp scanning from lo and up
385 for ( ; lo < m; lo++ ) {
386 lop = vector_entry( pv, lo );
387 if ( compar( *lop, *mp ) < 0 ) {
391 // if lo == m, then lop is wrong!!
392 // Find index of first item "below" mp scanning from hi and down
393 for ( ; hi > lo; hi-- ) {
394 hip = vector_entry( pv, hi );
395 if ( compar( *mp, *hip ) < 0 ) {
412 vector_qsort_part( pv, compar, low, m );
413 vector_qsort_part( pv, compar, m+1, high );
416 void vector_qsort(vector *pv,comparfn compar) {
417 vector_qsort_part( pv, compar, 0, pv->size );
420 void vector_iterate(vector *pv,
422 int (*itemfn)(vector_index,void*,void*),
425 vector_index index = start;
426 while ( index < pv->size ) {
427 void **slot = vector_next_used( pv, &index );
431 int i = index & VECTOR_LEVEL_MASK ;
432 for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) {
433 if ( itemfn( index, *slot, data ) ) {
440 // Find surrounding indexes for a given item key in a sparse vector
441 void *vector_bsearch(vector *pv,vector_index *index,const void *key,
442 int (*compare)(const void *key, const void *item)) {
444 vector_index hi = pv->size;
445 if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) {
450 vector_index m = lo + ( hi - lo ) / 2;
451 void **slot = vector_next_used( pv, &m );
452 int c = compare( key, *slot );