src/base/hash/cl_hash.h

   1 // General hashtables
   2
   3 #ifndef _CL_HASH_H
   4 #define _CL_HASH_H
   5
   6 #include "cln/object.h"
   7 #include "cln/malloc.h"
   8 #include "cln/abort.h"
   9 #include "cl_iterator.h"
  10
  11 namespace cln {
  12
  13 const long htentry_last = 0; // means that there is no next entry
  14
  15 // These forward declarations are needed for Sun CC 3.0.1 and 4.0.1.
  16 template <class htentry> struct _cl_hashtable_iterator;
  17
  18 template <class htentry>
  19 struct cl_heap_hashtable : public cl_heap {
  20         friend struct _cl_hashtable_iterator<htentry>;
  21 protected:
  22     typedef struct htxentry {
  23         long next;     // > 0: pseudo-list continues at next-1
  24                        // == 0: end of pseudo-list
  25                        // == -1: end of pseudo-free-list
  26                        // < -1: part of pseudo-free-list, continues at -next-2
  27         htentry entry; // if next >= 0
  28     } htxentry;
  29     long _modulus; // size of the primary entry table, > 0
  30     long _size;  // maximum number of entries
  31     long _count; // current number of entries
  32     long _freelist; // start of pseudo-free-list
  33     long * _slots;  // vector of length _modulus
  34     htxentry * _entries; // vector of length _size
  35     void* _total_vector;
  36     cl_boolean (*_garcol_fun) (cl_heap*); // Function to make room in the table.
  37                                // Putting some intelligent function here turns
  38                                // a normal hash table into a "weak" hash table.
  39 public:
  40     // Allocation.
  41     void* operator new (size_t size) { return malloc_hook(size); }
  42     // Deallocation.
  43     void operator delete (void* ptr) { free_hook(ptr); }
  44     // Constructor: build a new, empty table.
  45     cl_heap_hashtable (long initial_size = 5) : cl_heap (),
  46         _size (initial_size), _count (0), _garcol_fun (no_garcol)
  47     {
  48         _modulus = compute_modulus(_size);
  49         _total_vector = malloc_hook(_modulus*sizeof(long) + _size*sizeof(htxentry));
  50         _slots = (long*) ((char*)_total_vector + 0);
  51         _entries = (htxentry *) ((char*)_total_vector + _modulus*sizeof(long));
  52         for (var long hi = _modulus-1; hi >= 0; hi--)
  53             _slots[hi] = 0;
  54         var long free_list_head = -1;
  55         for (var long i = _size-1; i >= 0; i--) {
  56             _entries[i].next = free_list_head;
  57             free_list_head = -2-i;
  58         }
  59         _freelist = free_list_head;
  60     }
  61     // Destructor.
  62     ~cl_heap_hashtable ()
  63     {
  64         for (long i = 0; i < _size; i++)
  65             if (_entries[i].next >= 0)
  66                 _entries[i].~htxentry();
  67         free_hook(_total_vector);
  68     }
  69     // Count number of entries.
  70     long num_entries ()
  71     {
  72         #if 0
  73         var long n = 0;
  74         for (long i = 0; i < _size; i++)
  75             if (_entries[i].next >= 0)
  76                 n++;
  77         return n;
  78         #else
  79         /* We already have an up-to-date count. */
  80         return _count;
  81         #endif
  82     }
  83     // Iterator.
  84     _cl_hashtable_iterator<htentry> iterator ();
  85 protected:
  86     // Compute the modulus, given the maximum number of entries.
  87     static long compute_modulus (long size)
  88     {
  89         // It should be somewhat greater than size, since we want to
  90         // avoid collisions.
  91         // With N = size and M = modulus := k*size, the probability for a
  92         // * primary slot to be empty is
  93         //     (1-1/M)^N == exp(-N/M) == exp(-1/k).
  94         // * primary slot to carry a pseudo-list of length 1 is
  95         //     N 1/M (1-1/M)^(N-1) == exp(-N/M)*N/M == exp(-1/k)*1/k.
  96         // * primary slot to carry a pseudo-list of length >1 (collision) is
  97         //     1 - (1-1/M)^N - N 1/M (1-1/M)^(N-1)
  98         //     == 1 - exp(-N/M)*(1 + N/M) == 1 - (exp(-1/k)*(1+1/k)).
  99         // Sample values:
 100         //              = 0   = 1   > 1
 101         //   k = 1.0   0.37  0.37  0.26
 102         //   k = 1.5   0.51  0.34  0.14
 103         //   k = 2.0   0.61  0.30  0.09
 104         // I think k = 1.0 is reasonable.
 105         // Furthermore, we make sure that M is not divisible by 2, 3, 5.
 106         // Because in some applications, the hash codes are divisible
 107         // by 2 or 3, and if the modulus were divisible by this number,
 108         // only every second or every third primary slot would be filled,
 109         // resulting in many collisions.
 110         var long m = 1*size;
 111         // Make sure m is not divisible by 2.
 112         if ((m % 2) == 0)
 113             m++;
 114         // Make sure m is not divisible by 3.
 115         if ((m % 3) == 0)
 116             m += 2;
 117         // Make sure m is not divisible by 5.
 118         if ((m % 5) == 0) {
 119             m += 2;
 120             if ((m % 3) == 0)
 121                 m += 2;
 122         }
 123         return m;
 124     }
 125     // Return the index of a free entry. Assumes the free list is non-empty.
 126     long get_free_index ()
 127     {
 128         // Check whether there is some in the free list.
 129         if (_freelist < -1) {
 130             var long index = -2-_freelist;
 131             _freelist = _entries[index].next;
 132             return index;
 133         }
 134         #if !(defined(__hppa__) && !defined(__GNUC__)) // workaround HP CC problem
 135         cl_abort();
 136         #endif
 137         return -1; // dummy
 138     }
 139     // Put a free index into the free list.
 140     void put_free_index (long index)
 141     {
 142         _entries[index].next = _freelist;
 143         _freelist = -2-index;
 144     }
 145 private:
 146     // Default function to make room in a hash table.
 147     static cl_boolean no_garcol (cl_heap* ht) { unused ht; return cl_false; }
 148 };
 149
 150 template <class htentry>
 151 struct _cl_hashtable_iterator
 152   #if !(defined(__mips__) && !defined(__GNUC__)) // workaround SGI CC bug
 153     : cl_abstract_iterator<htentry>
 154   #endif
 155 {
 156 private:
 157     typename cl_heap_hashtable<htentry>::htxentry * _entries;
 158     long _index;
 159 public:
 160     _cl_hashtable_iterator () : _entries (0), _index (-1) {}
 161 public: /* ugh */
 162     _cl_hashtable_iterator (typename cl_heap_hashtable<htentry>::htxentry * e, long i)
 163         : _entries (e), _index (i)
 164     {
 165         do { _index--; }
 166            while (_index >= 0 && _entries[_index].next < 0);
 167     }
 168 public:
 169     bool endp () { return (_index < 0); }
 170     htentry& next ()
 171     {
 172         if (_index < 0)
 173             cl_abort();
 174         var long old_index = _index;
 175         do { _index--; }
 176            while (_index >= 0 && _entries[_index].next < 0);
 177         return _entries[old_index].entry;
 178     }
 179 };
 180
 181 template <class htentry>
 182 inline _cl_hashtable_iterator<htentry> cl_heap_hashtable<htentry>::iterator ()
 183 {
 184 #if defined(__GNUC__)
 185     return _cl_hashtable_iterator<htentry>::_cl_hashtable_iterator(_entries,_size);
 186 #else // workaround most C++ compilers' bug
 187     typedef _cl_hashtable_iterator<htentry> _cl_hashtable_iterator_type;
 188     return _cl_hashtable_iterator_type(_entries,_size);
 189 #endif
 190 }
 191
 192 }  // namespace cln
 193
 194 #endif /* _CL_HASH_H */