1 // Hash tables for making objects unique
7 #include "cl_iterator.h"
11 // In such a hash table an entry's key is determined by its value
12 // and not stored explicitly.
15 // - function bool equal (key1_type,key1_type);
16 // - function unsigned long hashcode (key1_type);
17 // - function key1_type hashkey (value_type);
18 // - constructor value_type::value_type (struct hashuniq *, key1_type);
20 template <class key1_type, class value_type>
21 struct cl_htuniqentry {
22 ALLOCATE_ANYWHERE(cl_htuniqentry)
24 const value_type& htvalue () { return val; }
25 cl_htuniqentry (const value_type& v)
27 #if (defined(__rs6000__) && !defined(__GNUC__))
32 template <class key1_type, class value_type>
33 struct cl_heap_hashtable_uniq : public cl_heap_hashtable <cl_htuniqentry <key1_type,value_type> > {
36 typedef cl_heap_hashtable <cl_htuniqentry <key1_type,value_type> > inherited;
37 typedef typename inherited::htxentry htxentry;
40 void* operator new (size_t size) { return malloc_hook(size); }
42 void operator delete (void* ptr) { free_hook(ptr); }
44 // Lookup (htref alias gethash).
45 // Returns a pointer which you should immediately dereference
47 value_type * get (const key1_type& key)
49 var long index = this->_slots[hashcode(key) % this->_modulus] - 1;
51 if (!(index < this->_size))
52 throw runtime_exception();
53 if (equal(key,hashkey(this->_entries[index].entry.val)))
54 return &this->_entries[index].entry.val;
55 index = this->_entries[index].next - 1;
59 // Store (htset alias puthash).
60 void put (const key1_type& key)
62 var unsigned long hcode = hashcode(key);
63 // Search whether it is already there.
65 var long index = this->_slots[hcode % this->_modulus] - 1;
67 if (!(index < this->_size))
68 throw runtime_exception();
69 if (equal(key,hashkey(this->_entries[index].entry.val)))
71 index = this->_entries[index].next - 1;
74 // Put it into the table.
76 var long hindex = hcode % this->_modulus; // _modulus may have changed!
77 var long index = this->get_free_index();
78 new (&this->_entries[index].entry) cl_htuniqentry<key1_type,value_type> (value_type((struct hashuniq *)0, key));
79 this->_entries[index].next = this->_slots[hindex];
80 this->_slots[hindex] = 1+index;
83 // Remove (htrem alias remhash).
84 void remove (const key1_type& key)
86 var long* _index = &this->_slots[hashcode(key) % this->_modulus];
88 var long index = *_index - 1;
89 if (!(index < this->_size))
90 throw runtime_exception();
91 if (equal(key,hashkey(this->_entries[index].entry.val))) {
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 !(defined(__sparc__) && !defined(__GNUC__))
115 if (this->_freelist < -1)
118 if (_garcol_fun(this))
119 if (this->_freelist < -1)
121 // No! Have to grow the hash table.
124 // workaround Sun C++ 4.1 inline function compiler bug
125 if (this->_freelist >= -1) {
126 if (!_garcol_fun(this) || (this->_freelist >= -1))
133 var long new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
134 var long new_modulus = inherited::compute_modulus(new_size);
135 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
136 var long* new_slots = (long*) ((char*)new_total_vector + 0);
137 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
138 for (var long hi = new_modulus-1; hi >= 0; hi--)
140 var long free_list_head = -1;
141 for (var long i = new_size-1; i >= 0; i--) {
142 new_entries[i].next = free_list_head;
143 free_list_head = -2-i;
145 var htxentry* old_entries = this->_entries;
146 for (var long old_index = 0; old_index < this->_size; old_index++)
147 if (old_entries[old_index].next >= 0) {
148 var value_type& val = old_entries[old_index].entry.val;
149 var long hindex = hashcode(hashkey(val)) % 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_htuniqentry<key1_type,value_type> (val);
153 new_entries[index].next = new_slots[hindex];
154 new_slots[hindex] = 1+index;
155 old_entries[old_index].~htxentry();
157 free_hook(this->_total_vector);
158 this->_modulus = new_modulus;
159 this->_size = new_size;
160 this->_freelist = free_list_head;
161 this->_slots = new_slots;
162 this->_entries = new_entries;
163 this->_total_vector = new_total_vector;
169 #endif /* _CL_HASHUNIQ_H */