topical media & game development

topical media & game development

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

lib-of-vs-libs-Poco-include-Poco-SimpleHashTable.h / h


  //
  // SimpleHashTable.h
  //
  //  $Id: //poco/1.3/Foundation/include/Poco/SimpleHashTable.h#2$ 
  //
  // Library: Foundation
  // Package: Hashing
  // Module:  SimpleHashTable
  //
  // Definition of the SimpleHashTable class.
  //
  // Copyright (c) 2006, Applied Informatics Software Engineering GmbH.
  // and Contributors.
  //
  // Permission is hereby granted, free of charge, to any person or organization
  // obtaining a copy of the software and accompanying documentation covered by
  // this license (the "Software") to use, reproduce, display, distribute,
  // execute, and transmit the Software, and to prepare derivative works of the
  // Software, and to permit third-parties to whom the Software is furnished to
  // do so, all subject to the following:
  // 
  // The copyright notices in the Software and this entire statement, including
  // the above license grant, this restriction and the following disclaimer,
  // must be included in all copies of the Software, in whole or in part, and
  // all derivative works of the Software, unless such copies or derivative
  // works are solely in the form of machine-executable object code generated by
  // a source language processor.
  // 
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  // FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
  // SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
  // FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
  // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  // DEALINGS IN THE SOFTWARE.
  //
  
  ifndef Foundation_SimpleHashTable_INCLUDED
  define Foundation_SimpleHashTable_INCLUDED
  
  include "Poco/Foundation.h"
  include "Poco/Exception.h"
  include "Poco/HashFunction.h"
  include "Poco/HashStatistic.h"
  include <vector>
  include <map>
  include <cstddef>
  include <algorithm>
  
  namespace Poco {

deprecated


  template <class Key, class Value, class KeyHashFunction = HashFunction<Key> >
  class SimpleHashTable

A SimpleHashTable stores a key value pair that can be looked up via a hashed key. In comparision to a HashTable, this class handles collisions by sequentially searching the next free location. This also means that the maximum size of this table is limited, i.e. if the hash table is full, it will throw an exception and that this class does not support remove operations. On the plus side it is faster than the HashTable. This class is NOT thread safe. { public: class HashEntry { public: Key key; Value value; HashEntry(const Key k, const Value v): key(k), value(v) { } };


          typedef std::vector<HashEntry*> HashTableVector;
  
          SimpleHashTable(UInt32 capacity = 251): _entries(capacity, 0), _size(0), _capacity(capacity)

Creates the SimpleHashTable. { }


          SimpleHashTable(const SimpleHashTable& ht):
                  _size(ht._size),
                  _capacity(ht._capacity)
          {
                  _entries.reserve(ht._capacity);
                  for (typename HashTableVector::iterator it = ht._entries.begin(); it != ht._entries.end(); ++it)
                  {
                          if (*it) 
                                  _entries.push_back(new HashEntry(*it));
                          else
                                  _entries.push_back(0);
                  }
          }
  
          ~SimpleHashTable()

Destroys the SimpleHashTable. { clear(); }


          SimpleHashTable& operator = (const SimpleHashTable& ht)
          {
                  if (this != &ht)
                  {
                          SimpleHashTable tmp(ht);
                          swap(tmp);
                  }
                  return *this;
          }
          
          void swap(SimpleHashTable& ht)
          {
                  using std::swap;
                  swap(_entries, ht._entries);
                  swap(_size, ht._size);
                  swap(_capacity, ht._capacity);
          }
  
          void clear()
          {
                  for (typename HashTableVector::iterator it = _entries.begin(); it != _entries.end(); ++it)
                  {
                          delete *it;
  			*it = 0;
                  }
                  _size = 0;
          }
  
          UInt32 insert(const Key& key, const Value& value)

Returns the hash value of the inserted item. Throws an exception if the entry was already inserted { UInt32 hsh = hash(key); insertRaw(key, hsh, value); return hsh; }


          Value& insertRaw(const Key& key, UInt32 hsh, const Value& value)

Returns the hash value of the inserted item. Throws an exception if the entry was already inserted { UInt32 pos = hsh; if (!_entries[pos]) _entries[pos] = new HashEntry(key, value); else { UInt32 origHash = hsh; while (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) throw ExistsException(); if (hsh - origHash > _capacity) throw PoolOverflowException("SimpleHashTable full"); hsh++; } pos = hsh % _capacity; _entries[pos] = new HashEntry(key, value); } _size++; return _entries[pos]->value; }


          UInt32 update(const Key& key, const Value& value)

Returns the hash value of the inserted item. Replaces an existing entry if it finds one { UInt32 hsh = hash(key); updateRaw(key, hsh, value); return hsh; }


          void updateRaw(const Key& key, UInt32 hsh, const Value& value)

Returns the hash value of the inserted item. Replaces an existing entry if it finds one { if (!_entries[hsh]) _entries[hsh] = new HashEntry(key, value); else { UInt32 origHash = hsh; while (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) { _entries[hsh % _capacity]->value = value; return; } if (hsh - origHash > _capacity) throw PoolOverflowException("SimpleHashTable full"); hsh++; } _entries[hsh % _capacity] = new HashEntry(key, value); } _size++; }


          UInt32 hash(const Key& key) const
          {
                  return _hash(key, _capacity);
          }
  
          const Value& get(const Key& key) const

Throws an exception if the value does not exist { UInt32 hsh = hash(key); return getRaw(key, hsh); }


          const Value& getRaw(const Key& key, UInt32 hsh) const

Throws an exception if the value does not exist { UInt32 origHash = hsh; while (true) { if (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) { return _entries[hsh % _capacity]->value; } } else throw InvalidArgumentException("value not found"); if (hsh - origHash > _capacity) throw InvalidArgumentException("value not found"); hsh++; } }


          Value& get(const Key& key)

Throws an exception if the value does not exist { UInt32 hsh = hash(key); return const_cast<Value&>(getRaw(key, hsh)); } const Value& operator [] (const Key& key) const { return get(key); } Value& operator [] (const Key& key) { UInt32 hsh = hash(key); UInt32 origHash = hsh; while (true) { if (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) { return _entries[hsh % _capacity]->value; } } else return insertRaw(key, hsh, Value()); if (hsh - origHash > _capacity) return insertRaw(key, hsh, Value()); hsh++; } }


          const Key& getKeyRaw(const Key& key, UInt32 hsh)

Throws an exception if the key does not exist. returns a reference to the internally stored key. Useful when someone does an insert and wants for performance reason only to store a pointer to the key in another collection { UInt32 origHash = hsh; while (true) { if (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) { return _entries[hsh % _capacity]->key; } } else throw InvalidArgumentException("key not found");


                          if (hsh - origHash > _capacity)
                                  throw InvalidArgumentException("key not found");
                          hsh++;
                  }
          }
  
          bool get(const Key& key, Value& v) const

Sets v to the found value, returns false if no value was found { UInt32 hsh = hash(key); return getRaw(key, hsh, v); }


          bool getRaw(const Key& key, UInt32 hsh, Value& v) const

Sets v to the found value, returns false if no value was found { UInt32 origHash = hsh; while (true) { if (_entries[hsh % _capacity]) { if (_entries[hsh % _capacity]->key == key) { v = _entries[hsh % _capacity]->value; return true; } } else return false; if (hsh - origHash > _capacity) return false; hsh++; } }


          bool exists(const Key& key) const
          {
                  UInt32 hsh = hash(key);
                  return existsRaw(key, hsh);
          }
  
          bool existsRaw(const Key& key, UInt32 hsh) const
          {
                  UInt32 origHash = hsh;
                  while (true)
                  {
                          if (_entries[hsh % _capacity])
                          {
                                  if (_entries[hsh % _capacity]->key == key)
                                  {
                                          return true;
                                  }
                          }
                          else
                                  return false;
                          if (hsh - origHash > _capacity)
                                  return false;
                          hsh++;
                  }
          }
  
          std::size_t size() const

Returns the number of elements already inserted into the SimpleHashTable { return _size; } UInt32 capacity() const { return _capacity; }


          void resize(UInt32 newSize)

Resizes the hashtable, rehashes all existing entries. Expensive! { if (_capacity != newSize) { SimpleHashTable tmp(newSize); swap(tmp); for (typename HashTableVector::const_iterator it = tmp._entries.begin(); it != tmp._entries.end(); ++it) { if (*it) { insertRaw((*it)->key, hash((*it)->key), (*it)->value); } } } }


          HashStatistic currentState(bool details = false) const

Returns the current internal state { UInt32 numberOfEntries = (UInt32)_size; UInt32 numZeroEntries = 0; UInt32 maxEntriesPerHash = 0; std::vector<UInt32> detailedEntriesPerHash; #ifdef _DEBUG UInt32 totalSize = 0; #endif for (int i=0; i < _capacity; ++i) { if (_entries[i]) { maxEntriesPerHash = 1; UInt32 size = 1; if (details) detailedEntriesPerHash.push_back(size); #ifdef DEBUG totalSize += size; #endif } else { numZeroEntries++; if (details) detailedEntriesPerHash.push_back(0); } } poco_assert_dbg(totalSize == numberOfEntries);


                  return HashStatistic(_capacity, numberOfEntries, numZeroEntries, maxEntriesPerHash, detailedEntriesPerHash);
          }
  
  private:
          HashTableVector _entries;
          std::size_t     _size;
          UInt32          _capacity;
          KeyHashFunction _hash;
  };
  
  } // namespace Poco
  
  endif // Foundation_HashTable_INCLUDED

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.