1 #include "hashvector.h"
3 // Find the slot for the keyed element, and return pointer to it, or
4 // to the first of holes encountered while considering collisions.
5 // Returns a pointer to the place for the item, or 0 in case of OOM or
6 // overfull hashvector (i.e. 0 shouldn't happen).
7 static void **hashvector_find_slot(hashvector *hv,void *key) {
8 unsigned long index = hv->keyhashcode( key ) % hv->table.size;
9 unsigned long i = index;
13 p = pvector_entry(&hv->table, i);
15 return 0; // This basically means OOM, and is a failure condition.
20 if ( (*p) == HV_HOLE ) {
22 hole = p; // Remember the first hole
24 } else if ( hv->haskey( *p, key ) ) {
27 if ( ++i == hv->table.size ) {
28 i = 0; // Roll-around the table
31 return 0; // Overfull hashvector!
34 return ( hole )? hole : p;
37 // Find the keyed element, and assign the x pointer, or assign 0.
38 // Returns 1 if element is found and 0 otherwise.
39 int hashvector_find(hashvector *hv,void *key,void **x) {
40 void **p = hashvector_find_slot( hv, key );
41 if ( p && *p && *p != HV_HOLE ) {
50 static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) {
51 if ( item != HV_HOLE ) {
52 hashvector_add( (hashvector *) data, item );
57 static int iter_item(unsigned long ix,void *item,void *data) {
58 if ( item && item != HV_HOLE ) {
59 hashvector_add( (hashvector *) data, item );
64 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
66 hv->table.size = new_size;
67 hv->table.entries = 0;
70 if ( new_size < hv->table.size ) {
71 pvector_resize( &tmp.table, 0, capture_item, hv );
73 pvector_iterate( &tmp.table, iter_item, hv );
77 // Add the given element.
78 int hashvector_add(hashvector *hv,void *item) {
79 void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
81 return -1; // OOM or overfull hashvector
84 if ( *p != HV_HOLE ) {
85 return 0; // Already added.
87 hv->holes--; // about to reuse a hole
91 if ( hv->fill + hv->holes > hv->table.size / 2 ) {
92 hashvector_resize( hv, hv->table.size * 2 );
97 // Delete the given item
98 int hashvector_delete(hashvector *hv,void *item) {
99 void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
109 if ( hv->table.size > 256 ) {
110 if ( hv->fill < hv->table.size / 4 ) {
111 hashvector_resize( hv, hv->table.size / 2 );
117 // Copy items into a pvector. Returns 0 on success and -1 on failure.
118 int hashvector_contents(hashvector *hv,pvector *pv) {
119 if ( pvector_resize( pv, hv->fill, 0, 0 ) ) {
122 unsigned long from = 0;
123 unsigned long to = 0;
124 while ( to < hv->fill ) {
125 void **slot = pvector_next_used( &hv->table, &from, 0, 0 );
127 if ( *slot != HV_HOLE ) {
128 pvector_set( pv, to++, *slot );
138 // A simple binary hashcode, (before modulo table size)
139 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
140 unsigned long value = 5381;
142 value += ( value << 5 ) + *(key++);