## 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.

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