source: XMLIO_V2/external/src/POCO/Foundation.save/Poco/LinearHashTable.h @ 80

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

        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;
        };
        
        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.
        {
        }
        
        ~LinearHashTable()
                /// Destroys the LinearHashTable.
        {
        }
        
        LinearHashTable& operator = (const LinearHashTable& table)
                /// Assigns another LinearHashTable.
        {
                LinearHashTable tmp(table);
                swap(tmp);
                return *this;
        }
        
        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);
        }
        
        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());
        }
        
        ConstIterator end() const
                /// Returns an iterator pointing to the end of the table.
        {
                return ConstIterator(_buckets.end(), _buckets.end(), _buckets.front().end());
        }
        
        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());
        }
        
        Iterator end()
                /// Returns an iterator pointing to the end of the table.
        {
                return Iterator(_buckets.end(), _buckets.end(), _buckets.front().end());
        }
                
        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();
        }

        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();
        }
        
        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;
        }
        
        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);
                }
        }
        
        void erase(Iterator it)
                /// Erases the element pointed to by it.
        {
                if (it != end())
                {
                        it._vecIt->erase(it._buckIt);
                        --_size;
                        merge();
                }
        }
        
        void erase(const Value& value)
                /// Erases the element with the given value, if it exists.
        {
                Iterator it = find(value);
                erase(it);
        }
        
        void clear()
                /// Erases all elements.
        {
                LinearHashTable empty;
                swap(empty);
        }
        
        std::size_t size() const
                /// Returns the number of elements in the table.
        {
                return _size;
        }
        
        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