X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=pvector%2Fpvector.c;h=08389542d4d545ad62f1f72b8e51c11ca26dfc23;hb=b901ebd3cd786e8cec0f10c461f8bcc8e4219081;hp=5dbb7d9e4f2e47a104e62ae80bd87b3a29c102a5;hpb=4a9c4d9ada3ef81415854b0ea5de844d5298eb43;p=rrq%2Frrqmisc.git

diff --git a/pvector/pvector.c b/pvector/pvector.c
index 5dbb7d9..0838954 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,32 +42,53 @@ 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*) )
+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 );
@@ -82,8 +103,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.
@@ -103,8 +125,8 @@ int pvector_resize(
 	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;
@@ -112,8 +134,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;
 	}
@@ -129,7 +151,11 @@ int pvector_resize(
 	    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.
@@ -156,13 +182,13 @@ 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;
     }
     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* ) );
@@ -177,16 +203,132 @@ 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)(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;
+	    }
+	}
+    }
+}