vector/hashvector.c

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