misspelling

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

diff --git a/vector/hashvector.c b/vector/hashvector.c
index bd6fb97b8697c1594414301a5cf3d28fead0b23e..0f5b31f6e640f9281bf982a9ca8fea422bd073d7 100644 (file)
--- a/vector/hashvector.c
+++ b/vector/hashvector.c
@@ -1,43 +1,65 @@
 #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;
@@ -76,7 +98,8 @@ static void hashvector_resize(hashvector *hv,unsigned long new_size) {
     
 // 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 +119,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;