X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fvector.c;h=2f1010c841791c0d66ed420e197023a238057540;hb=f9a90dad5d64b519557f6774ed16c6e99b82f72a;hp=5b3848842b30ec1058b4c39fb7cd38901de6836c;hpb=a0be49ff8fda77c328424c09d6d0ad4a9f7e8f66;p=rrq%2Frrqmisc.git diff --git a/vector/vector.c b/vector/vector.c index 5b38488..2f1010c 100644 --- a/vector/vector.c +++ b/vector/vector.c @@ -1,4 +1,5 @@ -#include +#include +#include #include #include "vector.h" @@ -9,56 +10,181 @@ */ /** ============================================================ **/ -#if VECTOR_LEVEL_BITS == 4 -typedef union { - vector_index as_whole; - struct { - unsigned int msb:4; unsigned int lsb:4; - } __attribute__ ((__packed__)) as_byte[8]; -} vector_indexing; -#define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 ) +static int VECTOR_BITS[4] = { 8, 4, 2, 64 }; + +typedef struct { + unsigned int a:2; + unsigned int b:2; + unsigned int c:2; + unsigned int d:2; +} bitpair; + +typedef struct { + unsigned int a:4; + unsigned int b:4; +} nibble; -#define VECTOR_PART_BYTE(i,p) ((vector_indexing*)(i))->as_byte[ (p)/2 ] +typedef struct { + unsigned int a:8; +} byte; -static int VECTOR_INDEX_PART(vector_index *index,int part) { - if ( part & 1 ) { - return VECTOR_PART_BYTE(index,part).lsb; +/** + * Return the index part for the given level of the vector's leveling + * variant. + * + * The vector variant indicates whether indexing uses 8, 4, or 2 bits + * per level. + */ +unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) { + unsigned char *px = (unsigned char *) index; + switch ( pv->variant ) { + case 0: { + byte *pp = (byte*)(px + level); + return pp->a; + } + case 1: { + 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 ) ); + switch ( level & 3 ) { + case 0: return pp->a; + case 1: return pp->b; + case 2: return pp->c; + case 3: return pp->d; + } + break; } - return VECTOR_PART_BYTE(index,part).msb; + case 3: + return (*index); + } + return 0; } -static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { - if ( part & 1 ) { - return ++VECTOR_PART_BYTE(index,part).lsb; +/** + * Increment the index part at the indivated level, cyclic but not + * carrying over to the upper level. Returns the new level index. + */ +static unsigned long VECTOR_INDEX_PART_INC( + vector *pv,vector_index *index, int level) +{ + unsigned char *px = (unsigned char *) index; + switch ( pv->variant ) { + case 0: { + byte *pp = (byte*)( px + level ); + return ++(pp->a); + } + case 1: { + 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 ); + switch ( level & 3 ) { + case 0: return ++(pp->a); + case 1: return ++(pp->b); + case 2: return ++(pp->c); + case 3: return ++(pp->d); + } + break; + } + case 3: + return ++(*index); } - return ++VECTOR_PART_BYTE(index,part).msb; + return 0; } -static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { - if ( part & 1 ) { - return VECTOR_PART_BYTE(index,part).lsb--; +/** + * Decrement the index part at the indicated level, cyclic but not + * carrying over to the upper level. Returns the prior level index. + */ +static unsigned long VECTOR_INDEX_PART_DEC( + vector *pv,vector_index *index, int level) +{ + unsigned char *px = (unsigned char *) index; + switch ( pv->variant ) { + case 0: { + byte *pp = (byte*)( px + level ); + return (pp->a)--; + } + case 1: { + nibble *pp = (nibble*)( px + ( level / 2 ) ); + switch ( level & 1 ) { + case 0: return (pp->a)--; + case 1: return (pp->b)--; + } + break; } - return VECTOR_PART_BYTE(index,part).msb--; + case 2: { + bitpair *pp = (bitpair*)( px + level / 4 ); + switch ( level & 0xf ) { + case 0: return (pp->a)--; + case 1: return (pp->b)--; + case 2: return (pp->c)--; + case 3: return (pp->d)--; + } + break; + } + case 3: + return (*index)--; + } + return 0; } -/** ============================================================ **/ -#elif VECTOR_LEVEL_BITS == 8 - -#define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 ) +#define ONES (~((vector_index) 0)) -typedef union { - vector_index as_whole; - unsigned char as_byte[8]; -} vector_indexing; +// 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 ); +} -#define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->as_byte[p]) +// 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) { + 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 ) ); +} -#define VECTOR_INDEX_PART_INC(i,p) (++VECTOR_INDEX_PART(i,p)) +// 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; + } + return 0; +} -#define VECTOR_INDEX_PART_DEC(i,p) (VECTOR_INDEX_PART(i,p)--) +// The number of levels to span vector pv wrt its size and variant +static unsigned int vector_levels(vector *pv,unsigned int size) { + if ( size < 4 ) { + 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; + } + return 0; +} -#endif /** ============================================================ **/ /** @@ -68,75 +194,162 @@ typedef union { * 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_page *page,vector_index *index,int level,vector_index end) { - void **p = (void**)&(*page)[ VECTOR_INDEX_PART( index, level ) ]; - for( ; *index < end; p++ ) { + vector *pv, + vector_page *page, + vector_index *index, + int level, + int *partial ) +{ + void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ]; + 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 - int whole = VECTOR_INDEX_PART( index, level - 1 ) == 0; - void **x = vector_level_next_used( *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. } - // The page *p is all empty, so can/should be reclaimed. - if ( whole ) { + // 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 - 1 ); } } - if ( VECTOR_INDEX_PART_INC( index, level ) == 0 ) { + if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) { break; // cycling this level => nothing found } } return 0; } +// Find the next used slot at given index or later. Returns pointer to +// the slot. This allows for a reclaim function that may reclaim slot +// items on the way to next used slot. +void **vector_next_used(vector *pv,vector_index *index) { + if ( pv->entries == 0 || *index >= pv->size ) { + *index = pv->size; + return 0; + } + int levels = vector_levels( pv, pv->size ); + int partial = 0; + do { + void **slot = vector_level_next_used( + pv, pv->entries, index, levels - 1, &partial ) ; + if ( slot == 0 ) { + break; // reached the end of the vector + } + if ( *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; +} -// The least number of levels to span index S (typically the size of a -// vector) -static unsigned int vector_levels(vector_index S) { - unsigned int N = 0; +/** + * Advances a vector index to the prior used slot at or below the + * given level, starting from the indexed entry (inclusive) and down. + * The function will free any empty pages it discovers, and then + * 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 *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 { - N++; - S /= VECTOR_SLOTS; - } while ( S ); - return N; + if ( *p ) { + if ( level == 0 ) { + return p; // This is a used entry + } + // *p is an index that needs to be inspected recursively + 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, 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 ); + } + } + p--; + } while ( VECTOR_INDEX_PART_DEC( pv, index, level ) != 0 ); + return 0; } // Find the next used slot at given index or later. Returns pointer to // the slot. This allows for a reclaim function that may reclaim slot // items on the way to next used slot. -void **vector_next_used(vector *pv,vector_index *index) { +void **vector_prev_used(vector *pv,vector_index *index) { if ( pv->entries == 0 || *index >= pv->size ) { *index = pv->size; return 0; } - int levels = vector_levels( pv->size ); - for ( ; *index < pv->size; (*index)++ ) { - void **slot = vector_level_next_used( - pv->entries, index, levels - 1, pv->size ) ; + int levels = vector_levels( pv, pv->size ); + int partial = 0; + do { + void **slot = vector_level_prev_used( + 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)-- != 0 ); + if ( partial == 0 ) { + free( pv->entries ); + pv->entries = 0; } + *index = pv->size; // reached the end of the vector return 0; } -// Reclaim tree of unused pages -static void vector_reclaim(vector_page *page,unsigned int level) { +// Reclaim tree of unused pages for a given level +static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) { int i = 0; if ( level > 0 ) { - for ( ; i < VECTOR_SLOTS; i++ ) { + for ( ; i < VECTOR_SLOTS( pv ); i++ ) { if ( (*page)[i] ) { - vector_reclaim( (vector_page *) (*page)[i], level - 1 ); + vector_reclaim( pv, (vector_page *) (*page)[i], level - 1 ); } } } @@ -156,27 +369,14 @@ int vector_resize( int (*reclaim)(vector *pv,vector_index index,void *item,void *data), void *data ) { - // Table of number of slots for a level above that of the number - // at the prior lower level. The first level (i.e., level 0) adds - // 15 slots to the one slot of no index page. Level 1 adds 15*16 - // slots, level 2 adds 15*(16^2), and generically level i adds - // 15*(16^i) slots. - static int level_delta[ VECTOR_INDEX_FIELDS ]; - if ( level_delta[ 0 ] == 0 ) { - int d = 1; - int i; - for ( i = 0; i < VECTOR_INDEX_FIELDS; i++ ) { - level_delta[ i ] = ( VECTOR_SLOTS - 1 ) * d; - d = VECTOR_SLOTS * d; - } - } struct { int old; int new; } level = { - vector_levels( pv->size ), - vector_levels( new_size ) + vector_levels( pv, pv->size ), + vector_levels( pv, new_size ) }; + vector_page *entries = 0; if ( pv->entries == 0 ) { pv->size = new_size; return 0; @@ -196,40 +396,61 @@ int vector_resize( // 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. - vector_page *entries; - vector_page **pp = &pv->entries; - while ( level.old-- > level.new ) { - if ( pp ) { - pp = (vector_page **)(*pp)[0]; + if ( pv->variant == 3 ) { // Follow vector size using realloc + if ( new_size > 0 ) { + entries = (vector_page*) + realloc( pv->entries, new_size * sizeof( void* ) ); + if ( entries == 0 ) { + return -2; // OOM + } } - } - if ( pp != &pv->entries ) { - entries = pv->entries; - if ( pp ) { - pv->entries = *pp; - *pp = 0; // Detach subtree - } else { + pv->entries = entries; + } else { + vector_page **pp = &pv->entries; + int i = level.old; + while ( i-- > level.new ) { + if ( pp ) { + pp = (vector_page **)(*pp); + } + } + if ( pp != &pv->entries ) { + entries = pv->entries; + if ( pp ) { + pv->entries = *pp; + *pp = 0; // Detach subtree + } else { + pv->entries = 0; + } + vector_reclaim( pv, entries, level.old - 1 ); + } + if ( new_size == 0 && pv->entries ) { + free( pv->entries ); pv->entries = 0; } - vector_reclaim( entries, level.old ); - } - if ( new_size == 0 && pv->entries ) { - free( pv->entries ); - pv->entries = 0; } } else { // vector is growing. Maybe insert levels. - while ( level.old < level.new ) { - vector_page *p = (vector_page *) - calloc( 1, sizeof( vector_page ) ); - if ( p == 0 ) { + if ( pv->variant == 3 ) { // Follow vector size using realloc + entries = (vector_page *)realloc( + pv->entries, new_size * sizeof( void* ) ); + if ( entries == 0 ) { return -2; // OOM } - (*p)[0] = pv->entries; - pv->entries = p; - pv->size += level_delta[ level.old++ ]; - // Note that the last level addition might make the size - // larger than requested, which gets corrected below. + pv->entries = entries; + memset( &(*entries)[ pv->size ], 0, + ( new_size - pv->size ) * sizeof( void* ) ); + } else { + for ( ; level.old < level.new; level.old++ ) { + vector_page *p = (vector_page *) + calloc( VECTOR_SLOTS( pv ), sizeof( void* ) ); + if ( p == 0 ) { + return -2; // OOM + } + (*p)[0] = pv->entries; + pv->entries = p; + // Should maybe change the size to match the level? + // otherwise recovery from OOM is impossible + } } } pv->size = new_size; @@ -239,62 +460,25 @@ int vector_resize( // Return pointer to the indexed page slot at the requested level, and // adding intermediate index pages if so requested. Returns 0 if // addition fails (OOM), or if not requested and page is missing. -static void **vector_access( - vector *pv,vector_index index,int level,int add) -{ +void **vector_access(vector *pv,vector_index index,int level,int add) { if ( index >= pv->size ) { return 0; } void **page = (void**) &pv->entries; - int i = vector_levels( pv->size ); + int i = vector_levels( pv, pv->size ); while ( i-- > level ) { if ( add && (*page) == 0 ) { - (*page) = calloc( VECTOR_SLOTS, sizeof( void* ) ); + (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) ); } page = (*page); if ( page == 0 ) { return 0; } - page += VECTOR_INDEX_PART( &index, i ); + page += VECTOR_INDEX_PART( pv, &index, i ); } return page; } -// 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; - } - 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( index, lv ) != 0 ); - 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->size ) - 1 ); - if ( slot == 0 ) { - *index = pv->size; - } - return slot; -} - // Map index into a value slot void **vector_entry(vector *pv,vector_index index) { return vector_access( pv, index, 0, 1 ); @@ -302,7 +486,6 @@ void **vector_entry(vector *pv,vector_index index) { inline void vector_set(vector *pv,vector_index index,void *value) { void **p = vector_entry( pv, index ); - //assert( p != 0 ); *p = value; } @@ -424,13 +607,11 @@ void vector_iterate(vector *pv, { vector_index index = start; while ( index < pv->size ) { - void **slot = vector_next_used( pv, &index ); - if ( slot == 0 ) { - break; - } - int i = index & VECTOR_LEVEL_MASK ; - for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) { - if ( itemfn( index, *slot, data ) ) { + int end = VECTOR_SLOTS( pv ); + int i = index & ( end - 1 ); + for ( ; i < end && index < pv->size; i++, index++ ) { + void **slot = vector_access( pv, index, 0, 0 ); + if ( itemfn( index, slot? *slot: 0, data ) ) { return; } } @@ -462,3 +643,31 @@ void *vector_bsearch(vector *pv,vector_index *index,const void *key, } return 0; } + +// Iterator callback. +static int checkunused(vector_index index,void *item,void *data) { + vector_index *last = (vector_index*) data; + if ( item == 0 ) { + (*last) = index; + return 1; + } + if ( *last > index ) { + // Only on the first iteration, with *last = vector_sie + if ( index == 0 ) { + (*last) = 1; + return 0; + } + *last = 0; + } else if ( index == (*last) ) { + (*last)++; + return 0; + } + return 1; +} + +// Scan forward for the next unused vector slot +vector_index vector_next_unused(vector *pv,vector_index index) { + vector_index unused = vector_size( pv ); + vector_iterate( pv, index, checkunused, &unused ); + return unused; +}