You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xalan.apache.org by mh...@apache.org on 2004/11/20 00:24:46 UTC

cvs commit: xml-xalan/c/src/xalanc/Include XalanMap.hpp

mhoyt       2004/11/19 15:24:46

  Modified:    c/src/xalanc/Include XalanMap.hpp
  Log:
  Improved XalanMap implementation
  
  Revision  Changes    Path
  1.17      +144 -149  xml-xalan/c/src/xalanc/Include/XalanMap.hpp
  
  Index: XalanMap.hpp
  ===================================================================
  RCS file: /home/cvs/xml-xalan/c/src/xalanc/Include/XalanMap.hpp,v
  retrieving revision 1.16
  retrieving revision 1.17
  diff -u -r1.16 -r1.17
  --- XalanMap.hpp	8 Nov 2004 18:08:50 -0000	1.16
  +++ XalanMap.hpp	19 Nov 2004 23:24:46 -0000	1.17
  @@ -29,8 +29,6 @@
   #include <utility>
   
   
  -
  -
   #include <xalanc/Include/XalanVector.hpp>
   #include <xalanc/Include/XalanList.hpp>
   
  @@ -38,6 +36,11 @@
   
   XALAN_CPP_NAMESPACE_BEGIN
   
  +#if defined(_MSC_VER)
  +#pragma warning(push)
  +#pragma warning(disable: 4189)
  +#endif
  +
   typedef size_t	size_type;
   
   template <class Key>
  @@ -91,35 +94,6 @@
   /**
    * Xalan map entry pair of a key and data
    */
  -template <class KeyType,  class DataType>
  -struct XalanMapEntry
  -{
  -    typedef KeyType     first_type;
  -    typedef DataType    second_type;
  -
  -	typedef size_t	size_type;
  -	
  -    XalanMapEntry(
  -            const first_type & theFirst, 
  -            const second_type& theSecond,
  -            size_type index = 0) : 
  -		first(theFirst),
  -        second(theSecond),
  -        bucketIndex(index)
  -	{
  -	}
  -
  -	XalanMapEntry() : 
  -		first(),
  -        second(),
  -        bucketIndex(size_type())
  -	{
  -	}
  -
  -    first_type      first;
  -    second_type     second;
  -    size_type       bucketIndex;
  -};
   
   
   
  @@ -140,7 +114,7 @@
   };
   
   template <class XalanMapTraits, class BaseIterator>
  -struct XalanMapIterator : public BaseIterator
  +struct XalanMapIterator
   {
       typedef typename XalanMapTraits::value_type         value_type;
       typedef typename XalanMapTraits::reference          reference;
  @@ -151,45 +125,52 @@
   
       typedef XalanMapIterator<
   		XalanMapIteratorTraits<value_type>, 
  -  		typename BaseIterator::iterator>	Iterator; 
  -
  -    XalanMapIterator() :
  -            BaseIterator()
  -    {
  -    }
  +  		BaseIterator>	                                Iterator; 
   
       XalanMapIterator(const Iterator & theRhs) :
  -            BaseIterator(theRhs)
  +        baseIterator(theRhs.baseIterator)
       {
       }
   
       XalanMapIterator(const BaseIterator & theRhs) :
  -            BaseIterator(theRhs)
  +        baseIterator(theRhs)
       {
       }
   
       XalanMapIterator operator++(int)
       {
  -	 XalanMapIterator temp(*this);
  -	 BaseIterator::operator++();
  -	 return temp;
  +	    XalanMapIterator temp(*this);
  +	    ++baseIterator;
  +	    return temp;
       }
   
       XalanMapIterator& operator++()
       {
  -	 BaseIterator::operator++();
  -	 return *this;
  +        ++baseIterator;
  +        return *this;
       }
   
       reference operator*() const
       {
  -        return *(BaseIterator::operator*());
  +        return *baseIterator->value;
       }
   
       pointer operator->() const
       {
  -        return (BaseIterator::operator*());
  +        return baseIterator->value;
  +    }
  +
  +    bool operator==(const XalanMapIterator& theRhs) const
  +    {
  +        return theRhs.baseIterator == baseIterator;
       }
  +
  +    bool operator!=(const XalanMapIterator& theRhs) const
  +    {
  +        return !(theRhs == *this);
  +    }
  +
  +    BaseIterator baseIterator;
   };
   
   
  @@ -206,26 +187,42 @@
   {
   public:
   	/**
  -	 * Each map entry is stored in a linked list.
  -	 * The hash buckets are a vector of pointers into the entry list
  -	 * An empty bucket will point to the end of the list,
  -	 * A non-empty bucket will point to its first entry.  Remaining
  -	 * entries in the chain follow the first and have the same index value.
  -	 */
  +	 * 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 XalanMapEntry<const key_type, data_type>   value_type;
  -    typedef value_type  Entry;
  +	typedef XALAN_STD_QUALIFIER pair<const key_type, data_type>   value_type;
   
  -	typedef XalanList<Entry*>									EntryListType;
  +    struct Entry
  +    {
  +        value_type* value;
  +        bool        erased;
   
  -    typedef XalanMapIterator<XalanMapIteratorTraits<Entry>, typename EntryListType::iterator>            iterator;
  -    typedef XalanMapIterator<XalanMapConstIteratorTraits<Entry>, typename EntryListType::const_iterator> const_iterator;
  +        Entry(value_type* theValue) :
  +            value(theValue),
  +            erased(false)
  +        {
  +        }
  +    };
   
  -	typedef XalanVector<iterator>		EntryPosVectorType;
  +    typedef XalanList<Entry>                                EntryListType;
  +
  +    typedef XalanVector<typename EntryListType::iterator>	BucketType;
  +    typedef XalanVector<BucketType>                         BucketTableType;
  +
  +    typedef XalanMapIterator<
  +                XalanMapIteratorTraits<value_type>, 
  +                typename EntryListType::iterator>           iterator;
  +    typedef XalanMapIterator<
  +                XalanMapConstIteratorTraits<value_type>, 
  +                typename EntryListType::iterator>     const_iterator;
   
       typedef typename MemoryManagedConstructionTraits<key_type>::Constructor  FirstConstructor;
       typedef typename MemoryManagedConstructionTraits<data_type>::Constructor SecondConstructor;
  @@ -238,20 +235,22 @@
   		m_loadFactor(loadFactor),
   		m_minBuckets(minBuckets),
   		m_size(0),
  -		m_entries(*m_memoryManager),
  -		m_buckets(*m_memoryManager)
  +		m_entries(theMemoryManager),
  +        m_freeEntries(theMemoryManager),
  +		m_buckets(theMemoryManager)
   	{
   	}
   
   	XalanMap(
   			const XalanMap &theRhs,
  -			MemoryManagerType&  theManager) :
  -        m_memoryManager(&theManager),
  +			MemoryManagerType&  theMemoryManager) :
  +        m_memoryManager(&theMemoryManager),
   		m_loadFactor(theRhs.m_loadFactor),
   		m_minBuckets(10),
   		m_size(0),
  -		m_entries(*m_memoryManager),
  -		m_buckets(size_type(m_loadFactor * theRhs.size())+ 1, m_entries.end(), theManager)
  +		m_entries(theMemoryManager),
  +        m_freeEntries(theMemoryManager),
  +		m_buckets(size_type(m_loadFactor * theRhs.size())+ 1, BucketType(*m_memoryManager), theMemoryManager)
   	{
   		const_iterator entry = theRhs.begin();
   		while(entry != theRhs.end())
  @@ -274,6 +273,16 @@
   	~XalanMap()
   	{
           doRemoveEntries();
  +
  +        if (!m_buckets.empty())
  +        {
  +            EntryListType::iterator toRemove = m_freeEntries.begin();
  +            while(toRemove != m_freeEntries.end())
  +            {
  +                deallocate(toRemove->value);
  +                ++toRemove;
  +            }      
  +        }
   	}
   
   	XalanMap & operator=(const XalanMap& theRhs) 
  @@ -283,7 +292,6 @@
   		return *this;
   	}
   
  -
   	size_type size() const
   	{
   		return m_size;
  @@ -301,7 +309,7 @@
   
   	const_iterator begin() const
   	{
  -		return m_entries.begin();
  +        return  const_cast<XalanMap*>(this)->begin();
   	}
   
   	iterator end()
  @@ -311,7 +319,7 @@
   
   	const_iterator end() const 
   	{
  -		return m_entries.end();
  +        return const_cast<XalanMap*>(this)->end();
   	}
   
   	iterator find(const key_type& key)
  @@ -321,16 +329,16 @@
   			const size_type     index = doHash(key);
               assert(index < m_buckets.size());
   
  -			iterator bucketPos = m_buckets[index];
  +            BucketType & bucket = m_buckets[index];
  +            typename BucketType::iterator pos = bucket.begin();
   
  -			while (bucketPos != m_entries.end() &&
  -				   bucketPos->bucketIndex == index)
  +			while (pos != bucket.end())
   			{
  -				if (m_equals(key,bucketPos->first))
  +				if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
   				{
  -					return bucketPos;
  +					return iterator(*pos);
   				}
  -				++bucketPos;
  +				++pos;
   			}
   		}
   
  @@ -372,7 +380,6 @@
   		}
   	}
   
  -
   	void erase(iterator pos)
   	{
   		if (pos != end())
  @@ -400,15 +407,16 @@
   	{
           doRemoveEntries();
   
  -		m_size = 0;
  -
  -		XALAN_STD_QUALIFIER fill(
  -            m_buckets.begin(),
  -            m_buckets.end(),
  -            m_entries.end());
  +		BucketTableType::iterator bucketPos = m_buckets.begin();
  +		while (bucketPos != m_buckets.end())
  +		{
  +			bucketPos->clear();
  +			++bucketPos;
  +		}
   
  -		m_entries.clear();
  -	}
  +        assert(0 == m_size);
  +        assert(m_entries.empty());
  +    }
   
   	void swap(XalanMap& theRhs)
   	{
  @@ -421,17 +429,18 @@
   		theRhs.m_memoryManager = tempMemoryManager;
   
   		m_entries.swap(theRhs.m_entries);
  +        m_freeEntries.swap(theRhs.m_freeEntries);
   		m_buckets.swap(theRhs.m_buckets);
   	}
   
  -	protected:
  +protected:
   
  -	iterator doCreateEntry(const key_type & key, const data_type*  data = 0)
  +    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, m_entries.end());
  +			m_buckets.insert(m_buckets.begin(), m_minBuckets, BucketType(*m_memoryManager));
   		}
   
   		// if the load factor has been reached, rehash
  @@ -442,56 +451,51 @@
   
   		size_type index = doHash(key);
   
  -		iterator & bucketStartPos = m_buckets[index];
  +        
  +        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;
   
  -		// insert a new entry as the first position in the bucket
  -        Entry * newEntry = allocate(1);
  -        FirstConstructor::construct(const_cast<key_type*>(&newEntry->first), key, *m_memoryManager);
  +        FirstConstructor::construct(const_cast<key_type*>(&newEntry.value->first), key, *m_memoryManager);
           if (data != 0)
           {
  -            SecondConstructor::construct(&newEntry->second, *data, *m_memoryManager);
  +            SecondConstructor::construct(&newEntry.value->second, *data, *m_memoryManager);
           }
           else
           {
  -             SecondConstructor::construct(&newEntry->second, *m_memoryManager);
  +             SecondConstructor::construct(&newEntry.value->second, *m_memoryManager);
           }
   
  -        new (&newEntry->bucketIndex) size_type(index);
  -		bucketStartPos = m_entries.insert(bucketStartPos, newEntry);
  -			
  -		++m_size;
  -		return bucketStartPos;
  +
  +        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)
  -	{
  -		size_type index = toRemovePos->bucketIndex;
  -		iterator nextPos = ++(iterator(toRemovePos));
  -
  -		// if the entry to remove is the first in the bucket
  -		// set the next entry as the first or,
  -		// if there are no more entries set it to the end
  -		if (m_buckets[index] == toRemovePos)
  -		{
  -			if (nextPos != m_entries.end() &&
  -                nextPos->bucketIndex == index)
  -			{
  -				m_buckets[index] = nextPos;
  -			}
  -			else
  -			{
  -				m_buckets[index] = m_entries.end();
  -			}
  -		}
  -        
  +	{   
           value_type& toRemove = *toRemovePos;
   #if defined(_MSC_VER) && _MSC_VER <= 1300
           toRemove.value_type::~value_type();
   #else
           toRemove.~value_type();
   #endif
  -        deallocate(&toRemove);
  -		m_entries.erase(toRemovePos);
  +        m_freeEntries.splice(
  +                m_freeEntries.end(), 
  +                m_entries, 
  +                toRemovePos.baseIterator);
  +
  +        toRemovePos.baseIterator->erased = true;
  +
   		--m_size;
   	}
   
  @@ -512,34 +516,16 @@
   	void rehash()
   	{
   		// grow the number of buckets by 60%
  -		EntryPosVectorType temp(size_type(1.6 * size()), m_entries.end(), *m_memoryManager);
  +		BucketTableType temp(size_type(1.6 * size()), BucketType(*m_memoryManager), *m_memoryManager);
   		m_buckets.swap(temp);
   	
  -		// move current entries into a temporary list
  -		EntryListType tempEntryList(*m_memoryManager);
  -		tempEntryList.splice(tempEntryList.begin(),m_entries, m_entries.begin(), m_entries.end());
  -
  -		// rehash each entry assign to bucket and insert into list
  -		while (tempEntryList.begin() != tempEntryList.end())
  +        // rehash each entry assign to bucket and insert into list
  +		EntryListType::iterator entryPos = m_entries.begin();
  +		while (entryPos != m_entries.end())
   		{
  -			iterator entry = tempEntryList.begin();
  -
  -			entry->bucketIndex = doHash(entry->first);
  -			iterator & bucketStartPos = m_buckets[entry->bucketIndex];
  -
  -			// if the bucket is empty assign to the entry and insert 
  -			// into the list, otherwise insert into front of the 
  -			// current first entry
  -			if (bucketStartPos == m_entries.end())
  -			{
  -				bucketStartPos = entry;
  -				m_entries.splice(m_entries.begin(), tempEntryList, entry);
  -			}
  -			else
  -			{
  -				m_entries.splice(bucketStartPos, tempEntryList, entry);
  -				--bucketStartPos;
  -			}
  +        	size_type index = doHash(entryPos->value->first);
  +			m_buckets[index].push_back(entryPos);
  +            ++entryPos;
   		}
   	}
   
  @@ -571,9 +557,9 @@
       }
   
   	// Data members...
  -	typename KeyTraits::Hasher					m_hash;
  +	typename KeyTraits::Hasher			m_hash;
   		
  -	typename KeyTraits::Comparator				m_equals;
  +	typename KeyTraits::Comparator		m_equals;
   
       MemoryManagerType*					m_memoryManager;
   
  @@ -583,15 +569,24 @@
   
   	size_type							m_size;
   
  -	EntryListType						m_entries;
  +    EntryListType						m_entries;
   
  -    EntryPosVectorType					m_buckets;
  +    EntryListType                       m_freeEntries;
   
  -    private:
  +    BucketTableType 					m_buckets;
  +
  +private:
       // not defined
       XalanMap();
       XalanMap(const XalanMap&);
   };
  +
  +
  +
  +#if defined(_MSC_VER)
  +#pragma warning(pop)
  +#endif
  +
   
   
   XALAN_CPP_NAMESPACE_END
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: xalan-cvs-unsubscribe@xml.apache.org
For additional commands, e-mail: xalan-cvs-help@xml.apache.org