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

LinearHashTable.h
//
// LinearHashTable.h
//
// $Id: //poco/1.3/Foundation/include/Poco/LinearHashTable.h#5 $
//
// Library: Foundation
// Package: Hashing
// Module:  LinearHashTable
//
// Definition of the LinearHashTable 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_LinearHashTable_INCLUDED
#define Foundation_LinearHashTable_INCLUDED


#include "Poco/Foundation.h"
#include "Poco/Hash.h"
#include <functional>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstddef>


namespace Poco {


template <class Value, class HashFunc = Hash<Value> >
00056 class LinearHashTable
      /// This class implements a linear hash table.
      ///
      /// In a linear hash table, the available address space
      /// grows or shrinks dynamically. A linar hash table thus
      /// supports any number of insertions or deletions without
      /// lookup or insertion performance deterioration.
      ///
      /// Linear hashing was discovered by Witold Litwin in 1980
      /// and described in the paper LINEAR HASHING: A NEW TOOL FOR FILE AND TABLE ADDRESSING.
      ///
      /// For more information on linear hashing, see <http://en.wikipedia.org/wiki/Linear_hash>.
      ///
      /// The LinearHashTable is not thread safe.
      ///
      /// Value must support comparison for equality.
      ///
      /// Find, insert and delete operations are basically O(1) with regard
      /// to the total number of elements in the table, and O(N) with regard
      /// to the number of elements in the bucket where the element is stored.
      /// On average, every bucket stores one element; the exact number depends
      /// on the quality of the hash function. In most cases, the maximum number of
      /// elements in a bucket should not exceed 3.
{
public:
      typedef Value               ValueType;
      typedef Value&              Reference;
      typedef const Value&        ConstReference;
      typedef Value*              Pointer;
      typedef const Value*        ConstPointer;
      typedef HashFunc            Hash;
      typedef std::vector<Value>  Bucket;
      typedef std::vector<Bucket> BucketVec;
      typedef typename Bucket::iterator    BucketIterator;
      typedef typename BucketVec::iterator BucketVecIterator;

00092       class ConstIterator: public std::iterator<std::forward_iterator_tag, Value>
      {
      public:
            ConstIterator()
            {
            }
            
            ConstIterator(const BucketVecIterator& vecIt, const BucketVecIterator& endIt, const BucketIterator& buckIt):
                  _vecIt(vecIt),
                  _endIt(endIt),
                  _buckIt(buckIt)
            {
            }

            ConstIterator(const ConstIterator& it):
                  _vecIt(it._vecIt),
                  _endIt(it._endIt),
                  _buckIt(it._buckIt)
            {
            }
            
            ConstIterator& operator = (const ConstIterator& it)
            {
                  ConstIterator tmp(it);
                  swap(tmp);
                  return *this;
            }
            
            void swap(ConstIterator& it)
            {
                  using std::swap;
                  swap(_vecIt, it._vecIt);
                  swap(_endIt, it._endIt);
                  swap(_buckIt, it._buckIt);
            }
            
            bool operator == (const ConstIterator& it) const
            {
                  return _vecIt == it._vecIt && (_vecIt == _endIt || _buckIt == it._buckIt);
            }

            bool operator != (const ConstIterator& it) const
            {
                  return _vecIt != it._vecIt || (_vecIt != _endIt && _buckIt != it._buckIt);
            }
            
            const typename Bucket::value_type& operator * () const
            {
                  return *_buckIt;
            }

            const typename Bucket::value_type* operator -> () const
            {
                  return &*_buckIt;
            }
            
            ConstIterator& operator ++ () // prefix
            {
                  if (_vecIt != _endIt)
                  {
                        ++_buckIt;
                        while (_vecIt != _endIt && _buckIt == _vecIt->end())
                        {
                              ++_vecIt;
                              if (_vecIt != _endIt) _buckIt = _vecIt->begin();
                        }
                  }
                  return *this;
            }
            
            ConstIterator operator ++ (int) // postfix
            {
                  ConstIterator tmp(*this);
                  ++*this;
                  return tmp;
            }
            
      protected:
            BucketVecIterator _vecIt;
            BucketVecIterator _endIt;
            BucketIterator    _buckIt;
            
            friend class LinearHashTable;
      };
      
00177       class Iterator: public ConstIterator
      {
      public:
            Iterator()
            {
            }
            
            Iterator(const BucketVecIterator& vecIt, const BucketVecIterator& endIt, const BucketIterator& buckIt):
                  ConstIterator(vecIt, endIt, buckIt)
            {
            }

            Iterator(const Iterator& it):
                  ConstIterator(it)
            {
            }
            
            Iterator& operator = (const Iterator& it)
            {
                  Iterator tmp(it);
                  swap(tmp);
                  return *this;
            }
            
            void swap(Iterator& it)
            {
                  ConstIterator::swap(it);
            }
                        
            typename Bucket::value_type& operator * ()
            {
                  return *this->_buckIt;
            }

            const typename Bucket::value_type& operator * () const
            {
                  return *this->_buckIt;
            }

            typename Bucket::value_type* operator -> ()
            {
                  return &*this->_buckIt;
            }

            const typename Bucket::value_type* operator -> () const
            {
                  return &*this->_buckIt;
            }
            
            Iterator& operator ++ () // prefix
            {
                  ConstIterator::operator ++ ();
                  return *this;
            }
            
            Iterator operator ++ (int) // postfix
            {
                  Iterator tmp(*this);
                  ++*this;
                  return tmp;
            }

            friend class LinearHashTable;
      };
      
      LinearHashTable(std::size_t initialReserve = 64): 
            _split(0),
            _front(1),
            _size(0)
            /// Creates the LinearHashTable, using the given initialReserve.
      {
            _buckets.reserve(calcSize(initialReserve));
            _buckets.push_back(Bucket());
      }
      
      LinearHashTable(const LinearHashTable& table):
            _buckets(table._buckets),
            _split(table._split),
            _front(table._front),
            _size(table._size)
            /// Creates the LinearHashTable by copying another one.
      {
      }
      
00261       ~LinearHashTable()
            /// Destroys the LinearHashTable.
      {
      }
      
00266       LinearHashTable& operator = (const LinearHashTable& table)
            /// Assigns another LinearHashTable.
      {
            LinearHashTable tmp(table);
            swap(tmp);
            return *this;
      }
      
00274       void swap(LinearHashTable& table)
            /// Swaps the LinearHashTable with another one.
      {
            using std::swap;
            swap(_buckets, table._buckets);
            swap(_split, table._split);
            swap(_front, table._front);
            swap(_size, table._size);
      }
      
00284       ConstIterator begin() const
            /// Returns an iterator pointing to the first entry, if one exists.
      {
            BucketVecIterator it(_buckets.begin());
            BucketVecIterator end(_buckets.end());
            while (it != end && it->empty())
            {
                  ++it;
            }
            if (it == end)
                  return this->end();
            else
                  return ConstIterator(it, end, it->begin());
      }
      
00299       ConstIterator end() const
            /// Returns an iterator pointing to the end of the table.
      {
            return ConstIterator(_buckets.end(), _buckets.end(), _buckets.front().end());
      }
      
00305       Iterator begin()
            /// Returns an iterator pointing to the first entry, if one exists.
      {
            BucketVecIterator it(_buckets.begin());
            BucketVecIterator end(_buckets.end());
            while (it != end && it->empty())
            {
                  ++it;
            }
            if (it == end)
                  return this->end();
            else
                  return Iterator(it, end, it->begin());
      }
      
00320       Iterator end()
            /// Returns an iterator pointing to the end of the table.
      {
            return Iterator(_buckets.end(), _buckets.end(), _buckets.front().end());
      }
            
00326       ConstIterator find(const Value& value) const
            /// Finds an entry in the table.
      {
            std::size_t addr = bucketAddress(value);
            BucketVecIterator it(_buckets.begin() + addr);
            BucketIterator buckIt(std::find(it->begin(), it->end(), value));
            if (buckIt != it->end())
                  return ConstIterator(it, _buckets.end(), buckIt);
            else
                  return end();
      }

00338       Iterator find(const Value& value)
            /// Finds an entry in the table.
      {
            std::size_t addr = bucketAddress(value);
            BucketVecIterator it(_buckets.begin() + addr);
            BucketIterator buckIt(std::find(it->begin(), it->end(), value));
            if (buckIt != it->end())
                  return Iterator(it, _buckets.end(), buckIt);
            else
                  return end();
      }
      
00350       std::size_t count(const Value& value) const
            /// Returns the number of elements with the given
            /// value, with is either 1 or 0.
      {
            return find(value) != end() ? 1 : 0;
      }
      
00357       std::pair<Iterator, bool> insert(const Value& value)
            /// Inserts an element into the table.
            ///
            /// If the element already exists in the table,
            /// a pair(iterator, false) with iterator pointing to the 
            /// existing element is returned.
            /// Otherwise, the element is inserted an a 
            /// pair(iterator, true) with iterator
            /// pointing to the new element is returned.
      {
            split();
            std::size_t addr = bucketAddress(value);
            BucketVecIterator it(_buckets.begin() + addr);
            BucketIterator buckIt(std::find(it->begin(), it->end(), value));
            if (buckIt == it->end())
            {
                  buckIt = it->insert(buckIt, value);
                  ++_size;
                  return std::make_pair(Iterator(it, _buckets.end(), buckIt), true);
            }
            else
            {
                  return std::make_pair(Iterator(it, _buckets.end(), buckIt), false);
            }
      }
      
00383       void erase(Iterator it)
            /// Erases the element pointed to by it.
      {
            if (it != end())
            {
                  it._vecIt->erase(it._buckIt);
                  --_size;
                  merge();
            }
      }
      
00394       void erase(const Value& value)
            /// Erases the element with the given value, if it exists.
      {
            Iterator it = find(value);
            erase(it);
      }
      
00401       void clear()
            /// Erases all elements.
      {
            LinearHashTable empty;
            swap(empty);
      }
      
00408       std::size_t size() const
            /// Returns the number of elements in the table.
      {
            return _size;
      }
      
00414       bool empty() const
            /// Returns true iff the table is empty.
      {
            return _size == 0;
      }
      
protected:
      std::size_t bucketAddress(const Value& value) const
      {
            std::size_t n = _hash(value);
            if (n % _front >= _split)
                  return n % _front;
            else
                  return n % (2*_front);
      }
      
      void split()
      {
            if (_split == _front)
            {
                  _split = 0;
                  _front *= 2;
                  _buckets.reserve(_front*2);
            }
            Bucket tmp;
            _buckets.push_back(tmp);
            _buckets[_split].swap(tmp);
            ++_split;
            for (BucketIterator it = tmp.begin(); it != tmp.end(); ++it)
            {
                  using std::swap;
                  std::size_t addr = bucketAddress(*it);
                  _buckets[addr].push_back(Value());
                  swap(*it, _buckets[addr].back());
            }
      }
      
      void merge()
      {
            if (_split == 0)
            {
                  _front /= 2;
                  _split = _front;
            }
            --_split;
            Bucket tmp;
            tmp.swap(_buckets.back());
            _buckets.pop_back();
            for (BucketIterator it = tmp.begin(); it != tmp.end(); ++it)
            {
                  using std::swap;
                  std::size_t addr = bucketAddress(*it);
                  _buckets[addr].push_back(Value());
                  swap(*it, _buckets[addr].back());
            }
      }
      
      static std::size_t calcSize(std::size_t initialSize)
      {
            std::size_t size = 32;
            while (size < initialSize) size *= 2;
            return size;
      }
      
private:
      // Evil hack: _buckets must be mutable because both ConstIterator and Iterator hold 
      // ordinary iterator's (not const_iterator's).
      mutable BucketVec _buckets;
      std::size_t _split;
      std::size_t _front;
      std::size_t _size;
      HashFunc    _hash;
};


} // namespace Poco


#endif // Foundation_LinearHashTable_INCLUDED

Generated by  Doxygen 1.6.0   Back to index