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 int *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
  46 void **pvector_next_used(pvector *pv,unsigned int *index,
  47                          int (*reclaim)(pvector *,int,void*) )
  48 {
  49     int levels = PV_LEVELS( pv->size );
  50     while ( *index < pv->size ) {
  51         void **slot = pvector_level_next_used(
  52             pv->entries, index, levels - 1, pv->size ) ;
  53         if ( slot && *slot ) {
  54             if ( reclaim && reclaim( pv, *index, *slot ) == 0 ) {
  55                 *slot = 0;
  56             } else {
  57                 return *slot;
  58             }
  59         }
  60         (*index)++;
  61     }
  62     return 0;
  63 }
  64
  65 // Reclaim tree of unused pages
  66 static void pvector_reclaim(pvector_page *page) {
  67     int i = 0;
  68     for ( ; i < 256; i++ ) {
  69         if ( (*page)[i] ) {
  70             pvector_reclaim( (pvector_page *) (*page)[i] );
  71         }
  72     }
  73     free( page );
  74 }
  75
  76 // Resize vector, using the reclaim function as needed, to handle any
  77 // excess items or to veto the resize. Returns the index of the veto, if
  78 // any, or <0 otherwise, with -1 indicating success and -2 indicating
  79 // OOM while growing.
  80 //
  81 // Nothe that resizing may result in the introduction/removal of
  82 // indexing levels and pages, so as to keep the leveling accurate for
  83 // the size.
  84 int pvector_resize(
  85     pvector *pv,unsigned int new_size,
  86     int (*reclaim)(pvector *,int,void*) )
  87 {
  88     // Table of number of slots for a level above that of the number
  89     // at the prior lower level.
  90     // The first level (i.e., level 0) adds 255 slots to the one slot
  91     // of no index page. Level 1 adds 255*256 slots, level 2 adds
  92     // 255*(256^2), and generically level i adds 255*(256^i) slots.
  93     static int level_delta[8];
  94     if ( level_delta[ 0 ] == 0 ) {
  95         int d = 1;
  96         int i;
  97         for ( i = 0; i < 8; i++ ) {
  98             level_delta[ i ] = 255 * d;
  99             d = 256 * d;
 100         }
 101     }
 102     struct {
 103         int old;
 104         int new;
 105     } level = {
 106         PV_LEVELS( pv->size ),
 107         PV_LEVELS( new_size )
 108     };
 109     if ( pv->entries == 0 ) {
 110         pv->size = new_size;
 111         return 0;
 112     }
 113     // A shrinking pvector might be veto-ed
 114     if ( new_size < pv->size ) {
 115         unsigned int index = new_size;
 116         void **slot = pvector_next_used( pv, &index, reclaim );
 117         if ( slot ) {
 118             return index;
 119         }
 120         // At this point we know that there are no slots used after
 121         // the new_size size, so now it's time to remove and reclaim
 122         // any superflouous top level pages.
 123         pvector_page *entries;
 124         pvector_page **pp = &pv->entries;
 125         while ( level.old-- > level.new ) {
 126             pp = (pvector_page **)(*pp)[0];
 127         }
 128         if ( pp != &pv->entries ) {
 129             entries = pv->entries;
 130             pv->entries = *pp;
 131             *pp = 0;
 132             pvector_reclaim( entries );
 133         }
 134     } else {
 135         // pvector is growing. Maybe insert levels.
 136         while ( level.old < level.new ) {
 137             pvector_page *p = (pvector_page *)
 138                 calloc( 1, sizeof( pvector_page ) );
 139             if ( p == 0 ) {
 140                 return -2; // OOM
 141             }
 142             (*p)[0] = pv->entries;
 143             pv->entries = p;
 144             pv->size += level_delta[ level.old++ ];
 145             // Note that the last level addition might make the size
 146             // larger than requested, which gets corrected below.
 147         }
 148     }
 149     pv->size = new_size;
 150     return -1;
 151 }
 152
 153 // Return a pointer to the indexed item the given page level, adding
 154 // intermediate pages if requested. Returns 0 if addition fails (OOM),
 155 // or if not requested and page is missing.
 156 // Level 0 = pointer to the item entry itself.
 157 // Level PVECTORLEVELS( pv->size ) - 1 =
 158 static void **pvector_access(
 159     pvector *pv,unsigned int index,int level,int add)
 160 {
 161     if ( index >= pv->size ) {
 162         return 0;
 163     }
 164     void **page = (void**) &pv->entries;
 165     int i = PV_LEVELS( pv->size );
 166     while (  i-- > level ) {
 167         if ( add && (*page) == 0 ) {
 168             (*page) = calloc( 256, sizeof( void* ) );
 169         }
 170         page = (*page);
 171         if ( page == 0 ) {
 172             return 0;
 173         }
 174         page += ((pvector_index)index).level[ i ];
 175     }
 176     return page;
 177 }
 178
 179 // Map index into a value slot
 180 void **pvector_entry(pvector *pv,unsigned int index) {
 181     return pvector_access( pv, index, 0, 1 );
 182 }
 183
 184 inline void pvector_set(pvector *pv,unsigned int index,void *value) {
 185     void **p = pvector_entry( pv, index );
 186     *p = value;
 187 }
 188
 189 inline void *pvector_get(pvector *pv,unsigned int index) {
 190     return *(pvector_entry( pv, index ));
 191 }
 192