pvector/hashvector.c

   1 #include "hashvector.h"
   2
   3 // Find the slot for the keyed element, and return pointer to it.
   4 static void **hashvector_find_slot(hashvector *hv,void *key) {
   5     unsigned int index = hv->keyhashcode( key ) % hv->table.size;
   6     unsigned int i = index;
   7     void **hole = 0;
   8     for ( ;; ) {
   9         void **p = pvector_entry(&hv->table, i);
  10         if ( p == 0 ) {
  11             return 0;
  12         }
  13         if ( *p ) {
  14             if ( (*p) != HV_HOLE ) {
  15                 if ( hv->haskey( *p, key ) ) {
  16                     return p;
  17                 }
  18             } else {
  19                 if ( hole == 0 ) {
  20                     hole = p;
  21                 }
  22                 if ( ++i == hv->table.size ) {
  23                     i = 0;
  24                 }
  25                 if ( i != index ) {
  26                     continue;
  27                 }
  28             }
  29         }
  30         return ( hole )? hole : p;
  31     }
  32 }
  33
  34 // Find the keyed element, and assign the x pointer, or assign 0.
  35 // Returns 1 if element is found and 0 otherwise.
  36 int hashvector_find(hashvector *hv,void *key,void **x) {
  37     void **p = hashvector_find_slot( hv, key );
  38     if ( p && *p && *p != HV_HOLE ) {
  39         *x = *p;
  40         return 1;
  41     }
  42     return 0;
  43 }
  44
  45 static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) {
  46     if ( item != HV_HOLE ) {
  47         hashvector_add( (hashvector *) data, item );
  48     }
  49     return 0;
  50 }
  51
  52 static void hashvector_resize(hashvector *hv,unsigned int new_size) {
  53     hashvector tmp = *hv;
  54     hv->table.size = new_size;
  55     hv->table.entries = 0;
  56     hv->fill = 0;
  57     hv->holes = 0;
  58     pvector_resize( &tmp.table, 0, capture_item, hv );
  59 }
  60
  61 // Add the given element.
  62 void hashvector_add(hashvector *hv,void *item) {
  63     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
  64     if ( p ) {
  65         if ( *p ) {
  66             if ( *p != HV_HOLE ) {
  67                 return;
  68             }
  69             hv->holes--;
  70         }
  71         *p = item;
  72         hv->fill++;
  73         if ( hv->fill + hv->holes > hv->table.size / 2 ) {
  74             hashvector_resize( hv, hv->table.size * 2 );
  75         }
  76     }
  77 }
  78
  79 // Return the next element starting at i, or 0 if there are no more.
  80 // Also increment the index to be of the element + 1, or -1 if there
  81 // are no more elements.
  82 //unsigned char *htnext(htable *table,int *i);
  83
  84 // Delete the given element.
  85 void hashvector_delete(hashvector *hv,void *item) {
  86     void **p = hashvector_find_slot( hv, hv->itemkey( item ) );
  87     if ( p && *p && *p != HV_HOLE ) {
  88         *p = HV_HOLE;
  89         hv->holes++;
  90         if ( hv->table.size > 256 ) {
  91             if ( hv->fill < hv->table.size / 2 ) {
  92                 hashvector_resize( hv, hv->table.size / 2 );
  93             }
  94         }
  95     }
  96 }
  97
  98 // Copy items into a pvector. Returns 0 on success and -1 on failure.
  99 int hashvector_pack(hashvector *hv,pvector *pv) {
 100     if ( pvector_resize( pv, hv->fill, 0, 0 ) ) {
 101         return -1;
 102     }
 103     unsigned long from = 0;
 104     unsigned long to = 0;
 105     while ( to < hv->fill ) {
 106         void **slot = pvector_next_used( &hv->table, &from, 0, 0 );
 107         if ( slot ) {
 108             if ( *slot != HV_HOLE ) {
 109                 pvector_set( pv, to++, *slot );
 110             }
 111             from++;
 112         } else {
 113             break;
 114         }
 115     }
 116     return 0;
 117 }