1 // Hash tables for making objects unique
6 #include "base/hash/cl_hash.h"
7 #include "base/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)
29 template <class key1_type, class value_type>
30 struct cl_heap_hashtable_uniq : public cl_heap_hashtable <cl_htuniqentry <key1_type,value_type> > {
33 typedef cl_heap_hashtable <cl_htuniqentry <key1_type,value_type> > inherited;
34 typedef typename inherited::htxentry htxentry;
37 void* operator new (size_t size) { return malloc_hook(size); }
39 void operator delete (void* ptr) { free_hook(ptr); }
41 // Lookup (htref alias gethash).
42 // Returns a pointer which you should immediately dereference
44 value_type * get (const key1_type& key)
46 var long index = this->_slots[hashcode(key) % this->_modulus] - 1;
48 if (!(index < this->_size))
49 throw runtime_exception();
50 if (equal(key,hashkey(this->_entries[index].entry.val)))
51 return &this->_entries[index].entry.val;
52 index = this->_entries[index].next - 1;
56 // Store (htset alias puthash).
57 void put (const key1_type& key)
59 var unsigned long hcode = hashcode(key);
60 // Search whether it is already there.
62 var long index = this->_slots[hcode % this->_modulus] - 1;
64 if (!(index < this->_size))
65 throw runtime_exception();
66 if (equal(key,hashkey(this->_entries[index].entry.val)))
68 index = this->_entries[index].next - 1;
71 // Put it into the table.
73 var long hindex = hcode % this->_modulus; // _modulus may have changed!
74 var long index = this->get_free_index();
75 new (&this->_entries[index].entry) cl_htuniqentry<key1_type,value_type> (value_type((struct hashuniq *)0, key));
76 this->_entries[index].next = this->_slots[hindex];
77 this->_slots[hindex] = 1+index;
80 // Remove (htrem alias remhash).
81 void remove (const key1_type& key)
83 var long* _index = &this->_slots[hashcode(key) % this->_modulus];
85 var long index = *_index - 1;
86 if (!(index < this->_size))
87 throw runtime_exception();
88 if (equal(key,hashkey(this->_entries[index].entry.val))) {
89 // Remove _entries[index].entry
90 *_index = this->_entries[index].next;
91 this->_entries[index].~htxentry();
92 // The entry is now free.
93 this->put_free_index(index);
98 _index = &this->_entries[index].next;
101 // Iterate through the table.
102 // No stuff should be inserted into the table during the iteration,
103 // or you may find yourself iterating over an entry vector which has
104 // already been freed!
107 // Prepare a store operation: make sure that the free list is non-empty.
108 // This may change the table's size!
109 void prepare_store ()
111 if (this->_freelist < -1)
114 if (this->_garcol_fun(this))
115 if (this->_freelist < -1)
117 // No! Have to grow the hash table.
122 var long new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
123 var long new_modulus = inherited::compute_modulus(new_size);
124 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
125 var long* new_slots = (long*) ((char*)new_total_vector + 0);
126 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
127 for (var long hi = new_modulus-1; hi >= 0; hi--)
129 var long free_list_head = -1;
130 for (var long i = new_size-1; i >= 0; i--) {
131 new_entries[i].next = free_list_head;
132 free_list_head = -2-i;
134 var htxentry* old_entries = this->_entries;
135 for (var long old_index = 0; old_index < this->_size; old_index++)
136 if (old_entries[old_index].next >= 0) {
137 var value_type& val = old_entries[old_index].entry.val;
138 var long hindex = hashcode(hashkey(val)) % new_modulus;
139 var long index = -2-free_list_head;
140 free_list_head = new_entries[index].next;
141 new (&new_entries[index].entry) cl_htuniqentry<key1_type,value_type> (val);
142 new_entries[index].next = new_slots[hindex];
143 new_slots[hindex] = 1+index;
144 old_entries[old_index].~htxentry();
146 free_hook(this->_total_vector);
147 this->_modulus = new_modulus;
148 this->_size = new_size;
149 this->_freelist = free_list_head;
150 this->_slots = new_slots;
151 this->_entries = new_entries;
152 this->_total_vector = new_total_vector;
158 #endif /* _CL_HASHUNIQ_H */