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,unsigned long 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 static unsigned int pvector_levels(unsigned long S) {
49 return (unsigned int) ( 39 - __builtin_clz( S - 1 ) ) / 8;
52 // Find the next used slot at given index or later. Returns pointer to
54 void **pvector_next_used(
55 pvector *pv,unsigned long *index,
56 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
59 if ( pv->entries == 0 ) {
63 int levels = pvector_levels( pv->size );
64 for ( ; *index < pv->size; (*index)++ ) {
65 void **slot = pvector_level_next_used(
66 pv->entries, index, levels - 1, pv->size ) ;
68 // reached the end of the vector
73 // Try reclaiming the slot,
74 if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
84 // Reclaim tree of unused pages
85 static void pvector_reclaim(pvector_page *page,unsigned int level) {
88 for ( ; i < 256; i++ ) {
90 pvector_reclaim( (pvector_page *) (*page)[i], level - 1 );
97 // Resize vector, using the reclaim function as needed, to handle any
98 // excess items or to veto the resize. Returns the index of the veto, if
99 // any, or <0 otherwise, with -1 indicating success and -2 indicating
100 // OOM while growing.
102 // Nothe that resizing may result in the introduction/removal of
103 // indexing levels and pages, so as to keep the leveling accurate for
106 pvector *pv,unsigned long new_size,
107 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
110 // Table of number of slots for a level above that of the number
111 // at the prior lower level.
112 // The first level (i.e., level 0) adds 255 slots to the one slot
113 // of no index page. Level 1 adds 255*256 slots, level 2 adds
114 // 255*(256^2), and generically level i adds 255*(256^i) slots.
115 static int level_delta[8];
116 if ( level_delta[ 0 ] == 0 ) {
119 for ( i = 0; i < 8; i++ ) {
120 level_delta[ i ] = 255 * d;
128 pvector_levels( pv->size ),
129 pvector_levels( new_size )
131 if ( pv->entries == 0 ) {
135 // A shrinking pvector might be veto-ed
136 if ( new_size < pv->size ) {
137 unsigned long index = new_size;
138 void **slot = pvector_next_used( pv, &index, reclaim, data );
142 // At this point we know that there are no slots used after
143 // the new_size size, so now it's time to remove and reclaim
144 // any superflouous top level pages.
145 pvector_page *entries;
146 pvector_page **pp = &pv->entries;
147 while ( level.old-- > level.new ) {
148 pp = (pvector_page **)(*pp)[0];
150 if ( pp != &pv->entries ) {
151 entries = pv->entries;
154 pvector_reclaim( entries, level.old );
156 if ( new_size == 0 ) {
161 // pvector is growing. Maybe insert levels.
162 while ( level.old < level.new ) {
163 pvector_page *p = (pvector_page *)
164 calloc( 1, sizeof( pvector_page ) );
168 (*p)[0] = pv->entries;
170 pv->size += level_delta[ level.old++ ];
171 // Note that the last level addition might make the size
172 // larger than requested, which gets corrected below.
179 // Return a pointer to the indexed item the given page level, adding
180 // intermediate pages if requested. Returns 0 if addition fails (OOM),
181 // or if not requested and page is missing.
182 // Level 0 = pointer to the item entry itself.
183 // Level PVECTORLEVELS( pv->size ) - 1 =
184 static void **pvector_access(
185 pvector *pv,unsigned long index,int level,int add)
187 if ( index >= pv->size ) {
190 void **page = (void**) &pv->entries;
191 int i = pvector_levels( pv->size );
192 while ( i-- > level ) {
193 if ( add && (*page) == 0 ) {
194 (*page) = calloc( 256, sizeof( void* ) );
200 page += ((pvector_index)index).level[ i ];
205 // Map index into a value slot
206 void **pvector_entry(pvector *pv,unsigned long index) {
207 return pvector_access( pv, index, 0, 1 );
210 inline void pvector_set(pvector *pv,unsigned long index,void *value) {
211 void **p = pvector_entry( pv, index );
215 inline void *pvector_get(pvector *pv,unsigned long index) {
216 return *(pvector_entry( pv, index ));
219 int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) {
224 void pvector_append(pvector *pv,void *value) {
225 pvector_resize( pv, pv->size + 1, 0, 0 );
226 pvector_set( pv, pv->size - 1, value );
229 // copy block of n items from src[si] to dst[di]
230 // no efficiency hacks
231 void pvector_copy(pvector *dst,unsigned long di,
232 pvector *src,unsigned long si,unsigned long n) {
233 if ( dst != src || di < si ) {
235 pvector_set( dst, di++, pvector_get( src, si++ ) );
237 } else if ( di > si ){
241 pvector_set( dst, di--, pvector_get( src, si-- ) );
246 void pvector_dump(pvector *pv,
247 int (*itemdump)(const unsigned long,const void *)) {
248 unsigned long index = 0;
249 for ( ; index < pv->size; index++ ) {
250 void **slot = pvector_next_used( pv, &index, 0, 0 );
254 itemdump( index, *slot );
260 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
261 typedef int (*comparfn)(const void *,const void *);
263 static void pvector_qsort_part(
264 pvector *pv,comparfn compar,
265 unsigned long low,unsigned long high)
270 unsigned long lo = low;
271 unsigned long m = high - 1;
277 unsigned long hi = m - 1;
278 void **mp = pvector_entry( pv, m );
281 // Find index of first item "above" mp scanning from lo and up
282 for ( ; lo < m; lo++ ) {
283 lop = pvector_entry( pv, lo );
284 if ( compar( *lop, *mp ) < 0 ) {
288 // if lo == m, then lop is wrong!!
289 // Find index of first item "below" mp scanning from hi and down
290 for ( ; hi > lo; hi-- ) {
291 hip = pvector_entry( pv, hi );
292 if ( compar( *mp, *hip ) < 0 ) {
309 pvector_qsort_part( pv, compar, low, m );
310 pvector_qsort_part( pv, compar, m+1, high );
313 void pvector_qsort(pvector *pv,comparfn compar) {
314 pvector_qsort_part( pv, compar, 0, pv->size );
317 void pvector_iterate(pvector *pv,
318 int (*itemfn)(unsigned long,void*,void*),
321 unsigned long index = 0;
322 while ( index < pv->size ) {
323 void **slot = pvector_next_used( pv, &index, 0, 0 );
327 int i = index & 0xff;
328 for ( ; i < 256 && index < pv->size; i++, index++, slot++ ) {
329 if ( itemfn( index, *slot, data ) ) {