5 * Representing a vector of void* accessible via an indexing structure
6 * as levels of same-size pages. A "qvector_page" is a contiguous
11 * Advances a qvector index to the next used slot at or below the
12 * given level, starting from the indexed entry (inclusive) and up.
13 * The function will free any empty pages it discovers, and then
14 * update the index slots accordingly. The given index is advanced
15 * cyclically to match the found slot. The function returns a slot
16 * pointer to the used slot, if any, and 0 otherwise.
18 static void **qvector_level_next_used(
19 qvector_page *page,qvector_index *index,int level,qvector_index end) {
20 void **p = (void**)&(*page)[ PV_PART( index, level ) ];
21 for( ; *index < end; p++ ) {
24 return p; // This is a used entry
26 // *p is an index that needs to be inspected recursively
27 int whole = PV_PART( index, level - 1 ) == 0;
28 void **x = qvector_level_next_used( *p, index, level - 1, end );
30 return x; // Used slot was found; return it.
32 // The page *p is all empty, so can/should be reclaimed.
38 if ( ++PV_PART( index, level ) == 0 ) {
39 break; // cycling this level => nothing found
45 // The least number of levels to span index S (typically the size of a
47 static unsigned int qvector_levels(qvector_index S) {
56 // Find the next used slot at given index or later. Returns pointer to
58 void **qvector_next_used(
59 qvector *pv,qvector_index *index,
60 int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
63 if ( pv->entries == 0 ) {
67 int levels = qvector_levels( pv->size );
68 for ( ; *index < pv->size; (*index)++ ) {
69 void **slot = qvector_level_next_used(
70 pv->entries, index, levels - 1, pv->size ) ;
72 // reached the end of the vector
77 // Try reclaiming the slot,
78 if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
88 // Reclaim tree of unused pages
89 static void qvector_reclaim(qvector_page *page,unsigned int level) {
92 for ( ; i < QV_SLOTS; i++ ) {
94 qvector_reclaim( (qvector_page *) (*page)[i], level - 1 );
101 // Resize vector, using the reclaim function as needed, to handle any
102 // excess items or to veto the resize. Returns the index of the veto, if
103 // any, or <0 otherwise, with -1 indicating success and -2 indicating
104 // OOM while growing.
106 // Nothe that resizing may result in the introduction/removal of
107 // indexing levels and pages, so as to keep the leveling accurate for
110 qvector *pv,qvector_index new_size,
111 int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
114 // Table of number of slots for a level above that of the number
115 // at the prior lower level. The first level (i.e., level 0) adds
116 // 15 slots to the one slot of no index page. Level 1 adds 15*16
117 // slots, level 2 adds 15*(16^2), and generically level i adds
119 static int level_delta[ QV_INDEX_FIELDS ];
120 if ( level_delta[ 0 ] == 0 ) {
123 for ( i = 0; i < QV_INDEX_FIELDS; i++ ) {
124 level_delta[ i ] = 15 * d;
132 qvector_levels( pv->size ),
133 qvector_levels( new_size )
135 if ( pv->entries == 0 ) {
139 // A shrinking qvector might be veto-ed
140 if ( new_size < pv->size ) {
141 qvector_index index = new_size;
142 void **slot = qvector_next_used( pv, &index, reclaim, data );
146 // At this point we know that there are no slots used after
147 // the new_size size, so now it's time to remove and reclaim
148 // any superflouous top level pages.
149 qvector_page *entries;
150 qvector_page **pp = &pv->entries;
151 while ( level.old-- > level.new ) {
152 pp = (qvector_page **)(*pp)[0];
154 if ( pp != &pv->entries ) {
155 entries = pv->entries;
158 qvector_reclaim( entries, level.old );
160 if ( new_size == 0 ) {
165 // qvector is growing. Maybe insert levels.
166 while ( level.old < level.new ) {
167 qvector_page *p = (qvector_page *)
168 calloc( 1, sizeof( qvector_page ) );
172 (*p)[0] = pv->entries;
174 pv->size += level_delta[ level.old++ ];
175 // Note that the last level addition might make the size
176 // larger than requested, which gets corrected below.
183 // Return a pointer to the indexed item the given page level, adding
184 // intermediate pages if requested. Returns 0 if addition fails (OOM),
185 // or if not requested and page is missing.
186 // Level 0 = pointer to the item entry itself.
187 // Level QVECTORLEVELS( pv->size ) - 1 =
188 static void **qvector_access(
189 qvector *pv,qvector_index index,int level,int add)
191 if ( index >= pv->size ) {
194 void **page = (void**) &pv->entries;
195 int i = qvector_levels( pv->size );
196 while ( i-- > level ) {
197 if ( add && (*page) == 0 ) {
198 (*page) = calloc( QV_SLOTS, sizeof( void* ) );
204 page += PV_PART( &index, i );
209 // Map index into a value slot
210 void **qvector_entry(qvector *pv,qvector_index index) {
211 return qvector_access( pv, index, 0, 1 );
214 inline void qvector_set(qvector *pv,qvector_index index,void *value) {
215 void **p = qvector_entry( pv, index );
219 inline void *qvector_get(qvector *pv,qvector_index index) {
220 return *(qvector_entry( pv, index ));
223 int qvector_reclaim_any(qvector *pv,qvector_index ix,void *item,void *data) {
228 void qvector_append(qvector *pv,void *value) {
229 qvector_resize( pv, pv->size + 1, 0, 0 );
230 qvector_set( pv, pv->size - 1, value );
233 // copy block of n items from src[si] to dst[di]
234 // no efficiency hacks
235 void qvector_copy(qvector *dst,qvector_index di,
236 qvector *src,qvector_index si,qvector_index n) {
237 if ( dst != src || di < si ) {
239 qvector_set( dst, di++, qvector_get( src, si++ ) );
241 } else if ( di > si ){
245 qvector_set( dst, di--, qvector_get( src, si-- ) );
250 void qvector_dump(qvector *pv,
251 int (*itemdump)(const qvector_index,const void *)) {
252 qvector_index index = 0;
253 for ( ; index < pv->size; index++ ) {
254 void **slot = qvector_next_used( pv, &index, 0, 0 );
258 itemdump( index, *slot );
264 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
265 typedef int (*comparfn)(const void *,const void *);
267 static void qvector_qsort_part(
268 qvector *pv,comparfn compar,
269 qvector_index low,qvector_index high)
274 qvector_index lo = low;
275 qvector_index m = high - 1;
281 qvector_index hi = m - 1;
282 void **mp = qvector_entry( pv, m );
285 // Find index of first item "above" mp scanning from lo and up
286 for ( ; lo < m; lo++ ) {
287 lop = qvector_entry( pv, lo );
288 if ( compar( *lop, *mp ) < 0 ) {
292 // if lo == m, then lop is wrong!!
293 // Find index of first item "below" mp scanning from hi and down
294 for ( ; hi > lo; hi-- ) {
295 hip = qvector_entry( pv, hi );
296 if ( compar( *mp, *hip ) < 0 ) {
313 qvector_qsort_part( pv, compar, low, m );
314 qvector_qsort_part( pv, compar, m+1, high );
317 void qvector_qsort(qvector *pv,comparfn compar) {
318 qvector_qsort_part( pv, compar, 0, pv->size );
321 void qvector_iterate(qvector *pv,
322 int (*itemfn)(qvector_index,void*,void*),
325 qvector_index index = 0;
326 while ( index < pv->size ) {
327 void **slot = qvector_next_used( pv, &index, 0, 0 );
331 int i = index & 0xff;
332 for ( ; i < QV_SLOTS && index < pv->size; i++, index++, slot++ ) {
333 if ( itemfn( index, *slot, data ) ) {