5 * Representing a vector of void* accessible via an indexing structure
6 * as levels of same-size pages. A "pvector_page" is a contiguous
11 * Advances a pvector 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 **pvector_level_next_used(
19 pvector_page *page,unsigned long *index,int level,int end) {
20 void **p = (void**)&(*page)[ ((pvector_index*)index)->level[ 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 = ((pvector_index*)index)->level[ level - 1 ] == 0;
28 void **x = pvector_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 ( ++(((pvector_index*)index)->level[ level ]) == 0 ) {
39 break; // cycling this level => nothing found
45 // Find the next used slot at given index or later. Returns pointer to
47 void **pvector_next_used(
48 pvector *pv,unsigned long *index,
49 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
52 if ( pv->entries == 0 ) {
56 int levels = PV_LEVELS( pv->size );
57 for ( ; *index < pv->size; (*index)++ ) {
58 void **slot = pvector_level_next_used(
59 pv->entries, index, levels - 1, pv->size ) ;
61 // reached the end of the vector
66 // Try reclaiming the slot,
67 if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
78 // Reclaim tree of unused pages
79 static void pvector_reclaim(pvector_page *page) {
81 for ( ; i < 256; i++ ) {
83 pvector_reclaim( (pvector_page *) (*page)[i] );
89 // Resize vector, using the reclaim function as needed, to handle any
90 // excess items or to veto the resize. Returns the index of the veto, if
91 // any, or <0 otherwise, with -1 indicating success and -2 indicating
94 // Nothe that resizing may result in the introduction/removal of
95 // indexing levels and pages, so as to keep the leveling accurate for
98 pvector *pv,unsigned long new_size,
99 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
102 // Table of number of slots for a level above that of the number
103 // at the prior lower level.
104 // The first level (i.e., level 0) adds 255 slots to the one slot
105 // of no index page. Level 1 adds 255*256 slots, level 2 adds
106 // 255*(256^2), and generically level i adds 255*(256^i) slots.
107 static int level_delta[8];
108 if ( level_delta[ 0 ] == 0 ) {
111 for ( i = 0; i < 8; i++ ) {
112 level_delta[ i ] = 255 * d;
120 PV_LEVELS( pv->size ),
121 PV_LEVELS( new_size )
123 if ( pv->entries == 0 ) {
127 // A shrinking pvector might be veto-ed
128 if ( new_size < pv->size ) {
129 unsigned long index = new_size;
130 void **slot = pvector_next_used( pv, &index, reclaim, data );
134 // At this point we know that there are no slots used after
135 // the new_size size, so now it's time to remove and reclaim
136 // any superflouous top level pages.
137 pvector_page *entries;
138 pvector_page **pp = &pv->entries;
139 while ( level.old-- > level.new ) {
140 pp = (pvector_page **)(*pp)[0];
142 if ( pp != &pv->entries ) {
143 entries = pv->entries;
146 pvector_reclaim( entries );
148 if ( new_size == 0 ) {
153 // pvector is growing. Maybe insert levels.
154 while ( level.old < level.new ) {
155 pvector_page *p = (pvector_page *)
156 calloc( 1, sizeof( pvector_page ) );
160 (*p)[0] = pv->entries;
162 pv->size += level_delta[ level.old++ ];
163 // Note that the last level addition might make the size
164 // larger than requested, which gets corrected below.
171 // Return a pointer to the indexed item the given page level, adding
172 // intermediate pages if requested. Returns 0 if addition fails (OOM),
173 // or if not requested and page is missing.
174 // Level 0 = pointer to the item entry itself.
175 // Level PVECTORLEVELS( pv->size ) - 1 =
176 static void **pvector_access(
177 pvector *pv,unsigned long index,int level,int add)
179 if ( index >= pv->size ) {
182 void **page = (void**) &pv->entries;
183 int i = PV_LEVELS( pv->size );
184 while ( i-- > level ) {
185 if ( add && (*page) == 0 ) {
186 (*page) = calloc( 256, sizeof( void* ) );
192 page += ((pvector_index)index).level[ i ];
197 // Map index into a value slot
198 void **pvector_entry(pvector *pv,unsigned long index) {
199 return pvector_access( pv, index, 0, 1 );
202 inline void pvector_set(pvector *pv,unsigned long index,void *value) {
203 void **p = pvector_entry( pv, index );
207 inline void *pvector_get(pvector *pv,unsigned long index) {
208 return *(pvector_entry( pv, index ));
211 int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) {
216 void pvector_append(pvector *pv,void *value) {
217 pvector_resize( pv, pv->size + 1, 0, 0 );
218 pvector_set( pv, pv->size - 1, value );
221 // copy block of n items from src[si] to dst[di]
222 // no efficiency hacks
223 void pvector_copy(pvector *dst,unsigned long di,
224 pvector *src,unsigned long si,unsigned long n) {
225 if ( dst != src || di < si ) {
227 pvector_set( dst, di++, pvector_get( src, si++ ) );
229 } else if ( di > si ){
233 pvector_set( dst, di--, pvector_get( src, si-- ) );
238 void pvector_dump(pvector *pv,int (*itemdump)(unsigned long,void *)) {
239 unsigned long index = 0;
240 for ( ; index < pv->size; index++ ) {
241 void **slot = pvector_next_used( pv, &index, 0, 0 );
245 itemdump( index, *slot );
251 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
252 typedef int (*comparfn)(void *,void *);
254 static void pvector_qsort_part(
255 pvector *pv,comparfn compar,
256 unsigned long low,unsigned long high)
261 unsigned long lo = low;
262 unsigned long m = high - 1;
268 unsigned long hi = m - 1;
269 void **mp = pvector_entry( pv, m );
272 // Find index of first item "above" mp scanning from lo and up
273 for ( ; lo < m; lo++ ) {
274 lop = pvector_entry( pv, lo );
275 if ( compar( *lop, *mp ) < 0 ) {
279 // if lo == m, then lop is wrong!!
280 // Find index of first item "below" mp scanning from hi and down
281 for ( ; hi > lo; hi-- ) {
282 hip = pvector_entry( pv, hi );
283 if ( compar( *mp, *hip ) < 0 ) {
300 pvector_qsort_part( pv, compar, low, m );
301 pvector_qsort_part( pv, compar, m+1, high );
304 void pvector_qsort(pvector *pv,int (*compar)(void *,void *)) {
305 pvector_qsort_part( pv, compar, 0, pv->size );