src/base/hash/cl_hash2.h

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