From b4647b184df6ce07762053d48b4ee650a73068af Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Mon, 20 Jun 2022 22:39:49 +1000 Subject: [PATCH] Using 64-bit index. Added more primitives. --- pvector/pvector.c | 146 +++++++++++++++++++++++++++++++++++++++++----- pvector/pvector.h | 52 ++++++++++++----- 2 files changed, 168 insertions(+), 30 deletions(-) diff --git a/pvector/pvector.c b/pvector/pvector.c index 5dbb7d9..d744556 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,int 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 ); +} diff --git a/pvector/pvector.h b/pvector/pvector.h index bc42bec..b41b151 100644 --- a/pvector/pvector.h +++ b/pvector/pvector.h @@ -23,8 +23,8 @@ typedef void* pvector_page[256]; * implementation assumes LE integer layout. */ typedef union { - unsigned int whole; - unsigned char level[4]; + unsigned long whole; // 64-bit unsigned integer + unsigned char level[8]; } pvector_index; /*! @@ -38,7 +38,7 @@ typedef union { * to 256^N content entries. */ typedef struct _pvector { - unsigned int size; //!< Limit for the logical entries[] + unsigned long size; //!< Limit for the logical entries[] pvector_page *entries; //!< Pointer to entries indexing } pvector; @@ -51,11 +51,25 @@ typedef struct _pvector { #define PV_PART(p,i) (((unsigned char*)&i)[p]) /*! - * Function: int pvector_resize( pvector *pv,unsigned int new_size, - * int (*reclaim)(pvector *,int,void*) ) + * Find the next used slot at given index or later. With a reclaim + * function, it will be invoked for verifying that the item is + * actually in use, in which case it returns 1. Otherwise it should + * reclaim any memory for the item and return 0; + */ +void **pvector_next_used( + pvector *pv,unsigned long *index, + int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data), + void *data ); + +/*! + * Function: int pvector_resize( + * pvector *pv,unsigned long new_size, + * int (*reclaim)(pvector *,unsigned long,void *item,void *data), + * void *data ) * \param pv * \param new_size * \param reclaim + * \param data * * Tries to resize the given pvector to a new size. This may result in * the introduction or removal of indexing pages, so that the leveling @@ -69,18 +83,19 @@ typedef struct _pvector { * reclaim function is invoked successively for these. The reclaim * function must, in addition to memory-managing the entry, return 0 * upon success and non-zero to veto the attempted pvector size - * change. + * change. The data argument is passed on to the reclaim function. * * The pvector_resize function returns 0 on success, with the size * duly changed. Otherwise the function retains the current size and * returns -index-1 for the index of the veto-ed entry. */ 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 ); /*! - * Function: void **pvector_entry(pvector *pv,unsigned int index) + * Function: void **pvector_entry(pvector *pv,unsigned long index) * \param pv - the pvector record * \param index - the slot index * @@ -91,19 +106,28 @@ int pvector_resize( * that slot pointers are only valid while the pvector size is * unchanged. */ -extern void **pvector_entry(pvector *pv,unsigned int index); +extern void **pvector_entry(pvector *pv,unsigned long index); /*! - * Function: unsigned int pvector_size(pvector *pv) + * Function: unsigned long pvector_size(pvector *pv) * \param pv - the pvector record * \returns the size of the pvector. */ -inline unsigned int pvector_size(pvector *pv) { +inline unsigned long pvector_size(pvector *pv) { return pv->size; } -void pvector_set(pvector *pv,unsigned int index,void *value); +void pvector_set(pvector *pv,unsigned long index,void *value); + +void *pvector_get(pvector *pv,unsigned long index); + +void pvector_append(pvector *pv,void *value); + +void pvector_copy(pvector *dst,unsigned long di, + pvector *src,unsigned long si,unsigned long n); + +void pvector_dump(pvector *pv,int (*itemdump)(unsigned long ,void *)); -void *pvector_get(pvector *pv,unsigned int index); +void pvector_qsort(pvector *pv,int (*compar)(void *,void *)); #endif -- 2.39.2