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 byte_index_levels: {
  43         byte *pp = (byte*)(px + level);
  44         return pp->a;
  45     }
  46     case nibble_index_levels: {
  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 bitpair_index_levels: {
  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 single_index_level:
  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 byte_index_levels: {
  80         byte *pp = (byte*)( px + level );
  81         return ++(pp->a);
  82     }
  83     case nibble_index_levels: {
  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 bitpair_index_levels: {
  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 single_index_level:
 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 byte_index_levels: {
 117         byte *pp = (byte*)( px + level );
 118         return (pp->a)--;
 119     }
 120     case nibble_index_levels: {
 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 bitpair_index_levels: {
 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 single_index_level:
 139         return (*index)--;
 140     }
 141     return 0;
 142 }
 143
 144 #define ONES  (~((vector_index) 0))
 145
 146 // Set index to first 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 byte_index_levels: return 256;
 167     case nibble_index_levels: return 16;
 168     case bitpair_index_levels: return 4;
 169     case single_index_level: 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 byte_index_levels: return ((int)(log2( size - 1 ) / 8)) + 1;
 181     case nibble_index_levels: return ((int)(log2( size - 1 ) / 4)) + 1;
 182     case bitpair_index_levels: return ((int)(log2( size - 1 ) / 2)) + 1;
 183     case single_index_level: 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  * The last parameter is a flag that gets set when the scanning is
 198  * partial (i.e. not the whole index page).
 199  */
 200 static void **vector_level_next_used(
 201     vector *pv,
 202     vector_page *page,
 203     vector_index *index,
 204     int level,
 205     int *partial )
 206 {
 207     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 208     if ( VECTOR_INDEX_PART( pv, index, level ) != 0 ) {
 209         *partial = 1;
 210     }
 211     for( ; *index < pv->size; p++ ) {
 212         if ( *p ) {
 213             if ( level == 0 ) {
 214                 return p; // This is a used entry
 215             }
 216             // *p is an index that needs to be inspected recursively
 217             int w = 0;
 218             void **x = vector_level_next_used( pv, *p, index, level - 1, &w );
 219             if ( x ) {
 220                 return x; // Used slot was found; return it.
 221             }
 222             // If the page *p is all empty, so can/should be reclaimed.
 223             if ( w == 0 ) {
 224                 free( *p );
 225                 *p = 0;
 226             } else {
 227                 *partial = 1;
 228             }
 229         } else {
 230             if ( level > 0 ) {
 231                 VECTOR_INDEX_FIRST( pv, index, level - 1 );
 232             }
 233         }
 234         if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
 235             break; // cycling this level => nothing found
 236         }
 237     }
 238     return 0;
 239 }
 240
 241 // Find the next used slot at given index or later. Returns pointer to
 242 // the slot. This allows for a reclaim function that may reclaim slot
 243 // items on the way to next used slot.
 244 void **vector_next_used(vector *pv,vector_index *index) {
 245     if ( pv->entries == 0 || *index >= pv->size ) {
 246         *index = pv->size;
 247         return 0;
 248     }
 249     int levels = vector_levels( pv, pv->size );
 250     int partial = 0;
 251     do {
 252         void **slot = vector_level_next_used(
 253             pv, pv->entries, index, levels - 1, &partial ) ;
 254         if ( slot == 0 ) {
 255             break; // reached the end of the vector
 256         }
 257         if ( *slot ) {
 258             return slot;
 259         }
 260     } while ( ++(*index) < pv->size );
 261     if ( partial == 0 ) {
 262         free( pv->entries );
 263         pv->entries = 0;
 264     }
 265     *index = pv->size; // reached the end of the vector
 266     return 0;
 267 }
 268
 269 /**
 270  * Advances a vector index to the prior used slot at or below the
 271  * given level, starting from the indexed entry (inclusive) and down.
 272  * The function will free any empty pages it discovers, and then
 273  * update the index slots accordingly. The given index is advanced
 274  * cyclically to match the found slot. The function returns a slot
 275  * pointer to the used slot, if any, and 0 otherwise.
 276  * The last parameter is a flag that gets set when the scanning is
 277  * partial (i.e. not the whole index page).
 278  */
 279 static void **vector_level_prev_used(
 280     vector *pv,
 281     vector_page *page,
 282     vector_index *index,
 283     int level,
 284     int *partial )
 285 {
 286     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 287     if ( VECTOR_INDEX_PART( pv, index, level ) != VECTOR_SLOTS( pv ) - 1 ) {
 288         *partial = 1;
 289     }
 290     do {
 291         if ( *p ) {
 292             if ( level == 0 ) {
 293                 return p; // This is a used entry
 294             }
 295             // *p is an index that needs to be inspected recursively
 296             int w = 0;
 297             void **x = vector_level_prev_used( pv, *p, index, level - 1, &w );
 298             if ( x ) {
 299                 return x; // Used slot was found; return it.
 300             }
 301             // If the page *p is all empty, it can/should be reclaimed.
 302             if ( w == 0 ) {
 303                 free( *p );
 304                 *p = 0;
 305             } else {
 306                 *partial = 1;
 307             }
 308         } else {
 309             if ( level > 0 ) {
 310                 VECTOR_INDEX_LAST( pv, index, level );
 311             }
 312         }
 313         p--;
 314     } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 );
 315     return 0;
 316 }
 317
 318 // Find the next used slot at given index or later. Returns pointer to
 319 // the slot. This allows for a reclaim function that may reclaim slot
 320 // items on the way to next used slot.
 321 void **vector_prev_used(vector *pv,vector_index *index) {
 322     if ( pv->entries == 0 || *index >= pv->size ) {
 323         *index = pv->size;
 324         return 0;
 325     }
 326     int levels = vector_levels( pv, pv->size );
 327     int partial = 0;
 328     do {
 329         void **slot = vector_level_prev_used(
 330             pv, pv->entries, index, levels - 1, &partial ) ;
 331         if ( slot == 0 ) {
 332             break; // reached the end of the vector
 333         }
 334         if ( *slot ) {
 335             return slot;
 336         }
 337     } while ( (*index)-- != 0 );
 338     if ( partial == 0 ) {
 339         free( pv->entries );
 340         pv->entries = 0;
 341     }
 342     *index = pv->size; // reached the end of the vector
 343     return 0;
 344 }
 345
 346 // Reclaim tree of unused pages for a given level
 347 static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) {
 348     int i = 0;
 349     if ( level > 0 ) {
 350         for ( ; i < VECTOR_SLOTS( pv ); i++ ) {
 351             if ( (*page)[i] ) {
 352                 vector_reclaim( pv, (vector_page *) (*page)[i], level - 1 );
 353             }
 354         }
 355     }
 356     free( page );
 357 }
 358
 359 // Resize vector, using the reclaim function as needed, to handle any
 360 // excess items or to veto the resize. Returns the index of the veto,
 361 // if any, or <0 otherwise, with -1 indicating success and -2
 362 // indicating OOM
 363 //
 364 // Note that resizing may result in the introduction/removal of
 365 // indexing levels and pages, so as to keep the leveling accurate for
 366 // the size.
 367 int vector_resize(
 368     vector *pv,vector_index new_size,
 369     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
 370     void *data )
 371 {
 372     struct {
 373         int old;
 374         int new;
 375     } level = {
 376         vector_levels( pv, pv->size ),
 377         vector_levels( pv, new_size )
 378     };
 379     vector_page *entries = 0;
 380     if ( pv->entries == 0 ) {
 381         pv->size = new_size;
 382         return 0;
 383     }
 384     // A shrinking vector might be veto-ed
 385     if ( new_size < pv->size ) {
 386         vector_index index = new_size;
 387         void **slot = vector_next_used( pv, &index );
 388         while ( slot ) {
 389             if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
 390                 *slot = 0;
 391                 slot = vector_next_used( pv, &index );
 392                 continue;
 393             }
 394             return index;
 395         }
 396         // At this point we know that there are no slots used after
 397         // the new_size size, so now it's time to remove and reclaim
 398         // any superflouous top level pages.
 399         if ( pv->variant == single_index_level ) {
 400             // Follow vector size using realloc
 401             if ( new_size > 0 ) {
 402                 entries = (vector_page*)
 403                     realloc( pv->entries, new_size * sizeof( void* ) );
 404                 if ( entries == 0 ) {
 405                     return -2; // OOM
 406                 }
 407             }
 408             pv->entries = entries;
 409         } else {
 410             vector_page **pp = &pv->entries;
 411             int i = level.old;
 412             while ( i-- > level.new ) {
 413                 if ( pp ) {
 414                     pp = (vector_page **)(*pp);
 415                 }
 416             }
 417             if ( pp != &pv->entries ) {
 418                 entries = pv->entries;
 419                 if ( pp ) {
 420                     pv->entries = *pp;
 421                     *pp = 0; // Detach subtree
 422                 } else {
 423                     pv->entries = 0;
 424                 }
 425                 vector_reclaim( pv, entries, level.old - 1 );
 426             }
 427             if ( new_size == 0 && pv->entries ) {
 428                 free( pv->entries );
 429                 pv->entries = 0;
 430             }
 431         }
 432     } else {
 433         // vector is growing. Maybe insert levels.
 434         if ( pv->variant == single_index_level ) {
 435             // Follow vector size using realloc
 436             entries = (vector_page *)realloc(
 437                 pv->entries, new_size * sizeof( void* ) );
 438             if ( entries == 0 ) {
 439                 return -2; // OOM
 440             }
 441             pv->entries = entries;
 442             memset( &(*entries)[ pv->size ], 0,
 443                     ( new_size - pv->size ) * sizeof( void* ) );
 444         } else {
 445             for ( ; level.old < level.new; level.old++ ) {
 446                 vector_page *p = (vector_page *)
 447                     calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 448                 if ( p == 0 ) {
 449                     return -2; // OOM
 450                 }
 451                 (*p)[0] = pv->entries;
 452                 pv->entries = p;
 453                 // Should maybe change the size to match the level?
 454                 // otherwise recovery from OOM is impossible
 455             }
 456         }
 457     }
 458     pv->size = new_size;
 459     return -1;
 460 }
 461
 462 // Return pointer to the indexed page slot at the requested level, and
 463 // adding intermediate index pages if so requested. Returns 0 if
 464 // addition fails (OOM), or if not requested and page is missing.
 465 void **vector_access(vector *pv,vector_index index,int level,int add) {
 466     if ( index >= pv->size ) {
 467         return 0;
 468     }
 469     void **page = (void**) &pv->entries;
 470     int i = vector_levels( pv, pv->size );
 471     while (  i-- > level ) {
 472         if ( add && (*page) == 0 ) {
 473             (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 474         }
 475         page = (*page);
 476         if ( page == 0 ) {
 477             return 0;
 478         }
 479         page += VECTOR_INDEX_PART( pv, &index, i );
 480     }
 481     return page;
 482 }
 483
 484 // Map index into a value slot
 485 void **vector_entry(vector *pv,vector_index index) {
 486     return vector_access( pv, index, 0, 1 );
 487 }
 488
 489 inline void vector_set(vector *pv,vector_index index,void *value) {
 490     void **p = vector_entry( pv, index );
 491     *p = value;
 492 }
 493
 494 // Set value at index but return the old value
 495 void *vector_get_set(vector *pv,vector_index index,void *value) {
 496     void **p = vector_entry( pv, index );
 497     void *old = *p;
 498     *p = value;
 499     return old;
 500 }
 501
 502 inline void *vector_get(vector *pv,vector_index index) {
 503     void **p = vector_entry( pv, index );
 504     return *p;
 505 }
 506
 507 int vector_free_any(vector *pv,vector_index ix,void *item,void *data) {
 508     free( item );
 509     return 0;
 510 }
 511
 512 int vector_clear_any(vector *pv,vector_index ix,void *item,void *data) {
 513     return 0;
 514 }
 515
 516 void vector_append(vector *pv,void *value) {
 517     vector_resize( pv, pv->size + 1, 0, 0 );
 518     vector_set( pv, pv->size - 1, value );
 519 }
 520
 521 // copy block of n items from src[si] to dst[di]
 522 // no efficiency hacks
 523 void vector_copy(vector *dst,vector_index di,
 524               vector *src,vector_index si,vector_index n) {
 525     if ( dst != src || di < si ) {
 526         while ( n-- != 0 ) {
 527             vector_set( dst, di++, vector_get( src, si++ ) );
 528         }
 529     } else if ( di > si ){
 530         di += n - 1;
 531         si += n - 1;
 532         while ( n-- != 0 ) {
 533             vector_set( dst, di--, vector_get( src, si-- ) );
 534         }
 535     }
 536 }
 537
 538 vector *vector_clone(enum vector_variant variant,vector *src) {
 539     vector *dst = (vector*) malloc( sizeof( vector ) );
 540     (*dst) = (vector) { .variant = variant, .size = 0, .entries = 0 };
 541     vector_resize( dst, src->size, 0, 0 );
 542     vector_copy( dst, 0, src, 0, src->size );
 543     return dst;
 544 }
 545
 546 void vector_dump(vector *pv,
 547                  void (*itemdump)(const vector_index,const void *)) {
 548     vector_index index = 0;
 549     for ( ; index < pv->size; index++ ) {
 550         void **slot = vector_next_used( pv, &index );
 551         if ( slot == 0 ) {
 552             break;
 553         }
 554         itemdump( index, *slot );
 555     }
 556 }
 557
 558 //// Quicksort
 559
 560 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 561  typedef int (*comparfn)(const void *,const void *);
 562
 563 static void vector_qsort_part(
 564     vector *pv,comparfn compar,
 565     vector_index low,vector_index high)
 566 {
 567     if ( low >= high ) {
 568         return;
 569     }
 570     vector_index lo = low;
 571     vector_index m = high - 1;
 572
 573     if ( lo >= m  ) {
 574         return;
 575     }
 576
 577     vector_index hi = m - 1;
 578     void **mp = vector_entry( pv, m );
 579     void **lop, **hip;
 580     for ( ;; ) {
 581         // Find index of first item "above" mp scanning from lo and up
 582         for ( ; lo < m; lo++ ) {
 583             lop = vector_entry( pv, lo );
 584             if ( compar( *lop, *mp ) < 0 ) {
 585                 break;
 586             }
 587         }
 588         // if  lo == m, then lop is wrong!!
 589         // Find index of first item "below" mp scanning from hi and down
 590         for ( ; hi > lo; hi-- ) {
 591             hip = vector_entry( pv, hi );
 592             if ( compar( *mp, *hip ) < 0 ) {
 593                 break;
 594             }
 595         }
 596         if ( lo >= hi ) {
 597             if ( lo < m ) {
 598                 void *x = *lop;
 599                 *lop = *mp;
 600                 *mp = x;
 601                 m = lo;
 602             }
 603             break;
 604         }
 605         void *x = *lop;
 606         *lop = *hip;
 607         *hip = x;
 608     }
 609     vector_qsort_part( pv, compar, low, m );
 610     vector_qsort_part( pv, compar, m+1, high );
 611 }
 612
 613 void vector_qsort(vector *pv,comparfn compar) {
 614     vector_qsort_part( pv, compar, 0, pv->size );
 615 }
 616
 617 void vector_iterate(vector *pv,
 618                     vector_index start,
 619                     int (*itemfn)(vector_index,void*,void*),
 620                     void *data )
 621 {
 622     vector_index index = start;
 623     while ( index < pv->size ) {
 624         int end = VECTOR_SLOTS( pv );
 625         int i = index & ( end - 1 );
 626         for ( ; i < end && index < pv->size; i++, index++ ) {
 627             void **slot = vector_access( pv, index, 0, 0 );
 628             if ( itemfn( index, slot? *slot: 0, data ) ) {
 629                 return;
 630             }
 631         }
 632     }
 633 }
 634
 635 struct find_data {
 636     void *value;
 637     vector_index index;
 638 };
 639
 640 static int vector_find_item(vector_index index, void *item,void *data) {
 641     struct find_data *fd = (struct find_data*)data;
 642     if ( fd->value != item ) {
 643         return 0;
 644     }
 645     fd->index = index;
 646     return 1;
 647 }
 648
 649 vector_index vector_find(vector *pv,void *value) {
 650     struct find_data fd = {
 651         .value = value,
 652         .index = pv->size
 653     };
 654     vector_iterate( pv, 0, vector_find_item, &fd );
 655     return fd.index;
 656 }
 657
 658 // Find surrounding indexes for a given item key in a sparse vector
 659 void *vector_bsearch(vector *pv,vector_index *index,const void *key,
 660                      int (*compare)(const void *key, const void *item)) {
 661     vector_index lo = 0;
 662     vector_index hi = pv->size;
 663     if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) {
 664         return 0;
 665     }
 666     hi++;
 667     while ( lo < hi ) {
 668         vector_index m = lo + ( hi - lo ) / 2;
 669         void **slot = vector_next_used( pv, &m );
 670         int c = compare( key, *slot );
 671         if ( c == 0 ) {
 672             *index = m;
 673             return *slot;
 674         }
 675         if ( c < 0 ) {
 676             hi = m;
 677         } else {
 678             lo = m + 1;
 679         }
 680     }
 681     return 0;
 682 }
 683
 684 // Iterator callback.
 685 static int checkunused(vector_index index,void *item,void *data) {
 686     vector_index *last = (vector_index*) data;
 687     if ( item == 0 ) {
 688         (*last) = index;
 689         return 1;
 690     }
 691     if ( *last > index ) {
 692         // Only on the first iteration,  with *last = vector_sie
 693         if ( index == 0 ) {
 694             (*last) = 1;
 695             return 0;
 696         }
 697         *last = 0;
 698     } else if ( index == (*last) ) {
 699         (*last)++;
 700         return 0;
 701     }
 702     return 1;
 703 }
 704
 705 // Scan forward for the next unused vector slot
 706 vector_index vector_next_unused(vector *pv,vector_index index) {
 707     vector_index unused = vector_size( pv );
 708     vector_iterate( pv, index, checkunused, &unused );
 709     return unused;
 710 }