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