X-Git-Url: https://ginac.de/CLN/cln.git//cln.git?a=blobdiff_plain;f=src%2Fbase%2Fhash%2Fcl_hashset.h;h=c8457e63676dc598f89e82a0ec639e7d8f040ce0;hb=3a895e313b91bd8b23bab81d45efce63ca47cde7;hp=a89c1262ecd78036af3ad27e6c820d10251c06a7;hpb=850abfde7f0d985ba01526c346bcd0d733562943;p=cln.git diff --git a/src/base/hash/cl_hashset.h b/src/base/hash/cl_hashset.h index a89c126..c8457e6 100644 --- a/src/base/hash/cl_hashset.h +++ b/src/base/hash/cl_hashset.h @@ -3,14 +3,14 @@ #ifndef _CL_HASHSET_H #define _CL_HASHSET_H -#include "cl_hash.h" -#include "cl_iterator.h" +#include "base/hash/cl_hash.h" +#include "base/cl_iterator.h" namespace cln { // Requirements: // - function bool equal (key1_type,key1_type); -// - function unsigned long hashcode (key1_type); +// - function uintptr_t hashcode (key1_type); template struct cl_htsetentry { @@ -22,6 +22,11 @@ struct cl_htsetentry { template struct cl_heap_hashtable_set : public cl_heap_hashtable > { +protected: + // Abbreviations. + typedef cl_heap_hashtable > inherited; + typedef typename inherited::htxentry htxentry; +public: // Allocation. void* operator new (size_t size) { return malloc_hook(size); } // Deallocation. @@ -30,59 +35,59 @@ public: // Lookup (htref alias gethash). bool get (const key1_type& key) { - var long index = _slots[hashcode(key) % _modulus] - 1; + var intptr_t index = this->_slots[hashcode(key) % this->_modulus] - 1; while (index >= 0) { - if (!(index < _size)) - cl_abort(); - if (equal(key,_entries[index].entry.key)) + if (!(index < this->_size)) + throw runtime_exception(); + if (equal(key,this->_entries[index].entry.key)) return true; - index = _entries[index].next - 1; + index = this->_entries[index].next - 1; } return false; } // Store (htset alias puthash). void put (const key1_type& key) { - var unsigned long hcode = hashcode(key); + var uintptr_t hcode = hashcode(key); // Search whether it is already there. { - var long index = _slots[hcode % _modulus] - 1; + var intptr_t index = this->_slots[hcode % this->_modulus] - 1; while (index >= 0) { - if (!(index < _size)) - cl_abort(); - if (equal(key,_entries[index].entry.key)) + if (!(index < this->_size)) + throw runtime_exception(); + if (equal(key,this->_entries[index].entry.key)) return; - index = _entries[index].next - 1; + index = this->_entries[index].next - 1; } } // Put it into the table. prepare_store(); - var long hindex = hcode % _modulus; // _modulus may have changed! - var long index = get_free_index(); - new (&_entries[index].entry) cl_htsetentry (key); - _entries[index].next = _slots[hindex]; - _slots[hindex] = 1+index; - _count++; + var intptr_t hindex = hcode % this->_modulus; // _modulus may have changed! + var intptr_t index = this->get_free_index(); + new (&this->_entries[index].entry) cl_htsetentry (key); + this->_entries[index].next = this->_slots[hindex]; + this->_slots[hindex] = 1+index; + this->_count++; } // Remove (htrem alias remhash). void remove (const key1_type& key) { - var long* _index = &_slots[hashcode(key) % _modulus]; + var intptr_t* _index = &this->_slots[hashcode(key) % this->_modulus]; while (*_index > 0) { - var long index = *_index - 1; - if (!(index < _size)) - cl_abort(); - if (equal(key,_entries[index].entry.key)) { + var intptr_t index = *_index - 1; + if (!(index < this->_size)) + throw runtime_exception(); + if (equal(key,this->_entries[index].entry.key)) { // Remove _entries[index].entry - *_index = _entries[index].next; - _entries[index].~htxentry(); + *_index = this->_entries[index].next; + this->_entries[index].~htxentry(); // The entry is now free. - put_free_index(index); + this->put_free_index(index); // That's it. - _count--; + this->_count--; return; } - _index = &_entries[index].next; + _index = &this->_entries[index].next; } } // Iterate through the table. @@ -95,56 +100,48 @@ private: // This may change the table's size! void prepare_store () { - #if !(defined(__sparc__) && !defined(__GNUC__)) - if (_freelist < -1) + if (this->_freelist < -1) return; // Can we make room? - if (_garcol_fun(this)) - if (_freelist < -1) + if (this->_garcol_fun(this)) + if (this->_freelist < -1) return; // No! Have to grow the hash table. grow(); - #else - // workaround Sun C++ 4.1 inline function compiler bug - if (_freelist >= -1) { - if (!_garcol_fun(this) || (_freelist >= -1)) - grow(); - } - #endif } void grow () { - var long new_size = _size + (_size >> 1) + 1; // _size*1.5 - var long new_modulus = compute_modulus(new_size); - var void* new_total_vector = malloc_hook(new_modulus*sizeof(long) + new_size*sizeof(htxentry)); - var long* new_slots = (long*) ((char*)new_total_vector + 0); - var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(long)); - for (var long hi = new_modulus-1; hi >= 0; hi--) + var intptr_t new_size = this->_size + (this->_size >> 1) + 1; // _size*1.5 + var intptr_t new_modulus = inherited::compute_modulus(new_size); + var void* new_total_vector = malloc_hook(new_modulus*sizeof(intptr_t) + new_size*sizeof(htxentry)); + var intptr_t* new_slots = (intptr_t*) ((char*)new_total_vector + 0); + var htxentry* new_entries = (htxentry *) ((char*)new_total_vector + new_modulus*sizeof(intptr_t)); + for (var intptr_t hi = new_modulus-1; hi >= 0; hi--) new_slots[hi] = 0; - var long free_list_head = -1; - for (var long i = new_size-1; i >= 0; i--) { + var intptr_t free_list_head = -1; + for (var intptr_t i = new_size-1; i >= 0; i--) { new_entries[i].next = free_list_head; free_list_head = -2-i; } - var htxentry* old_entries = _entries; - for (var long old_index = 0; old_index < _size; old_index++) + var htxentry* old_entries = this->_entries; + for (var intptr_t old_index = 0; old_index < this->_size; old_index++) if (old_entries[old_index].next >= 0) { var key1_type& key = old_entries[old_index].entry.key; - var long hindex = hashcode(key) % new_modulus; - var long index = -2-free_list_head; + var intptr_t hindex = hashcode(key) % new_modulus; + var intptr_t index = -2-free_list_head; free_list_head = new_entries[index].next; new (&new_entries[index].entry) cl_htsetentry (key); new_entries[index].next = new_slots[hindex]; new_slots[hindex] = 1+index; old_entries[old_index].~htxentry(); } - free_hook(_total_vector); - _modulus = new_modulus; - _size = new_size; - _freelist = free_list_head; - _slots = new_slots; - _entries = new_entries; - _total_vector = new_total_vector; + free_hook(this->_total_vector); + this->_modulus = new_modulus; + this->_size = new_size; + this->_freelist = free_list_head; + this->_slots = new_slots; + this->_entries = new_entries; + this->_total_vector = new_total_vector; } };