vector/HashVector.c

   1 #include <stdlib.h>
   2 #include <HashVector.h>
   3
   4 // Find the slot for the keyed element, and return pointer to it, or
   5 // to the first of holes encountered while considering collisions.
   6 // Returns a pointer to the place for the item, or 0 in case of OOM or
   7 // overfull HashVector (i.e. 0 shouldn't happen).
   8 // If itemkey is set, then the itemkey callback function is used for
   9 // obtaining a temporary key from the item.
  10 static void **HashVector_find_slot(
  11     HashVector *hv, void *key, unsigned long *i, int itemkey )
  12 {
  13     if ( itemkey ) {
  14          // Get actual key from keying item
  15         key = ItemKeyFun_itemkey( hv->type, key );
  16     }
  17     unsigned long index = ItemKeyFun_hashcode( hv->type, key ) % hv->table.size;
  18     *i = index;
  19     void **hole = 0;
  20     void **p = 0;
  21     for ( ;; ) {
  22         p = Vector_entry( &hv->table, (*i) );
  23         if ( p == 0 ) {
  24             if ( itemkey ) {
  25                 ItemKeyFun_releasekey( hv->type, key );
  26             }
  27             return 0; // This basically means OOM, and is a failure condition.
  28         }
  29         if ( (*p) == 0 ) {
  30             if ( itemkey ) {
  31                 ItemKeyFun_releasekey( hv->type, key );
  32             }
  33             return ( hole )? hole : p; // Not found; it's place is here.
  34         }
  35         if ( (*p) == HV_HOLE ) {
  36             if ( hole == 0 ) {
  37                 hole = p; // Remember the first hole
  38             }
  39         } else if ( ItemKeyFun_haskey( hv->type, (*p), key ) ) {
  40             if ( itemkey ) {
  41                 ItemKeyFun_releasekey( hv->type, key );
  42             }
  43             return p; // Found
  44         }
  45         if ( ++(*i) == hv->table.size ) {
  46             (*i) = 0; // Roll-around the table
  47         }
  48         if ( (*i) == index ) {
  49             if ( itemkey ) {
  50                 ItemKeyFun_releasekey( hv->type, key );
  51             }
  52             return 0; // Overfull HashVector!
  53         }
  54     }
  55 }
  56
  57 // Find the keyed item
  58 void *HashVector_find(HashVector *hv,void *key) {
  59     VectorIndex index = 0;
  60     void **slot = HashVector_find_slot( hv, &index, key, 0 );
  61     return ( slot && *slot && *slot != HV_HOLE )? *slot : 0;
  62 }
  63
  64 // Find any element at or after the index that admits to the key.
  65 // Update index and return item.
  66 void *HashVector_next(HashVector *hv,VectorIndex *index) {
  67     for ( ; (*index) < hv->table.size; (*index)++ ) {
  68         void **p = Vector_next_used( &hv->table, index );
  69         if ( p == 0 ) {
  70             break;
  71         }
  72         if ( *p && *p != HV_HOLE ) {
  73             return *p;
  74         }
  75     }
  76     (*index) = hv->table.size;
  77     return 0;
  78 }
  79
  80 static int capture_item(Vector *pv,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 int iter_item(unsigned long ix,void *item,void *data) {
  88     if ( item && item != HV_HOLE ) {
  89         HashVector_add( (HashVector *) data, item );
  90     }
  91     return 0;
  92 }
  93
  94 static void HashVector_resize(HashVector *hv,unsigned long new_size) {
  95     HashVector tmp = *hv;
  96     hv->table.size = new_size;
  97     hv->table.entries = 0;
  98     hv->fill = 0;
  99     hv->holes = 0;
 100     if ( new_size < hv->table.size ) {
 101         Vector_resize( &tmp.table, 0, capture_item, hv );
 102     } else {
 103         Vector_iterate( &tmp.table, 0, iter_item, hv );
 104     }
 105 }
 106
 107 // Add the given element.
 108 int HashVector_add(HashVector *hv,void *item) {
 109     unsigned long i;
 110     void **p = HashVector_find_slot( hv, item, &i, 1 );
 111     if ( p == 0 ) {
 112         return -1; // OOM or overfull HashVector
 113     }
 114     if ( *p ) {
 115         if ( *p != HV_HOLE ) {
 116             return 0; // Already added.
 117         }
 118         hv->holes--; // about to reuse a hole
 119     }
 120     *p = item;
 121     hv->fill++;
 122     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
 123         HashVector_resize( hv, hv->table.size * 2 );
 124     }
 125     return 1;
 126 }
 127
 128 // Delete the given item
 129 int HashVector_delete(HashVector *hv,void *item) {
 130     unsigned long i;
 131     void **p = HashVector_find_slot( hv, item, &i, 1 );
 132     if ( p == 0 ) {
 133         return -1;
 134     }
 135     if ( *p != item ) {
 136         return 0;
 137     }
 138     // Check if subsequent slot is occupied
 139     if ( ++i >= hv->table.size ) {
 140         i = 0;
 141     }
 142     void **q = Vector_access( &hv->table, i, 0, 0 );
 143     if ( q && (*q) ) {
 144         *p = HV_HOLE;
 145         hv->holes++;
 146     } else {
 147         *p = 0;
 148     }
 149     hv->fill--;
 150     if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
 151          hv->fill < hv->table.size / 4 ) {
 152         HashVector_resize( hv, hv->table.size / 2 );
 153     }
 154     return 1;
 155 }
 156
 157 Vector *HashVector_contents(
 158     HashVector *hv,enum VectorVariant variant,Vector *v)
 159 {
 160     if ( v == 0 ) {
 161         if ( hv->fill == 0 ) {
 162             return 0;
 163         }
 164         v = (Vector*) malloc( sizeof( Vector ) );
 165     } else {
 166         Vector_resize( v, 0, Vector_clear_any, 0 );
 167     }
 168     (*v) = (Vector) { .variant = variant, 0, 0 };
 169     if ( hv->fill == 0 ) {
 170         return v;
 171     }
 172     Vector_resize( v, hv->fill, 0, 0 );
 173     VectorIndex i;
 174     VectorIndex j = 0;
 175     for ( i = 0; i < v->size; i++, j++ ) {
 176         Vector_set( v, i, HashVector_next( hv, &j ) );
 177     }
 178     return v;
 179 }
 180
 181 // A simple binary hashcode, (before modulo table size)
 182 unsigned long HashVector_hashcode(unsigned char *key,unsigned long n) {
 183     unsigned long value = 5381;
 184     while ( n-- ) {
 185         value += ( value << 5 ) + *(key++);
 186     }
 187     return value;
 188 }
 189
 190
 191 HashVector *HashVector_create(enum VectorVariant variant,ItemKeyFun *type) {
 192     HashVector *hv = (HashVector*) malloc( sizeof( HashVector ) );
 193     (*hv) = (HashVector) {
 194         .table = (Vector) {
 195             .variant = variant,
 196             .size = 16,
 197             .entries = 0
 198         },
 199         .fill = 0,
 200         .holes = 0,
 201         .type = type
 202     };
 203     return hv;
 204 }
 205