cleanup

[rrq/rrqmisc.git] / pvector / pvector.c

diff --git a/pvector/pvector.c b/pvector/pvector.c
index d7445561a9eb5aa5dce8ec900add566c09661b68..08389542d4d545ad62f1f72b8e51c11ca26dfc23 100644 (file)
--- 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;
+           }
+       }
+    }
+}