* pointer to the used slot, if any, and 0 otherwise.
*/
static void **pvector_level_next_used(
- pvector_page *page,unsigned int *index,int level,int end) {
+ pvector_page *page,unsigned long *index,int level,unsigned long end) {
void **p = (void**)&(*page)[ ((pvector_index*)index)->level[ level ] ];
for( ; *index < end; p++ ) {
if ( *p ) {
return 0;
}
-// Find the next used slot at given index or later
-void **pvector_next_used(pvector *pv,unsigned int *index,
- int (*reclaim)(pvector *,int,void*) )
+static unsigned int pvector_levels(unsigned long S) {
+ if ( S <= 1 ) {
+ return 1;
+ }
+ return (unsigned int) ( 39 - __builtin_clz( S - 1 ) ) / 8;
+}
+
+// Find the next used slot at given index or later. Returns pointer to
+// the slot.
+void **pvector_next_used(
+ pvector *pv,unsigned long *index,
+ int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
+ void *data )
{
- int levels = PV_LEVELS( pv->size );
- while ( *index < pv->size ) {
+ if ( pv->entries == 0 ) {
+ *index = pv->size;
+ return 0;
+ }
+ int levels = pvector_levels( pv->size );
+ for ( ; *index < pv->size; (*index)++ ) {
void **slot = pvector_level_next_used(
pv->entries, index, levels - 1, pv->size ) ;
- if ( slot && *slot ) {
- if ( reclaim && reclaim( pv, *index, *slot ) == 0 ) {
+ 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;
+ return slot;
}
}
- (*index)++;
}
return 0;
}
// Reclaim tree of unused pages
-static void pvector_reclaim(pvector_page *page) {
+static void pvector_reclaim(pvector_page *page,unsigned int level) {
int i = 0;
- for ( ; i < 256; i++ ) {
- if ( (*page)[i] ) {
- pvector_reclaim( (pvector_page *) (*page)[i] );
+ if ( level > 0 ) {
+ for ( ; i < 256; i++ ) {
+ if ( (*page)[i] ) {
+ pvector_reclaim( (pvector_page *) (*page)[i], level - 1 );
+ }
}
}
free( page );
// indexing levels and pages, so as to keep the leveling accurate for
// the size.
int pvector_resize(
- pvector *pv,unsigned int new_size,
- int (*reclaim)(pvector *,int,void*) )
+ pvector *pv,unsigned long new_size,
+ int (*reclaim)(pvector *pv,unsigned long 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.
int old;
int new;
} level = {
- PV_LEVELS( pv->size ),
- PV_LEVELS( new_size )
+ pvector_levels( pv->size ),
+ pvector_levels( new_size )
};
if ( pv->entries == 0 ) {
pv->size = new_size;
}
// A shrinking pvector might be veto-ed
if ( new_size < pv->size ) {
- unsigned int index = new_size;
- void **slot = pvector_next_used( pv, &index, reclaim );
+ unsigned long index = new_size;
+ void **slot = pvector_next_used( pv, &index, reclaim, data );
if ( slot ) {
return index;
}
entries = pv->entries;
pv->entries = *pp;
*pp = 0;
- pvector_reclaim( entries );
+ pvector_reclaim( entries, level.old );
+ }
+ if ( new_size == 0 ) {
+ free( pv->entries );
+ pv->entries = 0;
}
} else {
// pvector is growing. Maybe insert levels.
// Level 0 = pointer to the item entry itself.
// Level PVECTORLEVELS( pv->size ) - 1 =
static void **pvector_access(
- pvector *pv,unsigned int index,int level,int add)
+ pvector *pv,unsigned long index,int level,int add)
{
if ( index >= pv->size ) {
return 0;
}
void **page = (void**) &pv->entries;
- int i = PV_LEVELS( pv->size );
+ int i = pvector_levels( pv->size );
while ( i-- > level ) {
if ( add && (*page) == 0 ) {
(*page) = calloc( 256, sizeof( void* ) );
}
// Map index into a value slot
-void **pvector_entry(pvector *pv,unsigned int index) {
+void **pvector_entry(pvector *pv,unsigned long index) {
return pvector_access( pv, index, 0, 1 );
}
-inline void pvector_set(pvector *pv,unsigned int index,void *value) {
+inline void pvector_set(pvector *pv,unsigned long index,void *value) {
void **p = pvector_entry( pv, index );
*p = value;
}
-inline void *pvector_get(pvector *pv,unsigned int index) {
+inline void *pvector_get(pvector *pv,unsigned long index) {
return *(pvector_entry( pv, index ));
}
+int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) {
+ free( item );
+ return 0;
+}
+
+void pvector_append(pvector *pv,void *value) {
+ pvector_resize( pv, pv->size + 1, 0, 0 );
+ pvector_set( pv, pv->size - 1, value );
+}
+
+// copy block of n items from src[si] to dst[di]
+// no efficiency hacks
+void pvector_copy(pvector *dst,unsigned long di,
+ pvector *src,unsigned long si,unsigned long n) {
+ if ( dst != src || di < si ) {
+ while ( n-- != 0 ) {
+ pvector_set( dst, di++, pvector_get( src, si++ ) );
+ }
+ } else if ( di > si ){
+ di += n - 1;
+ si += n - 1;
+ while ( n-- != 0 ) {
+ pvector_set( dst, di--, pvector_get( src, si-- ) );
+ }
+ }
+}
+
+void pvector_dump(pvector *pv,
+ int (*itemdump)(const unsigned long,const void *)) {
+ unsigned long index = 0;
+ for ( ; index < pv->size; index++ ) {
+ void **slot = pvector_next_used( pv, &index, 0, 0 );
+ if ( slot == 0 ) {
+ break;
+ }
+ itemdump( index, *slot );
+ }
+}
+
+//// Quicksort
+
+// Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
+typedef int (*comparfn)(const void *,const void *);
+
+static void pvector_qsort_part(
+ pvector *pv,comparfn compar,
+ unsigned long low,unsigned long high)
+{
+ if ( low >= high ) {
+ return;
+ }
+ unsigned long lo = low;
+ unsigned long m = high - 1;
+
+ if ( lo >= m ) {
+ return;
+ }
+
+ unsigned long hi = m - 1;
+ void **mp = pvector_entry( pv, m );
+ void **lop, **hip;
+ for ( ;; ) {
+ // Find index of first item "above" mp scanning from lo and up
+ for ( ; lo < m; lo++ ) {
+ lop = pvector_entry( pv, lo );
+ if ( compar( *lop, *mp ) < 0 ) {
+ break;
+ }
+ }
+ // if lo == m, then lop is wrong!!
+ // Find index of first item "below" mp scanning from hi and down
+ for ( ; hi > lo; hi-- ) {
+ hip = pvector_entry( pv, hi );
+ if ( compar( *mp, *hip ) < 0 ) {
+ break;
+ }
+ }
+ if ( lo >= hi ) {
+ if ( lo < m ) {
+ void *x = *lop;
+ *lop = *mp;
+ *mp = x;
+ m = lo;
+ }
+ break;
+ }
+ void *x = *lop;
+ *lop = *hip;
+ *hip = x;
+ }
+ pvector_qsort_part( pv, compar, low, m );
+ pvector_qsort_part( pv, compar, m+1, high );
+}
+
+void pvector_qsort(pvector *pv,comparfn compar) {
+ pvector_qsort_part( pv, compar, 0, pv->size );
+}
+
+void pvector_iterate(pvector *pv,
+ int (*itemfn)(unsigned long,void*,void*),
+ void *data )
+{
+ unsigned long index = 0;
+ while ( index < pv->size ) {
+ void **slot = pvector_next_used( pv, &index, 0, 0 );
+ if ( slot == 0 ) {
+ break;
+ }
+ int i = index & 0xff;
+ for ( ; i < 256 && index < pv->size; i++, index++, slot++ ) {
+ if ( itemfn( index, *slot, data ) ) {
+ return;
+ }
+ }
+ }
+}
projects / rrq / rrqmisc.git / blobdiff