src/base/hash/cl_hashuniq.h

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