X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fvector.c;h=16d5577f19a44e17977229aa16cb6882b1bb196e;hb=2bd18d410e42775bbdaab680447d1e2c43f5491c;hp=a9c6b63f87e787ec10c90247caf349a3dfee2b17;hpb=c1aae73b1fafd372c4f38a1a205e20a9f22a2fa0;p=rrq%2Frrqmisc.git

diff --git a/vector/vector.c b/vector/vector.c
index a9c6b63..16d5577 100644
--- a/vector/vector.c
+++ b/vector/vector.c
@@ -39,20 +39,20 @@ typedef struct {
 unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
     unsigned char *px = (unsigned char *) index;
     switch ( pv->variant ) {
-    case 0: {
+    case byte_index_levels: {
 	byte *pp = (byte*)(px + level);
 	return pp->a;
     }
-    case 1: {
-	nibble *pp = (nibble*)(px + ( level / 2 ));
+    case nibble_index_levels: {
+	nibble *pp = (nibble*)( px + ( level / 2 ) );
 	switch ( level & 1 ) {
 	case 0: return pp->a;
 	case 1: return pp->b;
 	}
 	break;
     }
-    case 2: {
-	bitpair *pp = (bitpair*)(px + ( level / 4 ));
+    case bitpair_index_levels: {
+	bitpair *pp = (bitpair*)( px + ( level / 4 ) );
 	switch ( level & 3 ) {
 	case 0: return pp->a;
 	case 1: return pp->b;
@@ -61,7 +61,7 @@ unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
 	}
 	break;
     }
-    case 3:
+    case single_index_level:
 	return (*index);
     }
     return 0;
@@ -76,11 +76,11 @@ static unsigned long VECTOR_INDEX_PART_INC(
 {
     unsigned char *px = (unsigned char *) index;
     switch ( pv->variant ) {
-    case 0: {
+    case byte_index_levels: {
 	byte *pp = (byte*)( px + level );
 	return ++(pp->a);
     }
-    case 1: {
+    case nibble_index_levels: {
 	nibble *pp = (nibble*)( px + ( level / 2 ) );
 	switch ( level & 1 ) {
 	case 0: return ++(pp->a);
@@ -88,9 +88,9 @@ static unsigned long VECTOR_INDEX_PART_INC(
 	}
 	break;
     }
-    case 2: {
+    case bitpair_index_levels: {
 	bitpair *pp = (bitpair*)( px + level / 4 );
-	switch ( level & 0xf ) {
+	switch ( level & 3 ) {
 	case 0: return ++(pp->a);
 	case 1: return ++(pp->b);
 	case 2: return ++(pp->c);
@@ -98,7 +98,7 @@ static unsigned long VECTOR_INDEX_PART_INC(
 	}
 	break;
     }
-    case 3:
+    case single_index_level:
 	return ++(*index);
     }
     return 0;
@@ -113,11 +113,11 @@ static unsigned long VECTOR_INDEX_PART_DEC(
 {
     unsigned char *px = (unsigned char *) index;
     switch ( pv->variant ) {
-    case 0: {
+    case byte_index_levels: {
 	byte *pp = (byte*)( px + level );
 	return (pp->a)--;
     }
-    case 1: {
+    case nibble_index_levels: {
 	nibble *pp = (nibble*)( px + ( level / 2 ) );
 	switch ( level & 1 ) {
 	case 0: return (pp->a)--;
@@ -125,7 +125,7 @@ static unsigned long VECTOR_INDEX_PART_DEC(
 	}
 	break;
     }
-    case 2: {
+    case bitpair_index_levels: {
 	bitpair *pp = (bitpair*)( px + level / 4 );
 	switch ( level & 0xf ) {
 	case 0: return (pp->a)--;
@@ -135,7 +135,7 @@ static unsigned long VECTOR_INDEX_PART_DEC(
 	}
 	break;
     }
-    case 3:
+    case single_index_level:
 	return (*index)--;
     }
     return 0;
@@ -143,23 +143,30 @@ static unsigned long VECTOR_INDEX_PART_DEC(
 
 #define ONES  (~((vector_index) 0))
 
-// Set index to last value for all index parts at level and lower.
+// Set index to first value for all index parts at level and lower.
 static void VECTOR_INDEX_FIRST(vector *pv,vector_index *index, int level) {
     (*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
 }
 
 // Set index to last value for all index parts at level and lower.
 static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int level) {
-    (*index) |= ONES >> ( 64 - VECTOR_BITS[ pv->variant ] * level );
+    static unsigned long ones[] = { 255, 15, 3 };
+    unsigned long x = ones[ pv->variant ];
+    while ( level-- ) {
+	(*index) |= x;
+	x <<= VECTOR_BITS[ pv->variant ];
+    }
+    // 255, 25, 3
+    //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
 }
 
 // Return number of slots for a vector variant.
 unsigned long VECTOR_SLOTS(vector *pv) {
     switch ( pv->variant ) {
-    case 0: return 256;
-    case 1: return 16;
-    case 2: return 4;
-    case 3: return pv->size;
+    case byte_index_levels: return 256;
+    case nibble_index_levels: return 16;
+    case bitpair_index_levels: return 4;
+    case single_index_level: return pv->size;
     }
     return 0;
 }
@@ -170,10 +177,10 @@ static unsigned int vector_levels(vector *pv,unsigned int size) {
 	return 1;
     }
     switch ( pv->variant ) {
-    case 0: return ((int)(log2( size - 1 ) / 8)) + 1;
-    case 1: return ((int)(log2( size - 1 ) / 4)) + 1;
-    case 2: return ((int)(log2( size - 1 ) / 2)) + 1;
-    case 3: return 1;
+    case byte_index_levels: return ((int)(log2( size - 1 ) / 8)) + 1;
+    case nibble_index_levels: return ((int)(log2( size - 1 ) / 4)) + 1;
+    case bitpair_index_levels: return ((int)(log2( size - 1 ) / 2)) + 1;
+    case single_index_level: return 1;
     }
     return 0;
 }
@@ -187,29 +194,41 @@ static unsigned int vector_levels(vector *pv,unsigned int size) {
  * 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.
+ * The last parameter is a flag that gets set when the scanning is
+ * partial (i.e. not the whole index page).
  */
 static void **vector_level_next_used(
     vector *pv,
     vector_page *page,
     vector_index *index,
     int level,
-    vector_index end )
+    int *partial )
 {
     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
-    for( ; *index < end; p++ ) {
+    if ( VECTOR_INDEX_PART( pv, index, level ) != 0 ) {
+	*partial = 1;
+    }
+    for( ; *index < pv->size; p++ ) {
 	if ( *p ) {
 	    if ( level == 0 ) {
 		return p; // This is a used entry
 	    }
 	    // *p is an index that needs to be inspected recursively
-	    void **x = vector_level_next_used( pv, *p, index, level - 1, end );
+	    int w = 0;
+	    void **x = vector_level_next_used( pv, *p, index, level - 1, &w );
 	    if ( x ) {
 		return x; // Used slot was found; return it.
 	    }
 	    // If the page *p is all empty, so can/should be reclaimed.
+	    if ( w == 0 ) {
+		free( *p );
+		*p = 0;
+	    } else {
+		*partial = 1;
+	    }
 	} else {
 	    if ( level > 0 ) {
-		VECTOR_INDEX_FIRST( pv, index, level );
+		VECTOR_INDEX_FIRST( pv, index, level - 1 );
 	    }
 	}
 	if ( VECTOR_INDEX_PART_INC( pv, index, level ) == 0 ) {
@@ -228,20 +247,25 @@ void **vector_next_used(vector *pv,vector_index *index) {
 	return 0;
     }
     int levels = vector_levels( pv, pv->size );
-    for ( ; *index < pv->size; (*index)++ ) {
+    int partial = 0;
+    do {
 	void **slot = vector_level_next_used(
-	    pv, pv->entries, index, levels - 1, pv->size ) ;
+	    pv, pv->entries, index, levels - 1, &partial ) ;
 	if ( slot == 0 ) {
-	    *index = pv->size; // reached the end of the vector
-	} else 	if ( *slot == 0 ) {
-	    continue;
+	    break; // reached the end of the vector
+	}
+	if ( *slot ) {
+	    return slot;
 	}
-	return slot;
+    } while ( ++(*index) < pv->size );
+    if ( partial == 0 ) {
+	free( pv->entries );
+	pv->entries = 0;
     }
+    *index = pv->size; // reached the end of the vector
     return 0;
 }
 
-#if 1
 /**
  * Advances a vector index to the prior used slot at or below the
  * given level, starting from the indexed entry (inclusive) and down.
@@ -249,25 +273,38 @@ void **vector_next_used(vector *pv,vector_index *index) {
  * 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.
+ * The last parameter is a flag that gets set when the scanning is
+ * partial (i.e. not the whole index page).
  */
 static void **vector_level_prev_used(
     vector *pv,
     vector_page *page,
     vector_index *index,
-    int level )
+    int level,
+    int *partial )
 {
     void **p = (void**)&(*page)[ VECTOR_INDEX_PART( pv, index, level ) ];
+    if ( VECTOR_INDEX_PART( pv, index, level ) != VECTOR_SLOTS( pv ) - 1 ) {
+	*partial = 1;
+    }
     do {
 	if ( *p ) {
 	    if ( level == 0 ) {
 		return p; // This is a used entry
 	    }
 	    // *p is an index that needs to be inspected recursively
-	    void **x = vector_level_prev_used( pv, *p, index, level - 1 );
+	    int w = 0;
+	    void **x = vector_level_prev_used( pv, *p, index, level - 1, &w );
 	    if ( x ) {
 		return x; // Used slot was found; return it.
 	    }
-	    // If the page *p is all empty, so can/should be reclaimed.
+	    // If the page *p is all empty, it can/should be reclaimed.
+	    if ( w == 0 ) {
+		free( *p );
+		*p = 0;
+	    } else {
+		*partial = 1;
+	    }
 	} else {
 	    if ( level > 0 ) {
 		VECTOR_INDEX_LAST( pv, index, level );
@@ -287,9 +324,10 @@ void **vector_prev_used(vector *pv,vector_index *index) {
 	return 0;
     }
     int levels = vector_levels( pv, pv->size );
+    int partial = 0;
     do {
 	void **slot = vector_level_prev_used(
-	    pv, pv->entries, index, levels - 1 ) ;
+	    pv, pv->entries, index, levels - 1, &partial ) ;
 	if ( slot == 0 ) {
 	    break; // reached the end of the vector
 	}
@@ -297,49 +335,14 @@ void **vector_prev_used(vector *pv,vector_index *index) {
 	    return slot;
 	}
     } while ( (*index)-- != 0 );
-    *index = pv->size;
-    return 0;
-}
-
-#endif
-
-#if 0
-// Find the first in-use slot at or before the index, at the level
-static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) {
-    void **slot = vector_access( pv, *index, lv, 0 );
-    if ( slot == 0 ) {
-	return 0;
+    if ( partial == 0 ) {
+	free( pv->entries );
+	pv->entries = 0;
     }
-    do {
-	if ( *slot ) {
-	    if ( lv == 0 ) {
-		return slot;
-	    }
-	    void **sub = vector_prev_used_level( pv, index, lv - 1 );
-	    if ( sub ) {
-		return sub;
-	    }
-	}
-	slot--;
-    } while ( VECTOR_INDEX_PART_DEC( pv, index, lv ) != 0 );
+    *index = pv->size; // reached the end of the vector
     return 0;
 }
 
-// Find nearest used slot at or prior to the given index.
-void **vector_prev_used(vector *pv,vector_index *index) {
-    if ( pv->entries == 0 || *index >= pv->size ) {
-	*index = pv->size;
-	return 0;
-    }
-    void **slot = vector_prev_used_level(
-	pv, index, vector_levels( pv, pv->size ) - 1 );
-    if ( slot == 0 ) {
-	*index = pv->size;
-    }
-    return slot;
-}
-#endif
-
 // Reclaim tree of unused pages for a given level
 static void vector_reclaim(vector *pv,vector_page *page,unsigned int level) {
     int i = 0;
@@ -393,7 +396,8 @@ int vector_resize(
 	// 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.
-	if ( pv->variant == 3 ) { // Follow vector size using realloc
+	if ( pv->variant == single_index_level ) {
+	    // Follow vector size using realloc
 	    if ( new_size > 0 ) {
 		entries = (vector_page*)
 		    realloc( pv->entries, new_size * sizeof( void* ) );
@@ -427,7 +431,8 @@ int vector_resize(
 	}
     } else {
 	// vector is growing. Maybe insert levels.
-	if ( pv->variant == 3 ) { // Follow vector size using realloc
+	if ( pv->variant == single_index_level ) {
+	    // Follow vector size using realloc
 	    entries = (vector_page *)realloc(
 		pv->entries, new_size * sizeof( void* ) );
 	    if ( entries == 0 ) {
@@ -526,6 +531,14 @@ void vector_copy(vector *dst,vector_index di,
     }
 }
 
+vector *vector_clone(enum vector_variant variant,vector *src) {
+    vector *dst = (vector*) malloc( sizeof( vector ) );
+    (*dst) = (vector) { .variant = variant, .size = 0, .entries = 0 };
+    vector_resize( dst, src->size, 0, 0 );
+    vector_copy( dst, 0, src, 0, src->size );
+    return dst;
+}
+
 void vector_dump(vector *pv,
 		 void (*itemdump)(const vector_index,const void *)) {
     vector_index index = 0;
@@ -604,20 +617,40 @@ void vector_iterate(vector *pv,
 {
     vector_index index = start;
     while ( index < pv->size ) {
-	void **slot = vector_next_used( pv, &index );
-	if ( slot == 0 ) {
-	    break;
-	}
 	int end = VECTOR_SLOTS( pv );
 	int i = index & ( end - 1 );
-	for ( ; i < end && index < pv->size; i++, index++, slot++ ) {
-	    if ( itemfn( index, *slot, data ) ) {
+	for ( ; i < end && index < pv->size; i++, index++ ) {
+	    void **slot = vector_access( pv, index, 0, 0 );
+	    if ( itemfn( index, slot? *slot: 0, data ) ) {
 		return;
 	    }
 	}
     }
 }
 
+struct find_data {
+    void *value;
+    vector_index index;
+};
+
+static int vector_find_item(vector_index index, void *item,void *data) {
+    struct find_data *fd = (struct find_data*)data;
+    if ( fd->value != item ) {
+	return 0;
+    }
+    fd->index = index;
+    return 1;
+}
+
+vector_index vector_find(vector *pv,void *value) {
+    struct find_data fd = {
+	.value = value,
+	.index = pv->size
+    };
+    vector_iterate( pv, 0, vector_find_item, &fd );
+    return fd.index;
+}
+
 // Find surrounding indexes for a given item key in a sparse vector
 void *vector_bsearch(vector *pv,vector_index *index,const void *key,
 		     int (*compare)(const void *key, const void *item)) {