XalanMap.hpp

Go to the documentation of this file.

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the  "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
#if !defined(XALANMAP_HEADER_GUARD_1357924680)
#define XALANMAP_HEADER_GUARD_1357924680
 
 
// Base include file.  Must be first.
#include <xalanc/Include/PlatformDefinitions.hpp>
 
 
 
#include <cstddef>
#include <algorithm>
#include <functional>
#include <utility>
 
 
#include <xalanc/Include/XalanVector.hpp>
#include <xalanc/Include/XalanList.hpp>
 
 
 
namespace XALAN_CPP_NAMESPACE {
 
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable: 4189)
#endif
 
typedef size_t  size_type;
 
template <class Key>
class XalanHasher
{
public:
    size_type operator()(const Key& key) const
    {
        const char *byteArray = reinterpret_cast<const char*>(&key);
 
        size_type result = 0;
 
        for (size_type i = 0; i < sizeof(Key); ++i)
        {
            result = (result << 1) ^ byteArray[i];
        }
 
        return result;
    }
};
 
template <class Key>
struct XalanMapKeyTraits
{
    typedef XalanHasher<Key>                    Hasher;
    typedef std::equal_to<Key>   Comparator;
};
 
 
template <class Key>
struct XalanHashMemberPointer
{
 
    size_type operator() (const Key * key) const
    {
        assert (key != 0);
        return key->hash();
    }
};
 
template <class Key>
struct XalanHashMemberReference
{
 
    size_type operator() (const Key& key) const
    {
        return key.hash();
    }
};
 
 
 
template <class Value>
struct XalanMapIteratorTraits
{
    typedef Value           value_type;
    typedef Value&          reference;
    typedef Value*          pointer;
};
 
template <class Value>
struct XalanMapConstIteratorTraits
{
    typedef Value           value_type;
    typedef const Value&    reference;
    typedef const Value*    pointer;
};
 
template <class XalanMapTraits, class BaseIterator>
struct XalanMapIterator
{
    typedef typename XalanMapTraits::value_type         value_type;
    typedef typename XalanMapTraits::reference          reference;
    typedef typename XalanMapTraits::pointer            pointer;
 
    typedef ptrdiff_t                           difference_type;
    typedef std::bidirectional_iterator_tag iterator_category;
 
    typedef XalanMapIterator<
        XalanMapIteratorTraits<value_type>, 
        BaseIterator>                                   Iterator; 
 
    XalanMapIterator(const Iterator & theRhs) :
        baseIterator(theRhs.baseIterator)
    {
    }
 
    XalanMapIterator(const BaseIterator & theRhs) :
        baseIterator(theRhs)
    {
    }
 
    XalanMapIterator operator++(int)
    {
        XalanMapIterator temp(*this);
        ++baseIterator;
        return temp;
    }
 
    XalanMapIterator& operator++()
    {
        ++baseIterator;
        return *this;
    }
 
    reference operator*() const
    {
        return *baseIterator->value;
    }
 
    pointer operator->() const
    {
        return baseIterator->value;
    }
 
    bool operator==(const XalanMapIterator& theRhs) const
    {
        return theRhs.baseIterator == baseIterator;
    }
 
    bool operator!=(const XalanMapIterator& theRhs) const
    {
        return !(theRhs == *this);
    }
 
    BaseIterator baseIterator;
};
 
 
 
/**
  * Xalan implementation of a hashtable.
  *
  */
template <
        class Key,
        class Value,
        class KeyTraits = XalanMapKeyTraits<Key>,
        class KeyConstructionTraits = MemoryManagedConstructionTraits<Key>,
        class ValueConstructionTraits = MemoryManagedConstructionTraits<Value> >
class XalanMap
{
public:
    /**
     * Each map entry is stored in a linked list where an entry
     * consists of a pointer to the key/value pair and a flag to indicate
     * whether the entry has been erased.
     * The hash buckets are a vector of pointers into the entry list.
     * Deleted entries are spliced into another list and marked 'erased'.
     */
 
    typedef Key                 key_type;
    typedef Value               data_type;
    typedef size_t              size_type;
 
    typedef std::pair<const key_type, data_type>   value_type;
 
    struct Entry
    {
        value_type* value;
        bool        erased;
 
        Entry(value_type* theValue) :
            value(theValue),
            erased(false)
        {
        }
    };
 
    typedef XalanList<Entry>                                EntryListType;
 
    typedef XalanVector<typename EntryListType::iterator>   BucketType;
    typedef XalanVector<BucketType, ConstructWithMemoryManagerTraits<BucketType> >      BucketTableType;
 
    typedef typename EntryListType::iterator       EntryListIterator;
    typedef typename BucketTableType::iterator     TableIterator;
    typedef typename BucketType::iterator          BucketIterator;
 
    typedef XalanMapIterator<
                XalanMapIteratorTraits<value_type>, 
                typename EntryListType::iterator>           iterator;
    typedef XalanMapIterator<
                XalanMapConstIteratorTraits<value_type>, 
                typename EntryListType::iterator>     const_iterator;
 
    typedef typename KeyConstructionTraits::Constructor     FirstConstructor;
    typedef typename ValueConstructionTraits::Constructor   SecondConstructor;
 
    enum
    {
        eDefaultMinBuckets = 29u,
        eDefaultEraseThreshold = 50u,
        eMinimumBucketSize = 5u
    };
 
 
    XalanMap(
            MemoryManager&  theMemoryManager,
            double              loadFactor = 0.75,
            size_type           minBuckets = eDefaultMinBuckets,
            size_type           eraseThreshold = eDefaultEraseThreshold) :
        m_memoryManager(&theMemoryManager),
        m_loadFactor(loadFactor),
        m_minBuckets(minBuckets),
        m_size(0),
        m_entries(theMemoryManager),
        m_freeEntries(theMemoryManager),
        m_buckets(theMemoryManager),
        m_eraseCount(0),
        m_eraseThreshold(eraseThreshold)
    {
    }
 
    XalanMap(
            const XalanMap&     theRhs,
            MemoryManager&  theMemoryManager) :
        m_memoryManager(&theMemoryManager),
        m_loadFactor(theRhs.m_loadFactor),
        m_minBuckets(theRhs.m_minBuckets),
        m_size(0),
        m_entries(theMemoryManager),
        m_freeEntries(theMemoryManager),
        m_buckets(
            size_type(m_loadFactor * theRhs.size()) + 1,
            BucketType(*m_memoryManager),
            theMemoryManager),
        m_eraseCount(0),
        m_eraseThreshold(theRhs.m_eraseThreshold)
    {
        const_iterator entry = theRhs.begin();
 
        while(entry != theRhs.end())
        {
            insert(*entry);
            ++entry;
        }
 
        assert(m_size == theRhs.m_size);
    }
 
    MemoryManager&
    getMemoryManager()
    {
        assert (m_memoryManager != 0);
 
        return *m_memoryManager;
    }
 
    ~XalanMap()
    {
        doRemoveEntries();
 
        if (!m_buckets.empty())
        {
            EntryListIterator   toRemove = m_freeEntries.begin();
 
            while(toRemove != m_freeEntries.end())
            {
                deallocate(toRemove->value);
                ++toRemove;
            }      
        }
    }
 
    XalanMap&
    operator=(const XalanMap&   theRhs) 
    {
        XalanMap    theTemp(theRhs, *m_memoryManager);
 
        swap(theTemp);
 
        return *this;
    }
 
    size_type size() const
    {
        return m_size;
    }
 
    bool empty() const
    {
        return m_size == 0;
    }
 
    iterator begin()
    {
        return m_entries.begin();
    }
 
    const_iterator begin() const
    {
        return  const_cast<XalanMap*>(this)->begin();
    }
 
    iterator end()
    {
        return m_entries.end();
    }
 
    const_iterator end() const 
    {
        return const_cast<XalanMap*>(this)->end();
    }
 
    iterator find(const key_type& key)
    {
        if (m_size != 0)
        {
            assert(m_buckets.empty() == false);
 
            const size_type     index = doHash(key);
            assert(index < m_buckets.size());
 
            BucketType&     bucket = m_buckets[index];
            BucketIterator  pos = bucket.begin();
 
            while (pos != bucket.end())
            {
                if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
                {
                    return iterator(*pos);
                }
                ++pos;
            }
        }
 
        return end();
    }
 
    const_iterator find(const key_type& key) const 
    {
        return const_cast<XalanMap *>(this)->find(key);
    }
 
    data_type & operator[](const key_type& key)
    {
        iterator pos = find(key);
 
        if (pos == end())
        {
            pos = doCreateEntry(key);
        }
 
        return (*pos).second;
    }
 
    void
    insert(const value_type&    value)
    {
        insert(value.first, value.second);
    }
 
    void insert(const key_type& key, const data_type& data)
    {
        const const_iterator    pos = find(key);
 
        if (pos == end())
        {
            doCreateEntry(key, &data);
        }
    }
 
    void erase(iterator pos)
    {
        if (pos != end())
        {
            doErase(pos);
        }
    }
 
    size_type erase(const key_type& key)
    {
        const iterator  pos = find(key);
 
        if (pos != end())
        {
            doErase(pos);
 
            return 1;
        }
        else
        {
            return 0;
        }
    }
 
    void clear() 
    {
        doRemoveEntries();
 
        TableIterator   bucketPos = m_buckets.begin();
 
        while (bucketPos != m_buckets.end())
        {
            bucketPos->clear();
            ++bucketPos;
        }
 
        m_eraseCount = 0;
 
        assert(0 == m_size);
        assert(m_entries.empty());
    }
 
    void swap(XalanMap& theRhs)
    {
        const size_type tempSize = m_size;
        m_size = theRhs.m_size;
        theRhs.m_size = tempSize;
 
        MemoryManager* const    tempMemoryManager = m_memoryManager;
        m_memoryManager = theRhs.m_memoryManager;
        theRhs.m_memoryManager = tempMemoryManager;
 
        const size_type     tempEraseCount = m_eraseCount;
        m_eraseCount = theRhs.m_eraseCount;
        theRhs.m_eraseCount = tempEraseCount;
 
        const size_type     tempEraseTheshold = m_eraseThreshold;
        m_eraseThreshold = theRhs.m_eraseThreshold;
        theRhs.m_eraseThreshold = tempEraseTheshold;
 
        m_entries.swap(theRhs.m_entries);
        m_freeEntries.swap(theRhs.m_freeEntries);
        m_buckets.swap(theRhs.m_buckets);
    }
 
protected:
 
    iterator doCreateEntry(const key_type & key, const data_type*  data = 0)
    {
        // if there are no buckets, create initial minimum set of buckets
        if (m_buckets.empty())
        {
            m_buckets.insert(
                m_buckets.begin(),
                m_minBuckets,
                BucketType(*m_memoryManager));
        }
 
        // if the load factor has been reached, rehash
        if (size_type(m_loadFactor * size()) > m_buckets.size())
        {
            rehash();
        }
 
        const size_type     index = doHash(key);
 
        if (m_freeEntries.empty())
        {
            m_freeEntries.push_back(Entry(allocate(1)));
        }
 
        // insert a new entry as the first position in the bucket
        Entry&  newEntry = m_freeEntries.back();
        newEntry.erased = false;
 
        FirstConstructor::construct(
            const_cast<key_type*>(&newEntry.value->first),
            key,
            *m_memoryManager);
 
        if (data != 0)
        {
            SecondConstructor::construct(
                &newEntry.value->second,
                *data,
                *m_memoryManager);
        }
        else
        {
             SecondConstructor::construct(
                 &newEntry.value->second,
                 *m_memoryManager);
        }
 
        m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end());
 
        m_buckets[index].push_back(--m_entries.end());
 
        ++m_size;
 
        return iterator(--m_entries.end());
    }
 
    void doRemoveEntry(const iterator & toRemovePos)
    {   
        value_type& toRemove = *toRemovePos;
#if defined(_MSC_VER) && _MSC_VER <= 1300
        toRemove.value_type::~value_type();
#else
        toRemove.~value_type();
#endif
        m_freeEntries.splice(
                m_freeEntries.end(), 
                m_entries, 
                toRemovePos.baseIterator);
 
        toRemovePos.baseIterator->erased = true;
 
        --m_size;
    }
 
    void
    doRemoveEntries()
    {
        while(size() > 0)
        {
            doRemoveEntry(begin());
        }
    }
 
    void
    doErase(iterator    pos)
    {
        assert(pos != end());
 
        doRemoveEntry(pos);
 
        ++m_eraseCount;
 
        if (m_eraseCount == m_eraseThreshold)
        {
            compactBuckets();
 
            m_eraseCount = 0;
        }
    }
 
    size_type
    doHash(
            const Key&  key,
            size_type   modulus) const
    {
        assert(modulus != 0);
 
        return m_hash(key) % modulus;
    }
 
    size_type doHash(const Key & key) const
    {
        return doHash(key, m_buckets.size());
    }
 
    void rehash()
    {
        // grow the number of buckets by 60%
        const size_type     theNewSize = size_type(1.6 * size());
        assert(theNewSize != 0);
 
        BucketTableType     temp(
                                theNewSize,
                                BucketType(*m_memoryManager),
                                *m_memoryManager);
 
        // rehash each entry assign to bucket and insert into list
        EntryListIterator   entryPos = m_entries.begin();
 
        while (entryPos != m_entries.end())
        {
            const size_type     index =
                doHash(
                    entryPos->value->first,
                    theNewSize);
 
            temp[index].push_back(entryPos);
 
            ++entryPos;
        }
 
        // Now that we've rebuilt the buckets, swap the rebuilt
        // buckets with our existing buckets.
        m_buckets.swap(temp);
    }
 
    value_type*
    allocate(size_type  size)
    {
        const size_type     theBytesNeeded = size * sizeof(value_type);
 
        assert(m_memoryManager != 0);
 
        void*   pointer = m_memoryManager->allocate(theBytesNeeded);
 
        assert(pointer != 0);
 
        return reinterpret_cast<value_type*>(pointer);
    }
 
    void
    deallocate(value_type*  pointer)
    {
        assert(m_memoryManager != 0);
 
        m_memoryManager->deallocate(pointer);
    }
 
    static size_type
    calculateNewBucketCapacity(
            size_type   theCurrentSize,
            size_type   theExtraCapacity)
    {
        assert(theExtraCapacity > theCurrentSize);
 
        // We'll use the current extra capacity a convenient number.
        // Perhaps a better choice would be to determine how much
        // of the extra capacity to keep, but we really need to
        // figure out how to keep the buckets compacted during
        // removal of an item.
        return theCurrentSize == 0 ?
                    eMinimumBucketSize :
                    theExtraCapacity;
    }
 
    void
    compactBuckets()
    {
        for(TableIterator i = m_buckets.begin();
                i != m_buckets.end();
                    ++i)
        {
            BucketType&     theCurrentBucket = *i;
 
            BucketIterator  j = theCurrentBucket.begin();
 
            while(j != theCurrentBucket.end())
            {
                if ((*j)->erased == true)
                {
                    j = theCurrentBucket.erase(j);
                }
                else
                {
                    ++j;
                }
            }
 
            // Now we should do something if the
            // bucket has a much greater capacity
            // than the number of items in it.
            const size_type     theCurrentSize =
                theCurrentBucket.size();
 
            const size_type     theExtraCapacity =
                theCurrentBucket.capacity() - theCurrentSize;
 
            if (theExtraCapacity > theCurrentSize)
            {
                const size_type     theNewCapacity =
                    calculateNewBucketCapacity(
                        theCurrentSize,
                        theExtraCapacity);
 
                // Create a copy of the bucket, and
                // give it the new capacity of the extra
                // capacity.
                BucketType  theTempBucket(
                                theCurrentBucket,
                                *m_memoryManager,
                                theNewCapacity);
 
                theCurrentBucket.swap(theTempBucket);
            }
        }
    }
 
    // Data members...
    typename KeyTraits::Hasher          m_hash;
        
    typename KeyTraits::Comparator      m_equals;
 
    MemoryManager*                  m_memoryManager;
 
    double                              m_loadFactor;
 
    const size_type                     m_minBuckets;
 
    size_type                           m_size;
 
    EntryListType                       m_entries;
 
    EntryListType                       m_freeEntries;
 
    BucketTableType                     m_buckets;
 
    size_type                           m_eraseCount;
    
    size_type                           m_eraseThreshold;
 
private:
 
    // These are not implemented.
    XalanMap();
 
    XalanMap(const XalanMap&);
};
 
 
 
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
 
 
 
}
 
 
 
#endif  // XALANMAP_HEADER_GUARD_1357924680