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 at or after the index. Update index and
  60 // return item.
  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 = hashvector_find_slot( hv, key, &i, 0 );
  65         if ( p == 0 ) {
  66             break;
  67         }
  68         if ( *p && *p != HV_HOLE ) {
  69             if ( key && hv->type->haskey( hv->type, key, *p ) == 0 ) {
  70                 continue;
  71             }
  72             if ( index ) {
  73                 (*index) = i;
  74             }
  75             return *p;
  76         }
  77     }
  78     if ( index ) {
  79         (*index) = hv->table.size;
  80     }
  81     return 0;
  82 }
  83
  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 );
  87     }
  88     return 0;
  89 }
  90
  91 static int iter_item(unsigned long ix,void *item,void *data) {
  92     if ( item && item != HV_HOLE ) {
  93         hashvector_add( (hashvector *) data, item );
  94     }
  95     return 0;
  96 }
  97
  98 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
  99     hashvector tmp = *hv;
 100     hv->table.size = new_size;
 101     hv->table.entries = 0;
 102     hv->fill = 0;
 103     hv->holes = 0;
 104     if ( new_size < hv->table.size ) {
 105         vector_resize( &tmp.table, 0, capture_item, hv );
 106     } else {
 107         vector_iterate( &tmp.table, 0, iter_item, hv );
 108     }
 109 }
 110
 111 // Add the given element.
 112 int hashvector_add(hashvector *hv,void *item) {
 113     unsigned long i;
 114     void **p = hashvector_find_slot( hv, item, &i, 1 );
 115     if ( p == 0 ) {
 116         return -1; // OOM or overfull hashvector
 117     }
 118     if ( *p ) {
 119         if ( *p != HV_HOLE ) {
 120             return 0; // Already added.
 121         }
 122         hv->holes--; // about to reuse a hole
 123     }
 124     *p = item;
 125     hv->fill++;
 126     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
 127         hashvector_resize( hv, hv->table.size * 2 );
 128     }
 129     return 1;
 130 }
 131
 132 // Delete the given item
 133 int hashvector_delete(hashvector *hv,void *item) {
 134     unsigned long i;
 135     void **p = hashvector_find_slot( hv, item, &i, 1 );
 136     if ( p == 0 ) {
 137         return -1;
 138     }
 139     if ( *p != item ) {
 140         return 0;
 141     }
 142     // Check if subsequent slot is occupied
 143     if ( ++i >= hv->table.size ) {
 144         i = 0;
 145     }
 146     void **q = vector_access( &hv->table, i, 0, 0 );
 147     if ( q && (*q) ) {
 148         *p = HV_HOLE;
 149         hv->holes++;
 150     } else {
 151         *p = 0;
 152     }
 153     hv->fill--;
 154     if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
 155          hv->fill < hv->table.size / 4 ) {
 156         hashvector_resize( hv, hv->table.size / 2 );
 157     }
 158     return 1;
 159 }
 160
 161 // Copy items into a vector. Returns 0 on success and -1 on failure.
 162 int hashvector_contents(hashvector *hv,vector *pv) {
 163     if ( vector_resize( pv, hv->fill, 0, 0 ) ) {
 164         return -1;
 165     }
 166     unsigned long from = 0;
 167     unsigned long to = 0;
 168     for ( ; to < hv->fill; from++ ) {
 169         void **slot = vector_next_used( &hv->table, &from );
 170         if ( slot == 0 ) {
 171             break;
 172         }
 173         if ( *slot != HV_HOLE ) {
 174             vector_set( pv, to++, *slot );
 175         }
 176     }
 177     return 0;
 178 }
 179
 180 // A simple binary hashcode, (before modulo table size)
 181 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
 182     unsigned long value = 5381;
 183     while ( n-- ) {
 184         value += ( value << 5 ) + *(key++);
 185     }
 186     return value;
 187 }
 188
 189
 190 hashvector *hashvector_create(enum vector_variant variant,itemkeyfun *type) {
 191     hashvector *hv = (hashvector*) malloc( sizeof( hashvector ) );
 192     (*hv) = (hashvector) {
 193         .table = (vector) {
 194             .variant = variant,
 195             .size = 16,
 196             .entries = 0
 197         },
 198         .fill = 0,
 199         .holes = 0,
 200         .type = type
 201     };
 202     return hv;
 203 }
 204