7 * Representing a Vector of void* accessible via an indexing structure
8 * as levels of same-size pages. A "VectorPage" is a contiguous array
9 * void*, and an index is "unsigned long" (64 bits).
12 /** ============================================================ **/
14 static int VECTOR_BITS[4] = { 8, 4, 2, 64 };
33 * Return the index part for the given level of the Vector's leveling
36 * The Vector variant indicates whether indexing uses 8, 4, or 2 bits
39 unsigned long VECTOR_INDEX_PART(Vector *pv,VectorIndex *index, int level) {
40 unsigned char *px = (unsigned char *) index;
41 switch ( pv->variant ) {
42 case byte_index_levels: {
43 Byte *pp = (Byte*)(px + level);
46 case Nibble_index_levels: {
47 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
48 switch ( level & 1 ) {
54 case BitPair_index_levels: {
55 BitPair *pp = (BitPair*)( px + ( level / 4 ) );
56 switch ( level & 3 ) {
64 case single_index_level:
71 * Increment the index part at the indivated level, cyclic but not
72 * carrying over to the upper level. Returns the new level index.
74 static unsigned long VECTOR_INDEX_PART_INC(
75 Vector *pv,VectorIndex *index, int level)
77 unsigned char *px = (unsigned char *) index;
78 switch ( pv->variant ) {
79 case byte_index_levels: {
80 Byte *pp = (Byte*)( px + level );
83 case Nibble_index_levels: {
84 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
85 switch ( level & 1 ) {
86 case 0: return ++(pp->a);
87 case 1: return ++(pp->b);
91 case BitPair_index_levels: {
92 BitPair *pp = (BitPair*)( px + level / 4 );
93 switch ( level & 3 ) {
94 case 0: return ++(pp->a);
95 case 1: return ++(pp->b);
96 case 2: return ++(pp->c);
97 case 3: return ++(pp->d);
101 case single_index_level:
108 * Decrement the index part at the indicated level, cyclic but not
109 * carrying over to the upper level. Returns the prior level index.
111 static unsigned long VECTOR_INDEX_PART_DEC(
112 Vector *pv,VectorIndex *index, int level)
114 unsigned char *px = (unsigned char *) index;
115 switch ( pv->variant ) {
116 case byte_index_levels: {
117 Byte *pp = (Byte*)( px + level );
120 case Nibble_index_levels: {
121 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
122 switch ( level & 1 ) {
123 case 0: return (pp->a)--;
124 case 1: return (pp->b)--;
128 case BitPair_index_levels: {
129 BitPair *pp = (BitPair*)( px + level / 4 );
130 switch ( level & 0xf ) {
131 case 0: return (pp->a)--;
132 case 1: return (pp->b)--;
133 case 2: return (pp->c)--;
134 case 3: return (pp->d)--;
138 case single_index_level:
144 #define ONES (~((VectorIndex) 0))
146 // Set index to first value for all index parts at level and lower.
147 static void VECTOR_INDEX_FIRST(Vector *pv,VectorIndex *index, int level) {
148 (*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
151 // Set index to last value for all index parts at level and lower.
152 static void VECTOR_INDEX_LAST(Vector *pv,VectorIndex *index, int level) {
153 static unsigned long ones[] = { 255, 15, 3 };
154 unsigned long x = ones[ pv->variant ];
157 x <<= VECTOR_BITS[ pv->variant ];
160 //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
163 // Return number of slots for a Vector variant.
164 unsigned long VECTOR_SLOTS(Vector *pv) {
165 switch ( pv->variant ) {
166 case byte_index_levels: return 256;
167 case Nibble_index_levels: return 16;
168 case BitPair_index_levels: return 4;
169 case single_index_level: return pv->size;
174 // The number of levels to span Vector pv wrt its size and variant
175 static unsigned int Vector_levels(Vector *pv,unsigned int size) {
179 switch ( pv->variant ) {
180 case byte_index_levels: return ((int)(log2( size - 1 ) / 8)) + 1;
181 case Nibble_index_levels: return ((int)(log2( size - 1 ) / 4)) + 1;
182 case BitPair_index_levels: return ((int)(log2( size - 1 ) / 2)) + 1;
183 case single_index_level: return 1;
188 /** ============================================================ **/
191 * Advances a Vector index to the next used slot at or below the
192 * given level, starting from the indexed entry (inclusive) and up.
193 * The function will free any empty pages it discovers, and then
194 * update the index slots accordingly. The given index is advanced
195 * cyclically to match the found slot. The function returns a slot
196 * pointer to the used slot, if any, and 0 otherwise.
197 * The last parameter is a flag that gets set when the scanning is
198 * partial (i.e. not the whole index page).
200 static void **Vector_level_next_used(
207 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
208 if ( VECTOR_INDEX_PART( pv, index, level ) != 0 ) {
211 for( ; *index < pv->size; p++ ) {
214 return p; // This is a used entry
216 // *p is an index that needs to be inspected recursively
218 void **x = Vector_level_next_used( pv, *p, index, level - 1, &w );
220 return x; // Used slot was found; return it.
222 // If the page *p is all empty, so can/should be reclaimed.
231 VECTOR_INDEX_FIRST( pv, index, level - 1 );
234 if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
235 break; // cycling this level => nothing found
241 // Find the next used slot at given index or later. Returns pointer to
242 // the slot. This allows for a reclaim function that may reclaim slot
243 // items on the way to next used slot.
244 void **Vector_next_used(Vector *pv,VectorIndex *index) {
245 if ( pv->entries == 0 || *index >= pv->size ) {
249 int levels = Vector_levels( pv, pv->size );
252 void **slot = Vector_level_next_used(
253 pv, pv->entries, index, levels - 1, &partial ) ;
255 break; // reached the end of the Vector
260 } while ( ++(*index) < pv->size );
261 if ( partial == 0 ) {
265 *index = pv->size; // reached the end of the Vector
270 * Advances a Vector index to the prior used slot at or below the
271 * given level, starting from the indexed entry (inclusive) and down.
272 * The function will free any empty pages it discovers, and then
273 * update the index slots accordingly. The given index is advanced
274 * cyclically to match the found slot. The function returns a slot
275 * pointer to the used slot, if any, and 0 otherwise.
276 * The last parameter is a flag that gets set when the scanning is
277 * partial (i.e. not the whole index page).
279 static void **Vector_level_prev_used(
286 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
287 if ( VECTOR_INDEX_PART( pv, index, level ) != VECTOR_SLOTS( pv ) - 1 ) {
293 return p; // This is a used entry
295 // *p is an index that needs to be inspected recursively
297 void **x = Vector_level_prev_used( pv, *p, index, level - 1, &w );
299 return x; // Used slot was found; return it.
301 // If the page *p is all empty, it can/should be reclaimed.
310 VECTOR_INDEX_LAST( pv, index, level );
314 } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 );
318 // Find the next used slot at given index or later. Returns pointer to
319 // the slot. This allows for a reclaim function that may reclaim slot
320 // items on the way to next used slot.
321 void **Vector_prev_used(Vector *pv,VectorIndex *index) {
322 if ( pv->entries == 0 || *index >= pv->size ) {
326 int levels = Vector_levels( pv, pv->size );
329 void **slot = Vector_level_prev_used(
330 pv, pv->entries, index, levels - 1, &partial ) ;
332 break; // reached the end of the Vector
337 } while ( (*index)-- != 0 );
338 if ( partial == 0 ) {
342 *index = pv->size; // reached the end of the Vector
346 // Reclaim tree of unused pages for a given level
347 static void Vector_reclaim(Vector *pv,VectorPage *page,unsigned int level) {
350 for ( ; i < VECTOR_SLOTS( pv ); i++ ) {
352 Vector_reclaim( pv, (VectorPage *) (*page)[i], level - 1 );
359 // Resize Vector, using the reclaim function as needed, to handle any
360 // excess items or to veto the resize. Returns the index of the veto,
361 // if any, or <0 otherwise, with -1 indicating success and -2
364 // Note that resizing may result in the introduction/removal of
365 // indexing levels and pages, so as to keep the leveling accurate for
368 Vector *pv,VectorIndex new_size,
369 int (*reclaim)(Vector *pv,VectorIndex index,void *item,void *data),
376 Vector_levels( pv, pv->size ),
377 Vector_levels( pv, new_size )
379 VectorPage *entries = 0;
380 if ( pv->entries == 0 ) {
384 // A shrinking Vector might be veto-ed
385 if ( new_size < pv->size ) {
386 VectorIndex index = new_size;
387 void **slot = Vector_next_used( pv, &index );
389 if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
391 slot = Vector_next_used( pv, &index );
396 // At this point we know that there are no slots used after
397 // the new_size size, so now it's time to remove and reclaim
398 // any superflouous top level pages.
399 if ( pv->variant == single_index_level ) {
400 // Follow Vector size using realloc
401 if ( new_size > 0 ) {
402 entries = (VectorPage*)
403 realloc( pv->entries, new_size * sizeof( void* ) );
404 if ( entries == 0 ) {
408 pv->entries = entries;
410 VectorPage **pp = &pv->entries;
412 while ( i-- > level.new ) {
414 pp = (VectorPage **)(*pp);
417 if ( pp != &pv->entries ) {
418 entries = pv->entries;
421 *pp = 0; // Detach subtree
425 Vector_reclaim( pv, entries, level.old - 1 );
427 if ( new_size == 0 && pv->entries ) {
433 // Vector is growing. Maybe insert levels.
434 if ( pv->variant == single_index_level ) {
435 // Follow Vector size using realloc
436 entries = (VectorPage *)realloc(
437 pv->entries, new_size * sizeof( void* ) );
438 if ( entries == 0 ) {
441 pv->entries = entries;
442 memset( &(*entries)[ pv->size ], 0,
443 ( new_size - pv->size ) * sizeof( void* ) );
445 for ( ; level.old < level.new; level.old++ ) {
446 VectorPage *p = (VectorPage *)
447 calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
451 (*p)[0] = pv->entries;
453 // Should maybe change the size to match the level?
454 // otherwise recovery from OOM is impossible
462 // Return pointer to the indexed page slot at the requested level, and
463 // adding intermediate index pages if so requested. Returns 0 if
464 // addition fails (OOM), or if not requested and page is missing.
465 void **Vector_access(Vector *pv,VectorIndex index,int level,int add) {
466 if ( index >= pv->size ) {
469 void **page = (void**) &pv->entries;
470 int i = Vector_levels( pv, pv->size );
471 while ( i-- > level ) {
472 if ( add && (*page) == 0 ) {
473 (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
479 page += VECTOR_INDEX_PART( pv, &index, i );
484 // Map index into a value slot
485 void **Vector_entry(Vector *pv,VectorIndex index) {
486 return Vector_access( pv, index, 0, 1 );
489 inline void Vector_set(Vector *pv,VectorIndex index,void *value) {
490 void **p = Vector_entry( pv, index );
494 // Set value at index but return the old value
495 void *Vector_get_set(Vector *pv,VectorIndex index,void *value) {
496 void **p = Vector_entry( pv, index );
502 inline void *Vector_get(Vector *pv,VectorIndex index) {
503 void **p = Vector_entry( pv, index );
507 int Vector_free_any(Vector *pv,VectorIndex ix,void *item,void *data) {
512 int Vector_clear_any(Vector *pv,VectorIndex ix,void *item,void *data) {
516 void Vector_append(Vector *pv,void *value) {
517 Vector_resize( pv, pv->size + 1, 0, 0 );
518 Vector_set( pv, pv->size - 1, value );
521 // copy block of n items from src[si] to dst[di]
522 // no efficiency hacks
523 void Vector_copy(Vector *dst,VectorIndex di,
524 Vector *src,VectorIndex si,VectorIndex n) {
525 if ( dst != src || di < si ) {
527 Vector_set( dst, di++, Vector_get( src, si++ ) );
529 } else if ( di > si ){
533 Vector_set( dst, di--, Vector_get( src, si-- ) );
538 Vector *Vector_clone(enum VectorVariant variant,Vector *src) {
539 Vector *dst = (Vector*) malloc( sizeof( Vector ) );
540 (*dst) = (Vector) { .variant = variant, .size = 0, .entries = 0 };
541 Vector_resize( dst, src->size, 0, 0 );
542 Vector_copy( dst, 0, src, 0, src->size );
546 void Vector_dump(Vector *pv,
547 void (*itemdump)(const VectorIndex,const void *)) {
548 VectorIndex index = 0;
549 for ( ; index < pv->size; index++ ) {
550 void **slot = Vector_next_used( pv, &index );
554 itemdump( index, *slot );
560 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
561 typedef int (*ComparFn)(const void *,const void *);
563 static void Vector_qsort_part(
564 Vector *pv,ComparFn compar,
565 VectorIndex low,VectorIndex high)
570 VectorIndex lo = low;
571 VectorIndex m = high - 1;
577 VectorIndex hi = m - 1;
578 void **mp = Vector_entry( pv, m );
581 // Find index of first item "above" mp scanning from lo and up
582 for ( ; lo < m; lo++ ) {
583 lop = Vector_entry( pv, lo );
584 if ( compar( *lop, *mp ) < 0 ) {
588 // if lo == m, then lop is wrong!!
589 // Find index of first item "below" mp scanning from hi and down
590 for ( ; hi > lo; hi-- ) {
591 hip = Vector_entry( pv, hi );
592 if ( compar( *mp, *hip ) < 0 ) {
609 Vector_qsort_part( pv, compar, low, m );
610 Vector_qsort_part( pv, compar, m+1, high );
613 void Vector_qsort(Vector *pv,ComparFn compar) {
614 Vector_qsort_part( pv, compar, 0, pv->size );
617 void Vector_iterate(Vector *pv,
619 int (*itemfn)(VectorIndex,void*,void*),
622 VectorIndex index = start;
623 while ( index < pv->size ) {
624 int end = VECTOR_SLOTS( pv );
625 int i = index & ( end - 1 );
626 for ( ; i < end && index < pv->size; i++, index++ ) {
627 void **slot = Vector_access( pv, index, 0, 0 );
628 if ( itemfn( index, slot? *slot: 0, data ) ) {
640 static int Vector_find_item(VectorIndex index, void *item,void *data) {
641 struct find_data *fd = (struct find_data*)data;
642 if ( fd->value != item ) {
649 VectorIndex Vector_find(Vector *pv,void *value) {
650 struct find_data fd = {
654 Vector_iterate( pv, 0, Vector_find_item, &fd );
658 // Find surrounding indexes for a given item key in a sparse Vector
659 void *Vector_bsearch(Vector *pv,VectorIndex *index,const void *key,
660 int (*compare)(const void *key, const void *item)) {
662 VectorIndex hi = pv->size;
663 if ( hi-- == 0 || Vector_prev_used( pv, &hi ) == 0 ) {
668 VectorIndex m = lo + ( hi - lo ) / 2;
669 void **slot = Vector_next_used( pv, &m );
670 int c = compare( key, *slot );
684 // Iterator callback.
685 static int checkunused(VectorIndex index,void *item,void *data) {
686 VectorIndex *last = (VectorIndex*) data;
691 if ( *last > index ) {
692 // Only on the first iteration, with *last = Vector_sie
698 } else if ( index == (*last) ) {
705 // Scan forward for the next unused Vector slot
706 VectorIndex Vector_next_unused(Vector *pv,VectorIndex index) {
707 VectorIndex unused = Vector_size( pv );
708 Vector_iterate( pv, index, checkunused, &unused );