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 00021 #if !defined(XALANDEQUE_HEADER_GUARD_1357924680) 00022 #define XALANDEQUE_HEADER_GUARD_1357924680 00023 00024 00025 00026 // Base include file. Must be first. 00027 #include <xalanc/Include/PlatformDefinitions.hpp> 00028 00029 00030 00031 #include <xalanc/Include/XalanVector.hpp> 00032 #include <xalanc/Include/XalanMemoryManagement.hpp> 00033 00034 00035 00036 XALAN_CPP_NAMESPACE_BEGIN 00037 00038 00039 00040 template <class Value> 00041 struct XalanDequeIteratorTraits 00042 { 00043 typedef Value value_type; 00044 typedef Value& reference; 00045 typedef Value* pointer; 00046 typedef const Value& const_reference; 00047 }; 00048 00049 template <class Value> 00050 struct XalanDequeConstIteratorTraits 00051 { 00052 typedef Value value_type; 00053 typedef const Value& reference; 00054 typedef const Value* pointer; 00055 typedef const Value& const_reference; 00056 }; 00057 00058 template <class XalanDequeTraits, class XalanDeque> 00059 struct XalanDequeIterator 00060 { 00061 typedef size_t size_type; 00062 typedef typename XalanDequeTraits::value_type value_type; 00063 typedef typename XalanDequeTraits::reference reference; 00064 typedef typename XalanDequeTraits::pointer pointer; 00065 typedef typename XalanDequeTraits::const_reference const_reference; 00066 typedef ptrdiff_t difference_type; 00067 00068 typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> Iterator; 00069 00070 typedef XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category; 00071 00072 XalanDequeIterator(XalanDeque* deque, 00073 size_type pos) : 00074 m_deque(deque), 00075 m_pos(pos) 00076 { 00077 } 00078 00079 XalanDequeIterator(const Iterator & iterator) : 00080 m_deque(iterator.m_deque), 00081 m_pos(iterator.m_pos) 00082 { 00083 } 00084 00085 XalanDequeIterator& operator=(const Iterator & iterator) 00086 { 00087 m_deque = iterator.m_deque; 00088 m_pos = iterator.m_pos; 00089 return *this; 00090 } 00091 00092 XalanDequeIterator& operator++() 00093 { 00094 ++m_pos; 00095 return *this; 00096 } 00097 00098 XalanDequeIterator operator++(int) 00099 { 00100 XalanDequeIterator temp = *this; 00101 ++m_pos; 00102 return temp; 00103 } 00104 00105 XalanDequeIterator& operator--() 00106 { 00107 --m_pos; 00108 return *this; 00109 } 00110 00111 pointer operator->() 00112 { 00113 return &(*m_deque[m_pos]); 00114 } 00115 00116 reference operator*() 00117 { 00118 return (*m_deque)[m_pos]; 00119 } 00120 00121 const_reference operator*() const 00122 { 00123 return (*m_deque)[m_pos]; 00124 } 00125 00126 XalanDequeIterator operator+(difference_type difference) const 00127 { 00128 return XalanDequeIterator(m_deque, m_pos + difference); 00129 } 00130 00131 XalanDequeIterator operator-(difference_type difference) const 00132 { 00133 return XalanDequeIterator(m_deque, m_pos - difference); 00134 } 00135 00136 difference_type operator-(const XalanDequeIterator &theRhs) const 00137 { 00138 return m_pos - theRhs.m_pos; 00139 } 00140 00141 bool operator==(const XalanDequeIterator & theRhs) const 00142 { 00143 return (theRhs.m_deque == m_deque) 00144 && theRhs.m_pos == m_pos; 00145 } 00146 00147 bool operator!=(const XalanDequeIterator & theRhs) const 00148 { 00149 return !(theRhs == *this); 00150 } 00151 00152 XalanDeque* m_deque; 00153 size_type m_pos; 00154 }; 00155 00159 template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> > 00160 class XalanDeque 00161 { 00162 public: 00163 00164 00165 typedef size_t size_type; 00166 00167 typedef Type value_type; 00168 typedef Type& reference; 00169 typedef const Type& const_reference; 00170 00171 typedef XalanVector<Type, ConstructionTraits> BlockType; 00172 00173 typedef XalanVector<BlockType*> BlockIndexType; 00174 00175 typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> iterator; 00176 typedef XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, XalanDeque> const_iterator; 00177 00178 #if defined(XALAN_HAS_STD_ITERATORS) 00179 typedef XALAN_STD_QUALIFIER reverse_iterator<iterator> reverse_iterator_; 00180 typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator> const_reverse_iterator_; 00181 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC) 00182 typedef XALAN_STD_QUALIFIER reverse_iterator< 00183 iterator, 00184 XALAN_STD_QUALIFIER random_access_iterator_tag, 00185 value_type> reverse_iterator_; 00186 typedef XALAN_STD_QUALIFIER reverse_iterator< 00187 const_iterator, 00188 XALAN_STD_QUALIFIER random_access_iterator_tag, 00189 const value_type> const_reverse_iterator_; 00190 #else 00191 typedef XALAN_STD_QUALIFIER reverse_iterator<iterator, value_type> reverse_iterator_; 00192 typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator, value_type, const_reference> const_reverse_iterator_; 00193 #endif 00194 00195 typedef reverse_iterator_ reverse_iterator; 00196 typedef const_reverse_iterator_ const_reverse_iterator; 00197 00198 XalanDeque( 00199 MemoryManagerType& memoryManager, 00200 size_type initialSize = 0, 00201 size_type blockSize = 10) : 00202 m_memoryManager(&memoryManager), 00203 m_blockSize(blockSize), 00204 m_blockIndex(memoryManager, 00205 initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)), 00206 m_freeBlockVector(memoryManager) 00207 { 00208 typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager); 00209 00210 XALAN_STD_QUALIFIER fill_n(XALAN_STD_QUALIFIER back_inserter(*this), initialSize, defaultValue.value); 00211 } 00212 00213 XalanDeque(const XalanDeque& theRhs, MemoryManagerType& memoryManager) : 00214 m_memoryManager(&memoryManager), 00215 m_blockSize(theRhs.m_blockSize), 00216 m_blockIndex(*theRhs.m_memoryManager, 00217 theRhs.size() / theRhs.m_blockSize + (theRhs.size() % theRhs.m_blockSize == 0 ? 0 : 1)), 00218 m_freeBlockVector(memoryManager) 00219 { 00220 XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this)); 00221 } 00222 00223 static XalanDeque* 00224 create( 00225 MemoryManagerType& theManager, 00226 size_type initialSize = 0, 00227 size_type blockSize = 10) 00228 { 00229 typedef XalanDeque ThisType; 00230 00231 XalanMemMgrAutoPtr<ThisType, false> theGuard( theManager , (ThisType*)theManager.allocate(sizeof(ThisType))); 00232 00233 ThisType* theResult = theGuard.get(); 00234 00235 new (theResult) ThisType(theManager, initialSize, blockSize); 00236 00237 theGuard.release(); 00238 00239 return theResult; 00240 } 00241 00242 ~XalanDeque() 00243 { 00244 clear(); 00245 typename BlockIndexType::iterator iter = m_freeBlockVector.begin(); 00246 00247 while (iter != m_freeBlockVector.end()) 00248 { 00249 (*iter)->~XalanVector<Type, ConstructionTraits>(); 00250 deallocate(*iter); 00251 ++iter; 00252 } 00253 } 00254 00255 iterator begin() 00256 { 00257 return iterator(this, 0); 00258 } 00259 00260 const_iterator begin() const 00261 { 00262 return const_iterator(const_cast<XalanDeque*>(this), 0); 00263 } 00264 00265 iterator end() 00266 { 00267 return iterator(this, size()); 00268 } 00269 00270 const_iterator end() const 00271 { 00272 return const_iterator(const_cast<XalanDeque*>(this), size()); 00273 } 00274 00275 const_reverse_iterator rbegin() const 00276 { 00277 return const_reverse_iterator(end()); 00278 } 00279 00280 const_reverse_iterator rend() const 00281 { 00282 return const_reverse_iterator(begin()); 00283 } 00284 00285 bool empty() const 00286 { 00287 return m_blockIndex.empty(); 00288 } 00289 00290 size_type size() const 00291 { 00292 if (m_blockIndex.empty()) 00293 { 00294 return 0; 00295 } 00296 else 00297 { 00298 return (m_blockIndex.size() - 1) * m_blockSize 00299 + m_blockIndex.back()->size(); 00300 } 00301 } 00302 00303 value_type& back() 00304 { 00305 return m_blockIndex.back()->back(); 00306 } 00307 00308 value_type& operator[](size_type index) 00309 { 00310 BlockType & block = *(m_blockIndex[index / m_blockSize]); 00311 return block[index % m_blockSize]; 00312 } 00313 00314 const value_type& operator[](size_type index) const 00315 { 00316 BlockType & block = *(m_blockIndex[index / m_blockSize]); 00317 return block[index % m_blockSize]; 00318 } 00319 00320 void clear() 00321 { 00322 typename BlockIndexType::iterator iter = m_blockIndex.begin(); 00323 00324 m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size()); 00325 00326 while (iter != m_blockIndex.end()) 00327 { 00328 (*iter)->clear(); 00329 m_freeBlockVector.push_back(*iter); 00330 ++iter; 00331 } 00332 00333 m_blockIndex.clear(); 00334 } 00335 00336 void push_back(const value_type & value) 00337 { 00338 if (m_blockIndex.empty() || 00339 m_blockIndex.back()->size() >= m_blockSize) 00340 { 00341 m_blockIndex.push_back(getNewBlock()); 00342 } 00343 00344 m_blockIndex.back()->push_back(value); 00345 } 00346 00347 void pop_back() 00348 { 00349 BlockType & lastBlock = *(m_blockIndex.back()); 00350 lastBlock.pop_back(); 00351 if (lastBlock.empty()) 00352 { 00353 m_freeBlockVector.push_back(&lastBlock); 00354 m_blockIndex.pop_back(); 00355 } 00356 } 00357 00358 void resize(size_type newSize) 00359 { 00360 typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager); 00361 if (newSize > size()) 00362 { 00363 for (size_type i = 0; i < newSize - size(); ++i) 00364 { 00365 push_back(defaultValue.value); 00366 } 00367 } 00368 else 00369 { 00370 for (size_type i = 0; i < size() - newSize; ++i) 00371 { 00372 pop_back(); 00373 } 00374 } 00375 } 00376 00377 void swap(XalanDeque& theRhs) 00378 { 00379 MemoryManagerType* tempMemoryManager = m_memoryManager; 00380 m_memoryManager = theRhs.m_memoryManager; 00381 theRhs.m_memoryManager = tempMemoryManager; 00382 00383 theRhs.m_blockIndex.swap(m_blockIndex); 00384 theRhs.m_freeBlockVector.swap(m_freeBlockVector); 00385 } 00386 00387 XalanDeque & operator=(const XalanDeque & theRhs) 00388 { 00389 clear(); 00390 XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this)); 00391 return *this; 00392 } 00393 00394 MemoryManagerType& 00395 getMemoryManager() 00396 { 00397 assert (m_memoryManager != 0); 00398 00399 return *m_memoryManager; 00400 } 00401 protected: 00402 00403 BlockType* getNewBlock() 00404 { 00405 BlockType * newBlock; 00406 00407 if (m_freeBlockVector.empty()) 00408 { 00409 newBlock = allocate(1); 00410 new (&*newBlock) BlockType(*m_memoryManager, m_blockSize); 00411 } 00412 else 00413 { 00414 newBlock = m_freeBlockVector.back(); 00415 m_freeBlockVector.pop_back(); 00416 } 00417 00418 assert (newBlock != 0); 00419 00420 return newBlock; 00421 } 00422 00423 BlockType* 00424 allocate(size_type size) 00425 { 00426 const size_type theBytesNeeded = size * sizeof(BlockType); 00427 00428 BlockType* pointer = (BlockType*)m_memoryManager->allocate(theBytesNeeded); 00429 00430 assert(pointer != 0); 00431 00432 return pointer; 00433 } 00434 00435 void 00436 deallocate(BlockType* pointer) 00437 { 00438 m_memoryManager->deallocate(pointer); 00439 } 00440 00441 MemoryManagerType* m_memoryManager; 00442 const size_type m_blockSize; 00443 00444 BlockIndexType m_blockIndex; 00445 BlockIndexType m_freeBlockVector; 00446 00447 private: 00448 // Not implemented 00449 XalanDeque(); 00450 XalanDeque(const XalanDeque&); 00451 00452 }; 00453 00454 00455 00456 XALAN_CPP_NAMESPACE_END 00457 00458 00459 00460 #endif // XALANDEQUE_HEADER_GUARD_1357924680 00461
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
![]() |
Xalan-C++ XSLT Processor Version 1.9 |
|