src/base/hash/cl_hash.h

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