vector/hashvector.c

   1 #include <stdlib.h>
   2 #include <hashvector.h>
   3
   4 #define SELF hv->type
   5
   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 )
  14 {
  15     if ( itemkey ) {
  16          // Get actual key from keying item
  17         key = hv->type->itemkey( SELF, key );
  18     }
  19     unsigned long index = hv->type->hashcode( SELF, key ) % hv->table.size;
  20     *i = index;
  21     void **hole = 0;
  22     void **p = 0;
  23     for ( ;; ) {
  24         p = vector_entry( &hv->table, (*i) );
  25         if ( p == 0 ) {
  26             if ( itemkey ) {
  27                 hv->type->releasekey( SELF, key );
  28             }
  29             return 0; // This basically means OOM, and is a failure condition.
  30         }
  31         if ( (*p) == 0 ) {
  32             if ( itemkey ) {
  33                 hv->type->releasekey( SELF, key );
  34             }
  35             return ( hole )? hole : p; // Not found; it's place is here.
  36         }
  37         if ( (*p) == HV_HOLE ) {
  38             if ( hole == 0 ) {
  39                 hole = p; // Remember the first hole
  40             }
  41         } else if ( hv->type->haskey( SELF, (*p), key ) ) {
  42             if ( itemkey ) {
  43                 hv->type->releasekey( SELF, key );
  44             }
  45             return p; // Found
  46         }
  47         if ( ++(*i) == hv->table.size ) {
  48             (*i) = 0; // Roll-around the table
  49         }
  50         if ( (*i) == index ) {
  51             if ( itemkey ) {
  52                 hv->type->releasekey( SELF, key );
  53             }
  54             return 0; // Overfull hashvector!
  55         }
  56     }
  57 }
  58
  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) {
  62     unsigned long i;
  63     void **p = hashvector_find_slot( hv, key, &i, 0 );
  64     if ( p && *p && *p != HV_HOLE ) {
  65         if ( x ) {
  66             *x = *p;
  67         }
  68         return 1;
  69     }
  70     return 0;
  71 }
  72
  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 );
  76     }
  77     return 0;
  78 }
  79
  80 static int iter_item(unsigned long ix,void *item,void *data) {
  81     if ( item && item != HV_HOLE ) {
  82         hashvector_add( (hashvector *) data, item );
  83     }
  84     return 0;
  85 }
  86
  87 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
  88     hashvector tmp = *hv;
  89     hv->table.size = new_size;
  90     hv->table.entries = 0;
  91     hv->fill = 0;
  92     hv->holes = 0;
  93     if ( new_size < hv->table.size ) {
  94         vector_resize( &tmp.table, 0, capture_item, hv );
  95     } else {
  96         vector_iterate( &tmp.table, 0, iter_item, hv );
  97     }
  98 }
  99
 100 // Add the given element.
 101 int hashvector_add(hashvector *hv,void *item) {
 102     unsigned long i;
 103     void **p = hashvector_find_slot( hv, item, &i, 1 );
 104     if ( p == 0 ) {
 105         return -1; // OOM or overfull hashvector
 106     }
 107     if ( *p ) {
 108         if ( *p != HV_HOLE ) {
 109             return 0; // Already added.
 110         }
 111         hv->holes--; // about to reuse a hole
 112     }
 113     *p = item;
 114     hv->fill++;
 115     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
 116         hashvector_resize( hv, hv->table.size * 2 );
 117     }
 118     return 1;
 119 }
 120
 121 // Delete the given item
 122 int hashvector_delete(hashvector *hv,void *item) {
 123     unsigned long i;
 124     void **p = hashvector_find_slot( hv, item, &i, 1 );
 125     if ( p == 0 ) {
 126         return -1;
 127     }
 128     if ( *p != item ) {
 129         return 0;
 130     }
 131     // Check if subsequent slot is occupied
 132     if ( ++i >= hv->table.size ) {
 133         i = 0;
 134     }
 135     void **q = vector_access( &hv->table, i, 0, 0 );
 136     if ( q && (*q) ) {
 137         *p = HV_HOLE;
 138         hv->holes++;
 139     } else {
 140         *p = 0;
 141     }
 142     hv->fill--;
 143     if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
 144          hv->fill < hv->table.size / 4 ) {
 145         hashvector_resize( hv, hv->table.size / 2 );
 146     }
 147     return 1;
 148 }
 149
 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 ) ) {
 153         return -1;
 154     }
 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 );
 159         if ( slot == 0 ) {
 160             break;
 161         }
 162         if ( *slot != HV_HOLE ) {
 163             vector_set( pv, to++, *slot );
 164         }
 165     }
 166     return 0;
 167 }
 168
 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;
 172     while ( n-- ) {
 173         value += ( value << 5 ) + *(key++);
 174     }
 175     return value;
 176 }
 177
 178
 179 hashvector *hashvector_create(int variant,itemkeyfun *type) {
 180     hashvector *hv = (hashvector*) malloc( sizeof( hashvector ) );
 181     (*hv) = (hashvector) {
 182         .table = (vector) {
 183             .variant = variant,
 184             .size = 16,
 185             .entries = 0
 186         },
 187         .fill = 0,
 188         .holes = 0,
 189         .type = type
 190     };
 191     return hv;
 192 }
 193