pvector/pvector.c

   1 #include <stdlib.h>
   2 #include "pvector.h"
   3
   4 /**
   5  * Representing a vector of void* accessible via an indexing structure
   6  * as levels of same-size pages. A "pvector_page" is a contiguous
   7  * array of 256 void*.
   8  */
   9
  10 /**
  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.
  17  */
  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++ ) {
  22         if ( *p ) {
  23             if ( level == 0 ) {
  24                 return p; // This is a used entry
  25             }
  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 );
  29             if ( x ) {
  30                 return x; // Used slot was found; return it.
  31             }
  32             // The page *p is all empty, so can/should be reclaimed.
  33             if ( whole ) {
  34                 free( *p );
  35                 *p = 0;
  36             }
  37         }
  38         if ( ++(((pvector_index*)index)->level[ level ]) == 0 ) {
  39             break; // cycling this level => nothing found
  40         }
  41     }
  42     return 0;
  43 }
  44
  45 static unsigned int pvector_levels(unsigned long S) {
  46     if ( S <= 1 ) {
  47         return 1;
  48     }
  49     return (unsigned int) ( 39 - __builtin_clz( S - 1 ) ) / 8;
  50 }
  51
  52 // Find the next used slot at given index or later. Returns pointer to
  53 // the slot.
  54 void **pvector_next_used(
  55     pvector *pv,unsigned long *index,
  56     int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
  57     void *data )
  58 {
  59     if ( pv->entries == 0 ) {
  60         *index = pv->size;
  61         return 0;
  62     }
  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 ) ;
  67         if ( slot == 0 ) {
  68             // reached the end of the vector
  69             *index = pv->size;
  70             break;
  71         }
  72         if ( *slot ) {
  73             // Try reclaiming the slot,
  74             if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
  75                 *slot = 0;
  76             } else {
  77                 return slot;
  78             }
  79         }
  80     }
  81     return 0;
  82 }
  83
  84 // Reclaim tree of unused pages
  85 static void pvector_reclaim(pvector_page *page,unsigned int level) {
  86     int i = 0;
  87     if ( level > 0 ) {
  88         for ( ; i < 256; i++ ) {
  89             if ( (*page)[i] ) {
  90                 pvector_reclaim( (pvector_page *) (*page)[i], level - 1 );
  91             }
  92         }
  93     }
  94     free( page );
  95 }
  96
  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.
 101 //
 102 // Nothe that resizing may result in the introduction/removal of
 103 // indexing levels and pages, so as to keep the leveling accurate for
 104 // the size.
 105 int pvector_resize(
 106     pvector *pv,unsigned long new_size,
 107     int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
 108     void *data )
 109 {
 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 ) {
 117         int d = 1;
 118         int i;
 119         for ( i = 0; i < 8; i++ ) {
 120             level_delta[ i ] = 255 * d;
 121             d = 256 * d;
 122         }
 123     }
 124     struct {
 125         int old;
 126         int new;
 127     } level = {
 128         pvector_levels( pv->size ),
 129         pvector_levels( new_size )
 130     };
 131     if ( pv->entries == 0 ) {
 132         pv->size = new_size;
 133         return 0;
 134     }
 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 );
 139         if ( slot ) {
 140             return index;
 141         }
 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];
 149         }
 150         if ( pp != &pv->entries ) {
 151             entries = pv->entries;
 152             pv->entries = *pp;
 153             *pp = 0;
 154             pvector_reclaim( entries, level.old );
 155         }
 156         if ( new_size == 0 ) {
 157             free( pv->entries );
 158             pv->entries = 0;
 159         }
 160     } else {
 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 ) );
 165             if ( p == 0 ) {
 166                 return -2; // OOM
 167             }
 168             (*p)[0] = pv->entries;
 169             pv->entries = p;
 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.
 173         }
 174     }
 175     pv->size = new_size;
 176     return -1;
 177 }
 178
 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)
 186 {
 187     if ( index >= pv->size ) {
 188         return 0;
 189     }
 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* ) );
 195         }
 196         page = (*page);
 197         if ( page == 0 ) {
 198             return 0;
 199         }
 200         page += ((pvector_index)index).level[ i ];
 201     }
 202     return page;
 203 }
 204
 205 // Map index into a value slot
 206 void **pvector_entry(pvector *pv,unsigned long index) {
 207     return pvector_access( pv, index, 0, 1 );
 208 }
 209
 210 inline void pvector_set(pvector *pv,unsigned long index,void *value) {
 211     void **p = pvector_entry( pv, index );
 212     *p = value;
 213 }
 214
 215 inline void *pvector_get(pvector *pv,unsigned long index) {
 216     return *(pvector_entry( pv, index ));
 217 }
 218
 219 int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) {
 220     free( item );
 221     return 0;
 222 }
 223
 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 );
 227 }
 228
 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 ) {
 234         while ( n-- != 0 ) {
 235             pvector_set( dst, di++, pvector_get( src, si++ ) );
 236         }
 237     } else if ( di > si ){
 238         di += n - 1;
 239         si += n - 1;
 240         while ( n-- != 0 ) {
 241             pvector_set( dst, di--, pvector_get( src, si-- ) );
 242         }
 243     }
 244 }
 245
 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 );
 251         if ( slot == 0 ) {
 252             break;
 253         }
 254         itemdump( index, *slot );
 255     }
 256 }
 257
 258 //// Quicksort
 259
 260 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 261 typedef int (*comparfn)(const void *,const void *);
 262
 263 static void pvector_qsort_part(
 264     pvector *pv,comparfn compar,
 265     unsigned long low,unsigned long high)
 266 {
 267     if ( low >= high ) {
 268         return;
 269     }
 270     unsigned long lo = low;
 271     unsigned long m = high - 1;
 272
 273     if ( lo >= m  ) {
 274         return;
 275     }
 276
 277     unsigned long hi = m - 1;
 278     void **mp = pvector_entry( pv, m );
 279     void **lop, **hip;
 280     for ( ;; ) {
 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 ) {
 285                 break;
 286             }
 287         }
 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 ) {
 293                 break;
 294             }
 295         }
 296         if ( lo >= hi ) {
 297             if ( lo < m ) {
 298                 void *x = *lop;
 299                 *lop = *mp;
 300                 *mp = x;
 301                 m = lo;
 302             }
 303             break;
 304         }
 305         void *x = *lop;
 306         *lop = *hip;
 307         *hip = x;
 308     }
 309     pvector_qsort_part( pv, compar, low, m );
 310     pvector_qsort_part( pv, compar, m+1, high );
 311 }
 312
 313 void pvector_qsort(pvector *pv,comparfn compar) {
 314     pvector_qsort_part( pv, compar, 0, pv->size );
 315 }
 316
 317 void pvector_iterate(pvector *pv,
 318                      int (*itemfn)(unsigned long,void*,void*),
 319                      void *data )
 320 {
 321     unsigned long index = 0;
 322     while ( index < pv->size ) {
 323         void **slot = pvector_next_used( pv, &index, 0, 0 );
 324         if ( slot == 0 ) {
 325             break;
 326         }
 327         int i = index & 0xff;
 328         for ( ; i < 256 && index < pv->size; i++, index++, slot++ ) {
 329             if ( itemfn( index, *slot, data ) ) {
 330                 return;
 331             }
 332         }
 333     }
 334 }