+++ /dev/null
-////////////////////////////////////////////////////////////////////////////////\r
-\r
-// Author: Andy Rushton\r
-// Copyright: (c) Southampton University 1999-2004\r
-// (c) Andy Rushton 2004-2009\r
-// License: BSD License, see ../docs/license.html\r
-\r
-////////////////////////////////////////////////////////////////////////////////\r
-\r
-namespace stlplus\r
-{\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // the element stored in the hash\r
-\r
- template<typename K, typename T, typename H, typename E>\r
- class hash_element\r
- {\r
- public:\r
- master_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> > m_master;\r
- std::pair<const K, T> m_value;\r
- hash_element<K,T,H,E>* m_next;\r
- unsigned m_hash;\r
-\r
- hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) : \r
- m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash) \r
- {\r
- }\r
-\r
- hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) : \r
- m_master(owner,this), m_value(value), m_next(0), m_hash(hash) \r
- {\r
- }\r
-\r
- ~hash_element(void)\r
- {\r
- m_next = 0;\r
- m_hash = 0;\r
- }\r
-\r
- const hash<K,T,H,E>* owner(void) const\r
- {\r
- return m_master.owner();\r
- }\r
-\r
- // generate the bin number from the hash value and the owner's number of bins\r
- unsigned bin(void) const\r
- {\r
- return m_hash % (owner()->m_bins);\r
- }\r
- };\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // iterator\r
-\r
- // null constructor\r
- template<typename K, typename T, class H, class E, typename V>\r
- hash_iterator<K,T,H,E,V>::hash_iterator(void)\r
- {\r
- }\r
-\r
- // non-null constructor used from within the hash to construct a valid iterator\r
- template<typename K, typename T, class H, class E, typename V>\r
- hash_iterator<K,T,H,E,V>::hash_iterator(hash_element<K,T,H,E>* element) :\r
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(element->m_master)\r
- {\r
- }\r
-\r
- // constructor used to create an end iterator\r
- template<typename K, typename T, class H, class E, typename V>\r
- hash_iterator<K,T,H,E,V>::hash_iterator(const hash<K,T,H,E>* owner) :\r
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(owner)\r
- {\r
- }\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- hash_iterator<K,T,H,E,V>::hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator) :\r
- safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(iterator)\r
- {\r
- }\r
-\r
- // destructor\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- hash_iterator<K,T,H,E,V>::~hash_iterator(void)\r
- {\r
- }\r
-\r
- // mode conversions\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- TYPENAME hash_iterator<K,T,H,E,V>::const_iterator hash_iterator<K,T,H,E,V>::constify(void) const\r
- {\r
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(*this);\r
- }\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- TYPENAME hash_iterator<K,T,H,E,V>::iterator hash_iterator<K,T,H,E,V>::deconstify(void) const\r
- {\r
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(*this);\r
- }\r
-\r
- // increment operator looks for the next element in the table\r
- // if there isn't one, then this becomes an end() iterator with m_bin = m_bins\r
- template<typename K, typename T, class H, class E, typename V>\r
- TYPENAME hash_iterator<K,T,H,E,V>::this_iterator& hash_iterator<K,T,H,E,V>::operator ++ (void)\r
- throw(null_dereference,end_dereference)\r
- {\r
- this->assert_valid();\r
- if (this->node()->m_next)\r
- set(this->node()->m_next->m_master);\r
- else\r
- {\r
- // failing that, subsequent hash values are tried until either an element is found or there are no more bins\r
- // in which case it becomes an end() iterator\r
- hash_element<K,T,H,E>* element = 0;\r
- unsigned current_bin = this->node()->bin();\r
- for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++)\r
- element = this->owner()->m_values[current_bin];\r
- if (element)\r
- set(element->m_master);\r
- else\r
- this->set_end();\r
- }\r
- return *this;\r
- }\r
-\r
- // post-increment is defined in terms of pre-increment\r
- template<typename K, typename T, class H, class E, typename V>\r
- TYPENAME hash_iterator<K,T,H,E,V>::this_iterator hash_iterator<K,T,H,E,V>::operator ++ (int)\r
- throw(null_dereference,end_dereference)\r
- {\r
- hash_iterator<K,T,H,E,V> old(*this);\r
- ++(*this);\r
- return old;\r
- }\r
-\r
- // two iterators are equal if they point to the same element\r
- // both iterators must be non-null and belong to the same table\r
- template<typename K, typename T, class H, class E, typename V>\r
- bool hash_iterator<K,T,H,E,V>::operator == (const hash_iterator<K,T,H,E,V>& r) const\r
- {\r
- return equal(r);\r
- }\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- bool hash_iterator<K,T,H,E,V>::operator != (const hash_iterator<K,T,H,E,V>& r) const\r
- {\r
- return !operator==(r);\r
- }\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- bool hash_iterator<K,T,H,E,V>::operator < (const hash_iterator<K,T,H,E,V>& r) const\r
- {\r
- return compare(r) < 0;\r
- }\r
-\r
- // iterator dereferencing is only legal on a non-null iterator\r
- template<typename K, typename T, class H, class E, typename V>\r
- V& hash_iterator<K,T,H,E,V>::operator*(void) const\r
- throw(null_dereference,end_dereference)\r
- {\r
- this->assert_valid();\r
- return this->node()->m_value;\r
- }\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- V* hash_iterator<K,T,H,E,V>::operator->(void) const\r
- throw(null_dereference,end_dereference)\r
- {\r
- return &(operator*());\r
- }\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // hash\r
-\r
- // totally arbitrary initial size used for auto-rehashed tables\r
- static unsigned hash_default_bins = 127;\r
-\r
- // constructor\r
- // tests whether the user wants auto-rehash\r
- // sets the rehash point to be a loading of 1.0 by setting it to the number of bins\r
- // uses the user's size unless this is zero, in which case implement the default\r
-\r
- template<typename K, typename T, class H, class E>\r
- hash<K,T,H,E>::hash(unsigned bins) :\r
- m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0)\r
- {\r
- m_values = new hash_element<K,T,H,E>*[m_bins];\r
- for (unsigned i = 0; i < m_bins; i++)\r
- m_values[i] = 0;\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- hash<K,T,H,E>::~hash(void)\r
- {\r
- // delete all the elements\r
- clear();\r
- // and delete the data structure\r
- delete[] m_values;\r
- m_values = 0;\r
- }\r
-\r
- // as usual, implement the copy constructor i.t.o. the assignment operator\r
-\r
- template<typename K, typename T, class H, class E>\r
- hash<K,T,H,E>::hash(const hash<K,T,H,E>& right) :\r
- m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0)\r
- {\r
- m_values = new hash_element<K,T,H,E>*[right.m_bins];\r
- // copy the rehash behaviour as well as the size\r
- for (unsigned i = 0; i < m_bins; i++)\r
- m_values[i] = 0;\r
- *this = right;\r
- }\r
-\r
- // assignment operator\r
- // this is done by copying the elements\r
- // the source and target hashes can be different sizes\r
- // the hash is self-copy safe, i.e. it is legal to say x = x;\r
-\r
- template<typename K, typename T, class H, class E>\r
- hash<K,T,H,E>& hash<K,T,H,E>::operator = (const hash<K,T,H,E>& r)\r
- {\r
- // make self-copy safe\r
- if (&r == this) return *this;\r
- // remove all the existing elements\r
- clear();\r
- // copy the elements across - remember that this is rehashing because the two\r
- // tables can be different sizes so there is no quick way of doing this by\r
- // copying the lists\r
- for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = r.begin(); i != r.end(); ++i)\r
- insert(i->first, i->second);\r
- return *this;\r
- }\r
-\r
- // number of values in the hash\r
- template<typename K, typename T, class H, class E>\r
- bool hash<K,T,H,E>::empty(void) const\r
- {\r
- return m_size == 0;\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- unsigned hash<K,T,H,E>::size(void) const\r
- {\r
- return m_size;\r
- }\r
-\r
- // equality\r
- template<typename K, typename T, class H, class E>\r
- bool hash<K,T,H,E>::operator == (const hash<K,T,H,E>& right) const\r
- {\r
- // this table is the same as the right table if they are the same table!\r
- if (&right == this) return true;\r
- // they must be the same size to be equal\r
- if (m_size != right.m_size) return false;\r
- // now every key in this must be in right and have the same data\r
- for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = begin(); i != end(); i++)\r
- {\r
- hash_iterator<K,T,H,E,const std::pair<const K,T> > found = right.find(i->first);\r
- if (found == right.end()) return false;\r
- if (!(i->second == found->second)) return false;\r
- }\r
- return true;\r
- }\r
-\r
- // set up the hash to auto-rehash at a specific size\r
- // setting the rehash size to 0 forces manual rehashing\r
- template<typename K, typename T, class H, class E>\r
- void hash<K,T,H,E>::auto_rehash(void)\r
- {\r
- m_rehash = m_bins;\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- void hash<K,T,H,E>::manual_rehash(void)\r
- {\r
- m_rehash = 0;\r
- }\r
-\r
- // the rehash function\r
- // builds a new hash table and moves the elements (without copying) from the old to the new\r
- // I store the un-modulused hash value in the element for more efficient rehashing\r
- // passing 0 to the bins parameter does auto-rehashing\r
- // passing any other value forces the number of bins\r
-\r
- template<typename K, typename T, class H, class E>\r
- void hash<K,T,H,E>::rehash(unsigned bins)\r
- {\r
- // user specified size: just take the user's value\r
- // auto calculate: if the load is high, increase the size; else do nothing\r
- unsigned new_bins = bins ? bins : m_bins;\r
- if (bins == 0 && m_size > 0)\r
- {\r
- // these numbers are pretty arbitrary\r
- // TODO - make them user-customisable?\r
- float load = loading();\r
- if (load > 2.0)\r
- new_bins = (unsigned)(m_bins * load);\r
- else if (load > 1.0)\r
- new_bins = m_bins * 2;\r
- }\r
- if (new_bins == m_bins) return;\r
- // set the new rehashing point if auto-rehashing is on\r
- if (m_rehash) m_rehash = new_bins;\r
- // move aside the old structure\r
- hash_element<K,T,H,E>** old_values = m_values;\r
- unsigned old_bins = m_bins;\r
- // create a replacement structure\r
- m_values = new hash_element<K,T,H,E>*[new_bins];\r
- for (unsigned i = 0; i < new_bins; i++)\r
- m_values[i] = 0;\r
- m_bins = new_bins;\r
- // move all the old elements across, rehashing each one\r
- for (unsigned j = 0; j < old_bins; j++)\r
- {\r
- while(old_values[j])\r
- {\r
- // unhook from the old structure\r
- hash_element<K,T,H,E>* current = old_values[j];\r
- old_values[j] = current->m_next;\r
- // rehash using the stored hash value\r
- unsigned bin = current->bin();\r
- // hook it into the new structure\r
- current->m_next = m_values[bin];\r
- m_values[bin] = current;\r
- }\r
- }\r
- // now delete the old structure\r
- delete[] old_values;\r
- }\r
-\r
- // the loading is the average number of elements per bin\r
- // this simplifies to the total elements divided by the number of bins\r
-\r
- template<typename K, typename T, class H, class E>\r
- float hash<K,T,H,E>::loading(void) const\r
- {\r
- return (float)m_size / (float)m_bins;\r
- }\r
-\r
- // remove all elements from the table\r
-\r
- template<typename K, typename T, class H, class E>\r
- void hash<K,T,H,E>::erase(void)\r
- {\r
- // unhook the list elements and destroy them\r
- for (unsigned i = 0; i < m_bins; i++)\r
- {\r
- hash_element<K,T,H,E>* current = m_values[i];\r
- while(current)\r
- {\r
- hash_element<K,T,H,E>* next = current->m_next;\r
- delete current;\r
- current = next;\r
- }\r
- m_values[i] = 0;\r
- }\r
- m_size = 0;\r
- }\r
-\r
- // test for whether a key is present in the table\r
-\r
- template<typename K, typename T, class H, class E>\r
- bool hash<K,T,H,E>::present(const K& key) const\r
- {\r
- return find(key) != end();\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::size_type hash<K,T,H,E>::count(const K& key) const\r
- {\r
- return present() ? 1 : 0;\r
- }\r
-\r
- // add a key and data element to the table - defined in terms of the general-purpose pair insert function\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key, const T& data)\r
- {\r
- return insert(std::pair<const K,T>(key,data)).first;\r
- }\r
-\r
- // insert a key/data pair into the table\r
- // this removes any old value with the same key since there is no multihash functionality\r
-\r
- template<typename K, typename T, class H, class E>\r
- std::pair<TYPENAME hash<K,T,H,E>::iterator, bool> hash<K,T,H,E>::insert(const std::pair<const K,T>& value)\r
- {\r
- // if auto-rehash is enabled, implement the auto-rehash before inserting the new value\r
- // the table is rehashed if this insertion makes the loading exceed 1.0\r
- if (m_rehash && (m_size >= m_rehash)) rehash();\r
- // calculate the new hash value\r
- unsigned hash_value_full = H()(value.first);\r
- unsigned bin = hash_value_full % m_bins;\r
- bool inserted = true;\r
- // unhook any previous value with this key\r
- // this has been inlined from erase(key) so that the hash value is not calculated twice\r
- hash_element<K,T,H,E>* previous = 0;\r
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
- {\r
- // first check the full stored hash value\r
- if (current->m_hash != hash_value_full) continue;\r
-\r
- // next try the equality operator\r
- if (!E()(current->m_value.first, value.first)) continue;\r
-\r
- // unhook this value and destroy it\r
- if (previous)\r
- previous->m_next = current->m_next;\r
- else\r
- m_values[bin] = current->m_next;\r
- delete current;\r
- m_size--;\r
-\r
- // we've overwritten a previous value\r
- inserted = false;\r
-\r
- // assume there can only be one match so we can give up now\r
- break;\r
- }\r
- // now hook in a new list element at the start of the list for this hash value\r
- hash_element<K,T,H,E>* new_item = new hash_element<K,T,H,E>(this, value, hash_value_full);\r
- new_item->m_next = m_values[bin];\r
- m_values[bin] = new_item;\r
- // increment the size count\r
- m_size++;\r
- // construct an iterator from the list node, and return whether inserted\r
- return std::make_pair(hash_iterator<K,T,H,E,std::pair<const K,T> >(new_item), inserted);\r
- }\r
-\r
- // insert a key with an empty data field ready to be filled in later\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key)\r
- {\r
- return insert(key,T());\r
- }\r
-\r
- // remove a key from the table - return true if the key was found and removed, false if it wasn't present\r
-\r
- template<typename K, typename T, class H, class E>\r
- bool hash<K,T,H,E>::erase(const K& key)\r
- {\r
- unsigned hash_value_full = H()(key);\r
- unsigned bin = hash_value_full % m_bins;\r
- // scan the list for an element with this key\r
- // need to keep a previous pointer because the lists are single-linked\r
- hash_element<K,T,H,E>* previous = 0;\r
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
- {\r
- // first check the full stored hash value\r
- if (current->m_hash != hash_value_full) continue;\r
-\r
- // next try the equality operator\r
- if (!E()(current->m_value.first, key)) continue;\r
-\r
- // found this key, so unhook the element from the list\r
- if (previous)\r
- previous->m_next = current->m_next;\r
- else\r
- m_values[bin] = current->m_next;\r
- // destroy it\r
- delete current;\r
- // remember to maintain the size count\r
- m_size--;\r
- return true;\r
- }\r
- return false;\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- void hash<K,T,H,E>::clear(void)\r
- {\r
- erase();\r
- }\r
-\r
- // search for a key in the table and return an iterator to it\r
- // if the search fails, returns an end() iterator\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::find(const K& key) const\r
- {\r
- // scan the list for this key's hash value for the element with a matching key\r
- unsigned hash_value_full = H()(key);\r
- unsigned bin = hash_value_full % m_bins;\r
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
- {\r
- if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(current);\r
- }\r
- return end();\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::find(const K& key)\r
- {\r
- // scan the list for this key's hash value for the element with a matching key\r
- unsigned hash_value_full = H()(key);\r
- unsigned bin = hash_value_full % m_bins;\r
- for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
- {\r
- if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(current);\r
- }\r
- return end();\r
- }\r
-\r
- // table lookup by key using the index operator[], returning a reference to the data field, not an iterator\r
- // this is rather like the std::map's [] operator\r
- // the difference is that I have a const and non-const version\r
- // the const version will not create the element if not present already, but the non-const version will\r
- // the non-const version is compatible with the behaviour of the map\r
-\r
- template<typename K, typename T, class H, class E>\r
- const T& hash<K,T,H,E>::operator[] (const K& key) const throw(std::out_of_range)\r
- {\r
- // this const version cannot change the hash, so has to raise an exception if the key is missing\r
- hash_iterator<K,T,H,E,const std::pair<const K,T> > found = find(key);\r
- if (found == end())\r
- throw std::out_of_range("key not found in stlplus::hash::operator[]");\r
- return found->second;\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- T& hash<K,T,H,E>::operator[] (const K& key)\r
- {\r
- // this non-const version can change the hash, so creates a new element if the key is missing\r
- hash_iterator<K,T,H,E,std::pair<const K,T> > found = find(key);\r
- if (found == end())\r
- found = insert(key);\r
- return found->second;\r
- }\r
-\r
- // iterators\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::begin(void) const\r
- {\r
- // find the first element\r
- for (unsigned bin = 0; bin < m_bins; bin++)\r
- if (m_values[bin])\r
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(m_values[bin]);\r
- // if the hash is empty, return the end iterator\r
- return end();\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::begin(void)\r
- {\r
- // find the first element\r
- for (unsigned bin = 0; bin < m_bins; bin++)\r
- if (m_values[bin])\r
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(m_values[bin]);\r
- // if the hash is empty, return the end iterator\r
- return end();\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::end(void) const\r
- {\r
- return hash_iterator<K,T,H,E,const std::pair<const K,T> >(this);\r
- }\r
-\r
- template<typename K, typename T, class H, class E>\r
- TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::end(void)\r
- {\r
- return hash_iterator<K,T,H,E,std::pair<const K,T> >(this);\r
- }\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
-\r
-} // end namespace stlplus\r
-\r
projects / chaz / yoink / blobdiff