src/base/hash/cl_hashset.h

   1 // Hash sets (hash tables with 1 key and no value)
   2
   3 #ifndef _CL_HASHSET_H
   4 #define _CL_HASHSET_H
   5
   6 #include "base/hash/cl_hash.h"
   7 #include "base/cl_iterator.h"
   8
   9 namespace cln {
  10
  11 // Requirements:
  12 // - function  bool equal (key1_type,key1_type);
  13 // - function  unsigned long hashcode (key1_type);
  14
  15 template <class key1_type>
  16 struct cl_htsetentry {
  17     ALLOCATE_ANYWHERE(cl_htsetentry)
  18     key1_type key;
  19     cl_htsetentry (const key1_type& k)
  20         : key (k) {}
  21 };
  22
  23 template <class key1_type>
  24 struct cl_heap_hashtable_set : public cl_heap_hashtable <cl_htsetentry <key1_type> > {
  25 protected:
  26     // Abbreviations.
  27     typedef cl_heap_hashtable <cl_htsetentry <key1_type> > inherited;
  28     typedef typename inherited::htxentry htxentry;
  29 public:
  30     // Allocation.
  31     void* operator new (size_t size) { return malloc_hook(size); }
  32     // Deallocation.
  33     void operator delete (void* ptr) { free_hook(ptr); }
  34 public:
  35     // Lookup (htref alias gethash).
  36     bool get (const key1_type& key)
  37     {
  38         var long index = this->_slots[hashcode(key) % this->_modulus] - 1;
  39         while (index >= 0) {
  40             if (!(index < this->_size))
  41                 throw runtime_exception();
  42             if (equal(key,this->_entries[index].entry.key))
  43                 return true;
  44             index = this->_entries[index].next - 1;
  45         }
  46         return false;
  47     }
  48     // Store (htset alias puthash).
  49     void put (const key1_type& key)
  50     {
  51         var unsigned long hcode = hashcode(key);
  52         // Search whether it is already there.
  53         {
  54             var long index = this->_slots[hcode % this->_modulus] - 1;
  55             while (index >= 0) {
  56                 if (!(index < this->_size))
  57                     throw runtime_exception();
  58                 if (equal(key,this->_entries[index].entry.key))
  59                     return;
  60                 index = this->_entries[index].next - 1;
  61             }
  62         }
  63         // Put it into the table.
  64         prepare_store();
  65         var long hindex = hcode % this->_modulus; // _modulus may have changed!
  66         var long index = this->get_free_index();
  67         new (&this->_entries[index].entry) cl_htsetentry<key1_type> (key);
  68         this->_entries[index].next = this->_slots[hindex];
  69         this->_slots[hindex] = 1+index;
  70         this->_count++;
  71     }
  72     // Remove (htrem alias remhash).
  73     void remove (const key1_type& key)
  74     {
  75         var long* _index = &this->_slots[hashcode(key) % this->_modulus];
  76         while (*_index > 0) {
  77             var long index = *_index - 1;
  78             if (!(index < this->_size))
  79                 throw runtime_exception();
  80             if (equal(key,this->_entries[index].entry.key)) {
  81                 // Remove _entries[index].entry
  82                 *_index = this->_entries[index].next;
  83                 this->_entries[index].~htxentry();
  84                 // The entry is now free.
  85                 this->put_free_index(index);
  86                 // That's it.
  87                 this->_count--;
  88                 return;
  89             }
  90             _index = &this->_entries[index].next;
  91         }
  92     }
  93     // Iterate through the table.
  94     // No stuff should be inserted into the table during the iteration,
  95     // or you may find yourself iterating over an entry vector which has
  96     // already been freed!
  97     // ??
  98 private:
  99     // Prepare a store operation: make sure that the free list is non-empty.
 100     // This may change the table's size!
 101     void prepare_store ()
 102     {
 103       #if !(defined(__sparc__) && !defined(__GNUC__))
 104         if (this->_freelist < -1)
 105             return;
 106         // Can we make room?
 107         if (_garcol_fun(this))
 108             if (this->_freelist < -1)
 109                 return;
 110         // No! Have to grow the hash table.
 111         grow();
 112       #else
 113         // workaround Sun C++ 4.1 inline function compiler bug
 114         if (this->_freelist >= -1) {
 115             if (!_garcol_fun(this) || (this->_freelist >= -1))
 116                 grow();
 117         }
 118       #endif
 119     }
 120     void grow ()
 121     {
 122         var long new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
 123         var long new_modulus = inherited::compute_modulus(new_size);
 124         var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
 125         var long* new_slots = (long*) ((char*)new_total_vector + 0);
 126         var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
 127         for (var long hi = new_modulus-1; hi >= 0; hi--)
 128             new_slots[hi] = 0;
 129         var long free_list_head = -1;
 130         for (var long i = new_size-1; i >= 0; i--) {
 131             new_entries[i].next = free_list_head;
 132             free_list_head = -2-i;
 133         }
 134         var htxentry* old_entries = this->_entries;
 135         for (var long old_index = 0; old_index < this->_size; old_index++)
 136             if (old_entries[old_index].next >= 0) {
 137                 var key1_type& key = old_entries[old_index].entry.key;
 138                 var long hindex = hashcode(key) % new_modulus;
 139                 var long index = -2-free_list_head;
 140                 free_list_head = new_entries[index].next;
 141                 new (&new_entries[index].entry) cl_htsetentry<key1_type> (key);
 142                 new_entries[index].next = new_slots[hindex];
 143                 new_slots[hindex] = 1+index;
 144                 old_entries[old_index].~htxentry();
 145             }
 146         free_hook(this->_total_vector);
 147         this->_modulus = new_modulus;
 148         this->_size = new_size;
 149         this->_freelist = free_list_head;
 150         this->_slots = new_slots;
 151         this->_entries = new_entries;
 152         this->_total_vector = new_total_vector;
 153     }
 154 };
 155
 156 }  // namespace cln
 157
 158 #endif /* _CL_HASHSET_H */