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 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 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  * 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 == 3 ) { // Follow vector size using realloc
 400             if ( new_size > 0 ) {
 401                 entries = (vector_page*)
 402                     realloc( pv->entries, new_size * sizeof( void* ) );
 403                 if ( entries == 0 ) {
 404                     return -2; // OOM
 405                 }
 406             }
 407             pv->entries = entries;
 408         } else {
 409             vector_page **pp = &pv->entries;
 410             int i = level.old;
 411             while ( i-- > level.new ) {
 412                 if ( pp ) {
 413                     pp = (vector_page **)(*pp);
 414                 }
 415             }
 416             if ( pp != &pv->entries ) {
 417                 entries = pv->entries;
 418                 if ( pp ) {
 419                     pv->entries = *pp;
 420                     *pp = 0; // Detach subtree
 421                 } else {
 422                     pv->entries = 0;
 423                 }
 424                 vector_reclaim( pv, entries, level.old - 1 );
 425             }
 426             if ( new_size == 0 && pv->entries ) {
 427                 free( pv->entries );
 428                 pv->entries = 0;
 429             }
 430         }
 431     } else {
 432         // vector is growing. Maybe insert levels.
 433         if ( pv->variant == 3 ) { // Follow vector size using realloc
 434             entries = (vector_page *)realloc(
 435                 pv->entries, new_size * sizeof( void* ) );
 436             if ( entries == 0 ) {
 437                 return -2; // OOM
 438             }
 439             pv->entries = entries;
 440             memset( &(*entries)[ pv->size ], 0,
 441                     ( new_size - pv->size ) * sizeof( void* ) );
 442         } else {
 443             for ( ; level.old < level.new; level.old++ ) {
 444                 vector_page *p = (vector_page *)
 445                     calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 446                 if ( p == 0 ) {
 447                     return -2; // OOM
 448                 }
 449                 (*p)[0] = pv->entries;
 450                 pv->entries = p;
 451                 // Should maybe change the size to match the level?
 452                 // otherwise recovery from OOM is impossible
 453             }
 454         }
 455     }
 456     pv->size = new_size;
 457     return -1;
 458 }
 459
 460 // Return pointer to the indexed page slot at the requested level, and
 461 // adding intermediate index pages if so requested. Returns 0 if
 462 // addition fails (OOM), or if not requested and page is missing.
 463 void **vector_access(vector *pv,vector_index index,int level,int add) {
 464     if ( index >= pv->size ) {
 465         return 0;
 466     }
 467     void **page = (void**) &pv->entries;
 468     int i = vector_levels( pv, pv->size );
 469     while (  i-- > level ) {
 470         if ( add && (*page) == 0 ) {
 471             (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 472         }
 473         page = (*page);
 474         if ( page == 0 ) {
 475             return 0;
 476         }
 477         page += VECTOR_INDEX_PART( pv, &index, i );
 478     }
 479     return page;
 480 }
 481
 482 // Map index into a value slot
 483 void **vector_entry(vector *pv,vector_index index) {
 484     return vector_access( pv, index, 0, 1 );
 485 }
 486
 487 inline void vector_set(vector *pv,vector_index index,void *value) {
 488     void **p = vector_entry( pv, index );
 489     *p = value;
 490 }
 491
 492 // Set value at index but return the old value
 493 void *vector_get_set(vector *pv,vector_index index,void *value) {
 494     void **p = vector_entry( pv, index );
 495     void *old = *p;
 496     *p = value;
 497     return old;
 498 }
 499
 500 inline void *vector_get(vector *pv,vector_index index) {
 501     void **p = vector_entry( pv, index );
 502     return *p;
 503 }
 504
 505 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
 506     free( item );
 507     return 0;
 508 }
 509
 510 void vector_append(vector *pv,void *value) {
 511     vector_resize( pv, pv->size + 1, 0, 0 );
 512     vector_set( pv, pv->size - 1, value );
 513 }
 514
 515 // copy block of n items from src[si] to dst[di]
 516 // no efficiency hacks
 517 void vector_copy(vector *dst,vector_index di,
 518               vector *src,vector_index si,vector_index n) {
 519     if ( dst != src || di < si ) {
 520         while ( n-- != 0 ) {
 521             vector_set( dst, di++, vector_get( src, si++ ) );
 522         }
 523     } else if ( di > si ){
 524         di += n - 1;
 525         si += n - 1;
 526         while ( n-- != 0 ) {
 527             vector_set( dst, di--, vector_get( src, si-- ) );
 528         }
 529     }
 530 }
 531
 532 void vector_dump(vector *pv,
 533                  void (*itemdump)(const vector_index,const void *)) {
 534     vector_index index = 0;
 535     for ( ; index < pv->size; index++ ) {
 536         void **slot = vector_next_used( pv, &index );
 537         if ( slot == 0 ) {
 538             break;
 539         }
 540         itemdump( index, *slot );
 541     }
 542 }
 543
 544 //// Quicksort
 545
 546 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 547  typedef int (*comparfn)(const void *,const void *);
 548
 549 static void vector_qsort_part(
 550     vector *pv,comparfn compar,
 551     vector_index low,vector_index high)
 552 {
 553     if ( low >= high ) {
 554         return;
 555     }
 556     vector_index lo = low;
 557     vector_index m = high - 1;
 558
 559     if ( lo >= m  ) {
 560         return;
 561     }
 562
 563     vector_index hi = m - 1;
 564     void **mp = vector_entry( pv, m );
 565     void **lop, **hip;
 566     for ( ;; ) {
 567         // Find index of first item "above" mp scanning from lo and up
 568         for ( ; lo < m; lo++ ) {
 569             lop = vector_entry( pv, lo );
 570             if ( compar( *lop, *mp ) < 0 ) {
 571                 break;
 572             }
 573         }
 574         // if  lo == m, then lop is wrong!!
 575         // Find index of first item "below" mp scanning from hi and down
 576         for ( ; hi > lo; hi-- ) {
 577             hip = vector_entry( pv, hi );
 578             if ( compar( *mp, *hip ) < 0 ) {
 579                 break;
 580             }
 581         }
 582         if ( lo >= hi ) {
 583             if ( lo < m ) {
 584                 void *x = *lop;
 585                 *lop = *mp;
 586                 *mp = x;
 587                 m = lo;
 588             }
 589             break;
 590         }
 591         void *x = *lop;
 592         *lop = *hip;
 593         *hip = x;
 594     }
 595     vector_qsort_part( pv, compar, low, m );
 596     vector_qsort_part( pv, compar, m+1, high );
 597 }
 598
 599 void vector_qsort(vector *pv,comparfn compar) {
 600     vector_qsort_part( pv, compar, 0, pv->size );
 601 }
 602
 603 void vector_iterate(vector *pv,
 604                     vector_index start,
 605                     int (*itemfn)(vector_index,void*,void*),
 606                     void *data )
 607 {
 608     vector_index index = start;
 609     while ( index < pv->size ) {
 610         int end = VECTOR_SLOTS( pv );
 611         int i = index & ( end - 1 );
 612         for ( ; i < end && index < pv->size; i++, index++ ) {
 613             void **slot = vector_access( pv, index, 0, 0 );
 614             if ( itemfn( index, slot? *slot: 0, data ) ) {
 615                 return;
 616             }
 617         }
 618     }
 619 }
 620
 621 // Find surrounding indexes for a given item key in a sparse vector
 622 void *vector_bsearch(vector *pv,vector_index *index,const void *key,
 623                      int (*compare)(const void *key, const void *item)) {
 624     vector_index lo = 0;
 625     vector_index hi = pv->size;
 626     if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) {
 627         return 0;
 628     }
 629     hi++;
 630     while ( lo < hi ) {
 631         vector_index m = lo + ( hi - lo ) / 2;
 632         void **slot = vector_next_used( pv, &m );
 633         int c = compare( key, *slot );
 634         if ( c == 0 ) {
 635             *index = m;
 636             return *slot;
 637         }
 638         if ( c < 0 ) {
 639             hi = m;
 640         } else {
 641             lo = m + 1;
 642         }
 643     }
 644     return 0;
 645 }
 646
 647 // Iterator callback.
 648 static int checkunused(vector_index index,void *item,void *data) {
 649     vector_index *last = (vector_index*) data;
 650     if ( item == 0 ) {
 651         (*last) = index;
 652         return 1;
 653     }
 654     if ( *last > index ) {
 655         // Only on the first iteration,  with *last = vector_sie
 656         if ( index == 0 ) {
 657             (*last) = 1;
 658             return 0;
 659         }
 660         *last = 0;
 661     } else if ( index == (*last) ) {
 662         (*last)++;
 663         return 0;
 664     }
 665     return 1;
 666 }
 667
 668 // Scan forward for the next unused vector slot
 669 vector_index vector_next_unused(vector *pv,vector_index index) {
 670     vector_index unused = vector_size( pv );
 671     vector_iterate( pv, index, checkunused, &unused );
 672     return unused;
 673 }