1 #include "hashvector.h"
5 // Find the slot for the keyed element, and return pointer to it, or
6 // to the first of holes encountered while considering collisions.
7 // Returns a pointer to the place for the item, or 0 in case of OOM or
8 // overfull hashvector (i.e. 0 shouldn't happen).
9 // If itemkey is set, then the itmekey callback function is used for
10 // obtaining a temporary key from the item.
11 static void **hashvector_find_slot(
12 hashvector *hv, void *key, unsigned long *i, int itemkey )
15 // Get actual key from keying item
16 key = hv->type->itemkey( SELF, key );
18 unsigned long index = hv->type->hashcode( SELF, key ) % hv->table.size;
23 p = vector_entry( &hv->table, (*i) );
26 hv->type->releasekey( SELF, key );
28 return 0; // This basically means OOM, and is a failure condition.
32 hv->type->releasekey( SELF, key );
34 return ( hole )? hole : p; // Not found; it's place is here.
36 if ( (*p) == HV_HOLE ) {
38 hole = p; // Remember the first hole
40 } else if ( hv->type->haskey( SELF, (*p), key ) ) {
42 hv->type->releasekey( SELF, key );
46 if ( ++(*i) == hv->table.size ) {
47 (*i) = 0; // Roll-around the table
49 if ( (*i) == index ) {
51 hv->type->releasekey( SELF, key );
53 return 0; // Overfull hashvector!
58 // Find the keyed element, and assign the x pointer, or assign 0.
59 // Returns 1 if element is found and 0 otherwise.
60 int hashvector_find(hashvector *hv,void *key,void **x) {
62 void **p = hashvector_find_slot( hv, key, &i, 0 );
63 if ( p && *p && *p != HV_HOLE ) {
72 static int capture_item(vector *pv,unsigned long ix,void *item,void *data) {
73 if ( item && item != HV_HOLE ) {
74 hashvector_add( (hashvector *) data, item );
79 static int iter_item(unsigned long ix,void *item,void *data) {
80 if ( item && item != HV_HOLE ) {
81 hashvector_add( (hashvector *) data, item );
86 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
88 hv->table.size = new_size;
89 hv->table.entries = 0;
92 if ( new_size < hv->table.size ) {
93 vector_resize( &tmp.table, 0, capture_item, hv );
95 vector_iterate( &tmp.table, 0, iter_item, hv );
99 // Add the given element.
100 int hashvector_add(hashvector *hv,void *item) {
102 void **p = hashvector_find_slot( hv, item, &i, 1 );
104 return -1; // OOM or overfull hashvector
107 if ( *p != HV_HOLE ) {
108 return 0; // Already added.
110 hv->holes--; // about to reuse a hole
114 if ( hv->fill + hv->holes > hv->table.size / 2 ) {
115 hashvector_resize( hv, hv->table.size * 2 );
120 // Delete the given item
121 int hashvector_delete(hashvector *hv,void *item) {
123 void **p = hashvector_find_slot( hv, item, &i, 1 );
130 // Check if subsequent slot is occupied
131 if ( ++i >= hv->table.size ) {
134 void **q = vector_access( &hv->table, i, 0, 0 );
142 if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
143 hv->fill < hv->table.size / 4 ) {
144 hashvector_resize( hv, hv->table.size / 2 );
149 // Copy items into a vector. Returns 0 on success and -1 on failure.
150 int hashvector_contents(hashvector *hv,vector *pv) {
151 if ( vector_resize( pv, hv->fill, 0, 0 ) ) {
154 unsigned long from = 0;
155 unsigned long to = 0;
156 for ( ; to < hv->fill; from++ ) {
157 void **slot = vector_next_used( &hv->table, &from );
161 if ( *slot != HV_HOLE ) {
162 vector_set( pv, to++, *slot );
168 // A simple binary hashcode, (before modulo table size)
169 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
170 unsigned long value = 5381;
172 value += ( value << 5 ) + *(key++);