vector/hashvector.c

   1 #include "hashvector.h"
   2
   3 // Find the slot for the keyed element, and return pointer to it, or
   4 // to the first of holes encountered while considering collisions.
   5 // Returns a pointer to the place for the item, or 0 in case of OOM or
   6 // overfull hashvector (i.e. 0 shouldn't happen).
   7 static void **hashvector_find_slot(hashvector *hv,void *key) {
   8     unsigned long index = hv->keyhashcode( key ) % hv->table.size;
   9     unsigned long i = index;
  10     void **hole = 0;
  11     void **p = 0;
  12     for ( ;; ) {
  13         p = vector_entry(&hv->table, i);
  14         if ( p == 0 ) {
  15             return 0; // This basically means OOM, and is a failure condition.
  16         }
  17         if ( *p == 0 ) {
  18             break; // Not found
  19         }
  20         if ( (*p) == HV_HOLE ) {
  21             if ( hole == 0 ) {
  22                 hole = p; // Remember the first hole
  23             }
  24         } else if ( hv->haskey( *p, key ) ) {
  25             return p; // Found
  26         }
  27         if ( ++i == hv->table.size ) {
  28             i = 0; // Roll-around the table
  29         }
  30         if ( i == index ) {
  31             return 0; // Overfull hashvector!
  32         }
  33     }
  34     return ( hole )? hole : p;
  35 }
  36
  37 // Find the keyed element, and assign the x pointer, or assign 0.
  38 // Returns 1 if element is found and 0 otherwise.
  39 int hashvector_find(hashvector *hv,void *key,void **x) {
  40     void **p = hashvector_find_slot( hv, key );
  41     if ( p && *p && *p != HV_HOLE ) {
  42         if ( x ) {
  43             *x = *p;
  44         }
  45         return 1;
  46     }
  47     return 0;
  48 }
  49
  50 static int capture_item(vector *pv,unsigned long ix,void *item,void *data) {
  51     if ( item && item != HV_HOLE ) {
  52         hashvector_add( (hashvector *) data, item );
  53     }
  54     return 0;
  55 }
  56
  57 static int iter_item(unsigned long ix,void *item,void *data) {
  58     if ( item && item != HV_HOLE ) {
  59         hashvector_add( (hashvector *) data, item );
  60     }
  61     return 0;
  62 }
  63
  64 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
  65     hashvector tmp = *hv;
  66     hv->table.size = new_size;
  67     hv->table.entries = 0;
  68     hv->fill = 0;
  69     hv->holes = 0;
  70     if ( new_size < hv->table.size ) {
  71         vector_resize( &tmp.table, 0, capture_item, hv );
  72     } else {
  73         vector_iterate( &tmp.table, 0, iter_item, hv );
  74     }
  75 }
  76
  77 // Add the given element.
  78 int hashvector_add(hashvector *hv,void *item) {
  79     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
  80     if ( p == 0 ) {
  81         return -1; // OOM or overfull hashvector
  82     }
  83     if ( *p ) {
  84         if ( *p != HV_HOLE ) {
  85             return 0; // Already added.
  86         }
  87         hv->holes--; // about to reuse a hole
  88     }
  89     *p = item;
  90     hv->fill++;
  91     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
  92         hashvector_resize( hv, hv->table.size * 2 );
  93     }
  94     return 1;
  95 }
  96
  97 // Delete the given item
  98 int hashvector_delete(hashvector *hv,void *item) {
  99     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
 100     if ( p == 0 ) {
 101         return -1;
 102     }
 103     if ( *p != item ) {
 104         return 0;
 105     }
 106     *p = HV_HOLE;
 107     hv->holes++;
 108     hv->fill--;
 109     if ( hv->table.size > VECTOR_SLOTS && hv->fill < hv->table.size / 4 ) {
 110         hashvector_resize( hv, hv->table.size / 2 );
 111     }
 112     return 1;
 113 }
 114
 115 // Copy items into a vector. Returns 0 on success and -1 on failure.
 116 int hashvector_contents(hashvector *hv,vector *pv) {
 117     if ( vector_resize( pv, hv->fill, 0, 0 ) ) {
 118         return -1;
 119     }
 120     unsigned long from = 0;
 121     unsigned long to = 0;
 122     for ( ; to < hv->fill; from++ ) {
 123         void **slot = vector_next_used( &hv->table, &from );
 124         if ( slot == 0 ) {
 125             break;
 126         }
 127         if ( *slot != HV_HOLE ) {
 128             vector_set( pv, to++, *slot );
 129         }
 130     }
 131     return 0;
 132 }
 133
 134 // A simple binary hashcode, (before modulo table size)
 135 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
 136     unsigned long value = 5381;
 137     while ( n-- ) {
 138         value += ( value << 5 ) + *(key++);
 139     }
 140     return value;
 141 }
 142