src/base/hash/cl_hash1.h

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