Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.9

Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

XalanMap.hpp

Go to the documentation of this file.
00001 /*
00002  * Copyright 1999-2004 The Apache Software Foundation.
00003  *
00004  * Licensed under the Apache License, Version 2.0 (the "License");
00005  * you may not use this file except in compliance with the License.
00006  * You may obtain a copy of the License at
00007  *
00008  *     http://www.apache.org/licenses/LICENSE-2.0
00009  *
00010  * Unless required by applicable law or agreed to in writing, software
00011  * distributed under the License is distributed on an "AS IS" BASIS,
00012  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  * See the License for the specific language governing permissions and
00014  * limitations under the License.
00015  */
00016 
00017 #if !defined(XALANMAP_HEADER_GUARD_1357924680)
00018 #define XALANMAP_HEADER_GUARD_1357924680
00019 
00020 
00021 // Base include file.  Must be first.
00022 #include <xalanc/Include/PlatformDefinitions.hpp>
00023 
00024 
00025 
00026 #include <cstddef>
00027 #include <algorithm>
00028 #include <functional>
00029 #include <utility>
00030 
00031 
00032 #include <xalanc/Include/XalanVector.hpp>
00033 #include <xalanc/Include/XalanList.hpp>
00034 
00035 
00036 
00037 XALAN_CPP_NAMESPACE_BEGIN
00038 
00039 #if defined(_MSC_VER)
00040 #pragma warning(push)
00041 #pragma warning(disable: 4189)
00042 #endif
00043 
00044 typedef size_t  size_type;
00045 
00046 template <class Key>
00047 class XalanHasher : public XALAN_STD_QUALIFIER unary_function<Key, size_type>
00048 {
00049 public:
00050     size_type operator()(const Key& key) const
00051     {
00052         const char *byteArray = reinterpret_cast<const char*>(&key);
00053 
00054         size_type result = 0;
00055 
00056         for (size_type i = 0; i < sizeof(Key); ++i)
00057         {
00058             result = (result << 1) ^ byteArray[i];
00059         }
00060 
00061         return result;
00062     }
00063 };
00064 
00065 template <class Key>
00066 struct XalanMapKeyTraits
00067 {
00068     typedef XalanHasher<Key>                    Hasher;
00069     typedef XALAN_STD_QUALIFIER equal_to<Key>   Comparator;
00070 };
00071 
00072 
00073 template <class Key>
00074 struct XalanHashMemberPointer
00075 {
00076 
00077     size_type operator() (const Key * key) const
00078     {
00079         assert (key != 0);
00080         return key->hash();
00081     }
00082 };
00083 
00084 template <class Key>
00085 struct XalanHashMemberReference
00086 {
00087 
00088     size_type operator() (const Key& key) const
00089     {
00090         return key.hash();
00091     }
00092 };
00093 
00094 
00095 
00096 template <class Value>
00097 struct XalanMapIteratorTraits
00098 {
00099     typedef Value           value_type;
00100     typedef Value&          reference;
00101     typedef Value*          pointer;
00102 };
00103 
00104 template <class Value>
00105 struct XalanMapConstIteratorTraits
00106 {
00107     typedef Value           value_type;
00108     typedef const Value&    reference;
00109     typedef const Value*    pointer;
00110 };
00111 
00112 template <class XalanMapTraits, class BaseIterator>
00113 struct XalanMapIterator
00114 {
00115     typedef typename XalanMapTraits::value_type         value_type;
00116     typedef typename XalanMapTraits::reference          reference;
00117     typedef typename XalanMapTraits::pointer            pointer;
00118 
00119     typedef ptrdiff_t                           difference_type;
00120     typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category;
00121 
00122     typedef XalanMapIterator<
00123         XalanMapIteratorTraits<value_type>, 
00124         BaseIterator>                                   Iterator; 
00125 
00126     XalanMapIterator(const Iterator & theRhs) :
00127         baseIterator(theRhs.baseIterator)
00128     {
00129     }
00130 
00131     XalanMapIterator(const BaseIterator & theRhs) :
00132         baseIterator(theRhs)
00133     {
00134     }
00135 
00136     XalanMapIterator operator++(int)
00137     {
00138         XalanMapIterator temp(*this);
00139         ++baseIterator;
00140         return temp;
00141     }
00142 
00143     XalanMapIterator& operator++()
00144     {
00145         ++baseIterator;
00146         return *this;
00147     }
00148 
00149     reference operator*() const
00150     {
00151         return *baseIterator->value;
00152     }
00153 
00154     pointer operator->() const
00155     {
00156         return baseIterator->value;
00157     }
00158 
00159     bool operator==(const XalanMapIterator& theRhs) const
00160     {
00161         return theRhs.baseIterator == baseIterator;
00162     }
00163 
00164     bool operator!=(const XalanMapIterator& theRhs) const
00165     {
00166         return !(theRhs == *this);
00167     }
00168 
00169     BaseIterator baseIterator;
00170 };
00171 
00172 
00173 
00178 template <
00179         class Key, 
00180         class Value,
00181         class KeyTraits = XalanMapKeyTraits<Key> >
00182 class XalanMap
00183 {
00184 public:
00193     typedef Key                 key_type;
00194     typedef Value               data_type;
00195     typedef size_t              size_type;
00196 
00197     typedef XALAN_STD_QUALIFIER pair<const key_type, data_type>   value_type;
00198 
00199     struct Entry
00200     {
00201         value_type* value;
00202         bool        erased;
00203 
00204         Entry(value_type* theValue) :
00205             value(theValue),
00206             erased(false)
00207         {
00208         }
00209     };
00210 
00211     typedef XalanList<Entry>                                EntryListType;
00212 
00213     typedef XalanVector<typename EntryListType::iterator>   BucketType;
00214     typedef XalanVector<BucketType, ConstructWithMemoryManagerTraits<BucketType> >      BucketTableType;
00215 
00216     typedef XalanMapIterator<
00217                 XalanMapIteratorTraits<value_type>, 
00218                 typename EntryListType::iterator>           iterator;
00219     typedef XalanMapIterator<
00220                 XalanMapConstIteratorTraits<value_type>, 
00221                 typename EntryListType::iterator>     const_iterator;
00222 
00223     typedef typename MemoryManagedConstructionTraits<key_type>::Constructor  FirstConstructor;
00224     typedef typename MemoryManagedConstructionTraits<data_type>::Constructor SecondConstructor;
00225 
00226     XalanMap(
00227             MemoryManagerType& theMemoryManager,
00228             float loadFactor = 0.75,
00229             size_type minBuckets = 10) :
00230         m_memoryManager(&theMemoryManager),
00231         m_loadFactor(loadFactor),
00232         m_minBuckets(minBuckets),
00233         m_size(0),
00234         m_entries(theMemoryManager),
00235         m_freeEntries(theMemoryManager),
00236         m_buckets(theMemoryManager)
00237     {
00238     }
00239 
00240     XalanMap(
00241             const XalanMap &theRhs,
00242             MemoryManagerType&  theMemoryManager) :
00243         m_memoryManager(&theMemoryManager),
00244         m_loadFactor(theRhs.m_loadFactor),
00245         m_minBuckets(10),
00246         m_size(0),
00247         m_entries(theMemoryManager),
00248         m_freeEntries(theMemoryManager),
00249         m_buckets(size_type(m_loadFactor * theRhs.size())+ 1, BucketType(*m_memoryManager), theMemoryManager)
00250     {
00251         const_iterator entry = theRhs.begin();
00252         while(entry != theRhs.end())
00253         {
00254             insert(*entry);
00255             ++entry;
00256         }
00257 
00258         assert(m_size == theRhs.m_size);
00259     }
00260 
00261     MemoryManagerType&
00262     getMemoryManager()
00263     {
00264         assert (m_memoryManager != 0);
00265 
00266         return *m_memoryManager;
00267     }
00268 
00269     ~XalanMap()
00270     {
00271         doRemoveEntries();
00272 
00273         if (!m_buckets.empty())
00274         {
00275             typename EntryListType::iterator toRemove = m_freeEntries.begin();
00276             while(toRemove != m_freeEntries.end())
00277             {
00278                 deallocate(toRemove->value);
00279                 ++toRemove;
00280             }      
00281         }
00282     }
00283 
00284     XalanMap & operator=(const XalanMap& theRhs) 
00285     {
00286         XalanMap theTemp(theRhs, *m_memoryManager);
00287         swap(theTemp);
00288         return *this;
00289     }
00290 
00291     size_type size() const
00292     {
00293         return m_size;
00294     }
00295 
00296     bool empty() const
00297     {
00298         return m_size == 0;
00299     }
00300 
00301     iterator begin()
00302     {
00303         return m_entries.begin();
00304     }
00305 
00306     const_iterator begin() const
00307     {
00308         return  const_cast<XalanMap*>(this)->begin();
00309     }
00310 
00311     iterator end()
00312     {
00313         return m_entries.end();
00314     }
00315 
00316     const_iterator end() const 
00317     {
00318         return const_cast<XalanMap*>(this)->end();
00319     }
00320 
00321     iterator find(const key_type& key)
00322     {
00323         if (!m_buckets.empty())
00324         {
00325             const size_type     index = doHash(key);
00326             assert(index < m_buckets.size());
00327 
00328             BucketType & bucket = m_buckets[index];
00329             typename BucketType::iterator pos = bucket.begin();
00330 
00331             while (pos != bucket.end())
00332             {
00333                 if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
00334                 {
00335                     return iterator(*pos);
00336                 }
00337                 ++pos;
00338             }
00339         }
00340 
00341         return end();
00342     }
00343 
00344     const_iterator find(const key_type& key) const 
00345     {
00346         return const_cast<XalanMap *>(this)->find(key);
00347     }
00348 
00349     data_type & operator[](const key_type& key)
00350     {
00351         iterator pos = find(key);
00352 
00353         if (pos == end())
00354         {
00355             pos = doCreateEntry(key);
00356         }
00357 
00358         return (*pos).second;
00359     }
00360 
00361     void insert(const value_type& value)
00362     {
00363         const key_type& key = value.first;
00364         const data_type& data = value.second;
00365 
00366         insert(key, data);
00367     }
00368 
00369     void insert(const key_type& key, const data_type& data)
00370     {
00371         const const_iterator    pos = find(key);
00372 
00373         if (pos == end())
00374         {
00375             doCreateEntry(key, &data);
00376         }
00377     }
00378 
00379     void erase(iterator pos)
00380     {
00381         if (pos != end())
00382         {
00383             doRemoveEntry(pos);
00384         }
00385     }
00386 
00387     size_type erase(const key_type& key)
00388     {
00389         const iterator  pos = find(key);
00390 
00391         if (pos != end())
00392         {
00393             erase(pos);
00394             return 1;
00395         }
00396         else
00397         {
00398             return 0;
00399         }
00400     }
00401 
00402     void clear() 
00403     {
00404         doRemoveEntries();
00405 
00406         typename BucketTableType::iterator bucketPos = m_buckets.begin();
00407         while (bucketPos != m_buckets.end())
00408         {
00409             bucketPos->clear();
00410             ++bucketPos;
00411         }
00412 
00413         assert(0 == m_size);
00414         assert(m_entries.empty());
00415     }
00416 
00417     void swap(XalanMap& theRhs)
00418     {
00419         size_type tempSize = m_size;
00420         m_size = theRhs.m_size;
00421         theRhs.m_size = tempSize;
00422 
00423         MemoryManagerType* tempMemoryManager = m_memoryManager;
00424         m_memoryManager = theRhs.m_memoryManager;
00425         theRhs.m_memoryManager = tempMemoryManager;
00426 
00427         m_entries.swap(theRhs.m_entries);
00428         m_freeEntries.swap(theRhs.m_freeEntries);
00429         m_buckets.swap(theRhs.m_buckets);
00430     }
00431 
00432 protected:
00433 
00434     iterator doCreateEntry(const key_type & key, const data_type*  data = 0)
00435     {
00436         // if there are no buckets, create initial minimum set of buckets
00437         if (m_buckets.empty())
00438         {
00439             m_buckets.insert(m_buckets.begin(), m_minBuckets, BucketType(*m_memoryManager));
00440         }
00441 
00442         // if the load factor has been reached, rehash
00443         if (size_type(m_loadFactor * size()) > m_buckets.size())
00444         {
00445             rehash();
00446         }
00447 
00448         size_type index = doHash(key);
00449 
00450         
00451         if (m_freeEntries.empty())
00452         {
00453             m_freeEntries.push_back(Entry(allocate(1)));
00454         }
00455         
00456         // insert a new entry as the first position in the bucket
00457         Entry& newEntry = m_freeEntries.back();
00458         newEntry.erased = false;
00459 
00460         FirstConstructor::construct(const_cast<key_type*>(&newEntry.value->first), key, *m_memoryManager);
00461         if (data != 0)
00462         {
00463             SecondConstructor::construct(&newEntry.value->second, *data, *m_memoryManager);
00464         }
00465         else
00466         {
00467              SecondConstructor::construct(&newEntry.value->second, *m_memoryManager);
00468         }
00469 
00470 
00471         m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end());
00472 
00473         m_buckets[index].push_back(--m_entries.end());
00474 
00475         ++m_size;
00476 
00477         return iterator(--m_entries.end());
00478     }
00479 
00480     void doRemoveEntry(const iterator & toRemovePos)
00481     {   
00482         value_type& toRemove = *toRemovePos;
00483 #if defined(_MSC_VER) && _MSC_VER <= 1300
00484         toRemove.value_type::~value_type();
00485 #else
00486         toRemove.~value_type();
00487 #endif
00488         m_freeEntries.splice(
00489                 m_freeEntries.end(), 
00490                 m_entries, 
00491                 toRemovePos.baseIterator);
00492 
00493         toRemovePos.baseIterator->erased = true;
00494 
00495         --m_size;
00496     }
00497 
00498     void
00499     doRemoveEntries()
00500     {
00501         while(size() > 0)
00502         {
00503             doRemoveEntry(begin());
00504         }
00505     }
00506 
00507     size_type doHash(const Key & key) const
00508     {
00509         return m_hash(key) % m_buckets.size();
00510     }
00511 
00512     void rehash()
00513     {
00514         // grow the number of buckets by 60%
00515         BucketTableType temp(size_type(1.6 * size()), BucketType(*m_memoryManager), *m_memoryManager);
00516         m_buckets.swap(temp);
00517     
00518         // rehash each entry assign to bucket and insert into list
00519         typename EntryListType::iterator entryPos = m_entries.begin();
00520         while (entryPos != m_entries.end())
00521         {
00522             size_type index = doHash(entryPos->value->first);
00523             m_buckets[index].push_back(entryPos);
00524             ++entryPos;
00525         }
00526     }
00527 
00528     value_type*
00529     allocate(size_type  size)
00530     {
00531         const size_type     theBytesNeeded = size * sizeof(value_type);
00532 
00533         assert( m_memoryManager != 0 );
00534 
00535         void*   pointer = m_memoryManager->allocate(theBytesNeeded);
00536 
00537         assert(pointer != 0);
00538 
00539         return (value_type*) pointer;
00540     }
00541 
00542     void
00543     deallocate(value_type*  pointer)
00544     {
00545         if (m_memoryManager == 0)
00546         {
00547             ::operator delete(pointer);
00548         }
00549         else
00550         {
00551             m_memoryManager->deallocate(pointer);
00552         }
00553     }
00554 
00555     // Data members...
00556     typename KeyTraits::Hasher          m_hash;
00557         
00558     typename KeyTraits::Comparator      m_equals;
00559 
00560     MemoryManagerType*                  m_memoryManager;
00561 
00562     float                               m_loadFactor;
00563 
00564     size_type                           m_minBuckets;
00565 
00566     size_type                           m_size;
00567 
00568     EntryListType                       m_entries;
00569 
00570     EntryListType                       m_freeEntries;
00571 
00572     BucketTableType                     m_buckets;
00573 
00574 private:
00575     // not defined
00576     XalanMap();
00577     XalanMap(const XalanMap&);
00578 };
00579 
00580 
00581 
00582 #if defined(_MSC_VER)
00583 #pragma warning(pop)
00584 #endif
00585 
00586 
00587 
00588 XALAN_CPP_NAMESPACE_END
00589 
00590 
00591 
00592 #endif  // XALANMAP_HEADER_GUARD_1357924680
00593 

Interpreting class diagrams

Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.

Xalan-C++ XSLT Processor Version 1.9
Copyright © 1999-2004 The Apache Software Foundation. All Rights Reserved.