X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=pvector%2Fhashvector.c;h=5efbd8af801eda3927d8265c2d4553cb4678f5ef;hb=4d7f93d07b12ad58f42e41f3e8ecd5550f3bd9c8;hp=35dcd2e2a9a7b9415910ac74b775c9a80297460a;hpb=ba5cab4faddcde50d4321267f775f0ab884da39e;p=rrq%2Frrqmisc.git

diff --git a/pvector/hashvector.c b/pvector/hashvector.c
index 35dcd2e..5efbd8a 100644
--- a/pvector/hashvector.c
+++ b/pvector/hashvector.c
@@ -1,34 +1,37 @@
 #include "hashvector.h"
 
-// Find the slot for the keyed element, and return pointer to it.
+// 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 int index = hv->keyhashcode( key ) % hv->table.size;
-    unsigned int i = index;
+    unsigned long index = hv->keyhashcode( key ) % hv->table.size;
+    unsigned long i = index;
     void **hole = 0;
+    void **p = 0;
     for ( ;; ) {
-	void **p = pvector_entry(&hv->table, i);
+	p = pvector_entry(&hv->table, i);
 	if ( p == 0 ) {
-	    return 0;
+	    return 0; // This basically means OOM, and is a failure condition.
 	}
-	if ( *p ) {
-	    if ( (*p) != HV_HOLE ) {
-		if ( hv->haskey( *p, key ) ) {
-		    return p;
-		}
-	    } else {
-		if ( hole == 0 ) {
-		    hole = p;
-		}
-		if ( ++i == hv->table.size ) {
-		    i = 0;
-		}
-		if ( i != index ) {
-		    continue;
-		}
+	if ( *p == 0 ) {
+	    break; // Not found
+	}
+	if ( (*p) == HV_HOLE ) {
+	    if ( hole == 0 ) {
+		hole = p; // Remember the first hole
 	    }
+	} else if ( hv->haskey( *p, key ) ) {
+	    return p; // Found
+	}
+	if ( ++i == hv->table.size ) {
+	    i = 0; // Roll-around the table
+	}
+	if ( i == index ) {
+	    return 0; // Overfull hashvector!
 	}
-	return ( hole )? hole : p;
     }
+    return ( hole )? hole : p;
 }
 
 // Find the keyed element, and assign the x pointer, or assign 0.
@@ -49,7 +52,7 @@ static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) {
     return 0;
 }
 
-static void hashvector_resize(hashvector *hv,unsigned int new_size) {
+static void hashvector_resize(hashvector *hv,unsigned long new_size) {
     hashvector tmp = *hv;
     hv->table.size = new_size;
     hv->table.entries = 0;
@@ -59,44 +62,46 @@ static void hashvector_resize(hashvector *hv,unsigned int new_size) {
 }
     
 // Add the given element.
-void hashvector_add(hashvector *hv,void *item) {
+int hashvector_add(hashvector *hv,void *item) {
     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
-    if ( p ) {
-	if ( *p ) {
-	    if ( *p != HV_HOLE ) {
-		return;
-	    }
-	    hv->holes--;
-	}
-	*p = item;
-	hv->fill++;
-	if ( hv->fill + hv->holes > hv->table.size / 2 ) {
-	    hashvector_resize( hv, hv->table.size * 2 );
+    if ( p == 0 ) {
+	return -1; // OOM or overfull hashvector
+    }
+    if ( *p ) {
+	if ( *p != HV_HOLE ) {
+	    return 0; // Already added.
 	}
+	hv->holes--; // about to reuse a hole
+    }
+    *p = item;
+    hv->fill++;
+    if ( hv->fill + hv->holes > hv->table.size / 2 ) {
+	hashvector_resize( hv, hv->table.size * 2 );
     }
+    return 1;
 }
 
-// Return the next element starting at i, or 0 if there are no more.
-// Also increment the index to be of the element + 1, or -1 if there
-// are no more elements.
-//unsigned char *htnext(htable *table,int *i);
-
-// Delete the given element.
-void hashvector_delete(hashvector *hv,void *item) {
+// Delete the given item
+int hashvector_delete(hashvector *hv,void *item) {
     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
-    if ( p && *p && *p != HV_HOLE ) {
-	*p = HV_HOLE;
-	hv->holes++;
-	if ( hv->table.size > 256 ) {
-	    if ( hv->fill < hv->table.size / 2 ) {
-		hashvector_resize( hv, hv->table.size / 2 );
-	    }
+    if ( p == 0 ) {
+	return -1;
+    }
+    if ( *p != item ) {
+	return 0;
+    }
+    *p = HV_HOLE;
+    hv->holes++;
+    if ( hv->table.size > 256 ) {
+	if ( hv->fill < hv->table.size / 2 ) {
+	    hashvector_resize( hv, hv->table.size / 2 );
 	}
     }
+    return 1;
 }
 
 // Copy items into a pvector. Returns 0 on success and -1 on failure.
-int hashvector_pack(hashvector *hv,pvector *pv) {
+int hashvector_contents(hashvector *hv,pvector *pv) {
     if ( pvector_resize( pv, hv->fill, 0, 0 ) ) {
 	return -1;
     }
@@ -115,3 +120,13 @@ int hashvector_pack(hashvector *hv,pvector *pv) {
     }
     return 0;
 }
+
+// A simple binary hashcode, (before modulo table size)
+unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
+    unsigned long value = 5381;
+    while ( n-- ) {
+	value += ( value << 5 ) + *(key++);
+    }
+    return value;
+}
+