00001 /* 00002 * Licensed to the Apache Software Foundation (ASF) under one 00003 * or more contributor license agreements. See the NOTICE file 00004 * distributed with this work for additional information 00005 * regarding copyright ownership. The ASF licenses this file 00006 * to you under the Apache License, Version 2.0 (the "License"); 00007 * you may not use this file except in compliance with the License. 00008 * You may obtain a copy of the License at 00009 * 00010 * http://www.apache.org/licenses/LICENSE-2.0 00011 * 00012 * Unless required by applicable law or agreed to in writing, software 00013 * distributed under the License is distributed on an "AS IS" BASIS, 00014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00015 * See the License for the specific language governing permissions and 00016 * limitations under the License. 00017 */ 00018 00019 #if !defined(XALANDEQUE_HEADER_GUARD_1357924680) 00020 #define XALANDEQUE_HEADER_GUARD_1357924680 00021 00022 00023 00024 // Base include file. Must be first. 00025 #include <xalanc/Include/PlatformDefinitions.hpp> 00026 00027 00028 00029 #include <xalanc/Include/XalanVector.hpp> 00030 #include <xalanc/Include/XalanMemoryManagement.hpp> 00031 00032 00033 00034 XALAN_CPP_NAMESPACE_BEGIN 00035 00036 00037 00038 template <class Value> 00039 struct XalanDequeIteratorTraits 00040 { 00041 typedef Value value_type; 00042 typedef Value& reference; 00043 typedef Value* pointer; 00044 typedef const Value& const_reference; 00045 }; 00046 00047 template <class Value> 00048 struct XalanDequeConstIteratorTraits 00049 { 00050 typedef Value value_type; 00051 typedef const Value& reference; 00052 typedef const Value* pointer; 00053 typedef const Value& const_reference; 00054 }; 00055 00056 template <class Traits, class XalanDeque> 00057 class XalanDequeIterator 00058 { 00059 public: 00060 00061 typedef size_t size_type; 00062 typedef typename Traits::value_type value_type; 00063 typedef typename Traits::reference reference; 00064 typedef typename Traits::pointer pointer; 00065 typedef typename Traits::const_reference const_reference; 00066 typedef ptrdiff_t difference_type; 00067 00068 typedef XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category; 00069 00070 // The non-const iterator type. In the case of the non-const instatiation, this 00071 // is the same type. 00072 typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> Iterator; 00073 00074 // The const version needs access to our private data members for copy construction and 00075 // assignment. For the const instantiation, this is a superfluous friend declaration, 00076 // since it's the same type as the class itself. 00077 friend class XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, XalanDeque>; 00078 00079 XalanDequeIterator( 00080 XalanDeque* deque, 00081 size_type pos) : 00082 m_deque(deque), 00083 m_pos(pos) 00084 { 00085 } 00086 00087 // This is standard copy-construction for the non-const iterator type. For the 00088 // const iterator type, this is copy construction from the non-const type, and the 00089 // compiler will generate the standard copy constructor. 00090 XalanDequeIterator(const Iterator& iterator) : 00091 m_deque(iterator.m_deque), 00092 m_pos(iterator.m_pos) 00093 { 00094 } 00095 00096 // This is the standard assignment operator for the non-const iterator type. 00097 // For the const iterator type, this is the assignment operator from the 00098 // non-const type, and the compiler will generate the standard assignment 00099 // operator. 00100 XalanDequeIterator& 00101 operator=(const Iterator& iterator) 00102 { 00103 m_deque = iterator.m_deque; 00104 m_pos = iterator.m_pos; 00105 00106 return *this; 00107 } 00108 00109 XalanDequeIterator& 00110 operator++() 00111 { 00112 ++m_pos; 00113 00114 return *this; 00115 } 00116 00117 XalanDequeIterator 00118 operator++(int) 00119 { 00120 XalanDequeIterator temp = *this; 00121 ++m_pos; 00122 00123 return temp; 00124 } 00125 00126 XalanDequeIterator& 00127 operator--() 00128 { 00129 --m_pos; 00130 00131 return *this; 00132 } 00133 00134 pointer 00135 operator->() 00136 { 00137 return &(*m_deque[m_pos]); 00138 } 00139 00140 reference 00141 operator*() 00142 { 00143 return (*m_deque)[m_pos]; 00144 } 00145 00146 const_reference 00147 operator*() const 00148 { 00149 return (*m_deque)[m_pos]; 00150 } 00151 00152 XalanDequeIterator 00153 operator+(difference_type difference) const 00154 { 00155 return XalanDequeIterator(m_deque, m_pos + difference); 00156 } 00157 00158 XalanDequeIterator 00159 operator-(difference_type difference) const 00160 { 00161 return XalanDequeIterator(m_deque, m_pos - difference); 00162 } 00163 00164 difference_type 00165 operator-(const XalanDequeIterator& theRHS) const 00166 { 00167 return m_pos - theRHS.m_pos; 00168 } 00169 00170 bool 00171 operator==(const XalanDequeIterator& theRHS) const 00172 { 00173 return theRHS.m_deque == m_deque && 00174 theRHS.m_pos == m_pos; 00175 } 00176 00177 bool 00178 operator!=(const XalanDequeIterator& theRHS) const 00179 { 00180 return !(theRHS == *this); 00181 } 00182 00183 bool 00184 operator<(const XalanDequeIterator& theRHS) const 00185 { 00186 return m_pos < theRHS.m_pos; 00187 } 00188 00189 private: 00190 00191 XalanDeque* m_deque; 00192 00193 size_type m_pos; 00194 }; 00195 00196 /** 00197 * Xalan implementation of deque 00198 */ 00199 template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> > 00200 class XalanDeque 00201 { 00202 public: 00203 00204 typedef size_t size_type; 00205 00206 typedef Type value_type; 00207 typedef Type& reference; 00208 typedef const Type& const_reference; 00209 00210 typedef XalanVector<Type, ConstructionTraits> BlockType; 00211 typedef XalanVector<BlockType*> BlockIndexType; 00212 00213 typedef XalanDeque<Type, ConstructionTraits> ThisType; 00214 00215 typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, ThisType> iterator; 00216 typedef XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, ThisType> const_iterator; 00217 00218 #if defined(XALAN_HAS_STD_ITERATORS) 00219 typedef XALAN_STD_QUALIFIER reverse_iterator<iterator> reverse_iterator_; 00220 typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator> const_reverse_iterator_; 00221 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC) 00222 typedef typename iterator::iterator_category iterator_category; 00223 00224 // This is a specific case for the Rogue Wave STL on Solaris. 00225 typedef XALAN_STD_QUALIFIER reverse_iterator< 00226 iterator, 00227 iterator_category, 00228 value_type> reverse_iterator_; 00229 00230 typedef XALAN_STD_QUALIFIER reverse_iterator< 00231 const_iterator, 00232 iterator_category, 00233 const value_type> const_reverse_iterator_; 00234 #else 00235 typedef XALAN_STD_QUALIFIER reverse_iterator< 00236 iterator, 00237 value_type> reverse_iterator_; 00238 00239 typedef XALAN_STD_QUALIFIER reverse_iterator< 00240 const_iterator, 00241 value_type, 00242 const_reference> const_reverse_iterator_; 00243 #endif 00244 00245 typedef reverse_iterator_ reverse_iterator; 00246 typedef const_reverse_iterator_ const_reverse_iterator; 00247 00248 typedef typename ConstructionTraits::Constructor Constructor; 00249 typedef typename Constructor::ConstructableType ConstructableType; 00250 00251 XalanDeque( 00252 MemoryManager& memoryManager, 00253 size_type initialSize = 0, 00254 size_type blockSize = 10) : 00255 m_memoryManager(&memoryManager), 00256 m_blockSize(blockSize), 00257 m_blockIndex(memoryManager, 00258 initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)), 00259 m_freeBlockVector(memoryManager) 00260 { 00261 const ConstructableType defaultValue(*m_memoryManager); 00262 00263 XALAN_USING_STD(fill_n) 00264 XALAN_USING_STD(back_inserter) 00265 00266 fill_n( 00267 back_inserter(*this), 00268 initialSize, 00269 defaultValue.value); 00270 } 00271 00272 XalanDeque( 00273 const XalanDeque& theRHS, 00274 MemoryManager& theMemoryManager) : 00275 m_memoryManager(&theMemoryManager), 00276 m_blockSize(theRHS.m_blockSize), 00277 m_blockIndex(*theRHS.m_memoryManager, 00278 theRHS.size() / theRHS.m_blockSize + (theRHS.size() % theRHS.m_blockSize == 0 ? 0 : 1)), 00279 m_freeBlockVector(theMemoryManager) 00280 { 00281 XALAN_USING_STD(copy) 00282 XALAN_USING_STD(back_inserter) 00283 00284 copy( 00285 theRHS.begin(), 00286 theRHS.end(), 00287 back_inserter(*this)); 00288 } 00289 00290 static XalanDeque* 00291 create( 00292 MemoryManager& theManager, 00293 size_type initialSize = 0, 00294 size_type blockSize = 10) 00295 { 00296 XalanAllocationGuard theGuard(theManager, theManager.allocate(sizeof(ThisType))); 00297 00298 ThisType* const theResult = 00299 new (theGuard.get()) ThisType(theManager, initialSize, blockSize); 00300 00301 theGuard.release(); 00302 00303 return theResult; 00304 } 00305 00306 ~XalanDeque() 00307 { 00308 destroyBlockList(m_freeBlockVector); 00309 00310 destroyBlockList(m_blockIndex); 00311 } 00312 00313 iterator 00314 begin() 00315 { 00316 return iterator(this, 0); 00317 } 00318 00319 const_iterator 00320 begin() const 00321 { 00322 return const_iterator(const_cast<XalanDeque*>(this), 0); 00323 } 00324 00325 iterator 00326 end() 00327 { 00328 return iterator(this, size()); 00329 } 00330 00331 const_iterator 00332 end() const 00333 { 00334 return const_iterator(const_cast<XalanDeque*>(this), size()); 00335 } 00336 00337 const_reverse_iterator 00338 rbegin() const 00339 { 00340 return const_reverse_iterator(end()); 00341 } 00342 00343 const_reverse_iterator 00344 rend() const 00345 { 00346 return const_reverse_iterator(begin()); 00347 } 00348 00349 bool 00350 empty() const 00351 { 00352 return m_blockIndex.empty(); 00353 } 00354 00355 size_type 00356 size() const 00357 { 00358 if (m_blockIndex.empty()) 00359 { 00360 return 0; 00361 } 00362 else 00363 { 00364 return (m_blockIndex.size() - 1) * m_blockSize 00365 + m_blockIndex.back()->size(); 00366 } 00367 } 00368 00369 value_type& 00370 back() 00371 { 00372 return m_blockIndex.back()->back(); 00373 } 00374 00375 value_type& 00376 operator[](size_type index) 00377 { 00378 BlockType& block = *m_blockIndex[index / m_blockSize]; 00379 00380 return block[index % m_blockSize]; 00381 } 00382 00383 const value_type& 00384 operator[](size_type index) const 00385 { 00386 BlockType& block = *m_blockIndex[index / m_blockSize]; 00387 00388 return block[index % m_blockSize]; 00389 } 00390 00391 void 00392 clear() 00393 { 00394 typename BlockIndexType::iterator iter = m_blockIndex.begin(); 00395 00396 m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size()); 00397 00398 while (iter != m_blockIndex.end()) 00399 { 00400 (*iter)->clear(); 00401 m_freeBlockVector.push_back(*iter); 00402 ++iter; 00403 } 00404 00405 m_blockIndex.clear(); 00406 } 00407 00408 void 00409 push_back(const value_type& value) 00410 { 00411 if (m_blockIndex.empty() || 00412 m_blockIndex.back()->size() >= m_blockSize) 00413 { 00414 pushNewIndexBlock(); 00415 } 00416 00417 m_blockIndex.back()->push_back(value); 00418 } 00419 00420 void 00421 pop_back() 00422 { 00423 assert(!empty()); 00424 00425 BlockType& lastBlock = *m_blockIndex.back(); 00426 lastBlock.pop_back(); 00427 00428 if (lastBlock.empty()) 00429 { 00430 m_freeBlockVector.push_back(&lastBlock); 00431 m_blockIndex.pop_back(); 00432 } 00433 } 00434 00435 void 00436 resize(size_type newSize) 00437 { 00438 const ConstructableType defaultValue(*m_memoryManager); 00439 00440 if (newSize > size()) 00441 { 00442 for (size_type i = 0; i < newSize - size(); ++i) 00443 { 00444 push_back(defaultValue.value); 00445 } 00446 } 00447 else 00448 { 00449 for (size_type i = 0; i < size() - newSize; ++i) 00450 { 00451 pop_back(); 00452 } 00453 } 00454 } 00455 00456 void 00457 swap(XalanDeque& theRHS) 00458 { 00459 MemoryManager* const temp = m_memoryManager; 00460 m_memoryManager = theRHS.m_memoryManager; 00461 theRHS.m_memoryManager = temp; 00462 00463 theRHS.m_blockIndex.swap(m_blockIndex); 00464 theRHS.m_freeBlockVector.swap(m_freeBlockVector); 00465 } 00466 00467 XalanDeque& 00468 operator=(const XalanDeque& theRHS) 00469 { 00470 if (this != &theRHS) 00471 { 00472 XALAN_USING_STD(copy) 00473 XALAN_USING_STD(back_inserter) 00474 00475 clear(); 00476 00477 copy( 00478 theRHS.begin(), 00479 theRHS.end(), 00480 back_inserter(*this)); 00481 } 00482 00483 return *this; 00484 } 00485 00486 MemoryManager& 00487 getMemoryManager() 00488 { 00489 assert (m_memoryManager != 0); 00490 00491 return *m_memoryManager; 00492 } 00493 00494 private: 00495 00496 void 00497 pushNewIndexBlock() 00498 { 00499 // Allocate space first, so we don't have to worry 00500 // about an out-of-memory error once we've constructed 00501 // the new block. 00502 m_blockIndex.push_back(0); 00503 00504 if (m_freeBlockVector.empty()) 00505 { 00506 XalanConstruct( 00507 *m_memoryManager, 00508 m_blockIndex.back(), 00509 *m_memoryManager, 00510 m_blockSize); 00511 } 00512 else 00513 { 00514 m_blockIndex.back() = m_freeBlockVector.back(); 00515 00516 // Now that ownership has been transfered, pop 00517 // it off the free list. 00518 m_freeBlockVector.pop_back(); 00519 } 00520 00521 assert(m_blockIndex.back() != 0); 00522 } 00523 00524 void 00525 destroyBlockList(BlockIndexType& theBlockIndex) 00526 { 00527 typename BlockIndexType::iterator iter = 00528 theBlockIndex.begin(); 00529 00530 while (iter != theBlockIndex.end()) 00531 { 00532 // Normally, we should be able to just call 00533 // the version of XalanDestroy() that accepts 00534 // a pointer, but Visual Studio 6 has issues 00535 // with partial ordering, so we're stuck with 00536 // this for now. 00537 if (*iter != 0) 00538 { 00539 XalanDestroy(*m_memoryManager, **iter); 00540 } 00541 00542 ++iter; 00543 } 00544 } 00545 00546 MemoryManager* m_memoryManager; 00547 00548 const size_type m_blockSize; 00549 00550 BlockIndexType m_blockIndex; 00551 BlockIndexType m_freeBlockVector; 00552 00553 00554 // These are not implemented 00555 XalanDeque(); 00556 00557 XalanDeque(const XalanDeque&); 00558 }; 00559 00560 00561 00562 XALAN_CPP_NAMESPACE_END 00563 00564 00565 00566 #endif // XALANDEQUE_HEADER_GUARD_1357924680 00567
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
Xalan-C++ XSLT Processor Version 1.11 |
|