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