1 // Hash tables with 1 key and a value
6 #include "base/hash/cl_hash.h"
7 #include "base/cl_iterator.h"
12 // - function bool equal (key1_type,key1_type);
13 // - function unsigned long hashcode (key1_type);
15 template <class key1_type, class value_type>
17 ALLOCATE_ANYWHERE(cl_htentry1)
20 const value_type& htvalue () { return val; }
21 cl_htentry1 (const key1_type& k, const value_type& v)
25 template <class key1_type, class value_type>
26 struct cl_heap_hashtable_1 : public cl_heap_hashtable <cl_htentry1 <key1_type,value_type> > {
29 typedef cl_heap_hashtable <cl_htentry1 <key1_type,value_type> > inherited;
30 typedef typename inherited::htxentry htxentry;
33 void* operator new (size_t size) { return malloc_hook(size); }
35 void operator delete (void* ptr) { 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 = this->_slots[hashcode(key) % this->_modulus] - 1;
44 if (!(index < this->_size))
45 throw runtime_exception();
46 if (equal(key,this->_entries[index].entry.key))
47 return &this->_entries[index].entry.val;
48 index = this->_entries[index].next - 1;
52 // Store (htset alias puthash).
53 void put (const key1_type& key, const value_type& val)
55 var unsigned long hcode = hashcode(key);
56 // Search whether it is already there.
58 var long index = this->_slots[hcode % this->_modulus] - 1;
60 if (!(index < this->_size))
61 throw runtime_exception();
62 if (equal(key,this->_entries[index].entry.key)) {
63 this->_entries[index].entry.val = val;
66 index = this->_entries[index].next - 1;
69 // Put it into the table.
71 var long hindex = hcode % this->_modulus; // _modulus may have changed!
72 var long index = this->get_free_index();
73 new (&this->_entries[index].entry) cl_htentry1<key1_type,value_type> (key,val);
74 this->_entries[index].next = this->_slots[hindex];
75 this->_slots[hindex] = 1+index;
78 // Remove (htrem alias remhash).
79 void remove (const key1_type& key)
81 var long* _index = &this->_slots[hashcode(key) % this->_modulus];
83 var long index = *_index - 1;
84 if (!(index < this->_size))
85 throw runtime_exception();
86 if (equal(key,this->_entries[index].entry.key)) {
87 // Remove _entries[index].entry
88 *_index = this->_entries[index].next;
89 this->_entries[index].~htxentry();
90 // The entry is now free.
91 this->put_free_index(index);
96 _index = &this->_entries[index].next;
99 // Iterate through the table.
100 // No stuff should be inserted into the table during the iteration,
101 // or you may find yourself iterating over an entry vector which has
102 // already been freed!
105 // Prepare a store operation: make sure that the free list is non-empty.
106 // This may change the table's size!
107 void prepare_store ()
109 if (this->_freelist < -1)
112 if (this->_garcol_fun(this))
113 if (this->_freelist < -1)
115 // No! Have to grow the hash table.
120 var long new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5
121 var long new_modulus = inherited::compute_modulus(new_size);
122 var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry));
123 var long* new_slots = (long*) ((char*)new_total_vector + 0);
124 var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long));
125 for (var long hi = new_modulus-1; hi >= 0; hi--)
127 var long free_list_head = -1;
128 for (var long i = new_size-1; i >= 0; i--) {
129 new_entries[i].next = free_list_head;
130 free_list_head = -2-i;
132 var htxentry* old_entries = this->_entries;
133 for (var long old_index = 0; old_index < this->_size; old_index++)
134 if (old_entries[old_index].next >= 0) {
135 var key1_type& key = old_entries[old_index].entry.key;
136 var value_type& val = old_entries[old_index].entry.val;
137 var long hindex = hashcode(key) % new_modulus;
138 var long index = -2-free_list_head;
139 free_list_head = new_entries[index].next;
140 new (&new_entries[index].entry) cl_htentry1<key1_type,value_type> (key,val);
141 new_entries[index].next = new_slots[hindex];
142 new_slots[hindex] = 1+index;
143 old_entries[old_index].~htxentry();
145 free_hook(this->_total_vector);
146 this->_modulus = new_modulus;
147 this->_size = new_size;
148 this->_freelist = free_list_head;
149 this->_slots = new_slots;
150 this->_entries = new_entries;
151 this->_total_vector = new_total_vector;
157 #endif /* _CL_HASH1_H */