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 & 0xf ) {
  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     (*index) |= ONES >> ( 64 - VECTOR_BITS[ pv->variant ] * level );
 154 }
 155
 156 // Return number of slots for a vector variant.
 157 unsigned long VECTOR_SLOTS(vector *pv) {
 158     switch ( pv->variant ) {
 159     case 0: return 256;
 160     case 1: return 16;
 161     case 2: return 4;
 162     case 3: return pv->size;
 163     }
 164     return 0;
 165 }
 166
 167 // The number of levels to span vector pv wrt its size and variant
 168 static unsigned int vector_levels(vector *pv,unsigned int size) {
 169     if ( size < 4 ) {
 170         return 1;
 171     }
 172     switch ( pv->variant ) {
 173     case 0: return ((int)(log2( size - 1 ) / 8)) + 1;
 174     case 1: return ((int)(log2( size - 1 ) / 4)) + 1;
 175     case 2: return ((int)(log2( size - 1 ) / 2)) + 1;
 176     case 3: return 1;
 177     }
 178     return 0;
 179 }
 180
 181 /** ============================================================ **/
 182
 183 /**
 184  * Advances a vector index to the next used slot at or below the
 185  * given level, starting from the indexed entry (inclusive) and up.
 186  * The function will free any empty pages it discovers, and then
 187  * update the index slots accordingly. The given index is advanced
 188  * cyclically to match the found slot. The function returns a slot
 189  * pointer to the used slot, if any, and 0 otherwise.
 190  */
 191 static void **vector_level_next_used(
 192     vector *pv,
 193     vector_page *page,
 194     vector_index *index,
 195     int level,
 196     vector_index end )
 197 {
 198     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 199     for( ; *index < end; p++ ) {
 200         if ( *p ) {
 201             if ( level == 0 ) {
 202                 return p; // This is a used entry
 203             }
 204             // *p is an index that needs to be inspected recursively
 205             void **x = vector_level_next_used( pv, *p, index, level - 1, end );
 206             if ( x ) {
 207                 return x; // Used slot was found; return it.
 208             }
 209             // If the page *p is all empty, so can/should be reclaimed.
 210         } else {
 211             if ( level > 0 ) {
 212                 VECTOR_INDEX_FIRST( pv, index, level );
 213             }
 214         }
 215         if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
 216             break; // cycling this level => nothing found
 217         }
 218     }
 219     return 0;
 220 }
 221
 222 // Find the next used slot at given index or later. Returns pointer to
 223 // the slot. This allows for a reclaim function that may reclaim slot
 224 // items on the way to next used slot.
 225 void **vector_next_used(vector *pv,vector_index *index) {
 226     if ( pv->entries == 0 || *index >= pv->size ) {
 227         *index = pv->size;
 228         return 0;
 229     }
 230     int levels = vector_levels( pv, pv->size );
 231     for ( ; *index < pv->size; (*index)++ ) {
 232         void **slot = vector_level_next_used(
 233             pv, pv->entries, index, levels - 1, pv->size ) ;
 234         if ( slot == 0 ) {
 235             *index = pv->size; // reached the end of the vector
 236         } else  if ( *slot == 0 ) {
 237             continue;
 238         }
 239         return slot;
 240     }
 241     return 0;
 242 }
 243
 244 #if 1
 245 /**
 246  * Advances a vector index to the prior used slot at or below the
 247  * given level, starting from the indexed entry (inclusive) and down.
 248  * The function will free any empty pages it discovers, and then
 249  * update the index slots accordingly. The given index is advanced
 250  * cyclically to match the found slot. The function returns a slot
 251  * pointer to the used slot, if any, and 0 otherwise.
 252  */
 253 static void **vector_level_prev_used(
 254     vector *pv,
 255     vector_page *page,
 256     vector_index *index,
 257     int level )
 258 {
 259     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
 260     do {
 261         if ( *p ) {
 262             if ( level == 0 ) {
 263                 return p; // This is a used entry
 264             }
 265             // *p is an index that needs to be inspected recursively
 266             void **x = vector_level_prev_used( pv, *p, index, level - 1 );
 267             if ( x ) {
 268                 return x; // Used slot was found; return it.
 269             }
 270             // If the page *p is all empty, so can/should be reclaimed.
 271         } else {
 272             if ( level > 0 ) {
 273                 VECTOR_INDEX_LAST( pv, index, level );
 274             }
 275         }
 276         p--;
 277     } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 );
 278     return 0;
 279 }
 280
 281 // Find the next used slot at given index or later. Returns pointer to
 282 // the slot. This allows for a reclaim function that may reclaim slot
 283 // items on the way to next used slot.
 284 void **vector_prev_used(vector *pv,vector_index *index) {
 285     if ( pv->entries == 0 || *index >= pv->size ) {
 286         *index = pv->size;
 287         return 0;
 288     }
 289     int levels = vector_levels( pv, pv->size );
 290     do {
 291         void **slot = vector_level_prev_used(
 292             pv, pv->entries, index, levels - 1 ) ;
 293         if ( slot == 0 ) {
 294             break; // reached the end of the vector
 295         }
 296         if ( *slot ) {
 297             return slot;
 298         }
 299     } while ( (*index)-- != 0 );
 300     *index = pv->size;
 301     return 0;
 302 }
 303
 304 #endif
 305
 306 #if 0
 307 // Find the first in-use slot at or before the index, at the level
 308 static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) {
 309     void **slot = vector_access( pv, *index, lv, 0 );
 310     if ( slot == 0 ) {
 311         return 0;
 312     }
 313     do {
 314         if ( *slot ) {
 315             if ( lv == 0 ) {
 316                 return slot;
 317             }
 318             void **sub = vector_prev_used_level( pv, index, lv - 1 );
 319             if ( sub ) {
 320                 return sub;
 321             }
 322         }
 323         slot--;
 324     } while ( VECTOR_INDEX_PART_DEC( pv, index, lv ) != 0 );
 325     return 0;
 326 }
 327
 328 // Find nearest used slot at or prior to the given index.
 329 void **vector_prev_used(vector *pv,vector_index *index) {
 330     if ( pv->entries == 0 || *index >= pv->size ) {
 331         *index = pv->size;
 332         return 0;
 333     }
 334     void **slot = vector_prev_used_level(
 335         pv, index, vector_levels( pv, pv->size ) - 1 );
 336     if ( slot == 0 ) {
 337         *index = pv->size;
 338     }
 339     return slot;
 340 }
 341 #endif
 342
 343 // Reclaim tree of unused pages for a given level
 344 static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) {
 345     int i = 0;
 346     if ( level > 0 ) {
 347         for ( ; i < VECTOR_SLOTS( pv ); i++ ) {
 348             if ( (*page)[i] ) {
 349                 vector_reclaim( pv, (vector_page *) (*page)[i], level - 1 );
 350             }
 351         }
 352     }
 353     free( page );
 354 }
 355
 356 // Resize vector, using the reclaim function as needed, to handle any
 357 // excess items or to veto the resize. Returns the index of the veto,
 358 // if any, or <0 otherwise, with -1 indicating success and -2
 359 // indicating OOM
 360 //
 361 // Note that resizing may result in the introduction/removal of
 362 // indexing levels and pages, so as to keep the leveling accurate for
 363 // the size.
 364 int vector_resize(
 365     vector *pv,vector_index new_size,
 366     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
 367     void *data )
 368 {
 369     struct {
 370         int old;
 371         int new;
 372     } level = {
 373         vector_levels( pv, pv->size ),
 374         vector_levels( pv, new_size )
 375     };
 376     vector_page *entries = 0;
 377     if ( pv->entries == 0 ) {
 378         pv->size = new_size;
 379         return 0;
 380     }
 381     // A shrinking vector might be veto-ed
 382     if ( new_size < pv->size ) {
 383         vector_index index = new_size;
 384         void **slot = vector_next_used( pv, &index );
 385         while ( slot ) {
 386             if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) {
 387                 *slot = 0;
 388                 slot = vector_next_used( pv, &index );
 389                 continue;
 390             }
 391             return index;
 392         }
 393         // At this point we know that there are no slots used after
 394         // the new_size size, so now it's time to remove and reclaim
 395         // any superflouous top level pages.
 396         if ( pv->variant == 3 ) { // Follow vector size using realloc
 397             if ( new_size > 0 ) {
 398                 entries = (vector_page*)
 399                     realloc( pv->entries, new_size * sizeof( void* ) );
 400                 if ( entries == 0 ) {
 401                     return -2; // OOM
 402                 }
 403             }
 404             pv->entries = entries;
 405         } else {
 406             vector_page **pp = &pv->entries;
 407             int i = level.old;
 408             while ( i-- > level.new ) {
 409                 if ( pp ) {
 410                     pp = (vector_page **)(*pp);
 411                 }
 412             }
 413             if ( pp != &pv->entries ) {
 414                 entries = pv->entries;
 415                 if ( pp ) {
 416                     pv->entries = *pp;
 417                     *pp = 0; // Detach subtree
 418                 } else {
 419                     pv->entries = 0;
 420                 }
 421                 vector_reclaim( pv, entries, level.old - 1 );
 422             }
 423             if ( new_size == 0 && pv->entries ) {
 424                 free( pv->entries );
 425                 pv->entries = 0;
 426             }
 427         }
 428     } else {
 429         // vector is growing. Maybe insert levels.
 430         if ( pv->variant == 3 ) { // Follow vector size using realloc
 431             entries = (vector_page *)realloc(
 432                 pv->entries, new_size * sizeof( void* ) );
 433             if ( entries == 0 ) {
 434                 return -2; // OOM
 435             }
 436             pv->entries = entries;
 437             memset( &(*entries)[ pv->size ], 0,
 438                     ( new_size - pv->size ) * sizeof( void* ) );
 439         } else {
 440             for ( ; level.old < level.new; level.old++ ) {
 441                 vector_page *p = (vector_page *)
 442                     calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 443                 if ( p == 0 ) {
 444                     return -2; // OOM
 445                 }
 446                 (*p)[0] = pv->entries;
 447                 pv->entries = p;
 448                 // Should maybe change the size to match the level?
 449                 // otherwise recovery from OOM is impossible
 450             }
 451         }
 452     }
 453     pv->size = new_size;
 454     return -1;
 455 }
 456
 457 // Return pointer to the indexed page slot at the requested level, and
 458 // adding intermediate index pages if so requested. Returns 0 if
 459 // addition fails (OOM), or if not requested and page is missing.
 460 void **vector_access(vector *pv,vector_index index,int level,int add) {
 461     if ( index >= pv->size ) {
 462         return 0;
 463     }
 464     void **page = (void**) &pv->entries;
 465     int i = vector_levels( pv, pv->size );
 466     while (  i-- > level ) {
 467         if ( add && (*page) == 0 ) {
 468             (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) );
 469         }
 470         page = (*page);
 471         if ( page == 0 ) {
 472             return 0;
 473         }
 474         page += VECTOR_INDEX_PART( pv, &index, i );
 475     }
 476     return page;
 477 }
 478
 479 // Map index into a value slot
 480 void **vector_entry(vector *pv,vector_index index) {
 481     return vector_access( pv, index, 0, 1 );
 482 }
 483
 484 inline void vector_set(vector *pv,vector_index index,void *value) {
 485     void **p = vector_entry( pv, index );
 486     *p = value;
 487 }
 488
 489 // Set value at index but return the old value
 490 void *vector_get_set(vector *pv,vector_index index,void *value) {
 491     void **p = vector_entry( pv, index );
 492     void *old = *p;
 493     *p = value;
 494     return old;
 495 }
 496
 497 inline void *vector_get(vector *pv,vector_index index) {
 498     void **p = vector_entry( pv, index );
 499     return *p;
 500 }
 501
 502 int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) {
 503     free( item );
 504     return 0;
 505 }
 506
 507 void vector_append(vector *pv,void *value) {
 508     vector_resize( pv, pv->size + 1, 0, 0 );
 509     vector_set( pv, pv->size - 1, value );
 510 }
 511
 512 // copy block of n items from src[si] to dst[di]
 513 // no efficiency hacks
 514 void vector_copy(vector *dst,vector_index di,
 515               vector *src,vector_index si,vector_index n) {
 516     if ( dst != src || di < si ) {
 517         while ( n-- != 0 ) {
 518             vector_set( dst, di++, vector_get( src, si++ ) );
 519         }
 520     } else if ( di > si ){
 521         di += n - 1;
 522         si += n - 1;
 523         while ( n-- != 0 ) {
 524             vector_set( dst, di--, vector_get( src, si-- ) );
 525         }
 526     }
 527 }
 528
 529 void vector_dump(vector *pv,
 530                  void (*itemdump)(const vector_index,const void *)) {
 531     vector_index index = 0;
 532     for ( ; index < pv->size; index++ ) {
 533         void **slot = vector_next_used( pv, &index );
 534         if ( slot == 0 ) {
 535             break;
 536         }
 537         itemdump( index, *slot );
 538     }
 539 }
 540
 541 //// Quicksort
 542
 543 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
 544  typedef int (*comparfn)(const void *,const void *);
 545
 546 static void vector_qsort_part(
 547     vector *pv,comparfn compar,
 548     vector_index low,vector_index high)
 549 {
 550     if ( low >= high ) {
 551         return;
 552     }
 553     vector_index lo = low;
 554     vector_index m = high - 1;
 555
 556     if ( lo >= m  ) {
 557         return;
 558     }
 559
 560     vector_index hi = m - 1;
 561     void **mp = vector_entry( pv, m );
 562     void **lop, **hip;
 563     for ( ;; ) {
 564         // Find index of first item "above" mp scanning from lo and up
 565         for ( ; lo < m; lo++ ) {
 566             lop = vector_entry( pv, lo );
 567             if ( compar( *lop, *mp ) < 0 ) {
 568                 break;
 569             }
 570         }
 571         // if  lo == m, then lop is wrong!!
 572         // Find index of first item "below" mp scanning from hi and down
 573         for ( ; hi > lo; hi-- ) {
 574             hip = vector_entry( pv, hi );
 575             if ( compar( *mp, *hip ) < 0 ) {
 576                 break;
 577             }
 578         }
 579         if ( lo >= hi ) {
 580             if ( lo < m ) {
 581                 void *x = *lop;
 582                 *lop = *mp;
 583                 *mp = x;
 584                 m = lo;
 585             }
 586             break;
 587         }
 588         void *x = *lop;
 589         *lop = *hip;
 590         *hip = x;
 591     }
 592     vector_qsort_part( pv, compar, low, m );
 593     vector_qsort_part( pv, compar, m+1, high );
 594 }
 595
 596 void vector_qsort(vector *pv,comparfn compar) {
 597     vector_qsort_part( pv, compar, 0, pv->size );
 598 }
 599
 600 void vector_iterate(vector *pv,
 601                     vector_index start,
 602                     int (*itemfn)(vector_index,void*,void*),
 603                     void *data )
 604 {
 605     vector_index index = start;
 606     while ( index < pv->size ) {
 607         void **slot = vector_next_used( pv, &index );
 608         if ( slot == 0 ) {
 609             break;
 610         }
 611         int end = VECTOR_SLOTS( pv );
 612         int i = index & ( end - 1 );
 613         for ( ; i < end && index < pv->size; i++, index++, slot++ ) {
 614             if ( itemfn( index, *slot, 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 }