Add hashvector_create + some polishing

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

diff --git a/vector/hashvector.c b/vector/hashvector.c
index 1afae8086f2985dde4dfbaa0755fbaa4cde55e88..c26125376e9d811abc67e80e02f0f6cad572dcb5 100644 (file)
--- a/vector/hashvector.c
+++ b/vector/hashvector.c
@@ -1,43 +1,66 @@
-#include "hashvector.h"
+#include <stdlib.h>
+#include <hashvector.h>
+
+#define SELF hv->type
 
 // Find the slot for the keyed element, and return pointer to it, or
 // to the first of holes encountered while considering collisions.
 // Returns a pointer to the place for the item, or 0 in case of OOM or
 // overfull hashvector (i.e. 0 shouldn't happen).
-static void **hashvector_find_slot(hashvector *hv,void *key) {
-    unsigned long index = hv->keyhashcode( key ) % hv->table.size;
-    unsigned long i = index;
+// If itemkey is set, then the itemkey callback function is used for
+// obtaining a temporary key from the item.
+static void **hashvector_find_slot(
+    hashvector *hv, void *key, unsigned long *i, int itemkey )
+{
+    if ( itemkey ) {
+        // Get actual key from keying item
+       key = hv->type->itemkey( SELF, key );
+    }
+    unsigned long index = hv->type->hashcode( SELF, key ) % hv->table.size;
+    *i = index;
     void **hole = 0;
     void **p = 0;
     for ( ;; ) {
-       p = vector_entry(&hv->table, i);
+       p = vector_entry( &hv->table, (*i) );
        if ( p == 0 ) {
+           if ( itemkey ) {
+               hv->type->releasekey( SELF, key );
+           }
            return 0; // This basically means OOM, and is a failure condition.
        }
-       if ( *p == 0 ) {
-           break; // Not found
+       if ( (*p) == 0 ) {
+           if ( itemkey ) {
+               hv->type->releasekey( SELF, key );
+           }
+           return ( hole )? hole : p; // Not found; it's place is here.
        }
        if ( (*p) == HV_HOLE ) {
            if ( hole == 0 ) {
                hole = p; // Remember the first hole
            }
-       } else if ( hv->haskey( *p, key ) ) {
+       } else if ( hv->type->haskey( SELF, (*p), key ) ) {
+           if ( itemkey ) {
+               hv->type->releasekey( SELF, key );
+           }
            return p; // Found
        }
-       if ( ++i == hv->table.size ) {
-           i = 0; // Roll-around the table
+       if ( ++(*i) == hv->table.size ) {
+           (*i) = 0; // Roll-around the table
        }
-       if ( i == index ) {
+       if ( (*i) == index ) {
+           if ( itemkey ) {
+               hv->type->releasekey( SELF, key );
+           }
            return 0; // Overfull hashvector!
        }
     }
-    return ( hole )? hole : p;
 }
 
 // Find the keyed element, and assign the x pointer, or assign 0.
 // Returns 1 if element is found and 0 otherwise.
 int hashvector_find(hashvector *hv,void *key,void **x) {
-    void **p = hashvector_find_slot( hv, key );
+    unsigned long i;
+    void **p = hashvector_find_slot( hv, key, &i, 0 );
     if ( p && *p && *p != HV_HOLE ) {
        if ( x ) {
            *x = *p;
@@ -48,7 +71,7 @@ int hashvector_find(hashvector *hv,void *key,void **x) {
 }
 
 static int capture_item(vector *pv,unsigned long ix,void *item,void *data) {
-    if ( item != HV_HOLE ) {
+    if ( item && item != HV_HOLE ) {
        hashvector_add( (hashvector *) data, item );
     }
     return 0;
@@ -70,13 +93,14 @@ static void hashvector_resize(hashvector *hv,unsigned long new_size) {
     if ( new_size < hv->table.size ) {
        vector_resize( &tmp.table, 0, capture_item, hv );
     } else {
-       vector_iterate( &tmp.table, iter_item, hv );
+       vector_iterate( &tmp.table, 0, iter_item, hv );
     }
 }
     
 // Add the given element.
 int hashvector_add(hashvector *hv,void *item) {
-    void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
+    unsigned long i;
+    void **p = hashvector_find_slot( hv, item, &i, 1 );
     if ( p == 0 ) {
        return -1; // OOM or overfull hashvector
     }
@@ -96,17 +120,28 @@ int hashvector_add(hashvector *hv,void *item) {
 
 // Delete the given item
 int hashvector_delete(hashvector *hv,void *item) {
-    void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
+    unsigned long i;
+    void **p = hashvector_find_slot( hv, item, &i, 1 );
     if ( p == 0 ) {
        return -1;
     }
     if ( *p != item ) {
        return 0;
     }
-    *p = HV_HOLE;
-    hv->holes++;
+    // Check if subsequent slot is occupied
+    if ( ++i >= hv->table.size ) {
+       i = 0;
+    }
+    void **q = vector_access( &hv->table, i, 0, 0 );
+    if ( q && (*q) ) {
+       *p = HV_HOLE;
+       hv->holes++;
+    } else {
+       *p = 0;
+    }
     hv->fill--;
-    if ( hv->table.size > VECTOR_SLOTS && hv->fill < hv->table.size / 4 ) {
+    if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
+        hv->fill < hv->table.size / 4 ) {
        hashvector_resize( hv, hv->table.size / 2 );
     }
     return 1;
@@ -119,16 +154,14 @@ int hashvector_contents(hashvector *hv,vector *pv) {
     }
     unsigned long from = 0;
     unsigned long to = 0;
-    while ( to < hv->fill ) {
-       void **slot = vector_next_used( &hv->table, &from, 0, 0 );
-       if ( slot ) {
-           if ( *slot != HV_HOLE ) {
-               vector_set( pv, to++, *slot );
-           }
-           from++;
-       } else {
+    for ( ; to < hv->fill; from++ ) {
+       void **slot = vector_next_used( &hv->table, &from );
+       if ( slot == 0 ) {
            break;
        }
+       if ( *slot != HV_HOLE ) {
+           vector_set( pv, to++, *slot );
+       }
     }
     return 0;
 }
@@ -142,3 +175,19 @@ unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
     return value;
 }
 
+
+hashvector *hashvector_create(int variant,itemkeyfun *type) {
+    hashvector *hv = (hashvector*) malloc( sizeof( hashvector ) );
+    (*hv) = (hashvector) {
+       .table = (vector) {
+           .variant = variant,
+           .size = 0,
+           .entries = 0
+       },
+       .fill = 0,
+       .holes = 0,
+       .type = type
+    };
+    return hv;
+}
+