X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=pvector%2Fpvector.c;h=3179376bc553a22a685eb202fb300bfcb3f52c83;hb=49912b2bb9fca7e0608e52ead72efdb14923b843;hp=5dbb7d9e4f2e47a104e62ae80bd87b3a29c102a5;hpb=4a9c4d9ada3ef81415854b0ea5de844d5298eb43;p=rrq%2Frrqmisc.git diff --git a/pvector/pvector.c b/pvector/pvector.c index 5dbb7d9..3179376 100644 --- a/pvector/pvector.c +++ b/pvector/pvector.c @@ -16,7 +16,7 @@ * 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 ) { @@ -42,19 +42,32 @@ static void **pvector_level_next_used( 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*) ) +// 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 ) { + if ( pv->entries == 0 ) { + *index = pv->size; + return 0; + } int levels = PV_LEVELS( pv->size ); - while ( *index < 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)++; @@ -82,8 +95,9 @@ static void pvector_reclaim(pvector_page *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. @@ -112,8 +126,8 @@ int pvector_resize( } // 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; } @@ -131,6 +145,10 @@ int pvector_resize( *pp = 0; pvector_reclaim( entries ); } + if ( new_size == 0 ) { + free( pv->entries ); + pv->entries = 0; + } } else { // pvector is growing. Maybe insert levels. while ( level.old < level.new ) { @@ -156,7 +174,7 @@ int pvector_resize( // 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; @@ -177,16 +195,112 @@ static void **pvector_access( } // 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)(unsigned long,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)(void *,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,int (*compar)(void *,void *)) { + pvector_qsort_part( pv, compar, 0, pv->size ); +}