pvector/qvector.c

   1 #include <stdlib.h>
   2 #include "qvector.h"
   3
   4 /**
   5  * Representing a vector of void* accessible via an indexing structure
   6  * as levels of same-size pages. A "qvector_page" is a contiguous
   7  * array of 16 void*.
   8  */
   9
  10 /**
  11  * Advances a qvector 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 **qvector_level_next_used(
  19     qvector_page *page,qvector_index *index,int level,qvector_index end) {
  20     void **p = (void**)&(*page)[ PV_PART( index, 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 = PV_PART( index, level - 1 ) == 0;
  28             void **x = qvector_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 ( ++PV_PART( index, level ) == 0 ) {
  39             break; // cycling this level => nothing found
  40         }
  41     }
  42     return 0;
  43 }
  44
  45 // The least number of levels to span index S (typically the size of a
  46 // qvector)
  47 static unsigned int qvector_levels(qvector_index S) {
  48     unsigned int N = 0;
  49     do {
  50         N++;
  51         S /= QV_SLOTS;
  52     } while ( S );
  53     return N;
  54 }
  55
  56 // Find the next used slot at given index or later. Returns pointer to
  57 // the slot.
  58 void **qvector_next_used(
  59     qvector *pv,qvector_index *index,
  60     int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
  61     void *data )
  62 {
  63     if ( pv->entries == 0 ) {
  64         *index = pv->size;
  65         return 0;
  66     }
  67     int levels = qvector_levels( pv->size );
  68     for ( ; *index < pv->size; (*index)++ ) {
  69         void **slot = qvector_level_next_used(
  70             pv->entries, index, levels - 1, pv->size ) ;
  71         if ( slot == 0 ) {
  72             // reached the end of the vector
  73             *index = pv->size;
  74             break;
  75         }
  76         if ( *slot ) {
  77             // Try reclaiming the slot,
  78             if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
  79                 *slot = 0;
  80             } else {
  81                 return slot;
  82             }
  83         }
  84     }
  85     return 0;
  86 }
  87
  88 // Reclaim tree of unused pages
  89 static void qvector_reclaim(qvector_page *page,unsigned int level) {
  90     int i = 0;
  91     if ( level > 0 ) {
  92         for ( ; i < QV_SLOTS; i++ ) {
  93             if ( (*page)[i] ) {
  94                 qvector_reclaim( (qvector_page *) (*page)[i], level - 1 );
  95             }
  96         }
  97     }
  98     free( page );
  99 }
 100
 101 // Resize vector, using the reclaim function as needed, to handle any
 102 // excess items or to veto the resize. Returns the index of the veto, if
 103 // any, or <0 otherwise, with -1 indicating success and -2 indicating
 104 // OOM while growing.
 105 //
 106 // Nothe that resizing may result in the introduction/removal of
 107 // indexing levels and pages, so as to keep the leveling accurate for
 108 // the size.
 109 int qvector_resize(
 110     qvector *pv,qvector_index new_size,
 111     int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
 112     void *data )
 113 {
 114     // Table of number of slots for a level above that of the number
 115     // at the prior lower level. The first level (i.e., level 0) adds
 116     // 15 slots to the one slot of no index page. Level 1 adds 15*16
 117     // slots, level 2 adds 15*(16^2), and generically level i adds
 118     // 15*(16^i) slots.
 119     static int level_delta[ QV_INDEX_FIELDS ];
 120     if ( level_delta[ 0 ] == 0 ) {
 121         int d = 1;
 122         int i;
 123         for ( i = 0; i < QV_INDEX_FIELDS; i++ ) {
 124             level_delta[ i ] = 15 * d;
 125             d = 16 * d;
 126         }
 127     }
 128     struct {
 129         int old;
 130         int new;
 131     } level = {
 132         qvector_levels( pv->size ),
 133         qvector_levels( new_size )
 134     };
 135     if ( pv->entries == 0 ) {
 136         pv->size = new_size;
 137         return 0;
 138     }
 139     // A shrinking qvector might be veto-ed
 140     if ( new_size < pv->size ) {
 141         qvector_index index = new_size;
 142         void **slot = qvector_next_used( pv, &index, reclaim, data );
 143         if ( slot ) {
 144             return index;
 145         }
 146         // At this point we know that there are no slots used after
 147         // the new_size size, so now it's time to remove and reclaim
 148         // any superflouous top level pages.
 149         qvector_page *entries;
 150         qvector_page **pp = &pv->entries;
 151         while ( level.old-- > level.new ) {
 152             pp = (qvector_page **)(*pp)[0];
 153         }
 154         if ( pp != &pv->entries ) {
 155             entries = pv->entries;
 156             pv->entries = *pp;
 157             *pp = 0;
 158             qvector_reclaim( entries, level.old );
 159         }
 160         if ( new_size == 0 ) {
 161             free( pv->entries );
 162             pv->entries = 0;
 163         }
 164     } else {
 165         // qvector is growing. Maybe insert levels.
 166         while ( level.old < level.new ) {
 167             qvector_page *p = (qvector_page *)
 168                 calloc( 1, sizeof( qvector_page ) );
 169             if ( p == 0 ) {
 170                 return -2; // OOM
 171             }
 172             (*p)[0] = pv->entries;
 173             pv->entries = p;
 174             pv->size += level_delta[ level.old++ ];
 175             // Note that the last level addition might make the size
 176             // larger than requested, which gets corrected below.
 177         }
 178     }
 179     pv->size = new_size;
 180     return -1;
 181 }
 182
 183 // Return a pointer to the indexed item the given page level, adding
 184 // intermediate pages if requested. Returns 0 if addition fails (OOM),
 185 // or if not requested and page is missing.
 186 // Level 0 = pointer to the item entry itself.
 187 // Level QVECTORLEVELS( pv->size ) - 1 =
 188 static void **qvector_access(
 189     qvector *pv,qvector_index index,int level,int add)
 190 {
 191     if ( index >= pv->size ) {
 192         return 0;
 193     }
 194     void **page = (void**) &pv->entries;
 195     int i = qvector_levels( pv->size );
 196     while (  i-- > level ) {
 197         if ( add && (*page) == 0 ) {
 198             (*page) = calloc( QV_SLOTS, sizeof( void* ) );
 199         }
 200         page = (*page);
 201         if ( page == 0 ) {
 202             return 0;
 203         }
 204         page += PV_PART( &index, i );
 205     }
 206     return page;
 207 }
 208
 209 // Map index into a value slot
 210 void **qvector_entry(qvector *pv,qvector_index index) {
 211     return qvector_access( pv, index, 0, 1 );
 212 }
 213
 214 inline void qvector_set(qvector *pv,qvector_index index,void *value) {
 215     void **p = qvector_entry( pv, index );
 216     *p = value;
 217 }
 218
 219 inline void *qvector_get(qvector *pv,qvector_index index) {
 220     return *(qvector_entry( pv, index ));
 221 }
 222
 223 int qvector_reclaim_any(qvector *pv,qvector_index ix,void *item,void *data) {
 224     free( item );
 225     return 0;
 226 }
 227
 228 void qvector_append(qvector *pv,void *value) {
 229     qvector_resize( pv, pv->size + 1, 0, 0 );
 230     qvector_set( pv, pv->size - 1, value );
 231 }
 232
 233 // copy block of n items from src[si] to dst[di]
 234 // no efficiency hacks
 235 void qvector_copy(qvector *dst,qvector_index di,
 236               qvector *src,qvector_index si,qvector_index n) {
 237     if ( dst != src || di < si ) {
 238         while ( n-- != 0 ) {
 239             qvector_set( dst, di++, qvector_get( src, si++ ) );
 240         }
 241     } else if ( di > si ){
 242         di += n - 1;
 243         si += n - 1;
 244         while ( n-- != 0 ) {
 245             qvector_set( dst, di--, qvector_get( src, si-- ) );
 246         }
 247     }
 248 }
 249
 250 void qvector_dump(qvector *pv,
 251                   int (*itemdump)(const qvector_index,const void *)) {
 252     qvector_index index = 0;
 253     for ( ; index < pv->size; index++ ) {
 254         void **slot = qvector_next_used( pv, &index, 0, 0 );
 255         if ( slot == 0 ) {
 256             break;
 257         }
 258         itemdump( index, *slot );
 259     }
 260 }
 261
 262 //// Quicksort
 263
 264 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 265 typedef int (*comparfn)(const void *,const void *);
 266
 267 static void qvector_qsort_part(
 268     qvector *pv,comparfn compar,
 269     qvector_index low,qvector_index high)
 270 {
 271     if ( low >= high ) {
 272         return;
 273     }
 274     qvector_index lo = low;
 275     qvector_index m = high - 1;
 276
 277     if ( lo >= m  ) {
 278         return;
 279     }
 280
 281     qvector_index hi = m - 1;
 282     void **mp = qvector_entry( pv, m );
 283     void **lop, **hip;
 284     for ( ;; ) {
 285         // Find index of first item "above" mp scanning from lo and up
 286         for ( ; lo < m; lo++ ) {
 287             lop = qvector_entry( pv, lo );
 288             if ( compar( *lop, *mp ) < 0 ) {
 289                 break;
 290             }
 291         }
 292         // if  lo == m, then lop is wrong!!
 293         // Find index of first item "below" mp scanning from hi and down
 294         for ( ; hi > lo; hi-- ) {
 295             hip = qvector_entry( pv, hi );
 296             if ( compar( *mp, *hip ) < 0 ) {
 297                 break;
 298             }
 299         }
 300         if ( lo >= hi ) {
 301             if ( lo < m ) {
 302                 void *x = *lop;
 303                 *lop = *mp;
 304                 *mp = x;
 305                 m = lo;
 306             }
 307             break;
 308         }
 309         void *x = *lop;
 310         *lop = *hip;
 311         *hip = x;
 312     }
 313     qvector_qsort_part( pv, compar, low, m );
 314     qvector_qsort_part( pv, compar, m+1, high );
 315 }
 316
 317 void qvector_qsort(qvector *pv,comparfn compar) {
 318     qvector_qsort_part( pv, compar, 0, pv->size );
 319 }
 320
 321 void qvector_iterate(qvector *pv,
 322                      int (*itemfn)(qvector_index,void*,void*),
 323                      void *data )
 324 {
 325     qvector_index index = 0;
 326     while ( index < pv->size ) {
 327         void **slot = qvector_next_used( pv, &index, 0, 0 );
 328         if ( slot == 0 ) {
 329             break;
 330         }
 331         int i = index & 0xff;
 332         for ( ; i < QV_SLOTS && index < pv->size; i++, index++, slot++ ) {
 333             if ( itemfn( index, *slot, data ) ) {
 334                 return;
 335             }
 336         }
 337     }
 338 }