X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=pvector%2Fpvector.c;h=08389542d4d545ad62f1f72b8e51c11ca26dfc23;hb=98b44ec4b554d4acee87cebef452c7eb12cf5add;hp=d7445561a9eb5aa5dce8ec900add566c09661b68;hpb=b4647b184df6ce07762053d48b4ee650a73068af;p=rrq%2Frrqmisc.git

diff --git a/pvector/pvector.c b/pvector/pvector.c
index d744556..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 long *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,6 +42,13 @@ static void **pvector_level_next_used(
     return 0;
 }
 
+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(
@@ -53,7 +60,7 @@ void **pvector_next_used(
 	*index = pv->size;
 	return 0;
     }
-    int levels = PV_LEVELS( pv->size );
+    int levels = pvector_levels( pv->size );
     for ( ; *index < pv->size; (*index)++ ) {
 	void **slot = pvector_level_next_used(
 	    pv->entries, index, levels - 1, pv->size ) ;
@@ -70,17 +77,18 @@ void **pvector_next_used(
 		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 );
@@ -117,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;
@@ -143,7 +151,7 @@ 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 );
@@ -180,7 +188,7 @@ static void **pvector_access(
 	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* ) );
@@ -235,7 +243,8 @@ void pvector_copy(pvector *dst,unsigned long di,
     }
 }
 
-void pvector_dump(pvector *pv,int (*itemdump)(unsigned long,void *)) {
+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 );
@@ -249,7 +258,7 @@ void pvector_dump(pvector *pv,int (*itemdump)(unsigned long,void *)) {
 //// Quicksort
 
 // Returns 1 for "in order", 0 for equal, and -1 for "wrong order"
-typedef int (*comparfn)(void *,void *);
+typedef int (*comparfn)(const void *,const void *);
 
 static void pvector_qsort_part(
     pvector *pv,comparfn compar,
@@ -301,6 +310,25 @@ static void pvector_qsort_part(
     pvector_qsort_part( pv, compar, m+1, high );
 }
 
-void pvector_qsort(pvector *pv,int (*compar)(void *,void *)) {
+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;
+	    }
+	}
+    }
+}