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