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