1 // Hash tables with 2 keys and a value
6 #include "base/hash/cl_hash.h"
7 #include "base/cl_iterator.h"
12 // - function bool equal (key1_type,key1_type);
13 // - function bool equal (key2_type,key2_type);
14 // - function unsigned long hashcode (key1_type,key2_type);
16 template <class key1_type, class key2_type, class value_type>
18 ALLOCATE_ANYWHERE(cl_htentry2)
22 const value_type& htvalue () { return val; }
23 cl_htentry2 (const key1_type& k1, const key2_type& k2, const value_type& v)
24 : key1 (k1), key2 (k2), val (v) {}
27 template <class key1_type, class key2_type, class value_type>
28 struct cl_heap_hashtable_2 : public cl_heap_hashtable <cl_htentry2 <key1_type,key2_type,value_type> > {
31 typedef cl_heap_hashtable <cl_htentry2 <key1_type,key2_type,value_type> > inherited;
32 typedef typename inherited::htxentry htxentry;
35 void* operator new (size_t size) { return malloc_hook(size); }
37 void operator delete (void* ptr) { free_hook(ptr); }
39 // Lookup (htref alias gethash).
40 // Returns a pointer which you should immediately dereference
42 value_type* get (const key1_type& key1, const key2_type& key2)
44 var long index = this->_slots[hashcode(key1,key2) % this->_modulus] - 1;
46 if (!(index < this->_size))
47 throw runtime_exception();
48 if (equal(key1,this->_entries[index].entry.key1)
49 && equal(key2,this->_entries[index].entry.key2))
50 return &this->_entries[index].entry.val;
51 index = this->_entries[index].next - 1;
55 // Store (htset alias puthash).
56 void put (const key1_type& key1, const key2_type& key2, const value_type& val)
58 var unsigned long hcode = hashcode(key1,key2);
59 // Search whether it is already there.
61 var long index = this->_slots[hcode % this->_modulus] - 1;
63 if (!(index < this->_size))
64 throw runtime_exception();
65 if (equal(key1,this->_entries[index].entry.key1)
66 && equal(key2,this->_entries[index].entry.key2)) {
67 this->_entries[index].entry.val = val;
70 index = this->_entries[index].next - 1;
73 // Put it into the table.
75 var long hindex = hcode % this->_modulus; // _modulus may have changed!
76 var long index = this->get_free_index();
77 new (&this->_entries[index].entry) cl_htentry2<key1_type,key2_type,value_type> (key1,key2,val);
78 this->_entries[index].next = this->_slots[hindex];
79 this->_slots[hindex] = 1+index;
82 // Remove (htrem alias remhash).
83 void remove (const key1_type& key1, const key2_type& key2)
85 var long* _index = &this->_slots[hashcode(key1,key2) % this->_modulus];
87 var long index = *_index - 1;
88 if (!(index < this->_size))
89 throw runtime_exception();
90 if (equal(key1,this->_entries[index].entry.key1)
91 && equal(key2,this->_entries[index].entry.key2)) {
92 // Remove _entries[index].entry
93 *_index = this->_entries[index].next;
94 this->_entries[index].~htxentry();
95 // The entry is now free.
96 this->put_free_index(index);
101 _index = &this->_entries[index].next;
104 // Iterate through the table.
105 // No stuff should be inserted into the table during the iteration,
106 // or you may find yourself iterating over an entry vector which has
107 // already been freed!
110 // Prepare a store operation: make sure that the free list is non-empty.
111 // This may change the table's size!
112 void prepare_store ()
114 if (this->_freelist < -1)
117 if (this->_garcol_fun(this))
118 if (this->_freelist < -1)
120 // No! Have to grow the hash table.
125 var long new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
126 var long new_modulus = inherited::compute_modulus(new_size);
127 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
128 var long* new_slots = (long*) ((char*)new_total_vector + 0);
129 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
130 for (var long hi = new_modulus-1; hi >= 0; hi--)
132 var long free_list_head = -1;
133 for (var long i = new_size-1; i >= 0; i--) {
134 new_entries[i].next = free_list_head;
135 free_list_head = -2-i;
137 var htxentry* old_entries = this->_entries;
138 for (var long old_index = 0; old_index < this->_size; old_index++)
139 if (old_entries[old_index].next >= 0) {
140 var key1_type& key1 = old_entries[old_index].entry.key1;
141 var key2_type& key2 = old_entries[old_index].entry.key2;
142 var value_type& val = old_entries[old_index].entry.val;
143 var long hindex = hashcode(key1,key2) % new_modulus;
144 var long index = -2-free_list_head;
145 free_list_head = new_entries[index].next;
146 new (&new_entries[index].entry) cl_htentry2<key1_type,key2_type,value_type> (key1,key2,val);
147 new_entries[index].next = new_slots[hindex];
148 new_slots[hindex] = 1+index;
149 old_entries[old_index].~htxentry();
151 free_hook(this->_total_vector);
152 this->_modulus = new_modulus;
153 this->_size = new_size;
154 this->_freelist = free_list_head;
155 this->_slots = new_slots;
156 this->_entries = new_entries;
157 this->_total_vector = new_total_vector;
163 #endif /* _CL_HASH2_H */