pvector/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 = pvector_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         *x = *p;
  43         return 1;
  44     }
  45     return 0;
  46 }
  47
  48 static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) {
  49     if ( item != HV_HOLE ) {
  50         hashvector_add( (hashvector *) data, item );
  51     }
  52     return 0;
  53 }
  54
  55 static void hashvector_resize(hashvector *hv,unsigned long new_size) {
  56     hashvector tmp = *hv;
  57     hv->table.size = new_size;
  58     hv->table.entries = 0;
  59     hv->fill = 0;
  60     hv->holes = 0;
  61     pvector_resize( &tmp.table, 0, capture_item, hv );
  62 }
  63
  64 // Add the given element.
  65 int hashvector_add(hashvector *hv,void *item) {
  66     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
  67     if ( p == 0 ) {
  68         return -1; // OOM or overfull hashvector
  69     }
  70     if ( *p ) {
  71         if ( *p != HV_HOLE ) {
  72             return 0; // Already added.
  73         }
  74         hv->holes--; // about to reuse a hole
  75     }
  76     *p = item;
  77     hv->fill++;
  78     if ( hv->fill + hv->holes > hv->table.size / 2 ) {
  79         hashvector_resize( hv, hv->table.size * 2 );
  80     }
  81     return 1;
  82 }
  83
  84 // Delete the given item
  85 int hashvector_delete(hashvector *hv,void *item) {
  86     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
  87     if ( p == 0 ) {
  88         return -1;
  89     }
  90     if ( *p != item ) {
  91         return 0;
  92     }
  93     *p = HV_HOLE;
  94     hv->holes++;
  95     if ( hv->table.size > 256 ) {
  96         if ( hv->fill < hv->table.size / 2 ) {
  97             hashvector_resize( hv, hv->table.size / 2 );
  98         }
  99     }
 100     return 1;
 101 }
 102
 103 // Copy items into a pvector. Returns 0 on success and -1 on failure.
 104 int hashvector_contents(hashvector *hv,pvector *pv) {
 105     if ( pvector_resize( pv, hv->fill, 0, 0 ) ) {
 106         return -1;
 107     }
 108     unsigned long from = 0;
 109     unsigned long to = 0;
 110     while ( to < hv->fill ) {
 111         void **slot = pvector_next_used( &hv->table, &from, 0, 0 );
 112         if ( slot ) {
 113             if ( *slot != HV_HOLE ) {
 114                 pvector_set( pv, to++, *slot );
 115             }
 116             from++;
 117         } else {
 118             break;
 119         }
 120     }
 121     return 0;
 122 }
 123
 124 // A simple binary hashcode, (before modulo table size)
 125 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n) {
 126     unsigned long value = 5381;
 127     while ( n-- ) {
 128         value += ( value << 5 ) + *(key++);
 129     }
 130     return value;
 131 }
 132