Use enum for variants; add "clone" and "find" and imporv doco

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

diff --git a/vector/vector.c b/vector/vector.c
index 2f1010c841791c0d66ed420e197023a238057540..16d5577f19a44e17977229aa16cb6882b1bb196e 100644 (file)
--- a/vector/vector.c
+++ b/vector/vector.c
@@ -39,11 +39,11 @@ 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: {
+    case nibble_index_levels: {
        nibble *pp = (nibble*)( px + ( level / 2 ) );
        switch ( level & 1 ) {
        case 0: return pp->a;
@@ -51,7 +51,7 @@ unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
        }
        break;
     }
-    case 2: {
+    case bitpair_index_levels: {
        bitpair *pp = (bitpair*)( px + ( level / 4 ) );
        switch ( level & 3 ) {
        case 0: return pp->a;
@@ -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,7 +88,7 @@ static unsigned long VECTOR_INDEX_PART_INC(
        }
        break;
     }
-    case 2: {
+    case bitpair_index_levels: {
        bitpair *pp = (bitpair*)( px + level / 4 );
        switch ( level & 3 ) {
        case 0: return ++(pp->a);
@@ -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;
@@ -163,10 +163,10 @@ static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int 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;
 }
@@ -177,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;
 }
@@ -396,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* ) );
@@ -430,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 ) {
@@ -529,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;
@@ -618,6 +628,29 @@ void vector_iterate(vector *pv,
     }
 }
 
+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)) {