X-Git-Url: https://ginac.de/CLN/cln.git//cln.git?a=blobdiff_plain;f=src%2Fbase%2Fhash%2Fcl_hash1.h;h=201f9512498e5e8e80388a0ad704386fad943a29;hb=3a895e313b91bd8b23bab81d45efce63ca47cde7;hp=2bd3e7ba461d31f4d45eeff216564bfde2e01268;hpb=850abfde7f0d985ba01526c346bcd0d733562943;p=cln.git diff --git a/src/base/hash/cl_hash1.h b/src/base/hash/cl_hash1.h index 2bd3e7b..201f951 100644 --- a/src/base/hash/cl_hash1.h +++ b/src/base/hash/cl_hash1.h @@ -3,18 +3,14 @@ #ifndef _CL_HASH1_H #define _CL_HASH1_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); - -#if (defined(__alpha__) && !defined(__GNUC__)) -template struct cl_htentry1; -#endif +// - function uintptr_t hashcode (key1_type); template struct cl_htentry1 { @@ -24,13 +20,15 @@ struct cl_htentry1 { const value_type& htvalue () { return val; } cl_htentry1 (const key1_type& k, const value_type& v) : key (k), val (v) {} -#if (defined(__rs6000__) && !defined(__GNUC__)) - cl_htentry1 () {} -#endif }; template struct cl_heap_hashtable_1 : 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. @@ -41,61 +39,61 @@ public: // if it is not NULL. value_type* 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)) - return &_entries[index].entry.val; - index = _entries[index].next - 1; + if (!(index < this->_size)) + throw runtime_exception(); + if (equal(key,this->_entries[index].entry.key)) + return &this->_entries[index].entry.val; + index = this->_entries[index].next - 1; } return NULL; } // Store (htset alias puthash). void put (const key1_type& key, const value_type& val) { - 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)) { - _entries[index].entry.val = val; + if (!(index < this->_size)) + throw runtime_exception(); + if (equal(key,this->_entries[index].entry.key)) { + this->_entries[index].entry.val = val; 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_htentry1 (key,val); - _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_htentry1 (key,val); + 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. @@ -108,57 +106,49 @@ 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 value_type& val = old_entries[old_index].entry.val; - 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_htentry1 (key,val); 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; } };