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,int 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 // Find the next used slot at given index or later. Returns pointer to
  46 // the slot.
  47 void **pvector_next_used(
  48     pvector *pv,unsigned long *index,
  49     int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
  50     void *data )
  51 {
  52     if ( pv->entries == 0 ) {
  53         *index = pv->size;
  54         return 0;
  55     }
  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 ) ;
  60         if ( slot == 0 ) {
  61             // reached the end of the vector
  62             *index = pv->size;
  63             break;
  64         }
  65         if ( *slot ) {
  66             // Try reclaiming the slot,
  67             if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
  68                 *slot = 0;
  69             } else {
  70                 return slot;
  71             }
  72         }
  73         (*index)++;
  74     }
  75     return 0;
  76 }
  77
  78 // Reclaim tree of unused pages
  79 static void pvector_reclaim(pvector_page *page) {
  80     int i = 0;
  81     for ( ; i < 256; i++ ) {
  82         if ( (*page)[i] ) {
  83             pvector_reclaim( (pvector_page *) (*page)[i] );
  84         }
  85     }
  86     free( page );
  87 }
  88
  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
  92 // OOM while growing.
  93 //
  94 // Nothe that resizing may result in the introduction/removal of
  95 // indexing levels and pages, so as to keep the leveling accurate for
  96 // the size.
  97 int pvector_resize(
  98     pvector *pv,unsigned long new_size,
  99     int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
 100     void *data )
 101 {
 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 ) {
 109         int d = 1;
 110         int i;
 111         for ( i = 0; i < 8; i++ ) {
 112             level_delta[ i ] = 255 * d;
 113             d = 256 * d;
 114         }
 115     }
 116     struct {
 117         int old;
 118         int new;
 119     } level = {
 120         PV_LEVELS( pv->size ),
 121         PV_LEVELS( new_size )
 122     };
 123     if ( pv->entries == 0 ) {
 124         pv->size = new_size;
 125         return 0;
 126     }
 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 );
 131         if ( slot ) {
 132             return index;
 133         }
 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];
 141         }
 142         if ( pp != &pv->entries ) {
 143             entries = pv->entries;
 144             pv->entries = *pp;
 145             *pp = 0;
 146             pvector_reclaim( entries );
 147         }
 148         if ( new_size == 0 ) {
 149             free( pv->entries );
 150             pv->entries = 0;
 151         }
 152     } else {
 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 ) );
 157             if ( p == 0 ) {
 158                 return -2; // OOM
 159             }
 160             (*p)[0] = pv->entries;
 161             pv->entries = p;
 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.
 165         }
 166     }
 167     pv->size = new_size;
 168     return -1;
 169 }
 170
 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)
 178 {
 179     if ( index >= pv->size ) {
 180         return 0;
 181     }
 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* ) );
 187         }
 188         page = (*page);
 189         if ( page == 0 ) {
 190             return 0;
 191         }
 192         page += ((pvector_index)index).level[ i ];
 193     }
 194     return page;
 195 }
 196
 197 // Map index into a value slot
 198 void **pvector_entry(pvector *pv,unsigned long index) {
 199     return pvector_access( pv, index, 0, 1 );
 200 }
 201
 202 inline void pvector_set(pvector *pv,unsigned long index,void *value) {
 203     void **p = pvector_entry( pv, index );
 204     *p = value;
 205 }
 206
 207 inline void *pvector_get(pvector *pv,unsigned long index) {
 208     return *(pvector_entry( pv, index ));
 209 }
 210
 211 int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) {
 212     free( item );
 213     return 0;
 214 }
 215
 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 );
 219 }
 220
 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 ) {
 226         while ( n-- != 0 ) {
 227             pvector_set( dst, di++, pvector_get( src, si++ ) );
 228         }
 229     } else if ( di > si ){
 230         di += n - 1;
 231         si += n - 1;
 232         while ( n-- != 0 ) {
 233             pvector_set( dst, di--, pvector_get( src, si-- ) );
 234         }
 235     }
 236 }
 237
 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 );
 242         if ( slot == 0 ) {
 243             break;
 244         }
 245         itemdump( index, *slot );
 246     }
 247 }
 248
 249 //// Quicksort
 250
 251 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 252 typedef int (*comparfn)(void *,void *);
 253
 254 static void pvector_qsort_part(
 255     pvector *pv,comparfn compar,
 256     unsigned long low,unsigned long high)
 257 {
 258     if ( low >= high ) {
 259         return;
 260     }
 261     unsigned long lo = low;
 262     unsigned long m = high - 1;
 263
 264     if ( lo >= m  ) {
 265         return;
 266     }
 267
 268     unsigned long hi = m - 1;
 269     void **mp = pvector_entry( pv, m );
 270     void **lop, **hip;
 271     for ( ;; ) {
 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 ) {
 276                 break;
 277             }
 278         }
 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 ) {
 284                 break;
 285             }
 286         }
 287         if ( lo >= hi ) {
 288             if ( lo < m ) {
 289                 void *x = *lop;
 290                 *lop = *mp;
 291                 *mp = x;
 292                 m = lo;
 293             }
 294             break;
 295         }
 296         void *x = *lop;
 297         *lop = *hip;
 298         *hip = x;
 299     }
 300     pvector_qsort_part( pv, compar, low, m );
 301     pvector_qsort_part( pv, compar, m+1, high );
 302 }
 303
 304 void pvector_qsort(pvector *pv,int (*compar)(void *,void *)) {
 305     pvector_qsort_part( pv, compar, 0, pv->size );
 306 }