+#include <assert.h>
#include <stdlib.h>
#include "vector.h"
* void*, and an index is "unsigned long" (64 bits).
*/
+/** ============================================================ **/
#if VECTOR_LEVEL_BITS == 4
typedef union {
vector_index as_whole;
}
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 )
#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
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) {
}
// 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;
}
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;
}
}
// 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(
// 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
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)
{
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;
+}
+
+// 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) {
}
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;
}
//// 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,
}
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;
}
}
}
}
+
+// 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;
+}
projects / rrq / rrqmisc.git / blobdiff