#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;
// 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
}
// 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;