1 // Hash sets (hash tables with 1 key and no value)
7 #include "cl_iterator.h"
12 // - function bool equal (key1_type,key1_type);
13 // - function unsigned long 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> > {
26 void* operator new (size_t size) { return malloc_hook(size); }
28 void operator delete (void* ptr) { free_hook(ptr); }
30 // Lookup (htref alias gethash).
31 bool get (const key1_type& key)
33 var long index = _slots[hashcode(key) % _modulus] - 1;
37 if (equal(key,_entries[index].entry.key))
39 index = _entries[index].next - 1;
43 // Store (htset alias puthash).
44 void put (const key1_type& key)
46 var unsigned long hcode = hashcode(key);
47 // Search whether it is already there.
49 var long index = _slots[hcode % _modulus] - 1;
53 if (equal(key,_entries[index].entry.key))
55 index = _entries[index].next - 1;
58 // Put it into the table.
60 var long hindex = hcode % _modulus; // _modulus may have changed!
61 var long index = get_free_index();
62 new (&_entries[index].entry) cl_htsetentry<key1_type> (key);
63 _entries[index].next = _slots[hindex];
64 _slots[hindex] = 1+index;
67 // Remove (htrem alias remhash).
68 void remove (const key1_type& key)
70 var long* _index = &_slots[hashcode(key) % _modulus];
72 var long index = *_index - 1;
75 if (equal(key,_entries[index].entry.key)) {
76 // Remove _entries[index].entry
77 *_index = _entries[index].next;
78 _entries[index].~htxentry();
79 // The entry is now free.
80 put_free_index(index);
85 _index = &_entries[index].next;
88 // Iterate through the table.
89 // No stuff should be inserted into the table during the iteration,
90 // or you may find yourself iterating over an entry vector which has
91 // already been freed!
94 // Prepare a store operation: make sure that the free list is non-empty.
95 // This may change the table's size!
98 #if !(defined(__sparc__) && !defined(__GNUC__))
102 if (_garcol_fun(this))
105 // No! Have to grow the hash table.
108 // workaround Sun C++ 4.1 inline function compiler bug
109 if (_freelist >= -1) {
110 if (!_garcol_fun(this) || (_freelist >= -1))
117 var long new_size = _size + (_size >> 1) + 1; // _size*1.5
118 var long new_modulus = compute_modulus(new_size);
119 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
120 var long* new_slots = (long*) ((char*)new_total_vector + 0);
121 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
122 for (var long hi = new_modulus-1; hi >= 0; hi--)
124 var long free_list_head = -1;
125 for (var long i = new_size-1; i >= 0; i--) {
126 new_entries[i].next = free_list_head;
127 free_list_head = -2-i;
129 var htxentry* old_entries = _entries;
130 for (var long old_index = 0; old_index < _size; old_index++)
131 if (old_entries[old_index].next >= 0) {
132 var key1_type& key = old_entries[old_index].entry.key;
133 var long hindex = hashcode(key) % new_modulus;
134 var long index = -2-free_list_head;
135 free_list_head = new_entries[index].next;
136 new (&new_entries[index].entry) cl_htsetentry<key1_type> (key);
137 new_entries[index].next = new_slots[hindex];
138 new_slots[hindex] = 1+index;
139 old_entries[old_index].~htxentry();
141 free_hook(_total_vector);
142 _modulus = new_modulus;
144 _freelist = free_list_head;
146 _entries = new_entries;
147 _total_vector = new_total_vector;
153 #endif /* _CL_HASHSET_H */