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 item
60 void *HashVector_find(HashVector *hv,void *key) {
61 VectorIndex index = 0;
62 void **slot = HashVector_find_slot( hv, &index, key, 0 );
63 return ( slot && *slot && *slot != HV_HOLE )? *slot : 0;
66 // Find any element at or after the index that admits to the key.
67 // Update index and return item.
68 void *HashVector_next(HashVector *hv,VectorIndex *index,void *key) {
69 unsigned long i = index? *index : 0;
70 for ( ; i < hv->table.size; i++ ) {
71 void **p = Vector_next_used( &hv->table, &i );
75 if ( *p && *p != HV_HOLE ) {
76 if ( key && hv->type->haskey( hv->type, *p, key ) == 0 ) {
86 (*index) = hv->table.size;
91 static int capture_item(Vector *pv,unsigned long ix,void *item,void *data) {
92 if ( item && item != HV_HOLE ) {
93 HashVector_add( (HashVector *) data, item );
98 static int iter_item(unsigned long ix,void *item,void *data) {
99 if ( item && item != HV_HOLE ) {
100 HashVector_add( (HashVector *) data, item );
105 static void HashVector_resize(HashVector *hv,unsigned long new_size) {
106 HashVector tmp = *hv;
107 hv->table.size = new_size;
108 hv->table.entries = 0;
111 if ( new_size < hv->table.size ) {
112 Vector_resize( &tmp.table, 0, capture_item, hv );
114 Vector_iterate( &tmp.table, 0, iter_item, hv );
118 // Add the given element.
119 int HashVector_add(HashVector *hv,void *item) {
121 void **p = HashVector_find_slot( hv, item, &i, 1 );
123 return -1; // OOM or overfull HashVector
126 if ( *p != HV_HOLE ) {
127 return 0; // Already added.
129 hv->holes--; // about to reuse a hole
133 if ( hv->fill + hv->holes > hv->table.size / 2 ) {
134 HashVector_resize( hv, hv->table.size * 2 );
139 // Delete the given item
140 int HashVector_delete(HashVector *hv,void *item) {
142 void **p = HashVector_find_slot( hv, item, &i, 1 );
149 // Check if subsequent slot is occupied
150 if ( ++i >= hv->table.size ) {
153 void **q = Vector_access( &hv->table, i, 0, 0 );
161 if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
162 hv->fill < hv->table.size / 4 ) {
163 HashVector_resize( hv, hv->table.size / 2 );
168 Vector *HashVector_contents(
169 HashVector *hv,enum VectorVariant variant,Vector *v)
172 if ( hv->fill == 0 ) {
175 v = (Vector*) malloc( sizeof( Vector ) );
177 Vector_resize( v, 0, Vector_clear_any, 0 );
179 (*v) = (Vector) { .variant = variant, 0, 0 };
180 if ( hv->fill == 0 ) {
183 Vector_resize( v, hv->fill, 0, 0 );
186 for ( i = 0; i < v->size; i++, j++ ) {
187 Vector_set( v, i, HashVector_next( hv, &j, 0 ) );
192 // A simple binary hashcode, (before modulo table size)
193 unsigned long HashVector_hashcode(unsigned char *key,unsigned long n) {
194 unsigned long value = 5381;
196 value += ( value << 5 ) + *(key++);
202 HashVector *HashVector_create(enum VectorVariant variant,ItemKeyFun *type) {
203 HashVector *hv = (HashVector*) malloc( sizeof( HashVector ) );
204 (*hv) = (HashVector) {