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 item
  60 void *HashVector_find(HashVector *hv,void *key) {
  61     VectorIndex index = 0;
  62     void **slot = HashVector_find_slot( hv, &index, key, 0 );
  63     return ( slot && *slot && *slot != HV_HOLE )? *slot : 0;
  64 }
  65
  66 // Find the keyed element at or after the index. Update index and
  67 // return item.
  68 void *HashVector_next(HashVector *hv,VectorIndex *index,void *key) {
  69     unsigned long i = index? *index : 0;
  70     for ( ; i < hv->table.size; i++ ) {
  71         void **p = Vector_next_used( &hv->table, &i );
  72         if ( p == 0 ) {
  73             break;
  74         }
  75         if ( *p && *p != HV_HOLE ) {
  76             if ( key && hv->type->haskey( hv->type, *p, key ) == 0 ) {
  77                 continue;
  78             }
  79             if ( index ) {
  80                 (*index) = i;
  81             }
  82             return *p;
  83         }
  84     }
  85     if ( index ) {
  86         (*index) = hv->table.size;
  87     }
  88     return 0;
  89 }
  90
  91 static int capture_item(Vector *pv,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 int iter_item(unsigned long ix,void *item,void *data) {
  99     if ( item && item != HV_HOLE ) {
 100         HashVector_add( (HashVector *) data, item );
 101     }
 102     return 0;
 103 }
 104
 105 static void HashVector_resize(HashVector *hv,unsigned long new_size) {
 106     HashVector tmp = *hv;
 107     hv->table.size = new_size;
 108     hv->table.entries = 0;
 109     hv->fill = 0;
 110     hv->holes = 0;
 111     if ( new_size < hv->table.size ) {
 112         Vector_resize( &tmp.table, 0, capture_item, hv );
 113     } else {
 114         Vector_iterate( &tmp.table, 0, iter_item, hv );
 115     }
 116 }
 117
 118 // Add the given element.
 119 int HashVector_add(HashVector *hv,void *item) {
 120     unsigned long i;
 121     void **p = HashVector_find_slot( hv, item, &i, 1 );
 122     if ( p == 0 ) {
 123         return -1; // OOM or overfull HashVector
 124     }
 125     if ( *p ) {
 126         if ( *p != HV_HOLE ) {
 127             return 0; // Already added.
 128         }
 129         hv->holes--; // about to reuse a hole
 130     }
 131     *p = item;
 132     hv->fill++;
 133     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
 134         HashVector_resize( hv, hv->table.size * 2 );
 135     }
 136     return 1;
 137 }
 138
 139 // Delete the given item
 140 int HashVector_delete(HashVector *hv,void *item) {
 141     unsigned long i;
 142     void **p = HashVector_find_slot( hv, item, &i, 1 );
 143     if ( p == 0 ) {
 144         return -1;
 145     }
 146     if ( *p != item ) {
 147         return 0;
 148     }
 149     // Check if subsequent slot is occupied
 150     if ( ++i >= hv->table.size ) {
 151         i = 0;
 152     }
 153     void **q = Vector_access( &hv->table, i, 0, 0 );
 154     if ( q && (*q) ) {
 155         *p = HV_HOLE;
 156         hv->holes++;
 157     } else {
 158         *p = 0;
 159     }
 160     hv->fill--;
 161     if ( hv->table.size > VECTOR_SLOTS( &hv->table ) &&
 162          hv->fill < hv->table.size / 4 ) {
 163         HashVector_resize( hv, hv->table.size / 2 );
 164     }
 165     return 1;
 166 }
 167
 168 Vector *HashVector_contents(
 169     HashVector *hv,enum VectorVariant variant,Vector *v)
 170 {
 171     if ( v == 0 ) {
 172         if ( hv->fill == 0 ) {
 173             return 0;
 174         }
 175         v = (Vector*) malloc( sizeof( Vector ) );
 176     } else {
 177         Vector_resize( v, 0, Vector_clear_any, 0 );
 178     }
 179     (*v) = (Vector) { .variant = variant, 0, 0 };
 180     if ( hv->fill == 0 ) {
 181         return v;
 182     }
 183     Vector_resize( v, hv->fill, 0, 0 );
 184     VectorIndex i;
 185     VectorIndex j = 0;
 186     for ( i = 0; i < v->size; i++, j++ ) {
 187         Vector_set( v, i, HashVector_next( hv, &j, 0 ) );
 188     }
 189     return v;
 190 }
 191
 192 // A simple binary hashcode, (before modulo table size)
 193 unsigned long HashVector_hashcode(unsigned char *key,unsigned long n) {
 194     unsigned long value = 5381;
 195     while ( n-- ) {
 196         value += ( value << 5 ) + *(key++);
 197     }
 198     return value;
 199 }
 200
 201
 202 HashVector *HashVector_create(enum VectorVariant variant,ItemKeyFun *type) {
 203     HashVector *hv = (HashVector*) malloc( sizeof( HashVector ) );
 204     (*hv) = (HashVector) {
 205         .table = (Vector) {
 206             .variant = variant,
 207             .size = 16,
 208             .entries = 0
 209         },
 210         .fill = 0,
 211         .holes = 0,
 212         .type = type
 213     };
 214     return hv;
 215 }
 216