vector/vector.c

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