Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.10

Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

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:
00192 
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 typename EntryListType::iterator       EntryListIterator;
00217     typedef typename BucketTableType::iterator     TableIterator;
00218     typedef typename BucketType::iterator          BucketIterator;
00219 
00220     typedef XalanMapIterator<
00221                 XalanMapIteratorTraits<value_type>, 
00222                 typename EntryListType::iterator>           iterator;
00223     typedef XalanMapIterator<
00224                 XalanMapConstIteratorTraits<value_type>, 
00225                 typename EntryListType::iterator>     const_iterator;
00226 
00227     typedef typename MemoryManagedConstructionTraits<key_type>::Constructor  FirstConstructor;
00228     typedef typename MemoryManagedConstructionTraits<data_type>::Constructor SecondConstructor;
00229 
00230     enum
00231     {
00232         eDefaultMinBuckets = 29u,
00233         eDefaultEraseThreshold = 50u,
00234         eMinimumBucketSize = 5u
00235     };
00236 
00237 
00238     XalanMap(
00239             MemoryManagerType&  theMemoryManager,
00240             float               loadFactor = 0.75,
00241             size_type           minBuckets = eDefaultMinBuckets,
00242             size_type           eraseThreshold = eDefaultEraseThreshold) :
00243         m_memoryManager(&theMemoryManager),
00244         m_loadFactor(loadFactor),
00245         m_minBuckets(minBuckets),
00246         m_size(0),
00247         m_entries(theMemoryManager),
00248         m_freeEntries(theMemoryManager),
00249         m_buckets(theMemoryManager),
00250         m_eraseCount(0),
00251         m_eraseThreshold(eraseThreshold)
00252     {
00253     }
00254 
00255     XalanMap(
00256             const XalanMap&     theRhs,
00257             MemoryManagerType&  theMemoryManager) :
00258         m_memoryManager(&theMemoryManager),
00259         m_loadFactor(theRhs.m_loadFactor),
00260         m_minBuckets(theRhs.m_minBuckets),
00261         m_size(0),
00262         m_entries(theMemoryManager),
00263         m_freeEntries(theMemoryManager),
00264         m_buckets(
00265             size_type(m_loadFactor * theRhs.size()) + 1,
00266             BucketType(*m_memoryManager),
00267             theMemoryManager),
00268         m_eraseCount(0),
00269         m_eraseThreshold(theRhs.m_eraseThreshold)
00270     {
00271         const_iterator entry = theRhs.begin();
00272 
00273         while(entry != theRhs.end())
00274         {
00275             insert(*entry);
00276             ++entry;
00277         }
00278 
00279         assert(m_size == theRhs.m_size);
00280     }
00281 
00282     MemoryManagerType&
00283     getMemoryManager()
00284     {
00285         assert (m_memoryManager != 0);
00286 
00287         return *m_memoryManager;
00288     }
00289 
00290     ~XalanMap()
00291     {
00292         doRemoveEntries();
00293 
00294         if (!m_buckets.empty())
00295         {
00296             EntryListIterator   toRemove = m_freeEntries.begin();
00297 
00298             while(toRemove != m_freeEntries.end())
00299             {
00300                 deallocate(toRemove->value);
00301                 ++toRemove;
00302             }      
00303         }
00304     }
00305 
00306     XalanMap&
00307     operator=(const XalanMap&   theRhs) 
00308     {
00309         XalanMap    theTemp(theRhs, *m_memoryManager);
00310 
00311         swap(theTemp);
00312 
00313         return *this;
00314     }
00315 
00316     size_type size() const
00317     {
00318         return m_size;
00319     }
00320 
00321     bool empty() const
00322     {
00323         return m_size == 0;
00324     }
00325 
00326     iterator begin()
00327     {
00328         return m_entries.begin();
00329     }
00330 
00331     const_iterator begin() const
00332     {
00333         return  const_cast<XalanMap*>(this)->begin();
00334     }
00335 
00336     iterator end()
00337     {
00338         return m_entries.end();
00339     }
00340 
00341     const_iterator end() const 
00342     {
00343         return const_cast<XalanMap*>(this)->end();
00344     }
00345 
00346     iterator find(const key_type& key)
00347     {
00348         if (m_size != 0)
00349         {
00350             assert(m_buckets.empty() == false);
00351 
00352             const size_type     index = doHash(key);
00353             assert(index < m_buckets.size());
00354 
00355             BucketType&     bucket = m_buckets[index];
00356             BucketIterator  pos = bucket.begin();
00357 
00358             while (pos != bucket.end())
00359             {
00360                 if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
00361                 {
00362                     return iterator(*pos);
00363                 }
00364                 ++pos;
00365             }
00366         }
00367 
00368         return end();
00369     }
00370 
00371     const_iterator find(const key_type& key) const 
00372     {
00373         return const_cast<XalanMap *>(this)->find(key);
00374     }
00375 
00376     data_type & operator[](const key_type& key)
00377     {
00378         iterator pos = find(key);
00379 
00380         if (pos == end())
00381         {
00382             pos = doCreateEntry(key);
00383         }
00384 
00385         return (*pos).second;
00386     }
00387 
00388     void
00389     insert(const value_type&    value)
00390     {
00391         insert(value.first, value.second);
00392     }
00393 
00394     void insert(const key_type& key, const data_type& data)
00395     {
00396         const const_iterator    pos = find(key);
00397 
00398         if (pos == end())
00399         {
00400             doCreateEntry(key, &data);
00401         }
00402     }
00403 
00404     void erase(iterator pos)
00405     {
00406         if (pos != end())
00407         {
00408             doErase(pos);
00409         }
00410     }
00411 
00412     size_type erase(const key_type& key)
00413     {
00414         const iterator  pos = find(key);
00415 
00416         if (pos != end())
00417         {
00418             doErase(pos);
00419 
00420             return 1;
00421         }
00422         else
00423         {
00424             return 0;
00425         }
00426     }
00427 
00428     void clear() 
00429     {
00430         doRemoveEntries();
00431 
00432         TableIterator   bucketPos = m_buckets.begin();
00433 
00434         while (bucketPos != m_buckets.end())
00435         {
00436             bucketPos->clear();
00437             ++bucketPos;
00438         }
00439 
00440         m_eraseCount = 0;
00441 
00442         assert(0 == m_size);
00443         assert(m_entries.empty());
00444     }
00445 
00446     void swap(XalanMap& theRhs)
00447     {
00448         const size_type tempSize = m_size;
00449         m_size = theRhs.m_size;
00450         theRhs.m_size = tempSize;
00451 
00452         MemoryManagerType* const    tempMemoryManager = m_memoryManager;
00453         m_memoryManager = theRhs.m_memoryManager;
00454         theRhs.m_memoryManager = tempMemoryManager;
00455 
00456         const size_type     tempEraseCount = m_eraseCount;
00457         m_eraseCount = theRhs.m_eraseCount;
00458         theRhs.m_eraseCount = tempEraseCount;
00459 
00460         const size_type     tempEraseTheshold = m_eraseThreshold;
00461         m_eraseThreshold = theRhs.m_eraseThreshold;
00462         theRhs.m_eraseThreshold = tempEraseTheshold;
00463 
00464         m_entries.swap(theRhs.m_entries);
00465         m_freeEntries.swap(theRhs.m_freeEntries);
00466         m_buckets.swap(theRhs.m_buckets);
00467     }
00468 
00469 protected:
00470 
00471     iterator doCreateEntry(const key_type & key, const data_type*  data = 0)
00472     {
00473         // if there are no buckets, create initial minimum set of buckets
00474         if (m_buckets.empty())
00475         {
00476             m_buckets.insert(
00477                 m_buckets.begin(),
00478                 m_minBuckets,
00479                 BucketType(*m_memoryManager));
00480         }
00481 
00482         // if the load factor has been reached, rehash
00483         if (size_type(m_loadFactor * size()) > m_buckets.size())
00484         {
00485             rehash();
00486         }
00487 
00488         const size_type     index = doHash(key);
00489 
00490         if (m_freeEntries.empty())
00491         {
00492             m_freeEntries.push_back(Entry(allocate(1)));
00493         }
00494 
00495         // insert a new entry as the first position in the bucket
00496         Entry&  newEntry = m_freeEntries.back();
00497         newEntry.erased = false;
00498 
00499         FirstConstructor::construct(
00500             const_cast<key_type*>(&newEntry.value->first),
00501             key,
00502             *m_memoryManager);
00503 
00504         if (data != 0)
00505         {
00506             SecondConstructor::construct(
00507                 &newEntry.value->second,
00508                 *data,
00509                 *m_memoryManager);
00510         }
00511         else
00512         {
00513              SecondConstructor::construct(
00514                  &newEntry.value->second,
00515                  *m_memoryManager);
00516         }
00517 
00518         m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end());
00519 
00520         m_buckets[index].push_back(--m_entries.end());
00521 
00522         ++m_size;
00523 
00524         return iterator(--m_entries.end());
00525     }
00526 
00527     void doRemoveEntry(const iterator & toRemovePos)
00528     {   
00529         value_type& toRemove = *toRemovePos;
00530 #if defined(_MSC_VER) && _MSC_VER <= 1300
00531         toRemove.value_type::~value_type();
00532 #else
00533         toRemove.~value_type();
00534 #endif
00535         m_freeEntries.splice(
00536                 m_freeEntries.end(), 
00537                 m_entries, 
00538                 toRemovePos.baseIterator);
00539 
00540         toRemovePos.baseIterator->erased = true;
00541 
00542         --m_size;
00543     }
00544 
00545     void
00546     doRemoveEntries()
00547     {
00548         while(size() > 0)
00549         {
00550             doRemoveEntry(begin());
00551         }
00552     }
00553 
00554     void
00555     doErase(iterator    pos)
00556     {
00557         assert(pos != end());
00558 
00559         doRemoveEntry(pos);
00560 
00561         ++m_eraseCount;
00562 
00563         if (m_eraseCount == m_eraseThreshold)
00564         {
00565             compactBuckets();
00566 
00567             m_eraseCount = 0;
00568         }
00569     }
00570 
00571     size_type
00572     doHash(
00573             const Key&  key,
00574             size_type   modulus) const
00575     {
00576         return m_hash(key) % modulus;
00577     }
00578 
00579     size_type doHash(const Key & key) const
00580     {
00581         return doHash(key, m_buckets.size());
00582     }
00583 
00584     void rehash()
00585     {
00586         // grow the number of buckets by 60%
00587         const size_type     theNewSize = size_type(1.6 * size());
00588 
00589         BucketTableType     temp(
00590                                 theNewSize,
00591                                 BucketType(*m_memoryManager),
00592                                 *m_memoryManager);
00593 
00594         // rehash each entry assign to bucket and insert into list
00595         EntryListIterator   entryPos = m_entries.begin();
00596 
00597         while (entryPos != m_entries.end())
00598         {
00599             const size_type     index =
00600                 doHash(
00601                     entryPos->value->first,
00602                     theNewSize);
00603 
00604             temp[index].push_back(entryPos);
00605 
00606             ++entryPos;
00607         }
00608 
00609         // Now that we've rebuilt the buckets, swap the rebuilt
00610         // buckets with our existing buckets.
00611         m_buckets.swap(temp);
00612     }
00613 
00614     value_type*
00615     allocate(size_type  size)
00616     {
00617         const size_type     theBytesNeeded = size * sizeof(value_type);
00618 
00619         assert(m_memoryManager != 0);
00620 
00621         void*   pointer = m_memoryManager->allocate(theBytesNeeded);
00622 
00623         assert(pointer != 0);
00624 
00625         return reinterpret_cast<value_type*>(pointer);
00626     }
00627 
00628     void
00629     deallocate(value_type*  pointer)
00630     {
00631         assert(m_memoryManager != 0);
00632 
00633         m_memoryManager->deallocate(pointer);
00634     }
00635 
00636     static size_type
00637     calculateNewBucketCapacity(
00638             size_type   theCurrentSize,
00639             size_type   theExtraCapacity)
00640     {
00641         assert(theExtraCapacity > theCurrentSize);
00642 
00643         // We'll use the current extra capacity a convenient number.
00644         // Perhaps a better choice would be to determine how much
00645         // of the extra capacity to keep, but we really need to
00646         // figure out how to keep the buckets compacted during
00647         // removal of an item.
00648         return theCurrentSize == 0 ?
00649                     eMinimumBucketSize :
00650                     theExtraCapacity;
00651     }
00652 
00653     void
00654     compactBuckets()
00655     {
00656         for(TableIterator i = m_buckets.begin();
00657                 i != m_buckets.end();
00658                     ++i)
00659         {
00660             BucketType&     theCurrentBucket = *i;
00661 
00662             BucketIterator  j = theCurrentBucket.begin();
00663 
00664             while(j != theCurrentBucket.end())
00665             {
00666                 if ((*j)->erased == true)
00667                 {
00668                     j = theCurrentBucket.erase(j);
00669                 }
00670                 else
00671                 {
00672                     ++j;
00673                 }
00674             }
00675 
00676             // Now we should do something if the
00677             // bucket has a much greater capacity
00678             // than the number of items in it.
00679             const size_type     theCurrentSize =
00680                 theCurrentBucket.size();
00681 
00682             const size_type     theExtraCapacity =
00683                 theCurrentBucket.capacity() - theCurrentSize;
00684 
00685             if (theExtraCapacity > theCurrentSize)
00686             {
00687                 const size_type     theNewCapacity =
00688                     calculateNewBucketCapacity(
00689                         theCurrentSize,
00690                         theExtraCapacity);
00691 
00692                 // Create a copy of the bucket, and
00693                 // give it the new capacity of the extra
00694                 // capacity.
00695                 BucketType  theTempBucket(
00696                                 theCurrentBucket,
00697                                 *m_memoryManager,
00698                                 theNewCapacity);
00699 
00700                 theCurrentBucket.swap(theTempBucket);
00701             }
00702         }
00703     }
00704 
00705     // Data members...
00706     typename KeyTraits::Hasher          m_hash;
00707         
00708     typename KeyTraits::Comparator      m_equals;
00709 
00710     MemoryManagerType*                  m_memoryManager;
00711 
00712     float                               m_loadFactor;
00713 
00714     const size_type                     m_minBuckets;
00715 
00716     size_type                           m_size;
00717 
00718     EntryListType                       m_entries;
00719 
00720     EntryListType                       m_freeEntries;
00721 
00722     BucketTableType                     m_buckets;
00723 
00724     size_type                           m_eraseCount;
00725     
00726     size_type                           m_eraseThreshold;
00727 
00728 private:
00729 
00730     // These are not implemented.
00731     XalanMap();
00732 
00733     XalanMap(const XalanMap&);
00734 };
00735 
00736 
00737 
00738 #if defined(_MSC_VER)
00739 #pragma warning(pop)
00740 #endif
00741 
00742 
00743 
00744 XALAN_CPP_NAMESPACE_END
00745 
00746 
00747 
00748 #endif  // XALANMAP_HEADER_GUARD_1357924680
00749 

Interpreting class diagrams

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

dot

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

Apache Logo