7 * \brief Re-allocate memory for the index of a Single_index_level
10 static VectorPage* Vector_single_realloc(Vector *pv,size_t new_size) {
11 new_size = new_size * sizeof( void* );
12 VectorPage *p = (VectorPage*) malloc( new_size );
14 size_t old_size = pv->size * sizeof( void* );
15 if ( old_size < new_size ) {
16 memset( ((char*)p) + old_size, 0, new_size - old_size );
17 memcpy( p, pv->entries, old_size );
19 memcpy( p, pv->entries, new_size );
27 * \brief Re-allocate memory for the index of a Single_index_level
30 static VectorPage* Vector_indexpage_calloc(Vector *pv) {
31 size_t size = VECTOR_SLOTS( pv ) * sizeof( void* );
32 VectorPage *p = (VectorPage*) malloc( size );
40 * Representing a Vector of void* accessible via an indexing structure
41 * as levels of same-size pages. A "VectorPage" is a contiguous array
42 * void*, and an index is "unsigned long" (64 bits).
45 /** ============================================================ **/
47 static int VECTOR_BITS[4] = { 8, 4, 2, 64 };
66 * Return the index part for the given level of the Vector's leveling
69 * The Vector variant indicates whether indexing uses 8, 4, or 2 bits
72 unsigned long VECTOR_INDEX_PART(Vector *pv,VectorIndex *index, int level) {
73 unsigned char *px = (unsigned char *) index;
74 switch ( pv->variant ) {
75 case Byte_index_levels: {
76 Byte *pp = (Byte*)(px + level);
79 case Nibble_index_levels: {
80 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
81 switch ( level & 1 ) {
87 case BitPair_index_levels: {
88 BitPair *pp = (BitPair*)( px + ( level / 4 ) );
89 switch ( level & 3 ) {
97 case Single_index_level:
104 * Increment the index part at the indivated level, cyclic but not
105 * carrying over to the upper level. Returns the new level index.
107 static unsigned long VECTOR_INDEX_PART_INC(
108 Vector *pv,VectorIndex *index, int level)
110 unsigned char *px = (unsigned char *) index;
111 switch ( pv->variant ) {
112 case Byte_index_levels: {
113 Byte *pp = (Byte*)( px + level );
116 case Nibble_index_levels: {
117 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
118 switch ( level & 1 ) {
119 case 0: return ++(pp->a);
120 case 1: return ++(pp->b);
124 case BitPair_index_levels: {
125 BitPair *pp = (BitPair*)( px + level / 4 );
126 switch ( level & 3 ) {
127 case 0: return ++(pp->a);
128 case 1: return ++(pp->b);
129 case 2: return ++(pp->c);
130 case 3: return ++(pp->d);
134 case Single_index_level:
141 * Decrement the index part at the indicated level, cyclic but not
142 * carrying over to the upper level. Returns the prior level index.
144 static unsigned long VECTOR_INDEX_PART_DEC(
145 Vector *pv,VectorIndex *index, int level)
147 unsigned char *px = (unsigned char *) index;
148 switch ( pv->variant ) {
149 case Byte_index_levels: {
150 Byte *pp = (Byte*)( px + level );
153 case Nibble_index_levels: {
154 Nibble *pp = (Nibble*)( px + ( level / 2 ) );
155 switch ( level & 1 ) {
156 case 0: return (pp->a)--;
157 case 1: return (pp->b)--;
161 case BitPair_index_levels: {
162 BitPair *pp = (BitPair*)( px + level / 4 );
163 switch ( level & 0xf ) {
164 case 0: return (pp->a)--;
165 case 1: return (pp->b)--;
166 case 2: return (pp->c)--;
167 case 3: return (pp->d)--;
171 case Single_index_level:
177 #define ONES (~((VectorIndex) 0))
179 // Set index to first value for all index parts at level and lower.
180 static void VECTOR_INDEX_FIRST(Vector *pv,VectorIndex *index, int level) {
181 (*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
184 // Set index to last value for all index parts at level and lower.
185 static void VECTOR_INDEX_LAST(Vector *pv,VectorIndex *index, int level) {
186 static unsigned long ones[] = { 255, 15, 3 };
187 unsigned long x = ones[ pv->variant ];
190 x <<= VECTOR_BITS[ pv->variant ];
193 //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
196 // Return number of slots for a Vector variant.
197 unsigned long VECTOR_SLOTS(Vector *pv) {
198 switch ( pv->variant ) {
199 case Byte_index_levels: return 256;
200 case Nibble_index_levels: return 16;
201 case BitPair_index_levels: return 4;
202 case Single_index_level: return pv->size;
207 // The number of levels to span a given size for Vector pv
208 static unsigned int Vector_levels(Vector *pv,unsigned long size) {
209 if ( size < 4 || pv->variant == Single_index_level ) {
213 int w = 63 - __builtin_clzl( size );
214 switch ( pv->variant ) {
215 case Byte_index_levels: return ((int)(w / 8)) + 1;
216 case Nibble_index_levels: return ((int)(w / 4)) + 1;
217 case BitPair_index_levels: return ((int)(w / 2)) + 1;
218 case Single_index_level: return 1;
223 /** ============================================================ **/
226 * Advances a Vector index to the next used slot at or below the
227 * given level, starting from the indexed entry (inclusive) and up.
228 * The function will free any empty pages it discovers, and then
229 * update the index slots accordingly. The given index is advanced
230 * cyclically to match the found slot. The function returns a slot
231 * pointer to the used slot, if any, and 0 otherwise.
232 * The last parameter is a flag that gets set when the scanning is
233 * partial (i.e. not the whole index page).
235 static void **Vector_level_next_used(
242 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
243 if ( VECTOR_INDEX_PART( pv, index, level ) != 0 ) {
246 for( ; *index < pv->size; p++ ) {
249 return p; // This is a used entry
251 // *p is an index that needs to be inspected recursively
253 void **x = Vector_level_next_used( pv, *p, index, level - 1, &w );
255 return x; // Used slot was found; return it.
257 // If the page *p is all empty, so can/should be reclaimed.
266 VECTOR_INDEX_FIRST( pv, index, level - 1 );
269 if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
270 break; // cycling this level => nothing found
276 // Find the next used slot at given index or later. Returns pointer to
277 // the slot. This allows for a reclaim function that may reclaim slot
278 // items on the way to next used slot.
279 void **Vector_next_used(Vector *pv,VectorIndex *index) {
280 if ( pv->entries == 0 || *index >= pv->size ) {
284 int levels = Vector_levels( pv, pv->size );
287 void **slot = Vector_level_next_used(
288 pv, pv->entries, index, levels - 1, &partial ) ;
290 break; // reached the end of the Vector
295 } while ( ++(*index) < pv->size );
296 if ( partial == 0 ) {
300 *index = pv->size; // reached the end of the Vector
305 * Advances a Vector index to the prior used slot at or below the
306 * given level, starting from the indexed entry (inclusive) and down.
307 * The function will free any empty pages it discovers, and then
308 * update the index slots accordingly. The given index is advanced
309 * cyclically to match the found slot. The function returns a slot
310 * pointer to the used slot, if any, and 0 otherwise.
311 * The last parameter is a flag that gets set when the scanning is
312 * partial (i.e. not the whole index page).
314 static void **Vector_level_prev_used(
321 void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
322 if ( VECTOR_INDEX_PART( pv, index, level ) != VECTOR_SLOTS( pv ) - 1 ) {
328 return p; // This is a used entry
330 // *p is an index that needs to be inspected recursively
332 void **x = Vector_level_prev_used( pv, *p, index, level - 1, &w );
334 return x; // Used slot was found; return it.
336 // If the page *p is all empty, it can/should be reclaimed.
345 VECTOR_INDEX_LAST( pv, index, level );
349 } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 );
353 // Find the next used slot at given index or later. Returns pointer to
354 // the slot. This allows for a reclaim function that may reclaim slot
355 // items on the way to next used slot.
356 void **Vector_prev_used(Vector *pv,VectorIndex *index) {
357 if ( pv->entries == 0 || *index >= pv->size ) {
361 int levels = Vector_levels( pv, pv->size );
364 void **slot = Vector_level_prev_used(
365 pv, pv->entries, index, levels - 1, &partial ) ;
367 break; // reached the end of the Vector
372 } while ( (*index)-- != 0 );
373 if ( partial == 0 ) {
377 *index = pv->size; // reached the end of the Vector
381 // Reclaim tree of unused pages for a given level
382 static void Vector_reclaim(Vector *pv,VectorPage *page,unsigned int level) {
385 for ( ; i < VECTOR_SLOTS( pv ); i++ ) {
387 Vector_reclaim( pv, (VectorPage *) (*page)[i], level - 1 );
394 // Resize Vector, using the reclaim function as needed, to handle any
395 // excess items or to veto the resize. Returns the index of the veto,
396 // if any, or <0 otherwise, with -1 indicating success and -2
399 // Note that resizing may result in the introduction/removal of
400 // indexing levels and pages, so as to keep the leveling accurate for
403 Vector *pv,VectorIndex new_size,
404 int (*reclaim)(Vector *pv,VectorIndex index,void *item,void *data),
411 Vector_levels( pv, pv->size ),
412 Vector_levels( pv, new_size )
414 VectorPage *entries = 0;
415 if ( pv->entries == 0 ) {
419 // A shrinking Vector might be veto-ed
420 if ( new_size < pv->size ) {
421 VectorIndex index = new_size;
422 void **slot = Vector_next_used( pv, &index );
424 if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
426 slot = Vector_next_used( pv, &index );
431 // At this point we know that there are no slots used after
432 // the new_size size, so now it's time to remove and reclaim
433 // any superflouous top level pages.
434 if ( pv->variant == Single_index_level ) {
435 // Follow Vector size using realloc
436 if ( new_size > 0 ) {
437 entries = Vector_single_realloc( pv, new_size );
438 if ( entries == 0 ) {
442 pv->entries = entries;
444 VectorPage **pp = &pv->entries;
446 while ( i-- > level.new ) {
448 pp = (VectorPage **)(*pp);
451 if ( pp != &pv->entries ) {
452 entries = pv->entries;
455 *pp = 0; // Detach subtree
459 Vector_reclaim( pv, entries, level.old - 1 );
461 if ( new_size == 0 && pv->entries ) {
467 // Vector is growing. Maybe insert levels.
468 if ( pv->variant == Single_index_level ) {
469 // Follow Vector size using realloc
470 entries = Vector_single_realloc( pv, new_size );
471 if ( entries == 0 ) {
474 pv->entries = entries;
475 memset( &(*entries)[ pv->size ], 0,
476 ( new_size - pv->size ) * sizeof( void* ) );
478 for ( ; level.old < level.new; level.old++ ) {
479 VectorPage *p = Vector_indexpage_calloc( pv );
483 (*p)[0] = pv->entries;
485 // Should maybe change the size to match the level?
486 // otherwise recovery from OOM is impossible
494 // Return pointer to the indexed page slot at the requested level, and
495 // adding intermediate index pages if so requested. Returns 0 if
496 // addition fails (OOM), or if not requested and page is missing.
497 void **Vector_access(Vector *pv,VectorIndex index,int level,int add) {
498 if ( index >= pv->size ) {
501 void **page = (void**) &pv->entries;
502 int i = Vector_levels( pv, pv->size );
503 while ( i-- > level ) {
504 if ( add && (*page) == 0 ) {
505 (*page) = Vector_indexpage_calloc( pv );
511 page += VECTOR_INDEX_PART( pv, &index, i );
516 // Map index into a value slot
517 void **Vector_entry(Vector *pv,VectorIndex index) {
518 return Vector_access( pv, index, 0, 1 );
521 inline void Vector_set(Vector *pv,VectorIndex index,void *value) {
522 void **p = Vector_entry( pv, index );
526 // Set value at index but return the old value
527 void *Vector_get_set(Vector *pv,VectorIndex index,void *value) {
528 void **p = Vector_entry( pv, index );
534 inline void *Vector_get(Vector *pv,VectorIndex index) {
535 void **p = Vector_entry( pv, index );
539 int Vector_free_any(Vector *pv,VectorIndex ix,void *item,void *data) {
540 (void)pv; (void)ix; (void)data;
545 int Vector_clear_any(Vector *pv,VectorIndex ix,void *item,void *data) {
546 (void)pv; (void)ix; (void)item; (void)data;
550 void Vector_append(Vector *pv,void *value) {
551 Vector_resize( pv, pv->size + 1, 0, 0 );
552 Vector_set( pv, pv->size - 1, value );
555 // copy block of n items from src[si] to dst[di]
556 // no efficiency hacks
557 void Vector_copy(Vector *dst,VectorIndex di,
558 Vector *src,VectorIndex si,VectorIndex n) {
559 if ( dst != src || di < si ) {
561 Vector_set( dst, di++, Vector_get( src, si++ ) );
563 } else if ( di > si ){
567 Vector_set( dst, di--, Vector_get( src, si-- ) );
572 Vector *Vector_clone(enum VectorVariant variant,Vector *src) {
573 Vector *dst = (Vector*) malloc( sizeof( Vector ) );
574 (*dst) = (Vector) { .variant = variant, .size = 0, .entries = 0 };
575 Vector_resize( dst, src->size, 0, 0 );
576 Vector_copy( dst, 0, src, 0, src->size );
580 void Vector_dump(Vector *pv,
581 void (*itemdump)(const VectorIndex,const void *)) {
582 VectorIndex index = 0;
583 for ( ; index < pv->size; index++ ) {
584 void **slot = Vector_next_used( pv, &index );
588 itemdump( index, *slot );
594 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
595 typedef int (*ComparFn)(const void *,const void *);
597 static void Vector_qsort_part(
598 Vector *pv,ComparFn compar,
599 VectorIndex low,VectorIndex high)
604 VectorIndex lo = low;
605 VectorIndex m = high - 1;
611 VectorIndex hi = m - 1;
612 void **mp = Vector_entry( pv, m );
616 // Find index of first item "above" mp scanning from lo and up
617 for ( ; lo < m; lo++ ) {
618 lop = Vector_entry( pv, lo );
619 if ( compar( *lop, *mp ) < 0 ) {
623 // if lo == m, then lop is wrong!!
624 // Find index of first item "below" mp scanning from hi and down
625 for ( ; hi > lo; hi-- ) {
626 hip = Vector_entry( pv, hi );
627 if ( compar( *mp, *hip ) < 0 ) {
644 Vector_qsort_part( pv, compar, low, m );
645 Vector_qsort_part( pv, compar, m+1, high );
648 void Vector_qsort(Vector *pv,ComparFn compar) {
649 Vector_qsort_part( pv, compar, 0, pv->size );
652 void Vector_iterate(Vector *pv,
654 int (*itemfn)(VectorIndex,void*,void*),
657 VectorIndex index = start;
658 while ( index < pv->size ) {
659 int end = VECTOR_SLOTS( pv );
660 int i = index & ( end - 1 );
661 for ( ; i < end && index < pv->size; i++, index++ ) {
662 void **slot = Vector_access( pv, index, 0, 0 );
663 if ( itemfn( index, slot? *slot: 0, data ) ) {
675 static int Vector_find_item(VectorIndex index, void *item,void *data) {
676 struct FindData *fd = (struct FindData*)data;
677 if ( fd->value != item ) {
684 VectorIndex Vector_find(Vector *pv,void *value) {
685 struct FindData fd = {
689 Vector_iterate( pv, 0, Vector_find_item, &fd );
693 // Find surrounding indexes for a given item key in a sparse Vector
694 void *Vector_bsearch(Vector *pv,VectorIndex *index,const void *key,
695 int (*compare)(const void *key, const void *item)) {
697 VectorIndex hi = pv->size;
698 if ( hi-- == 0 || Vector_prev_used( pv, &hi ) == 0 ) {
703 VectorIndex m = lo + ( hi - lo ) / 2;
704 void **slot = Vector_next_used( pv, &m );
705 int c = compare( key, *slot );
719 // Iterator callback.
720 static int checkunused(VectorIndex index,void *item,void *data) {
721 VectorIndex *last = (VectorIndex*) data;
726 if ( *last > index ) {
727 // Only on the first iteration, with *last = Vector_sie
733 } else if ( index == (*last) ) {
740 // Scan forward for the next unused Vector slot
741 VectorIndex Vector_next_unused(Vector *pv,VectorIndex index) {
742 VectorIndex unused = Vector_size( pv );
743 Vector_iterate( pv, index, checkunused, &unused );