vector/vector.c

   1 #include <stdlib.h>
   2 #include "vector.h"
   3
   4 /**
   5  * Representing a vector of void* accessible via an indexing structure
   6  * as levels of same-size pages. A "vector_page" is a contiguous array
   7  * void*, and an index is "unsigned long" (64 bits).
   8  */
   9
  10 #if VECTOR_LEVEL_BITS == 4
  11 typedef union {
  12     vector_index as_whole;
  13     struct {
  14         unsigned int msb:4; unsigned int lsb:4;
  15     } __attribute__ ((__packed__)) as_byte[8];
  16 } vector_indexing;
  17
  18 #define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 )
  19
  20 #define VECTOR_PART_BYTE(i,p) ((vector_indexing*)(i))->as_byte[ (p)/2 ]
  21
  22 static int VECTOR_INDEX_PART(vector_index *index,int part) {
  23     if ( part & 1 ) {
  24         return VECTOR_PART_BYTE(index,part).lsb;
  25     }
  26     return VECTOR_PART_BYTE(index,part).msb;
  27 }
  28
  29 static int VECTOR_INDEX_PART_INC(vector_index *index,int part) {
  30     if ( part & 1 ) {
  31         return ++VECTOR_PART_BYTE(index,part).lsb;
  32     }
  33     return ++VECTOR_PART_BYTE(index,part).msb;
  34 }
  35 #endif
  36
  37 /**
  38  * Advances a vector index to the next used slot at or below the
  39  * given level, starting from the indexed entry (inclusive) and up.
  40  * The function will free any empty pages it discovers, and then
  41  * update the index slots accordingly. The given index is advanced
  42  * cyclically to match the found slot. The function returns a slot
  43  * pointer to the used slot, if any, and 0 otherwise.
  44  */
  45 static void **vector_level_next_used(
  46     vector_page *page,vector_index *index,int level,vector_index end) {
  47     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( index, level ) ];
  48     for( ; *index < end; p++ ) {
  49         if ( *p ) {
  50             if ( level == 0 ) {
  51                 return p; // This is a used entry
  52             }
  53             // *p is an index that needs to be inspected recursively
  54             int whole = VECTOR_INDEX_PART( index, level - 1 ) == 0;
  55             void **x = vector_level_next_used( *p, index, level - 1, end );
  56             if ( x ) {
  57                 return x; // Used slot was found; return it.
  58             }
  59             // The page *p is all empty, so can/should be reclaimed.
  60             if ( whole ) {
  61                 free( *p );
  62                 *p = 0;
  63             }
  64         }
  65         if ( VECTOR_INDEX_PART_INC( index, level ) == 0 ) {
  66             break; // cycling this level => nothing found
  67         }
  68     }
  69     return 0;
  70 }
  71
  72 // The least number of levels to span index S (typically the size of a
  73 // vector)
  74 static unsigned int vector_levels(vector_index S) {
  75     unsigned int N = 0;
  76     do {
  77         N++;
  78         S /= VECTOR_SLOTS;
  79     } while ( S );
  80     return N;
  81 }
  82
  83 // Find the next used slot at given index or later. Returns pointer to
  84 // the slot.
  85 void **vector_next_used(
  86     vector *pv,vector_index *index,
  87     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
  88     void *data )
  89 {
  90     if ( pv->entries == 0 ) {
  91         *index = pv->size;
  92         return 0;
  93     }
  94     int levels = vector_levels( pv->size );
  95     for ( ; *index < pv->size; (*index)++ ) {
  96         void **slot = vector_level_next_used(
  97             pv->entries, index, levels - 1, pv->size ) ;
  98         if ( slot == 0 ) {
  99             // reached the end of the vector
 100             *index = pv->size;
 101             break;
 102         }
 103         if ( *slot ) {
 104             // Try reclaiming the slot,
 105             if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) {
 106                 *slot = 0;
 107             } else {
 108                 return slot;
 109             }
 110         }
 111     }
 112     return 0;
 113 }
 114
 115 // Reclaim tree of unused pages
 116 static void vector_reclaim(vector_page *page,unsigned int level) {
 117     int i = 0;
 118     if ( level > 0 ) {
 119         for ( ; i < VECTOR_SLOTS; i++ ) {
 120             if ( (*page)[i] ) {
 121                 vector_reclaim( (vector_page *) (*page)[i], level - 1 );
 122             }
 123         }
 124     }
 125     free( page );
 126 }
 127
 128 // Resize vector, using the reclaim function as needed, to handle any
 129 // excess items or to veto the resize. Returns the index of the veto, if
 130 // any, or <0 otherwise, with -1 indicating success and -2 indicating
 131 // OOM while growing.
 132 //
 133 // Nothe that resizing may result in the introduction/removal of
 134 // indexing levels and pages, so as to keep the leveling accurate for
 135 // the size.
 136 int vector_resize(
 137     vector *pv,vector_index new_size,
 138     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
 139     void *data )
 140 {
 141     // Table of number of slots for a level above that of the number
 142     // at the prior lower level. The first level (i.e., level 0) adds
 143     // 15 slots to the one slot of no index page. Level 1 adds 15*16
 144     // slots, level 2 adds 15*(16^2), and generically level i adds
 145     // 15*(16^i) slots.
 146     static int level_delta[ VECTOR_INDEX_FIELDS ];
 147     if ( level_delta[ 0 ] == 0 ) {
 148         int d = 1;
 149         int i;
 150         for ( i = 0; i < VECTOR_INDEX_FIELDS; i++ ) {
 151             level_delta[ i ] = ( VECTOR_SLOTS - 1 ) * d;
 152             d = VECTOR_SLOTS * d;
 153         }
 154     }
 155     struct {
 156         int old;
 157         int new;
 158     } level = {
 159         vector_levels( pv->size ),
 160         vector_levels( new_size )
 161     };
 162     if ( pv->entries == 0 ) {
 163         pv->size = new_size;
 164         return 0;
 165     }
 166     // A shrinking vector might be veto-ed
 167     if ( new_size < pv->size ) {
 168         vector_index index = new_size;
 169         void **slot = vector_next_used( pv, &index, reclaim, data );
 170         if ( slot ) {
 171             return index;
 172         }
 173         // At this point we know that there are no slots used after
 174         // the new_size size, so now it's time to remove and reclaim
 175         // any superflouous top level pages.
 176         vector_page *entries;
 177         vector_page **pp = &pv->entries;
 178         while ( level.old-- > level.new ) {
 179             if ( pp ) {
 180                 pp = (vector_page **)(*pp)[0];
 181             }
 182         }
 183         if ( pp != &pv->entries ) {
 184             entries = pv->entries;
 185             if ( pp ) {
 186                 pv->entries = *pp;
 187                 *pp = 0; // Detach subtree
 188             } else {
 189                 pv->entries = 0;
 190             }
 191             vector_reclaim( entries, level.old );
 192         }
 193         if ( new_size == 0 && pv->entries ) {
 194             free( pv->entries );
 195             pv->entries = 0;
 196         }
 197     } else {
 198         // vector is growing. Maybe insert levels.
 199         while ( level.old < level.new ) {
 200             vector_page *p = (vector_page *)
 201                 calloc( 1, sizeof( vector_page ) );
 202             if ( p == 0 ) {
 203                 return -2; // OOM
 204             }
 205             (*p)[0] = pv->entries;
 206             pv->entries = p;
 207             pv->size += level_delta[ level.old++ ];
 208             // Note that the last level addition might make the size
 209             // larger than requested, which gets corrected below.
 210         }
 211     }
 212     pv->size = new_size;
 213     return -1;
 214 }
 215
 216 // Return a pointer to the indexed item the given page level, adding
 217 // intermediate pages if requested. Returns 0 if addition fails (OOM),
 218 // or if not requested and page is missing.
 219 // Level 0 = pointer to the item entry itself.
 220 // Level VECTORLEVELS( pv->size ) - 1 =
 221 static void **vector_access(
 222     vector *pv,vector_index index,int level,int add)
 223 {
 224     if ( index >= pv->size ) {
 225         return 0;
 226     }
 227     void **page = (void**) &pv->entries;
 228     int i = vector_levels( pv->size );
 229     while (  i-- > level ) {
 230         if ( add && (*page) == 0 ) {
 231             (*page) = calloc( VECTOR_SLOTS, sizeof( void* ) );
 232         }
 233         page = (*page);
 234         if ( page == 0 ) {
 235             return 0;
 236         }
 237         page += VECTOR_INDEX_PART( &index, i );
 238     }
 239     return page;
 240 }
 241
 242 // Map index into a value slot
 243 void **vector_entry(vector *pv,vector_index index) {
 244     return vector_access( pv, index, 0, 1 );
 245 }
 246
 247 inline void vector_set(vector *pv,vector_index index,void *value) {
 248     void **p = vector_entry( pv, index );
 249     *p = value;
 250 }
 251
 252 inline void *vector_get(vector *pv,vector_index index) {
 253     return *(vector_entry( pv, index ));
 254 }
 255
 256 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
 257     free( item );
 258     return 0;
 259 }
 260
 261 void vector_append(vector *pv,void *value) {
 262     vector_resize( pv, pv->size + 1, 0, 0 );
 263     vector_set( pv, pv->size - 1, value );
 264 }
 265
 266 // copy block of n items from src[si] to dst[di]
 267 // no efficiency hacks
 268 void vector_copy(vector *dst,vector_index di,
 269               vector *src,vector_index si,vector_index n) {
 270     if ( dst != src || di < si ) {
 271         while ( n-- != 0 ) {
 272             vector_set( dst, di++, vector_get( src, si++ ) );
 273         }
 274     } else if ( di > si ){
 275         di += n - 1;
 276         si += n - 1;
 277         while ( n-- != 0 ) {
 278             vector_set( dst, di--, vector_get( src, si-- ) );
 279         }
 280     }
 281 }
 282
 283 void vector_dump(vector *pv,
 284                   int (*itemdump)(const vector_index,const void *)) {
 285     vector_index index = 0;
 286     for ( ; index < pv->size; index++ ) {
 287         void **slot = vector_next_used( pv, &index, 0, 0 );
 288         if ( slot == 0 ) {
 289             break;
 290         }
 291         itemdump( index, *slot );
 292     }
 293 }
 294
 295 //// Quicksort
 296
 297 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 298 typedef int (*comparfn)(const void *,const void *);
 299
 300 static void vector_qsort_part(
 301     vector *pv,comparfn compar,
 302     vector_index low,vector_index high)
 303 {
 304     if ( low >= high ) {
 305         return;
 306     }
 307     vector_index lo = low;
 308     vector_index m = high - 1;
 309
 310     if ( lo >= m  ) {
 311         return;
 312     }
 313
 314     vector_index hi = m - 1;
 315     void **mp = vector_entry( pv, m );
 316     void **lop, **hip;
 317     for ( ;; ) {
 318         // Find index of first item "above" mp scanning from lo and up
 319         for ( ; lo < m; lo++ ) {
 320             lop = vector_entry( pv, lo );
 321             if ( compar( *lop, *mp ) < 0 ) {
 322                 break;
 323             }
 324         }
 325         // if  lo == m, then lop is wrong!!
 326         // Find index of first item "below" mp scanning from hi and down
 327         for ( ; hi > lo; hi-- ) {
 328             hip = vector_entry( pv, hi );
 329             if ( compar( *mp, *hip ) < 0 ) {
 330                 break;
 331             }
 332         }
 333         if ( lo >= hi ) {
 334             if ( lo < m ) {
 335                 void *x = *lop;
 336                 *lop = *mp;
 337                 *mp = x;
 338                 m = lo;
 339             }
 340             break;
 341         }
 342         void *x = *lop;
 343         *lop = *hip;
 344         *hip = x;
 345     }
 346     vector_qsort_part( pv, compar, low, m );
 347     vector_qsort_part( pv, compar, m+1, high );
 348 }
 349
 350 void vector_qsort(vector *pv,comparfn compar) {
 351     vector_qsort_part( pv, compar, 0, pv->size );
 352 }
 353
 354 void vector_iterate(vector *pv,
 355                      int (*itemfn)(vector_index,void*,void*),
 356                      void *data )
 357 {
 358     vector_index index = 0;
 359     while ( index < pv->size ) {
 360         void **slot = vector_next_used( pv, &index, 0, 0 );
 361         if ( slot == 0 ) {
 362             break;
 363         }
 364         int i = index & VECTOR_LEVEL_MASK ;
 365         for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) {
 366             if ( itemfn( index, *slot, data ) ) {
 367                 return;
 368             }
 369         }
 370     }
 371 }