1 // Hash tables for making objects unique
7 #include "cl_iterator.h"
9 // In such a hash table an entry's key is determined by its value
10 // and not stored explicitly.
13 // - function bool equal (key1_type,key1_type);
14 // - function unsigned long hashcode (key1_type);
15 // - function key1_type hashkey (value_type);
16 // - constructor value_type::value_type (struct hashuniq *, key1_type);
18 template <class key1_type, class value_type>
19 struct cl_htuniqentry {
20 ALLOCATE_ANYWHERE(cl_htuniqentry)
22 const value_type& htvalue () { return val; }
23 cl_htuniqentry (const value_type& v)
25 #if (defined(__rs6000__) && !defined(__GNUC__))
30 template <class key1_type, class value_type>
31 struct cl_heap_hashtable_uniq : public cl_heap_hashtable <cl_htuniqentry <key1_type,value_type> > {
33 void* operator new (size_t size) { return cl_malloc_hook(size); }
35 void operator delete (void* ptr) { cl_free_hook(ptr); }
37 // Lookup (htref alias gethash).
38 // Returns a pointer which you should immediately dereference
40 value_type * get (const key1_type& key)
42 var long index = _slots[hashcode(key) % _modulus] - 1;
46 if (equal(key,hashkey(_entries[index].entry.val)))
47 return &_entries[index].entry.val;
48 index = _entries[index].next - 1;
52 // Store (htset alias puthash).
53 void put (const key1_type& key)
55 var unsigned long hcode = hashcode(key);
56 // Search whether it is already there.
58 var long index = _slots[hcode % _modulus] - 1;
62 if (equal(key,hashkey(_entries[index].entry.val)))
64 index = _entries[index].next - 1;
67 // Put it into the table.
69 var long hindex = hcode % _modulus; // _modulus may have changed!
70 var long index = get_free_index();
71 new (&_entries[index].entry) cl_htuniqentry<key1_type,value_type> (value_type((struct hashuniq *)0, key));
72 _entries[index].next = _slots[hindex];
73 _slots[hindex] = 1+index;
76 // Remove (htrem alias remhash).
77 void remove (const key1_type& key)
79 var long* _index = &_slots[hashcode(key) % _modulus];
81 var long index = *_index - 1;
84 if (equal(key,hashkey(_entries[index].entry.val))) {
85 // Remove _entries[index].entry
86 *_index = _entries[index].next;
87 _entries[index].~htxentry();
88 // The entry is now free.
89 put_free_index(index);
94 _index = &_entries[index].next;
97 // Iterate through the table.
98 // No stuff should be inserted into the table during the iteration,
99 // or you may find yourself iterating over an entry vector which has
100 // already been freed!
103 // Prepare a store operation: make sure that the free list is non-empty.
104 // This may change the table's size!
105 void prepare_store ()
107 #if !(defined(__sparc__) && !defined(__GNUC__))
111 if (_garcol_fun(this))
114 // No! Have to grow the hash table.
117 // workaround Sun C++ 4.1 inline function compiler bug
118 if (_freelist >= -1) {
119 if (!_garcol_fun(this) || (_freelist >= -1))
126 var long new_size = _size + (_size >> 1) + 1; // _size*1.5
127 var long new_modulus = compute_modulus(new_size);
128 var void* new_total_vector = cl_malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
129 var long* new_slots = (long*) ((char*)new_total_vector + 0);
130 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
131 for (var long hi = new_modulus-1; hi >= 0; hi--)
133 var long free_list_head = -1;
134 for (var long i = new_size-1; i >= 0; i--) {
135 new_entries[i].next = free_list_head;
136 free_list_head = -2-i;
138 var htxentry* old_entries = _entries;
139 for (var long old_index = 0; old_index < _size; old_index++)
140 if (old_entries[old_index].next >= 0) {
141 var value_type& val = old_entries[old_index].entry.val;
142 var long hindex = hashcode(hashkey(val)) % new_modulus;
143 var long index = -2-free_list_head;
144 free_list_head = new_entries[index].next;
145 new (&new_entries[index].entry) cl_htuniqentry<key1_type,value_type> (val);
146 new_entries[index].next = new_slots[hindex];
147 new_slots[hindex] = 1+index;
148 old_entries[old_index].~htxentry();
150 cl_free_hook(_total_vector);
151 _modulus = new_modulus;
153 _freelist = free_list_head;
155 _entries = new_entries;
156 _total_vector = new_total_vector;
160 #endif /* _CL_HASHUNIQ_H */