6 #include "cln/object.h"
7 #include "cln/malloc.h"
8 #include "cln/exception.h"
9 #include "base/cl_iterator.h"
13 const intptr_t htentry_last = 0; // means that there is no next entry
15 // These forward declarations are needed for Sun CC 3.0.1 and 4.0.1.
16 template <class htentry> struct _cl_hashtable_iterator;
18 template <class htentry>
19 struct cl_heap_hashtable : public cl_heap {
20 friend struct _cl_hashtable_iterator<htentry>;
22 typedef struct htxentry {
23 intptr_t 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
29 intptr_t _modulus; // size of the primary entry table, > 0
30 intptr_t _size; // maximum number of entries
31 intptr_t _count; // current number of entries
32 intptr_t _freelist; // start of pseudo-free-list
33 intptr_t * _slots; // vector of length _modulus
34 htxentry * _entries; // vector of length _size
36 bool (*_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.
41 void* operator new (size_t size) { return malloc_hook(size); }
43 void operator delete (void* ptr) { free_hook(ptr); }
44 // Constructor: build a new, empty table.
45 cl_heap_hashtable (intptr_t initial_size = 5) : cl_heap (),
46 _size (initial_size), _count (0), _garcol_fun (no_garcol)
48 _modulus = compute_modulus(_size);
49 _total_vector = malloc_hook(_modulus*sizeof(intptr_t) + _size*sizeof(htxentry));
50 _slots = (intptr_t*) ((char*)_total_vector + 0);
51 _entries = (htxentry *) ((char*)_total_vector + _modulus*sizeof(intptr_t));
52 for (var intptr_t hi = _modulus-1; hi >= 0; hi--)
54 var intptr_t free_list_head = -1;
55 for (var intptr_t i = _size-1; i >= 0; i--) {
56 _entries[i].next = free_list_head;
57 free_list_head = -2-i;
59 _freelist = free_list_head;
64 for (intptr_t i = 0; i < _size; i++)
65 if (_entries[i].next >= 0)
66 _entries[i].~htxentry();
67 free_hook(_total_vector);
69 // Count number of entries.
70 intptr_t num_entries ()
74 for (intptr_t i = 0; i < _size; i++)
75 if (_entries[i].next >= 0)
79 /* We already have an up-to-date count. */
84 _cl_hashtable_iterator<htentry> iterator ();
86 // Compute the modulus, given the maximum number of entries.
87 static intptr_t compute_modulus (intptr_t size)
89 // It should be somewhat greater than size, since we want to
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)).
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 intptr_t m = 1*size;
111 // Make sure m is not divisible by 2.
114 // Make sure m is not divisible by 3.
117 // Make sure m is not divisible by 5.
125 // Return the index of a free entry. Assumes the free list is non-empty.
126 intptr_t get_free_index ()
128 // Check whether there is some in the free list.
129 if (_freelist < -1) {
130 var intptr_t index = -2-_freelist;
131 _freelist = _entries[index].next;
134 throw runtime_exception();
137 // Put a free index into the free list.
138 void put_free_index (intptr_t index)
140 _entries[index].next = _freelist;
141 _freelist = -2-index;
144 // Default function to make room in a hash table.
145 static bool no_garcol (cl_heap* ht) { unused ht; return false; }
148 template <class htentry>
149 struct _cl_hashtable_iterator
150 : cl_abstract_iterator<htentry>
153 typename cl_heap_hashtable<htentry>::htxentry * _entries;
156 _cl_hashtable_iterator () : _entries (0), _index (-1) {}
158 _cl_hashtable_iterator (typename cl_heap_hashtable<htentry>::htxentry * e, intptr_t i)
159 : _entries (e), _index (i)
162 while (_index >= 0 && _entries[_index].next < 0);
165 bool endp () { return (_index < 0); }
169 throw runtime_exception();
170 var intptr_t old_index = _index;
172 while (_index >= 0 && _entries[_index].next < 0);
173 return _entries[old_index].entry;
177 template <class htentry>
178 inline _cl_hashtable_iterator<htentry> cl_heap_hashtable<htentry>::iterator ()
180 return _cl_hashtable_iterator<htentry>(_entries,_size);
185 #endif /* _CL_HASH_H */