Logo Search packages:      
Sourcecode: poco version File versions  Download package

SimpleHashTable.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> >
00058 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:
00069       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);
            }
      }

00100       ~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;
      }

00134       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;
      }

00143       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;
      }

00168       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;
      }

00177       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);
      }

00207       const Value& get(const Key& key) const
            /// Throws an exception if the value does not exist
      {
            UInt32 hsh = hash(key);
            return getRaw(key, hsh);
      }

00214       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++;
            }
      }

00235       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++;
            }
      }

00267       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++;
            }
      }

00291       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);
      }

00298       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++;
            }
      }

00346       std::size_t size() const
            /// Returns the number of elements already inserted into the SimpleHashTable
      {
            return _size;
      }
      
      UInt32 capacity() const
      {
            return _capacity;
      }

00357       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);
                        }
                  }
            }
      }

00374       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

Generated by  Doxygen 1.6.0   Back to index