1 // Hash sets (hash tables with 1 key and no value)
6 #include "base/hash/cl_hash.h"
7 #include "base/cl_iterator.h"
12 // - function bool equal (key1_type,key1_type);
13 // - function uintptr_t hashcode (key1_type);
15 template <class key1_type>
16 struct cl_htsetentry {
17 ALLOCATE_ANYWHERE(cl_htsetentry)
19 cl_htsetentry (const key1_type& k)
23 template <class key1_type>
24 struct cl_heap_hashtable_set : public cl_heap_hashtable <cl_htsetentry <key1_type> > {
27 typedef cl_heap_hashtable <cl_htsetentry <key1_type> > inherited;
28 typedef typename inherited::htxentry htxentry;
31 void* operator new (size_t size) { return malloc_hook(size); }
33 void operator delete (void* ptr) { free_hook(ptr); }
35 // Lookup (htref alias gethash).
36 bool get (const key1_type& key)
38 var intptr_t index = this->_slots[hashcode(key) % this->_modulus] - 1;
40 if (!(index < this->_size))
41 throw runtime_exception();
42 if (equal(key,this->_entries[index].entry.key))
44 index = this->_entries[index].next - 1;
48 // Store (htset alias puthash).
49 void put (const key1_type& key)
51 var uintptr_t hcode = hashcode(key);
52 // Search whether it is already there.
54 var intptr_t index = this->_slots[hcode % this->_modulus] - 1;
56 if (!(index < this->_size))
57 throw runtime_exception();
58 if (equal(key,this->_entries[index].entry.key))
60 index = this->_entries[index].next - 1;
63 // Put it into the table.
65 var intptr_t hindex = hcode % this->_modulus; // _modulus may have changed!
66 var intptr_t index = this->get_free_index();
67 new (&this->_entries[index].entry) cl_htsetentry<key1_type> (key);
68 this->_entries[index].next = this->_slots[hindex];
69 this->_slots[hindex] = 1+index;
72 // Remove (htrem alias remhash).
73 void remove (const key1_type& key)
75 var intptr_t* _index = &this->_slots[hashcode(key) % this->_modulus];
77 var intptr_t index = *_index - 1;
78 if (!(index < this->_size))
79 throw runtime_exception();
80 if (equal(key,this->_entries[index].entry.key)) {
81 // Remove _entries[index].entry
82 *_index = this->_entries[index].next;
83 this->_entries[index].~htxentry();
84 // The entry is now free.
85 this->put_free_index(index);
90 _index = &this->_entries[index].next;
93 // Iterate through the table.
94 // No stuff should be inserted into the table during the iteration,
95 // or you may find yourself iterating over an entry vector which has
96 // already been freed!
99 // Prepare a store operation: make sure that the free list is non-empty.
100 // This may change the table's size!
101 void prepare_store ()
103 if (this->_freelist < -1)
106 if (this->_garcol_fun(this))
107 if (this->_freelist < -1)
109 // No! Have to grow the hash table.
114 var intptr_t new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
115 var intptr_t new_modulus = inherited::compute_modulus(new_size);
116 var void* new_total_vector = malloc_hook(new_modulus*sizeof(intptr_t) + new_size*sizeof(htxentry));
117 var intptr_t* new_slots = (intptr_t*) ((char*)new_total_vector + 0);
118 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(intptr_t));
119 for (var intptr_t hi = new_modulus-1; hi >= 0; hi--)
121 var intptr_t free_list_head = -1;
122 for (var intptr_t i = new_size-1; i >= 0; i--) {
123 new_entries[i].next = free_list_head;
124 free_list_head = -2-i;
126 var htxentry* old_entries = this->_entries;
127 for (var intptr_t old_index = 0; old_index < this->_size; old_index++)
128 if (old_entries[old_index].next >= 0) {
129 var key1_type& key = old_entries[old_index].entry.key;
130 var intptr_t hindex = hashcode(key) % new_modulus;
131 var intptr_t index = -2-free_list_head;
132 free_list_head = new_entries[index].next;
133 new (&new_entries[index].entry) cl_htsetentry<key1_type> (key);
134 new_entries[index].next = new_slots[hindex];
135 new_slots[hindex] = 1+index;
136 old_entries[old_index].~htxentry();
138 free_hook(this->_total_vector);
139 this->_modulus = new_modulus;
140 this->_size = new_size;
141 this->_freelist = free_list_head;
142 this->_slots = new_slots;
143 this->_entries = new_entries;
144 this->_total_vector = new_total_vector;
150 #endif /* _CL_HASHSET_H */