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