From 0396bd0ae37004d834fec20c3371365a8c1777af Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Fri, 24 Jun 2022 11:31:32 +1000 Subject: [PATCH] slightly generalized page-indexed vector --- pvector/qvector.c | 338 ++++++++++++++++++++++++++++++++++++++++++++++ pvector/qvector.h | 170 +++++++++++++++++++++++ 2 files changed, 508 insertions(+) create mode 100644 pvector/qvector.c create mode 100644 pvector/qvector.h diff --git a/pvector/qvector.c b/pvector/qvector.c new file mode 100644 index 0000000..1fc34ed --- /dev/null +++ b/pvector/qvector.c @@ -0,0 +1,338 @@ +#include +#include "qvector.h" + +/** + * Representing a vector of void* accessible via an indexing structure + * as levels of same-size pages. A "qvector_page" is a contiguous + * array of 16 void*. + */ + +/** + * Advances a qvector index to the next used slot at or below the + * given level, starting from the indexed entry (inclusive) and up. + * The function will free any empty pages it discovers, and then + * update the index slots accordingly. The given index is advanced + * cyclically to match the found slot. The function returns a slot + * pointer to the used slot, if any, and 0 otherwise. + */ +static void **qvector_level_next_used( + qvector_page *page,qvector_index *index,int level,qvector_index end) { + void **p = (void**)&(*page)[ PV_PART( index, level ) ]; + for( ; *index < end; p++ ) { + if ( *p ) { + if ( level == 0 ) { + return p; // This is a used entry + } + // *p is an index that needs to be inspected recursively + int whole = PV_PART( index, level - 1 ) == 0; + void **x = qvector_level_next_used( *p, index, level - 1, end ); + if ( x ) { + return x; // Used slot was found; return it. + } + // The page *p is all empty, so can/should be reclaimed. + if ( whole ) { + free( *p ); + *p = 0; + } + } + if ( ++PV_PART( index, level ) == 0 ) { + break; // cycling this level => nothing found + } + } + return 0; +} + +// The least number of levels to span index S (typically the size of a +// qvector) +static unsigned int qvector_levels(qvector_index S) { + unsigned int N = 0; + do { + N++; + S /= QV_SLOTS; + } while ( S ); + return N; +} + +// Find the next used slot at given index or later. Returns pointer to +// the slot. +void **qvector_next_used( + qvector *pv,qvector_index *index, + int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), + void *data ) +{ + if ( pv->entries == 0 ) { + *index = pv->size; + return 0; + } + int levels = qvector_levels( pv->size ); + for ( ; *index < pv->size; (*index)++ ) { + void **slot = qvector_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; + } + } + } + return 0; +} + +// Reclaim tree of unused pages +static void qvector_reclaim(qvector_page *page,unsigned int level) { + int i = 0; + if ( level > 0 ) { + for ( ; i < QV_SLOTS; i++ ) { + if ( (*page)[i] ) { + qvector_reclaim( (qvector_page *) (*page)[i], level - 1 ); + } + } + } + free( page ); +} + +// 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. +// +// Nothe that resizing may result in the introduction/removal of +// indexing levels and pages, so as to keep the leveling accurate for +// the size. +int qvector_resize( + qvector *pv,qvector_index new_size, + int (*reclaim)(qvector *pv,qvector_index 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. The first level (i.e., level 0) adds + // 15 slots to the one slot of no index page. Level 1 adds 15*16 + // slots, level 2 adds 15*(16^2), and generically level i adds + // 15*(16^i) slots. + static int level_delta[ QV_INDEX_FIELDS ]; + if ( level_delta[ 0 ] == 0 ) { + int d = 1; + int i; + for ( i = 0; i < QV_INDEX_FIELDS; i++ ) { + level_delta[ i ] = 15 * d; + d = 16 * d; + } + } + struct { + int old; + int new; + } level = { + qvector_levels( pv->size ), + qvector_levels( new_size ) + }; + if ( pv->entries == 0 ) { + pv->size = new_size; + return 0; + } + // A shrinking qvector might be veto-ed + if ( new_size < pv->size ) { + qvector_index index = new_size; + void **slot = qvector_next_used( pv, &index, reclaim, data ); + if ( slot ) { + return index; + } + // At this point we know that there are no slots used after + // the new_size size, so now it's time to remove and reclaim + // any superflouous top level pages. + qvector_page *entries; + qvector_page **pp = &pv->entries; + while ( level.old-- > level.new ) { + pp = (qvector_page **)(*pp)[0]; + } + if ( pp != &pv->entries ) { + entries = pv->entries; + pv->entries = *pp; + *pp = 0; + qvector_reclaim( entries, level.old ); + } + if ( new_size == 0 ) { + free( pv->entries ); + pv->entries = 0; + } + } else { + // qvector is growing. Maybe insert levels. + while ( level.old < level.new ) { + qvector_page *p = (qvector_page *) + calloc( 1, sizeof( qvector_page ) ); + if ( p == 0 ) { + return -2; // OOM + } + (*p)[0] = pv->entries; + pv->entries = p; + pv->size += level_delta[ level.old++ ]; + // Note that the last level addition might make the size + // larger than requested, which gets corrected below. + } + } + pv->size = new_size; + 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 QVECTORLEVELS( pv->size ) - 1 = +static void **qvector_access( + qvector *pv,qvector_index index,int level,int add) +{ + if ( index >= pv->size ) { + return 0; + } + void **page = (void**) &pv->entries; + int i = qvector_levels( pv->size ); + while ( i-- > level ) { + if ( add && (*page) == 0 ) { + (*page) = calloc( QV_SLOTS, sizeof( void* ) ); + } + page = (*page); + if ( page == 0 ) { + return 0; + } + page += PV_PART( &index, i ); + } + return page; +} + +// Map index into a value slot +void **qvector_entry(qvector *pv,qvector_index index) { + return qvector_access( pv, index, 0, 1 ); +} + +inline void qvector_set(qvector *pv,qvector_index index,void *value) { + void **p = qvector_entry( pv, index ); + *p = value; +} + +inline void *qvector_get(qvector *pv,qvector_index index) { + return *(qvector_entry( pv, index )); +} + +int qvector_reclaim_any(qvector *pv,qvector_index ix,void *item,void *data) { + free( item ); + return 0; +} + +void qvector_append(qvector *pv,void *value) { + qvector_resize( pv, pv->size + 1, 0, 0 ); + qvector_set( pv, pv->size - 1, value ); +} + +// copy block of n items from src[si] to dst[di] +// no efficiency hacks +void qvector_copy(qvector *dst,qvector_index di, + qvector *src,qvector_index si,qvector_index n) { + if ( dst != src || di < si ) { + while ( n-- != 0 ) { + qvector_set( dst, di++, qvector_get( src, si++ ) ); + } + } else if ( di > si ){ + di += n - 1; + si += n - 1; + while ( n-- != 0 ) { + qvector_set( dst, di--, qvector_get( src, si-- ) ); + } + } +} + +void qvector_dump(qvector *pv, + int (*itemdump)(const qvector_index,const void *)) { + qvector_index index = 0; + for ( ; index < pv->size; index++ ) { + void **slot = qvector_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 qvector_qsort_part( + qvector *pv,comparfn compar, + qvector_index low,qvector_index high) +{ + if ( low >= high ) { + return; + } + qvector_index lo = low; + qvector_index m = high - 1; + + if ( lo >= m ) { + return; + } + + qvector_index hi = m - 1; + void **mp = qvector_entry( pv, m ); + void **lop, **hip; + for ( ;; ) { + // Find index of first item "above" mp scanning from lo and up + for ( ; lo < m; lo++ ) { + lop = qvector_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 = qvector_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; + } + qvector_qsort_part( pv, compar, low, m ); + qvector_qsort_part( pv, compar, m+1, high ); +} + +void qvector_qsort(qvector *pv,comparfn compar) { + qvector_qsort_part( pv, compar, 0, pv->size ); +} + +void qvector_iterate(qvector *pv, + int (*itemfn)(qvector_index,void*,void*), + void *data ) +{ + qvector_index index = 0; + while ( index < pv->size ) { + void **slot = qvector_next_used( pv, &index, 0, 0 ); + if ( slot == 0 ) { + break; + } + int i = index & 0xff; + for ( ; i < QV_SLOTS && index < pv->size; i++, index++, slot++ ) { + if ( itemfn( index, *slot, data ) ) { + return; + } + } + } +} diff --git a/pvector/qvector.h b/pvector/qvector.h new file mode 100644 index 0000000..2ceddbd --- /dev/null +++ b/pvector/qvector.h @@ -0,0 +1,170 @@ +#ifndef qvector_H +#define qvector_H + +/** + * A qvector is a dynamic pointer array implemented as an access tree + * of index pages. The indexing is done using "unsigned long" indexes. + */ + +/*! + * Type: qvector_index + * This is the general indexing used for qvector access. + */ +typedef unsigned long qvector_index; + +/*! + * Macro: QV_INDEX_BITS + * This defines the number of bits of a qvector index + */ +#define QV_INDEX_BITS sizeof( qvector_index ) + +/*! + * Macro: QV_LEVEL_BITS + * This defines the number of bits in the indexing bit field. + */ +#define QV_LEVEL_BITS 4 + +/*! + * Macro: QV_INDEX_FIELDS + * This defines the number of bit fields in an qvector index + */ +#define QV_INDEX_FIELDS ( ( QV_INDEX_BITS - 1 ) / QV_LEVEL_BITS + 1 ) + +/*! + * Macro: QV_SLOTS + * This defines the number of slots spanned by an index level + */ +#define QV_SLOTS ( 1 << QV_LEVEL_BITS ) + +/*! + * Type: qvector_page + * + * A qvector_page is an array of 16 void* items. + */ +typedef void* qvector_page[ QV_SLOTS ]; + +/*! + * Type: qvector_field + * This is QV_LEVEL_BITS size bit field + */ +typedef struct { int bits:QV_LEVEL_BITS; } qvector_field; + +/*! + * Type: qvector_indexing + * + * A qvector index is ether viewed in whole as an QV_INDEX_BITS wide + * unsigned, or in levels as a packed array of qvector_field index + * parts. This implementation assumes LE integer layout. + */ +typedef union { + qvector_index whole; // as a whole + qvector_field level[ QV_INDEX_FIELDS ]; // qua bits fields +} qvector_indexing; + +/*! + * Type: qvector + * + * A qvector is a compound of a size and a qvector_page pointer, which + * when non-null points out the top-most page of the qvector. The + * number of levels is derived from its size with level 0 being the + * leaf level of actual content. E.g., a qvector larger than 16 + * items, has at least two levels, and generally N levels may span up + * to 16^N content entries. + */ +typedef struct _qvector { + qvector_index size; //!< Limit for the logical entries[] + qvector_page *entries; //!< Pointer to entries indexing +} qvector; + +// Number of slots for page S +#define PV_LEVEL_SIZE(S) ((int)(exp( 16, (S) ))) + +// The indexing part for level part p in index i +#define PV_PART(i,p) (((qvector_indexing*)(i))->level[ p ].bits) + +/*! + * 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 **qvector_next_used( + qvector *pv,qvector_index *index, + int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), + void *data ); + +/*! + * Function: int qvector_resize( + * qvector *pv,qvector_index new_size, + * int (*reclaim)(qvector *,qvector_index,void *item,void *data), + * void *data ) + * \param pv + * \param new_size + * \param reclaim + * \param data + * + * Tries to resize the given qvector to a new size. This may result in + * the introduction or removal of indexing pages, so that the leveling + * is consistent with the qvector size. Thus, if it grows into a new + * 16^N level, then one or more new upper level pages are inserted as + * needed. If it shrinks below the current level, then top-level pages + * are remove. + * + * Also, if the new size is smaller than currently, then the now + * excess tail of entries is scanned for any used slots and the given + * 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 qvector size + * change. The data argument is passed on to the reclaim function. + * + * The qvector_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 qvector_resize( + qvector *pv, qvector_index new_size, + int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), + void *data ); + +/*! + * Function: void **qvector_entry(qvector *pv,qvector_index index) + * \param pv - the qvector record + * \param index - the slot index + * + * [pgix,epix] = modulo( index, pv->page ); + * + * \returns a direct pointer to the slot of the given index in the + * array, or 0 if the index is beyond the array limits (0-limit). Note + * that slot pointers are only valid while the qvector size is + * unchanged. + */ +extern void **qvector_entry(qvector *pv,qvector_index index); + +/*! + * Function: qvector_index qvector_size(qvector *pv) + * \param pv - the qvector record + * \returns the size of the qvector. + */ +inline qvector_index qvector_size(qvector *pv) { + return pv->size; +} + +void qvector_set(qvector *pv,qvector_index index,void *value); + +void *qvector_get(qvector *pv,qvector_index index); + +void qvector_append(qvector *pv,void *value); + +void qvector_copy(qvector *dst,qvector_index di, + qvector *src,qvector_index si,qvector_index n); + +void qvector_dump(qvector *pv, + int (*itemdump)(const qvector_index ,const void *)); + +void qvector_qsort(qvector *pv,int (*compar)(const void *,const void *)); + +void qvector_iterate(qvector *pv, + int (*itemfn)(qvector_index,void*,void*), + void*); + +#endif -- 2.39.2