-#include <assert.h>
+#include <string.h>
+#include <math.h>
#include <stdlib.h>
#include "vector.h"
*/
/** ============================================================ **/
-#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;
}
- return VECTOR_PART_BYTE(index,part).msb;
+ 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 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);
}
- return ++VECTOR_PART_BYTE(index,part).msb;
+ 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 & 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;
}
-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;
+ }
+ 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 VECTOR_PART_BYTE(index,part).msb--;
+ 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 last 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) {
+ (*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
/** ============================================================ **/
/**
* pointer to the used slot, if any, and 0 otherwise.
*/
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 ) ];
+ vector *pv,
+ vector_page *page,
+ vector_index *index,
+ int level,
+ vector_index end )
+{
+ void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
for( ; *index < end; 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 );
+ void **x = vector_level_next_used( pv, *p, index, level - 1, end );
if ( x ) {
return x; // Used slot was found; return it.
}
- // The page *p is all empty, so can/should be reclaimed.
- if ( whole ) {
- free( *p );
- *p = 0;
+ // If the page *p is all empty, so can/should be reclaimed.
+ } else {
+ if ( level > 0 ) {
+ VECTOR_INDEX_FIRST( pv, index, level );
}
}
- 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;
}
-
-// 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;
- do {
- N++;
- S /= VECTOR_SLOTS;
- } while ( S );
- return N;
-}
-
// 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.
*index = pv->size;
return 0;
}
- int levels = vector_levels( pv->size );
+ int levels = vector_levels( pv, pv->size );
for ( ; *index < pv->size; (*index)++ ) {
void **slot = vector_level_next_used(
- pv->entries, index, levels - 1, pv->size ) ;
+ pv, pv->entries, index, levels - 1, pv->size ) ;
if ( slot == 0 ) {
*index = pv->size; // reached the end of the vector
} else if ( *slot == 0 ) {
return 0;
}
-// Reclaim tree of unused pages
-static void vector_reclaim(vector_page *page,unsigned int level) {
+#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.
+ * 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.
+ */
+static void **vector_level_prev_used(
+ vector *pv,
+ vector_page *page,
+ vector_index *index,
+ int level )
+{
+ void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
+ 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 );
+ if ( x ) {
+ return x; // Used slot was found; return it.
+ }
+ // If the page *p is all empty, so can/should be reclaimed.
+ } 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_prev_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 );
+ do {
+ void **slot = vector_level_prev_used(
+ pv, pv->entries, index, levels - 1 ) ;
+ if ( slot == 0 ) {
+ break; // reached the end of the vector
+ }
+ if ( *slot ) {
+ 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;
+ }
+ 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 );
+ 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;
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 );
}
}
}
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;
// 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;
// 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 );
inline void vector_set(vector *pv,vector_index index,void *value) {
void **p = vector_entry( pv, index );
- //assert( p != 0 );
*p = value;
}
if ( slot == 0 ) {
break;
}
- int i = index & VECTOR_LEVEL_MASK ;
- for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) {
+ int end = VECTOR_SLOTS( pv );
+ int i = index & ( end - 1 );
+ for ( ; i < end && index < pv->size; i++, index++, slot++ ) {
if ( itemfn( index, *slot, data ) ) {
return;
}
}
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;
+}
projects / rrq / rrqmisc.git / blobdiff