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, and assign the x pointer, or assign 0.
60 // Returns 1 if element is found and 0 otherwise.
61 int hashvector_find(hashvector *hv,void *key,void **x) {
63 void **p = hashvector_find_slot( hv, key, &i, 0 );
64 if ( p && *p && *p != HV_HOLE ) {
73 static int capture_item(vector *pv,unsigned long ix,void *item,void *data) {
74 if ( item && item != HV_HOLE ) {
75 hashvector_add( (hashvector *) data, item );
80 static int iter_item(unsigned long ix,void *item,void *data) {
81 if ( item && item != HV_HOLE ) {
82 hashvector_add( (hashvector *) data, item );
87 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
89 hv->table.size = new_size;
90 hv->table.entries = 0;
93 if ( new_size < hv->table.size ) {
94 vector_resize( &tmp.table, 0, capture_item, hv );
96 vector_iterate( &tmp.table, 0, iter_item, hv );
100 // Add the given element.
101 int hashvector_add(hashvector *hv,void *item) {
103 void **p = hashvector_find_slot( hv, item, &i, 1 );
105 return -1; // OOM or overfull hashvector
108 if ( *p != HV_HOLE ) {
109 return 0; // Already added.
111 hv->holes--; // about to reuse a hole
115 if ( hv->fill + hv->holes > hv->table.size / 2 ) {
116 hashvector_resize( hv, hv->table.size * 2 );
121 // Delete the given item
122 int hashvector_delete(hashvector *hv,void *item) {
124 void **p = hashvector_find_slot( hv, item, &i, 1 );
131 // Check if subsequent slot is occupied
132 if ( ++i >= hv->table.size ) {
135 void **q = vector_access( &hv->table, i, 0, 0 );
143 if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
144 hv->fill < hv->table.size / 4 ) {
145 hashvector_resize( hv, hv->table.size / 2 );
150 // Copy items into a vector. Returns 0 on success and -1 on failure.
151 int hashvector_contents(hashvector *hv,vector *pv) {
152 if ( vector_resize( pv, hv->fill, 0, 0 ) ) {
155 unsigned long from = 0;
156 unsigned long to = 0;
157 for ( ; to < hv->fill; from++ ) {
158 void **slot = vector_next_used( &hv->table, &from );
162 if ( *slot != HV_HOLE ) {
163 vector_set( pv, to++, *slot );
169 // A simple binary hashcode, (before modulo table size)
170 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
171 unsigned long value = 5381;
173 value += ( value << 5 ) + *(key++);
179 hashvector *hashvector_create(int variant,itemkeyfun *type) {
180 hashvector *hv = (hashvector*) malloc( sizeof( hashvector ) );
181 (*hv) = (hashvector) {