#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.
int hashvector_find(hashvector *hv,void *key,void **x) {
void **p = hashvector_find_slot( hv, key );
if ( p && *p && *p != HV_HOLE ) {
- *x = *p;
+ if ( x ) {
+ *x = *p;
+ }
return 1;
}
return 0;
return 0;
}
-static void hashvector_resize(hashvector *hv,unsigned int new_size) {
+static int iter_item(unsigned long ix,void *item,void *data) {
+ if ( item && item != HV_HOLE ) {
+ hashvector_add( (hashvector *) data, item );
+ }
+ return 0;
+}
+
+static void hashvector_resize(hashvector *hv,unsigned long new_size) {
hashvector tmp = *hv;
hv->table.size = new_size;
hv->table.entries = 0;
hv->fill = 0;
hv->holes = 0;
- pvector_resize( &tmp.table, 0, capture_item, hv );
+ if ( new_size < hv->table.size ) {
+ pvector_resize( &tmp.table, 0, capture_item, hv );
+ } else {
+ pvector_iterate( &tmp.table, iter_item, hv );
+ }
}
// 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++;
+ hv->fill--;
+ if ( hv->table.size > 256 ) {
+ if ( hv->fill < hv->table.size / 4 ) {
+ 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;
}
}
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;
+}
+