--- /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