2 #include <hashvector.h>
6 // Find the slot for the keyed element, and return pointer to it, or
7 // to the first of holes encountered while considering collisions.
8 // Returns a pointer to the place for the item, or 0 in case of OOM or
9 // overfull hashvector (i.e. 0 shouldn't happen).
10 // If itemkey is set, then the itemkey callback function is used for
11 // obtaining a temporary key from the item.
12 static void **hashvector_find_slot(
13 hashvector *hv, void *key, unsigned long *i, int itemkey )
16 // Get actual key from keying item
17 key = hv->type->itemkey( SELF, key );
19 unsigned long index = hv->type->hashcode( SELF, key ) % hv->table.size;
24 p = vector_entry( &hv->table, (*i) );
27 hv->type->releasekey( SELF, key );
29 return 0; // This basically means OOM, and is a failure condition.
33 hv->type->releasekey( SELF, key );
35 return ( hole )? hole : p; // Not found; it's place is here.
37 if ( (*p) == HV_HOLE ) {
39 hole = p; // Remember the first hole
41 } else if ( hv->type->haskey( SELF, (*p), key ) ) {
43 hv->type->releasekey( SELF, key );
47 if ( ++(*i) == hv->table.size ) {
48 (*i) = 0; // Roll-around the table
50 if ( (*i) == index ) {
52 hv->type->releasekey( SELF, key );
54 return 0; // Overfull hashvector!
59 // Find the keyed element at or after the index. Update index and
61 void *hashvector_next(hashvector *hv,vector_index *index,void *key) {
62 unsigned long i = index? *index : 0;
63 for ( ; i < hv->table.size; i++ ) {
64 void **p = vector_next_used( &hv->table, &i );
68 if ( *p && *p != HV_HOLE ) {
69 if ( key && hv->type->haskey( hv->type, *p, key ) == 0 ) {
79 (*index) = hv->table.size;
84 static int capture_item(vector *pv,unsigned long ix,void *item,void *data) {
85 if ( item && item != HV_HOLE ) {
86 hashvector_add( (hashvector *) data, item );
91 static int iter_item(unsigned long ix,void *item,void *data) {
92 if ( item && item != HV_HOLE ) {
93 hashvector_add( (hashvector *) data, item );
98 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
100 hv->table.size = new_size;
101 hv->table.entries = 0;
104 if ( new_size < hv->table.size ) {
105 vector_resize( &tmp.table, 0, capture_item, hv );
107 vector_iterate( &tmp.table, 0, iter_item, hv );
111 // Add the given element.
112 int hashvector_add(hashvector *hv,void *item) {
114 void **p = hashvector_find_slot( hv, item, &i, 1 );
116 return -1; // OOM or overfull hashvector
119 if ( *p != HV_HOLE ) {
120 return 0; // Already added.
122 hv->holes--; // about to reuse a hole
126 if ( hv->fill + hv->holes > hv->table.size / 2 ) {
127 hashvector_resize( hv, hv->table.size * 2 );
132 // Delete the given item
133 int hashvector_delete(hashvector *hv,void *item) {
135 void **p = hashvector_find_slot( hv, item, &i, 1 );
142 // Check if subsequent slot is occupied
143 if ( ++i >= hv->table.size ) {
146 void **q = vector_access( &hv->table, i, 0, 0 );
154 if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
155 hv->fill < hv->table.size / 4 ) {
156 hashvector_resize( hv, hv->table.size / 2 );
161 vector *hashvector_contents(
162 hashvector *hv,enum vector_variant variant,vector *v)
165 if ( hv->fill == 0 ) {
168 v = (vector*) malloc( sizeof( vector ) );
170 vector_resize( v, 0, vector_clear_any, 0 );
172 (*v) = (vector) { .variant = variant, 0, 0 };
173 if ( hv->fill == 0 ) {
176 vector_resize( v, hv->fill, 0, 0 );
179 for ( i = 0; i < v->size; i++, j++ ) {
180 vector_set( v, i, hashvector_next( hv, &j, 0 ) );
185 // A simple binary hashcode, (before modulo table size)
186 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
187 unsigned long value = 5381;
189 value += ( value << 5 ) + *(key++);
195 hashvector *hashvector_create(enum vector_variant variant,itemkeyfun *type) {
196 hashvector *hv = (hashvector*) malloc( sizeof( hashvector ) );
197 (*hv) = (hashvector) {