X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fvector.c;h=5b3848842b30ec1058b4c39fb7cd38901de6836c;hb=a0be49ff8fda77c328424c09d6d0ad4a9f7e8f66;hp=feaed9f1792ae571d92083bd4a7c642d2f9f370a;hpb=015671d15f553787f4462906f8ddf8d63a0c710a;p=rrq%2Frrqmisc.git diff --git a/vector/vector.c b/vector/vector.c index feaed9f..5b38488 100644 --- a/vector/vector.c +++ b/vector/vector.c @@ -1,3 +1,4 @@ +#include #include #include "vector.h" @@ -7,6 +8,7 @@ * void*, and an index is "unsigned long" (64 bits). */ +/** ============================================================ **/ #if VECTOR_LEVEL_BITS == 4 typedef union { vector_index as_whole; @@ -32,7 +34,32 @@ static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { } return ++VECTOR_PART_BYTE(index,part).msb; } + +static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { + if ( part & 1 ) { + return VECTOR_PART_BYTE(index,part).lsb--; + } + return VECTOR_PART_BYTE(index,part).msb--; +} + +/** ============================================================ **/ +#elif VECTOR_LEVEL_BITS == 8 + +#define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 ) + +typedef union { + vector_index as_whole; + unsigned char as_byte[8]; +} vector_indexing; + +#define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->as_byte[p]) + +#define VECTOR_INDEX_PART_INC(i,p) (++VECTOR_INDEX_PART(i,p)) + +#define VECTOR_INDEX_PART_DEC(i,p) (VECTOR_INDEX_PART(i,p)--) + #endif +/** ============================================================ **/ /** * Advances a vector index to the next used slot at or below the @@ -69,6 +96,7 @@ static void **vector_level_next_used( 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) { @@ -81,13 +109,10 @@ static unsigned int vector_levels(vector_index S) { } // Find the next used slot at given index or later. Returns pointer to -// the slot. -void **vector_next_used( - vector *pv,vector_index *index, - int (*reclaim)(vector *pv,vector_index index,void *item,void *data), - void *data ) -{ - if ( pv->entries == 0 ) { +// 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; } @@ -96,18 +121,11 @@ void **vector_next_used( void **slot = vector_level_next_used( pv->entries, index, levels - 1, pv->size ) ; if ( slot == 0 ) { - // reached the end of the vector - *index = pv->size; - break; - } - if ( *slot ) { - // Try reclaiming the slot, - if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) { - *slot = 0; - } else { - return slot; - } + *index = pv->size; // reached the end of the vector + } else if ( *slot == 0 ) { + continue; } + return slot; } return 0; } @@ -126,11 +144,11 @@ static void vector_reclaim(vector_page *page,unsigned int level) { } // Resize vector, using the reclaim function as needed, to handle any -// excess items or to veto the resize. Returns the index of the veto, if -// any, or <0 otherwise, with -1 indicating success and -2 indicating -// OOM while growing. +// excess items or to veto the resize. Returns the index of the veto, +// if any, or <0 otherwise, with -1 indicating success and -2 +// indicating OOM // -// Nothe that resizing may result in the introduction/removal of +// Note that resizing may result in the introduction/removal of // indexing levels and pages, so as to keep the leveling accurate for // the size. int vector_resize( @@ -166,8 +184,13 @@ int vector_resize( // A shrinking vector might be veto-ed if ( new_size < pv->size ) { vector_index index = new_size; - void **slot = vector_next_used( pv, &index, reclaim, data ); - if ( slot ) { + void **slot = vector_next_used( pv, &index ); + while ( slot ) { + if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) { + *slot = 0; + slot = vector_next_used( pv, &index ); + continue; + } return index; } // At this point we know that there are no slots used after @@ -213,11 +236,9 @@ int vector_resize( return -1; } -// Return a pointer to the indexed item the given page level, adding -// intermediate pages if requested. Returns 0 if addition fails (OOM), -// or if not requested and page is missing. -// Level 0 = pointer to the item entry itself. -// Level VECTORLEVELS( pv->size ) - 1 = +// 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) { @@ -239,6 +260,41 @@ static void **vector_access( 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 ); @@ -246,11 +302,21 @@ 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; +} + +// Set value at index but return the old value +void *vector_get_set(vector *pv,vector_index index,void *value) { + void **p = vector_entry( pv, index ); + void *old = *p; *p = value; + return old; } inline void *vector_get(vector *pv,vector_index index) { - return *(vector_entry( pv, index )); + void **p = vector_entry( pv, index ); + return *p; } int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) { @@ -281,10 +347,10 @@ void vector_copy(vector *dst,vector_index di, } void vector_dump(vector *pv, - int (*itemdump)(const vector_index,const void *)) { + void (*itemdump)(const vector_index,const void *)) { vector_index index = 0; for ( ; index < pv->size; index++ ) { - void **slot = vector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index ); if ( slot == 0 ) { break; } @@ -295,7 +361,7 @@ void vector_dump(vector *pv, //// Quicksort // Returns 1 for "in order", 0 for equal, and -1 for "wrong order" -typedef int (*comparfn)(const void *,const void *); + typedef int (*comparfn)(const void *,const void *); static void vector_qsort_part( vector *pv,comparfn compar, @@ -352,12 +418,13 @@ void vector_qsort(vector *pv,comparfn compar) { } void vector_iterate(vector *pv, - int (*itemfn)(vector_index,void*,void*), - void *data ) + vector_index start, + int (*itemfn)(vector_index,void*,void*), + void *data ) { - vector_index index = 0; + vector_index index = start; while ( index < pv->size ) { - void **slot = vector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index ); if ( slot == 0 ) { break; } @@ -369,3 +436,29 @@ void vector_iterate(vector *pv, } } } + +// 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)) { + vector_index lo = 0; + vector_index hi = pv->size; + if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) { + return 0; + } + hi++; + while ( lo < hi ) { + vector_index m = lo + ( hi - lo ) / 2; + void **slot = vector_next_used( pv, &m ); + int c = compare( key, *slot ); + if ( c == 0 ) { + *index = m; + return *slot; + } + if ( c < 0 ) { + hi = m; + } else { + lo = m + 1; + } + } + return 0; +}