X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fhashvector.c;h=c26125376e9d811abc67e80e02f0f6cad572dcb5;hb=fff7d7c2ac83984bd2fc7ec3c72dc455c7c72807;hp=1afae8086f2985dde4dfbaa0755fbaa4cde55e88;hpb=c2fcc2eaad945b2bee685ca8b71c565158da0e18;p=rrq%2Frrqmisc.git

diff --git a/vector/hashvector.c b/vector/hashvector.c
index 1afae80..c261253 100644
--- 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;
+}
+