cleanup and commenting

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

diff --git a/pvector/hashvector.c b/pvector/hashvector.c
index 35dcd2e2a9a7b9415910ac74b775c9a80297460a..5efbd8af801eda3927d8265c2d4553cb4678f5ef 100644 (file)
--- 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;
+}
+