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