unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
unsigned char *px = (unsigned char *) index;
switch ( pv->variant ) {
- case 0: {
+ case byte_index_levels: {
byte *pp = (byte*)(px + level);
return pp->a;
}
- case 1: {
- nibble *pp = (nibble*)(px + ( level / 2 ));
+ case nibble_index_levels: {
+ nibble *pp = (nibble*)( px + ( level / 2 ) );
switch ( level & 1 ) {
case 0: return pp->a;
case 1: return pp->b;
}
break;
}
- case 2: {
- bitpair *pp = (bitpair*)(px + ( level / 4 ));
+ case bitpair_index_levels: {
+ bitpair *pp = (bitpair*)( px + ( level / 4 ) );
switch ( level & 3 ) {
case 0: return pp->a;
case 1: return pp->b;
}
break;
}
- case 3:
+ case single_index_level:
return (*index);
}
return 0;
{
unsigned char *px = (unsigned char *) index;
switch ( pv->variant ) {
- case 0: {
+ case byte_index_levels: {
byte *pp = (byte*)( px + level );
return ++(pp->a);
}
- case 1: {
+ case nibble_index_levels: {
nibble *pp = (nibble*)( px + ( level / 2 ) );
switch ( level & 1 ) {
case 0: return ++(pp->a);
}
break;
}
- case 2: {
+ case bitpair_index_levels: {
bitpair *pp = (bitpair*)( px + level / 4 );
- switch ( level & 0xf ) {
+ switch ( level & 3 ) {
case 0: return ++(pp->a);
case 1: return ++(pp->b);
case 2: return ++(pp->c);
}
break;
}
- case 3:
+ case single_index_level:
return ++(*index);
}
return 0;
{
unsigned char *px = (unsigned char *) index;
switch ( pv->variant ) {
- case 0: {
+ case byte_index_levels: {
byte *pp = (byte*)( px + level );
return (pp->a)--;
}
- case 1: {
+ case nibble_index_levels: {
nibble *pp = (nibble*)( px + ( level / 2 ) );
switch ( level & 1 ) {
case 0: return (pp->a)--;
}
break;
}
- case 2: {
+ case bitpair_index_levels: {
bitpair *pp = (bitpair*)( px + level / 4 );
switch ( level & 0xf ) {
case 0: return (pp->a)--;
}
break;
}
- case 3:
+ case single_index_level:
return (*index)--;
}
return 0;
#define ONES (~((vector_index) 0))
-// Set index to last value for all index parts at level and lower.
+// Set index to first value for all index parts at level and lower.
static void VECTOR_INDEX_FIRST(vector *pv,vector_index *index, int level) {
(*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
}
// Set index to last value for all index parts at level and lower.
static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int level) {
- (*index) |= ONES >> ( 64 - VECTOR_BITS[ pv->variant ] * level );
+ static unsigned long ones[] = { 255, 15, 3 };
+ unsigned long x = ones[ pv->variant ];
+ while ( level-- ) {
+ (*index) |= x;
+ x <<= VECTOR_BITS[ pv->variant ];
+ }
+ // 255, 25, 3
+ //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
}
// Return number of slots for a vector variant.
unsigned long VECTOR_SLOTS(vector *pv) {
switch ( pv->variant ) {
- case 0: return 256;
- case 1: return 16;
- case 2: return 4;
- case 3: return pv->size;
+ case byte_index_levels: return 256;
+ case nibble_index_levels: return 16;
+ case bitpair_index_levels: return 4;
+ case single_index_level: return pv->size;
}
return 0;
}
return 1;
}
switch ( pv->variant ) {
- case 0: return ((int)(log2( size - 1 ) / 8)) + 1;
- case 1: return ((int)(log2( size - 1 ) / 4)) + 1;
- case 2: return ((int)(log2( size - 1 ) / 2)) + 1;
- case 3: return 1;
+ case byte_index_levels: return ((int)(log2( size - 1 ) / 8)) + 1;
+ case nibble_index_levels: return ((int)(log2( size - 1 ) / 4)) + 1;
+ case bitpair_index_levels: return ((int)(log2( size - 1 ) / 2)) + 1;
+ case single_index_level: return 1;
}
return 0;
}
* update the index slots accordingly. The given index is advanced
* cyclically to match the found slot. The function returns a slot
* pointer to the used slot, if any, and 0 otherwise.
+ * The last parameter is a flag that gets set when the scanning is
+ * partial (i.e. not the whole index page).
*/
static void **vector_level_next_used(
vector *pv,
vector_page *page,
vector_index *index,
int level,
- vector_index end )
+ int *partial )
{
void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
- for( ; *index < end; p++ ) {
+ if ( VECTOR_INDEX_PART( pv, index, level ) != 0 ) {
+ *partial = 1;
+ }
+ for( ; *index < pv->size; p++ ) {
if ( *p ) {
if ( level == 0 ) {
return p; // This is a used entry
}
// *p is an index that needs to be inspected recursively
- void **x = vector_level_next_used( pv, *p, index, level - 1, end );
+ int w = 0;
+ void **x = vector_level_next_used( pv, *p, index, level - 1, &w );
if ( x ) {
return x; // Used slot was found; return it.
}
// If the page *p is all empty, so can/should be reclaimed.
+ if ( w == 0 ) {
+ free( *p );
+ *p = 0;
+ } else {
+ *partial = 1;
+ }
} else {
if ( level > 0 ) {
- VECTOR_INDEX_FIRST( pv, index, level );
+ VECTOR_INDEX_FIRST( pv, index, level - 1 );
}
}
if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
return 0;
}
int levels = vector_levels( pv, pv->size );
- for ( ; *index < pv->size; (*index)++ ) {
+ int partial = 0;
+ do {
void **slot = vector_level_next_used(
- pv, pv->entries, index, levels - 1, pv->size ) ;
+ pv, pv->entries, index, levels - 1, &partial ) ;
if ( slot == 0 ) {
- *index = pv->size; // reached the end of the vector
- } else if ( *slot == 0 ) {
- continue;
+ break; // reached the end of the vector
+ }
+ if ( *slot ) {
+ return slot;
}
- return slot;
+ } while ( ++(*index) < pv->size );
+ if ( partial == 0 ) {
+ free( pv->entries );
+ pv->entries = 0;
}
+ *index = pv->size; // reached the end of the vector
return 0;
}
-#if 1
/**
* Advances a vector index to the prior used slot at or below the
* given level, starting from the indexed entry (inclusive) and down.
* update the index slots accordingly. The given index is advanced
* cyclically to match the found slot. The function returns a slot
* pointer to the used slot, if any, and 0 otherwise.
+ * The last parameter is a flag that gets set when the scanning is
+ * partial (i.e. not the whole index page).
*/
static void **vector_level_prev_used(
vector *pv,
vector_page *page,
vector_index *index,
- int level )
+ int level,
+ int *partial )
{
void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
+ if ( VECTOR_INDEX_PART( pv, index, level ) != VECTOR_SLOTS( pv ) - 1 ) {
+ *partial = 1;
+ }
do {
if ( *p ) {
if ( level == 0 ) {
return p; // This is a used entry
}
// *p is an index that needs to be inspected recursively
- void **x = vector_level_prev_used( pv, *p, index, level - 1 );
+ int w = 0;
+ void **x = vector_level_prev_used( pv, *p, index, level - 1, &w );
if ( x ) {
return x; // Used slot was found; return it.
}
- // If the page *p is all empty, so can/should be reclaimed.
+ // If the page *p is all empty, it can/should be reclaimed.
+ if ( w == 0 ) {
+ free( *p );
+ *p = 0;
+ } else {
+ *partial = 1;
+ }
} else {
if ( level > 0 ) {
VECTOR_INDEX_LAST( pv, index, level );
return 0;
}
int levels = vector_levels( pv, pv->size );
+ int partial = 0;
do {
void **slot = vector_level_prev_used(
- pv, pv->entries, index, levels - 1 ) ;
+ pv, pv->entries, index, levels - 1, &partial ) ;
if ( slot == 0 ) {
break; // reached the end of the vector
}
return slot;
}
} while ( (*index)-- != 0 );
- *index = pv->size;
- return 0;
-}
-
-#endif
-
-#if 0
-// Find the first in-use slot at or before the index, at the level
-static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) {
- void **slot = vector_access( pv, *index, lv, 0 );
- if ( slot == 0 ) {
- return 0;
+ if ( partial == 0 ) {
+ free( pv->entries );
+ pv->entries = 0;
}
- do {
- if ( *slot ) {
- if ( lv == 0 ) {
- return slot;
- }
- void **sub = vector_prev_used_level( pv, index, lv - 1 );
- if ( sub ) {
- return sub;
- }
- }
- slot--;
- } while ( VECTOR_INDEX_PART_DEC( pv, index, lv ) != 0 );
+ *index = pv->size; // reached the end of the vector
return 0;
}
-// Find nearest used slot at or prior to the given index.
-void **vector_prev_used(vector *pv,vector_index *index) {
- if ( pv->entries == 0 || *index >= pv->size ) {
- *index = pv->size;
- return 0;
- }
- void **slot = vector_prev_used_level(
- pv, index, vector_levels( pv, pv->size ) - 1 );
- if ( slot == 0 ) {
- *index = pv->size;
- }
- return slot;
-}
-#endif
-
// Reclaim tree of unused pages for a given level
static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) {
int i = 0;
// At this point we know that there are no slots used after
// the new_size size, so now it's time to remove and reclaim
// any superflouous top level pages.
- if ( pv->variant == 3 ) { // Follow vector size using realloc
+ if ( pv->variant == single_index_level ) {
+ // Follow vector size using realloc
if ( new_size > 0 ) {
entries = (vector_page*)
realloc( pv->entries, new_size * sizeof( void* ) );
}
} else {
// vector is growing. Maybe insert levels.
- if ( pv->variant == 3 ) { // Follow vector size using realloc
+ if ( pv->variant == single_index_level ) {
+ // Follow vector size using realloc
entries = (vector_page *)realloc(
pv->entries, new_size * sizeof( void* ) );
if ( entries == 0 ) {
}
}
+vector *vector_clone(enum vector_variant variant,vector *src) {
+ vector *dst = (vector*) malloc( sizeof( vector ) );
+ (*dst) = (vector) { .variant = variant, .size = 0, .entries = 0 };
+ vector_resize( dst, src->size, 0, 0 );
+ vector_copy( dst, 0, src, 0, src->size );
+ return dst;
+}
+
void vector_dump(vector *pv,
void (*itemdump)(const vector_index,const void *)) {
vector_index index = 0;
{
vector_index index = start;
while ( index < pv->size ) {
- void **slot = vector_next_used( pv, &index );
- if ( slot == 0 ) {
- break;
- }
int end = VECTOR_SLOTS( pv );
int i = index & ( end - 1 );
- for ( ; i < end && index < pv->size; i++, index++, slot++ ) {
- if ( itemfn( index, *slot, data ) ) {
+ for ( ; i < end && index < pv->size; i++, index++ ) {
+ void **slot = vector_access( pv, index, 0, 0 );
+ if ( itemfn( index, slot? *slot: 0, data ) ) {
return;
}
}
}
}
+struct find_data {
+ void *value;
+ vector_index index;
+};
+
+static int vector_find_item(vector_index index, void *item,void *data) {
+ struct find_data *fd = (struct find_data*)data;
+ if ( fd->value != item ) {
+ return 0;
+ }
+ fd->index = index;
+ return 1;
+}
+
+vector_index vector_find(vector *pv,void *value) {
+ struct find_data fd = {
+ .value = value,
+ .index = pv->size
+ };
+ vector_iterate( pv, 0, vector_find_item, &fd );
+ return fd.index;
+}
+
// Find surrounding indexes for a given item key in a sparse vector
void *vector_bsearch(vector *pv,vector_index *index,const void *key,
int (*compare)(const void *key, const void *item)) {
projects / rrq / rrqmisc.git / blobdiff