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