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