1 // Hash tables with 2 keys and a value
7 #include "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) {}
25 #if (defined(__rs6000__) && !defined(__GNUC__))
30 template <class key1_type, class key2_type, class value_type>
31 struct cl_heap_hashtable_2 : public cl_heap_hashtable <cl_htentry2 <key1_type,key2_type,value_type> > {
33 void* operator new (size_t size) { return malloc_hook(size); }
35 void operator delete (void* ptr) { free_hook(ptr); }
37 // Lookup (htref alias gethash).
38 // Returns a pointer which you should immediately dereference
40 value_type* get (const key1_type& key1, const key2_type& key2)
42 var long index = _slots[hashcode(key1,key2) % _modulus] - 1;
46 if (equal(key1,_entries[index].entry.key1)
47 && equal(key2,_entries[index].entry.key2))
48 return &_entries[index].entry.val;
49 index = _entries[index].next - 1;
53 // Store (htset alias puthash).
54 void put (const key1_type& key1, const key2_type& key2, const value_type& val)
56 var unsigned long hcode = hashcode(key1,key2);
57 // Search whether it is already there.
59 var long index = _slots[hcode % _modulus] - 1;
63 if (equal(key1,_entries[index].entry.key1)
64 && equal(key2,_entries[index].entry.key2)) {
65 _entries[index].entry.val = val;
68 index = _entries[index].next - 1;
71 // Put it into the table.
73 var long hindex = hcode % _modulus; // _modulus may have changed!
74 var long index = get_free_index();
75 new (&_entries[index].entry) cl_htentry2<key1_type,key2_type,value_type> (key1,key2,val);
76 _entries[index].next = _slots[hindex];
77 _slots[hindex] = 1+index;
80 // Remove (htrem alias remhash).
81 void remove (const key1_type& key1, const key2_type& key2)
83 var long* _index = &_slots[hashcode(key1,key2) % _modulus];
85 var long index = *_index - 1;
88 if (equal(key1,_entries[index].entry.key1)
89 && equal(key2,_entries[index].entry.key2)) {
90 // Remove _entries[index].entry
91 *_index = _entries[index].next;
92 _entries[index].~htxentry();
93 // The entry is now free.
94 put_free_index(index);
99 _index = &_entries[index].next;
102 // Iterate through the table.
103 // No stuff should be inserted into the table during the iteration,
104 // or you may find yourself iterating over an entry vector which has
105 // already been freed!
108 // Prepare a store operation: make sure that the free list is non-empty.
109 // This may change the table's size!
110 void prepare_store ()
112 #if !(defined(__sparc__) && !defined(__GNUC__))
116 if (_garcol_fun(this))
119 // No! Have to grow the hash table.
122 // workaround Sun C++ 4.1 inline function compiler bug
123 if (_freelist >= -1) {
124 if (!_garcol_fun(this) || (_freelist >= -1))
131 var long new_size = _size + (_size >> 1) + 1; // _size*1.5
132 var long new_modulus = compute_modulus(new_size);
133 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
134 var long* new_slots = (long*) ((char*)new_total_vector + 0);
135 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
136 for (var long hi = new_modulus-1; hi >= 0; hi--)
138 var long free_list_head = -1;
139 for (var long i = new_size-1; i >= 0; i--) {
140 new_entries[i].next = free_list_head;
141 free_list_head = -2-i;
143 var htxentry* old_entries = _entries;
144 for (var long old_index = 0; old_index < _size; old_index++)
145 if (old_entries[old_index].next >= 0) {
146 var key1_type& key1 = old_entries[old_index].entry.key1;
147 var key2_type& key2 = old_entries[old_index].entry.key2;
148 var value_type& val = old_entries[old_index].entry.val;
149 var long hindex = hashcode(key1,key2) % new_modulus;
150 var long index = -2-free_list_head;
151 free_list_head = new_entries[index].next;
152 new (&new_entries[index].entry) cl_htentry2<key1_type,key2_type,value_type> (key1,key2,val);
153 new_entries[index].next = new_slots[hindex];
154 new_slots[hindex] = 1+index;
155 old_entries[old_index].~htxentry();
157 free_hook(_total_vector);
158 _modulus = new_modulus;
160 _freelist = free_list_head;
162 _entries = new_entries;
163 _total_vector = new_total_vector;
169 #endif /* _CL_HASH2_H */