vector/vector.c

   1 #include <string.h>
   2 #include <math.h>
   3 #include <stdlib.h>
   4 #include "vector.h"
   5
   6 /**
   7  * Representing a vector of void* accessible via an indexing structure
   8  * as levels of same-size pages. A "vector_page" is a contiguous array
   9  * void*, and an index is "unsigned long" (64 bits).
  10  */
  11
  12 /** ============================================================ **/
  13
  14 static int VECTOR_BITS[4] = { 8, 4, 2, 64 };
  15
  16 typedef struct {
  17     unsigned int a:2;
  18     unsigned int b:2;
  19     unsigned int c:2;
  20     unsigned int d:2;
  21 } bitpair;
  22
  23 typedef struct {
  24     unsigned int a:4;
  25     unsigned int b:4;
  26 } nibble;
  27
  28 typedef struct {
  29     unsigned int a:8;
  30 } byte;
  31
  32 /**
  33  * Return the index part for the given level of the vector's leveling
  34  * variant.
  35  *
  36  * The vector variant indicates whether indexing uses 8, 4, or 2 bits
  37  * per level.
  38  */
  39 unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
  40     unsigned char *px = (unsigned char *) index;
  41     switch ( pv->variant ) {
  42     case 0: {
  43         byte *pp = (byte*)(px + level);
  44         return pp->a;
  45     }
  46     case 1: {
  47         nibble *pp = (nibble*)( px + ( level / 2 ) );
  48         switch ( level & 1 ) {
  49         case 0: return pp->a;
  50         case 1: return pp->b;
  51         }
  52         break;
  53     }
  54     case 2: {
  55         bitpair *pp = (bitpair*)( px + ( level / 4 ) );
  56         switch ( level & 3 ) {
  57         case 0: return pp->a;
  58         case 1: return pp->b;
  59         case 2: return pp->c;
  60         case 3: return pp->d;
  61         }
  62         break;
  63     }
  64     case 3:
  65         return (*index);
  66     }
  67     return 0;
  68 }
  69
  70 /**
  71  * Increment the index part at the indivated level, cyclic but not
  72  * carrying over to the upper level. Returns the new level index.
  73  */
  74 static unsigned long VECTOR_INDEX_PART_INC(
  75     vector *pv,vector_index *index, int level)
  76 {
  77     unsigned char *px = (unsigned char *) index;
  78     switch ( pv->variant ) {
  79     case 0: {
  80         byte *pp = (byte*)( px + level );
  81         return ++(pp->a);
  82     }
  83     case 1: {
  84         nibble *pp = (nibble*)( px + ( level / 2 ) );
  85         switch ( level & 1 ) {
  86         case 0: return ++(pp->a);
  87         case 1: return ++(pp->b);
  88         }
  89         break;
  90     }
  91     case 2: {
  92         bitpair *pp = (bitpair*)( px + level / 4 );
  93         switch ( level & 3 ) {
  94         case 0: return ++(pp->a);
  95         case 1: return ++(pp->b);
  96         case 2: return ++(pp->c);
  97         case 3: return ++(pp->d);
  98         }
  99         break;
 100     }
 101     case 3:
 102         return ++(*index);
 103     }
 104     return 0;
 105 }
 106
 107 /**
 108  * Decrement the index part at the indicated level, cyclic but not
 109  * carrying over to the upper level. Returns the prior level index.
 110  */
 111 static unsigned long VECTOR_INDEX_PART_DEC(
 112     vector *pv,vector_index *index, int level)
 113 {
 114     unsigned char *px = (unsigned char *) index;
 115     switch ( pv->variant ) {
 116     case 0: {
 117         byte *pp = (byte*)( px + level );
 118         return (pp->a)--;
 119     }
 120     case 1: {
 121         nibble *pp = (nibble*)( px + ( level / 2 ) );
 122         switch ( level & 1 ) {
 123         case 0: return (pp->a)--;
 124         case 1: return (pp->b)--;
 125         }
 126         break;
 127     }
 128     case 2: {
 129         bitpair *pp = (bitpair*)( px + level / 4 );
 130         switch ( level & 0xf ) {
 131         case 0: return (pp->a)--;
 132         case 1: return (pp->b)--;
 133         case 2: return (pp->c)--;
 134         case 3: return (pp->d)--;
 135         }
 136         break;
 137     }
 138     case 3:
 139         return (*index)--;
 140     }
 141     return 0;
 142 }
 143
 144 #define ONES  (~((vector_index) 0))
 145
 146 // Set index to last value for all index parts at level and lower.
 147 static void VECTOR_INDEX_FIRST(vector *pv,vector_index *index, int level) {
 148     (*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
 149 }
 150
 151 // Set index to last value for all index parts at level and lower.
 152 static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int level) {
 153     static unsigned long ones[] = { 255, 15, 3 };
 154     unsigned long x = ones[ pv->variant ];
 155     while ( level-- ) {
 156         (*index) |= x;
 157         x <<= VECTOR_BITS[ pv->variant ];
 158     }
 159     // 255, 25, 3
 160     //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
 161 }
 162
 163 // Return number of slots for a vector variant.
 164 unsigned long VECTOR_SLOTS(vector *pv) {
 165     switch ( pv->variant ) {
 166     case 0: return 256;
 167     case 1: return 16;
 168     case 2: return 4;
 169     case 3: return pv->size;
 170     }
 171     return 0;
 172 }
 173
 174 // The number of levels to span vector pv wrt its size and variant
 175 static unsigned int vector_levels(vector *pv,unsigned int size) {
 176     if ( size < 4 ) {
 177         return 1;
 178     }
 179     switch ( pv->variant ) {
 180     case 0: return ((int)(log2( size - 1 ) / 8)) + 1;
 181     case 1: return ((int)(log2( size - 1 ) / 4)) + 1;
 182     case 2: return ((int)(log2( size - 1 ) / 2)) + 1;
 183     case 3: return 1;
 184     }
 185     return 0;
 186 }
 187
 188 /** ============================================================ **/
 189
 190 /**
 191  * Advances a vector index to the next used slot at or below the
 192  * given level, starting from the indexed entry (inclusive) and up.
 193  * The function will free any empty pages it discovers, and then
 194  * update the index slots accordingly. The given index is advanced
 195  * cyclically to match the found slot. The function returns a slot
 196  * pointer to the used slot, if any, and 0 otherwise.
 197  */
 198 static void **vector_level_next_used(
 199     vector *pv,
 200     vector_page *page,
 201     vector_index *index,
 202     int level,
 203     vector_index end )
 204 {
 205     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 206     for( ; *index < end; p++ ) {
 207         if ( *p ) {
 208             if ( level == 0 ) {
 209                 return p; // This is a used entry
 210             }
 211             // *p is an index that needs to be inspected recursively
 212             void **x = vector_level_next_used( pv, *p, index, level - 1, end );
 213             if ( x ) {
 214                 return x; // Used slot was found; return it.
 215             }
 216             // If the page *p is all empty, so can/should be reclaimed.
 217         } else {
 218             if ( level > 0 ) {
 219                 VECTOR_INDEX_FIRST( pv, index, level - 1 );
 220             }
 221         }
 222         if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
 223             break; // cycling this level => nothing found
 224         }
 225     }
 226     return 0;
 227 }
 228
 229 // Find the next used slot at given index or later. Returns pointer to
 230 // the slot. This allows for a reclaim function that may reclaim slot
 231 // items on the way to next used slot.
 232 void **vector_next_used(vector *pv,vector_index *index) {
 233     if ( pv->entries == 0 || *index >= pv->size ) {
 234         *index = pv->size;
 235         return 0;
 236     }
 237     int levels = vector_levels( pv, pv->size );
 238     for ( ; *index < pv->size; (*index)++ ) {
 239         void **slot = vector_level_next_used(
 240             pv, pv->entries, index, levels - 1, pv->size ) ;
 241         if ( slot == 0 ) {
 242             *index = pv->size; // reached the end of the vector
 243         } else  if ( *slot == 0 ) {
 244             continue;
 245         }
 246         return slot;
 247     }
 248     return 0;
 249 }
 250
 251 #if 1
 252 /**
 253  * Advances a vector index to the prior used slot at or below the
 254  * given level, starting from the indexed entry (inclusive) and down.
 255  * The function will free any empty pages it discovers, and then
 256  * update the index slots accordingly. The given index is advanced
 257  * cyclically to match the found slot. The function returns a slot
 258  * pointer to the used slot, if any, and 0 otherwise.
 259  */
 260 static void **vector_level_prev_used(
 261     vector *pv,
 262     vector_page *page,
 263     vector_index *index,
 264     int level )
 265 {
 266     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 267     do {
 268         if ( *p ) {
 269             if ( level == 0 ) {
 270                 return p; // This is a used entry
 271             }
 272             // *p is an index that needs to be inspected recursively
 273             void **x = vector_level_prev_used( pv, *p, index, level - 1 );
 274             if ( x ) {
 275                 return x; // Used slot was found; return it.
 276             }
 277             // If the page *p is all empty, so can/should be reclaimed.
 278         } else {
 279             if ( level > 0 ) {
 280                 VECTOR_INDEX_LAST( pv, index, level );
 281             }
 282         }
 283         p--;
 284     } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 );
 285     return 0;
 286 }
 287
 288 // Find the next used slot at given index or later. Returns pointer to
 289 // the slot. This allows for a reclaim function that may reclaim slot
 290 // items on the way to next used slot.
 291 void **vector_prev_used(vector *pv,vector_index *index) {
 292     if ( pv->entries == 0 || *index >= pv->size ) {
 293         *index = pv->size;
 294         return 0;
 295     }
 296     int levels = vector_levels( pv, pv->size );
 297     do {
 298         void **slot = vector_level_prev_used(
 299             pv, pv->entries, index, levels - 1 ) ;
 300         if ( slot == 0 ) {
 301             break; // reached the end of the vector
 302         }
 303         if ( *slot ) {
 304             return slot;
 305         }
 306     } while ( (*index)-- != 0 );
 307     *index = pv->size;
 308     return 0;
 309 }
 310
 311 #endif
 312
 313 #if 0
 314 // Find the first in-use slot at or before the index, at the level
 315 static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) {
 316     void **slot = vector_access( pv, *index, lv, 0 );
 317     if ( slot == 0 ) {
 318         return 0;
 319     }
 320     do {
 321         if ( *slot ) {
 322             if ( lv == 0 ) {
 323                 return slot;
 324             }
 325             void **sub = vector_prev_used_level( pv, index, lv - 1 );
 326             if ( sub ) {
 327                 return sub;
 328             }
 329         }
 330         slot--;
 331     } while ( VECTOR_INDEX_PART_DEC( pv, index, lv ) != 0 );
 332     return 0;
 333 }
 334
 335 // Find nearest used slot at or prior to the given index.
 336 void **vector_prev_used(vector *pv,vector_index *index) {
 337     if ( pv->entries == 0 || *index >= pv->size ) {
 338         *index = pv->size;
 339         return 0;
 340     }
 341     void **slot = vector_prev_used_level(
 342         pv, index, vector_levels( pv, pv->size ) - 1 );
 343     if ( slot == 0 ) {
 344         *index = pv->size;
 345     }
 346     return slot;
 347 }
 348 #endif
 349
 350 // Reclaim tree of unused pages for a given level
 351 static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) {
 352     int i = 0;
 353     if ( level > 0 ) {
 354         for ( ; i < VECTOR_SLOTS( pv ); i++ ) {
 355             if ( (*page)[i] ) {
 356                 vector_reclaim( pv, (vector_page *) (*page)[i], level - 1 );
 357             }
 358         }
 359     }
 360     free( page );
 361 }
 362
 363 // Resize vector, using the reclaim function as needed, to handle any
 364 // excess items or to veto the resize. Returns the index of the veto,
 365 // if any, or <0 otherwise, with -1 indicating success and -2
 366 // indicating OOM
 367 //
 368 // Note that resizing may result in the introduction/removal of
 369 // indexing levels and pages, so as to keep the leveling accurate for
 370 // the size.
 371 int vector_resize(
 372     vector *pv,vector_index new_size,
 373     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
 374     void *data )
 375 {
 376     struct {
 377         int old;
 378         int new;
 379     } level = {
 380         vector_levels( pv, pv->size ),
 381         vector_levels( pv, new_size )
 382     };
 383     vector_page *entries = 0;
 384     if ( pv->entries == 0 ) {
 385         pv->size = new_size;
 386         return 0;
 387     }
 388     // A shrinking vector might be veto-ed
 389     if ( new_size < pv->size ) {
 390         vector_index index = new_size;
 391         void **slot = vector_next_used( pv, &index );
 392         while ( slot ) {
 393             if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
 394                 *slot = 0;
 395                 slot = vector_next_used( pv, &index );
 396                 continue;
 397             }
 398             return index;
 399         }
 400         // At this point we know that there are no slots used after
 401         // the new_size size, so now it's time to remove and reclaim
 402         // any superflouous top level pages.
 403         if ( pv->variant == 3 ) { // Follow vector size using realloc
 404             if ( new_size > 0 ) {
 405                 entries = (vector_page*)
 406                     realloc( pv->entries, new_size * sizeof( void* ) );
 407                 if ( entries == 0 ) {
 408                     return -2; // OOM
 409                 }
 410             }
 411             pv->entries = entries;
 412         } else {
 413             vector_page **pp = &pv->entries;
 414             int i = level.old;
 415             while ( i-- > level.new ) {
 416                 if ( pp ) {
 417                     pp = (vector_page **)(*pp);
 418                 }
 419             }
 420             if ( pp != &pv->entries ) {
 421                 entries = pv->entries;
 422                 if ( pp ) {
 423                     pv->entries = *pp;
 424                     *pp = 0; // Detach subtree
 425                 } else {
 426                     pv->entries = 0;
 427                 }
 428                 vector_reclaim( pv, entries, level.old - 1 );
 429             }
 430             if ( new_size == 0 && pv->entries ) {
 431                 free( pv->entries );
 432                 pv->entries = 0;
 433             }
 434         }
 435     } else {
 436         // vector is growing. Maybe insert levels.
 437         if ( pv->variant == 3 ) { // Follow vector size using realloc
 438             entries = (vector_page *)realloc(
 439                 pv->entries, new_size * sizeof( void* ) );
 440             if ( entries == 0 ) {
 441                 return -2; // OOM
 442             }
 443             pv->entries = entries;
 444             memset( &(*entries)[ pv->size ], 0,
 445                     ( new_size - pv->size ) * sizeof( void* ) );
 446         } else {
 447             for ( ; level.old < level.new; level.old++ ) {
 448                 vector_page *p = (vector_page *)
 449                     calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 450                 if ( p == 0 ) {
 451                     return -2; // OOM
 452                 }
 453                 (*p)[0] = pv->entries;
 454                 pv->entries = p;
 455                 // Should maybe change the size to match the level?
 456                 // otherwise recovery from OOM is impossible
 457             }
 458         }
 459     }
 460     pv->size = new_size;
 461     return -1;
 462 }
 463
 464 // Return pointer to the indexed page slot at the requested level, and
 465 // adding intermediate index pages if so requested. Returns 0 if
 466 // addition fails (OOM), or if not requested and page is missing.
 467 void **vector_access(vector *pv,vector_index index,int level,int add) {
 468     if ( index >= pv->size ) {
 469         return 0;
 470     }
 471     void **page = (void**) &pv->entries;
 472     int i = vector_levels( pv, pv->size );
 473     while (  i-- > level ) {
 474         if ( add && (*page) == 0 ) {
 475             (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 476         }
 477         page = (*page);
 478         if ( page == 0 ) {
 479             return 0;
 480         }
 481         page += VECTOR_INDEX_PART( pv, &index, i );
 482     }
 483     return page;
 484 }
 485
 486 // Map index into a value slot
 487 void **vector_entry(vector *pv,vector_index index) {
 488     return vector_access( pv, index, 0, 1 );
 489 }
 490
 491 inline void vector_set(vector *pv,vector_index index,void *value) {
 492     void **p = vector_entry( pv, index );
 493     *p = value;
 494 }
 495
 496 // Set value at index but return the old value
 497 void *vector_get_set(vector *pv,vector_index index,void *value) {
 498     void **p = vector_entry( pv, index );
 499     void *old = *p;
 500     *p = value;
 501     return old;
 502 }
 503
 504 inline void *vector_get(vector *pv,vector_index index) {
 505     void **p = vector_entry( pv, index );
 506     return *p;
 507 }
 508
 509 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
 510     free( item );
 511     return 0;
 512 }
 513
 514 void vector_append(vector *pv,void *value) {
 515     vector_resize( pv, pv->size + 1, 0, 0 );
 516     vector_set( pv, pv->size - 1, value );
 517 }
 518
 519 // copy block of n items from src[si] to dst[di]
 520 // no efficiency hacks
 521 void vector_copy(vector *dst,vector_index di,
 522               vector *src,vector_index si,vector_index n) {
 523     if ( dst != src || di < si ) {
 524         while ( n-- != 0 ) {
 525             vector_set( dst, di++, vector_get( src, si++ ) );
 526         }
 527     } else if ( di > si ){
 528         di += n - 1;
 529         si += n - 1;
 530         while ( n-- != 0 ) {
 531             vector_set( dst, di--, vector_get( src, si-- ) );
 532         }
 533     }
 534 }
 535
 536 void vector_dump(vector *pv,
 537                  void (*itemdump)(const vector_index,const void *)) {
 538     vector_index index = 0;
 539     for ( ; index < pv->size; index++ ) {
 540         void **slot = vector_next_used( pv, &index );
 541         if ( slot == 0 ) {
 542             break;
 543         }
 544         itemdump( index, *slot );
 545     }
 546 }
 547
 548 //// Quicksort
 549
 550 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 551  typedef int (*comparfn)(const void *,const void *);
 552
 553 static void vector_qsort_part(
 554     vector *pv,comparfn compar,
 555     vector_index low,vector_index high)
 556 {
 557     if ( low >= high ) {
 558         return;
 559     }
 560     vector_index lo = low;
 561     vector_index m = high - 1;
 562
 563     if ( lo >= m  ) {
 564         return;
 565     }
 566
 567     vector_index hi = m - 1;
 568     void **mp = vector_entry( pv, m );
 569     void **lop, **hip;
 570     for ( ;; ) {
 571         // Find index of first item "above" mp scanning from lo and up
 572         for ( ; lo < m; lo++ ) {
 573             lop = vector_entry( pv, lo );
 574             if ( compar( *lop, *mp ) < 0 ) {
 575                 break;
 576             }
 577         }
 578         // if  lo == m, then lop is wrong!!
 579         // Find index of first item "below" mp scanning from hi and down
 580         for ( ; hi > lo; hi-- ) {
 581             hip = vector_entry( pv, hi );
 582             if ( compar( *mp, *hip ) < 0 ) {
 583                 break;
 584             }
 585         }
 586         if ( lo >= hi ) {
 587             if ( lo < m ) {
 588                 void *x = *lop;
 589                 *lop = *mp;
 590                 *mp = x;
 591                 m = lo;
 592             }
 593             break;
 594         }
 595         void *x = *lop;
 596         *lop = *hip;
 597         *hip = x;
 598     }
 599     vector_qsort_part( pv, compar, low, m );
 600     vector_qsort_part( pv, compar, m+1, high );
 601 }
 602
 603 void vector_qsort(vector *pv,comparfn compar) {
 604     vector_qsort_part( pv, compar, 0, pv->size );
 605 }
 606
 607 void vector_iterate(vector *pv,
 608                     vector_index start,
 609                     int (*itemfn)(vector_index,void*,void*),
 610                     void *data )
 611 {
 612     vector_index index = start;
 613     while ( index < pv->size ) {
 614         int end = VECTOR_SLOTS( pv );
 615         int i = index & ( end - 1 );
 616         for ( ; i < end && index < pv->size; i++, index++ ) {
 617             void **slot = vector_access( pv, index, 0, 0 );
 618             if ( slot && itemfn( index, *slot, data ) ) {
 619                 return;
 620             }
 621         }
 622     }
 623 }
 624
 625 // Find surrounding indexes for a given item key in a sparse vector
 626 void *vector_bsearch(vector *pv,vector_index *index,const void *key,
 627                      int (*compare)(const void *key, const void *item)) {
 628     vector_index lo = 0;
 629     vector_index hi = pv->size;
 630     if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) {
 631         return 0;
 632     }
 633     hi++;
 634     while ( lo < hi ) {
 635         vector_index m = lo + ( hi - lo ) / 2;
 636         void **slot = vector_next_used( pv, &m );
 637         int c = compare( key, *slot );
 638         if ( c == 0 ) {
 639             *index = m;
 640             return *slot;
 641         }
 642         if ( c < 0 ) {
 643             hi = m;
 644         } else {
 645             lo = m + 1;
 646         }
 647     }
 648     return 0;
 649 }
 650
 651 // Iterator callback.
 652 static int checkunused(vector_index index,void *item,void *data) {
 653     vector_index *last = (vector_index*) data;
 654     if ( item == 0 ) {
 655         (*last) = index;
 656         return 1;
 657     }
 658     if ( *last > index ) {
 659         // Only on the first iteration,  with *last = vector_sie
 660         if ( index == 0 ) {
 661             (*last) = 1;
 662             return 0;
 663         }
 664         *last = 0;
 665     } else if ( index == (*last) ) {
 666         (*last)++;
 667         return 0;
 668     }
 669     return 1;
 670 }
 671
 672 // Scan forward for the next unused vector slot
 673 vector_index vector_next_unused(vector *pv,vector_index index) {
 674     vector_index unused = vector_size( pv );
 675     vector_iterate( pv, index, checkunused, &unused );
 676     return unused;
 677 }