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 "cl_hash.h"
   7 #include "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     // 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& key)
  43     {
  44         var long index = _slots[hashcode(key) % _modulus] - 1;
  45         while (index >= 0) {
  46             if (!(index < _size))
  47                 cl_abort();
  48             if (equal(key,_entries[index].entry.key))
  49                 return &_entries[index].entry.val;
  50             index = _entries[index].next - 1;
  51         }
  52         return NULL;
  53     }
  54     // Store (htset alias puthash).
  55     void put (const key1_type& key, const value_type& val)
  56     {
  57         var unsigned long hcode = hashcode(key);
  58         // Search whether it is already there.
  59         {
  60             var long index = _slots[hcode % _modulus] - 1;
  61             while (index >= 0) {
  62                 if (!(index < _size))
  63                     cl_abort();
  64                 if (equal(key,_entries[index].entry.key)) {
  65                     _entries[index].entry.val = val;
  66                     return;
  67                 }
  68                 index = _entries[index].next - 1;
  69             }
  70         }
  71         // Put it into the table.
  72         prepare_store();
  73         var long hindex = hcode % _modulus; // _modulus may have changed!
  74         var long index = get_free_index();
  75         new (&_entries[index].entry) cl_htentry1<key1_type,value_type> (key,val);
  76         _entries[index].next = _slots[hindex];
  77         _slots[hindex] = 1+index;
  78         _count++;
  79     }
  80     // Remove (htrem alias remhash).
  81     void remove (const key1_type& key)
  82     {
  83         var long* _index = &_slots[hashcode(key) % _modulus];
  84         while (*_index > 0) {
  85             var long index = *_index - 1;
  86             if (!(index < _size))
  87                 cl_abort();
  88             if (equal(key,_entries[index].entry.key)) {
  89                 // Remove _entries[index].entry
  90                 *_index = _entries[index].next;
  91                 _entries[index].~htxentry();
  92                 // The entry is now free.
  93                 put_free_index(index);
  94                 // That's it.
  95                 _count--;
  96                 return;
  97             }
  98             _index = &_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 !(defined(__sparc__) && !defined(__GNUC__))
 112         if (_freelist < -1)
 113             return;
 114         // Can we make room?
 115         if (_garcol_fun(this))
 116             if (_freelist < -1)
 117                 return;
 118         // No! Have to grow the hash table.
 119         grow();
 120       #else
 121         // workaround Sun C++ 4.1 inline function compiler bug
 122         if (_freelist >= -1) {
 123             if (!_garcol_fun(this) || (_freelist >= -1))
 124                 grow();
 125         }
 126       #endif
 127     }
 128     void grow ()
 129     {
 130         var long new_size = _size + (_size >> 1) + 1; // _size*1.5
 131         var long new_modulus = compute_modulus(new_size);
 132         var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
 133         var long* new_slots = (long*) ((char*)new_total_vector + 0);
 134         var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
 135         for (var long hi = new_modulus-1; hi >= 0; hi--)
 136             new_slots[hi] = 0;
 137         var long free_list_head = -1;
 138         for (var long i = new_size-1; i >= 0; i--) {
 139             new_entries[i].next = free_list_head;
 140             free_list_head = -2-i;
 141         }
 142         var htxentry* old_entries = _entries;
 143         for (var long old_index = 0; old_index < _size; old_index++)
 144             if (old_entries[old_index].next >= 0) {
 145                 var key1_type& key = old_entries[old_index].entry.key;
 146                 var value_type& val = old_entries[old_index].entry.val;
 147                 var long hindex = hashcode(key) % new_modulus;
 148                 var long index = -2-free_list_head;
 149                 free_list_head = new_entries[index].next;
 150                 new (&new_entries[index].entry) cl_htentry1<key1_type,value_type> (key,val);
 151                 new_entries[index].next = new_slots[hindex];
 152                 new_slots[hindex] = 1+index;
 153                 old_entries[old_index].~htxentry();
 154             }
 155         free_hook(_total_vector);
 156         _modulus = new_modulus;
 157         _size = new_size;
 158         _freelist = free_list_head;
 159         _slots = new_slots;
 160         _entries = new_entries;
 161         _total_vector = new_total_vector;
 162     }
 163 };
 164
 165 }  // namespace cln
 166
 167 #endif /* _CL_HASH1_H */