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(XALANLIST_HEADER_GUARD_1357924680) 00020 #define XALANLIST_HEADER_GUARD_1357924680 00021 00022 00023 00024 // Base include file. Must be first. 00025 #include <xalanc/Include/PlatformDefinitions.hpp> 00026 00027 00028 00029 #include <cstddef> 00030 #include <algorithm> 00031 #include <cassert> 00032 #include <new> 00033 #include <iterator> 00034 #include <stdexcept> 00035 00036 00037 00038 #include <xalanc/Include/XalanMemoryManagement.hpp> 00039 00040 00041 00042 XALAN_CPP_NAMESPACE_BEGIN 00043 00044 00045 00046 template <class Value> 00047 struct XalanListIteratorTraits 00048 { 00049 typedef Value value_type; 00050 typedef Value& reference; 00051 typedef Value* pointer; 00052 }; 00053 00054 template <class Value> 00055 struct XalanListConstIteratorTraits 00056 { 00057 typedef Value value_type; 00058 typedef const Value& reference; 00059 typedef const Value* pointer; 00060 }; 00061 00062 template<class XalanListTraits, class Node> 00063 struct XalanListIteratorBase 00064 { 00065 typedef typename XalanListTraits::value_type value_type; 00066 typedef typename XalanListTraits::reference reference; 00067 typedef typename XalanListTraits::pointer pointer; 00068 00069 typedef ptrdiff_t difference_type; 00070 00071 typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category; 00072 00073 typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node> iterator; 00074 00075 XalanListIteratorBase(Node& node) : 00076 currentNode(&node) 00077 { 00078 } 00079 00080 XalanListIteratorBase(const iterator& theRhs) : 00081 currentNode(theRhs.currentNode) 00082 { 00083 } 00084 00085 XalanListIteratorBase operator++() 00086 { 00087 currentNode = currentNode->next; 00088 return *this; 00089 } 00090 00091 XalanListIteratorBase operator++(int) 00092 { 00093 Node& origNode = *currentNode; 00094 currentNode = currentNode->next; 00095 return XalanListIteratorBase(origNode); 00096 } 00097 00098 XalanListIteratorBase operator--() 00099 { 00100 currentNode = currentNode->prev; 00101 return *this; 00102 } 00103 00104 XalanListIteratorBase operator-(difference_type decrement) const 00105 { 00106 Node* node = currentNode; 00107 while (decrement > 0) 00108 { 00109 node = node->prev; 00110 --decrement; 00111 }; 00112 return XalanListIteratorBase(*node); 00113 } 00114 00115 reference operator*() const 00116 { 00117 return currentNode->value; 00118 } 00119 00120 pointer operator->() const 00121 { 00122 return ¤tNode->value; 00123 } 00124 00125 const XalanListIteratorBase & operator=(const XalanListIteratorBase& theRhs) 00126 { 00127 currentNode = theRhs.currentNode; 00128 return *this; 00129 } 00130 00131 bool operator!=(const XalanListIteratorBase& theRhs) const 00132 { 00133 return !operator==(theRhs); 00134 } 00135 00136 bool operator==(const XalanListIteratorBase& theRhs) const 00137 { 00138 return currentNode == theRhs.currentNode; 00139 } 00140 00141 Node& node() 00142 { 00143 return *currentNode; 00144 } 00145 00146 Node* currentNode; 00147 }; 00148 00149 00150 00151 /** 00152 * Xalan implementation of a doubly linked list 00153 */ 00154 template <class Type> 00155 class XalanList 00156 { 00157 public: 00158 00159 00160 typedef Type value_type; 00161 typedef value_type* pointer; 00162 typedef const value_type* const_pointer; 00163 typedef value_type& reference; 00164 typedef const value_type& const_reference; 00165 typedef size_t size_type; 00166 00167 typedef XalanList<value_type> ThisType; 00168 00169 struct Node 00170 { 00171 Node( 00172 const value_type & theValue, 00173 Node& prevNode, 00174 Node& nextNode) : 00175 value(theValue), 00176 prev(&prevNode), 00177 next(&nextNode) 00178 { 00179 } 00180 00181 value_type value; 00182 Node* prev; 00183 Node* next; 00184 }; 00185 00186 typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node> iterator; 00187 typedef XalanListIteratorBase<XalanListConstIteratorTraits<value_type>, Node> const_iterator; 00188 00189 #if defined(XALAN_HAS_STD_ITERATORS) 00190 typedef XALAN_STD_QUALIFIER reverse_iterator<iterator> reverse_iterator_; 00191 typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator> const_reverse_iterator_; 00192 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC) 00193 typedef typename iterator::iterator_category iterator_category; 00194 00195 // This is a specific case for the Rogue Wave STL on Solaris. 00196 typedef XALAN_STD_QUALIFIER reverse_iterator< 00197 iterator, 00198 iterator_category, 00199 value_type> reverse_iterator_; 00200 00201 typedef XALAN_STD_QUALIFIER reverse_iterator< 00202 const_iterator, 00203 iterator_category, 00204 const value_type> const_reverse_iterator_; 00205 #else 00206 typedef XALAN_STD_QUALIFIER reverse_iterator< 00207 iterator, 00208 value_type> reverse_iterator_; 00209 00210 typedef XALAN_STD_QUALIFIER reverse_iterator< 00211 const_iterator, 00212 value_type, 00213 const_reference> const_reverse_iterator_; 00214 #endif 00215 00216 typedef reverse_iterator_ reverse_iterator; 00217 typedef const_reverse_iterator_ const_reverse_iterator; 00218 00219 typedef typename MemoryManagedConstructionTraits<value_type>::Constructor Constructor; 00220 00221 XalanList( 00222 MemoryManager& theManager) : 00223 m_memoryManager(&theManager), 00224 m_listHead(0), 00225 m_freeListHeadPtr(0) 00226 { 00227 } 00228 00229 ~XalanList() 00230 { 00231 if (m_listHead != 0) 00232 { 00233 iterator pos = begin(); 00234 while (pos != end()) 00235 { 00236 destroyNode(pos++.node()); 00237 } 00238 00239 Node * freeNode = m_freeListHeadPtr; 00240 while (freeNode != 0) 00241 { 00242 Node * nextNode = freeNode->next; 00243 deallocate(freeNode); 00244 freeNode = nextNode; 00245 } 00246 00247 deallocate(m_listHead); 00248 } 00249 } 00250 00251 MemoryManager& 00252 getMemoryManager() 00253 { 00254 assert(m_memoryManager != 0 ); 00255 00256 return *m_memoryManager; 00257 } 00258 00259 const MemoryManager& 00260 getMemoryManager() const 00261 { 00262 assert(m_memoryManager != 0 ); 00263 00264 return *m_memoryManager; 00265 } 00266 00267 iterator 00268 begin() 00269 { 00270 return iterator(*(getListHead().next)); 00271 } 00272 00273 const_iterator 00274 begin() const 00275 { 00276 return const_iterator(*(getListHead().next)); 00277 } 00278 00279 iterator 00280 end() 00281 { 00282 return iterator(getListHead()); 00283 } 00284 00285 const_iterator 00286 end() const 00287 { 00288 return const_iterator(getListHead()); 00289 } 00290 00291 reverse_iterator 00292 rbegin() 00293 { 00294 return reverse_iterator(end()); 00295 } 00296 00297 const_reverse_iterator 00298 rbegin() const 00299 { 00300 return const_reverse_iterator(end()); 00301 } 00302 00303 reverse_iterator 00304 rend() 00305 { 00306 return reverse_iterator(begin()); 00307 } 00308 00309 const_reverse_iterator 00310 rend() const 00311 { 00312 return const_reverse_iterator(begin()); 00313 } 00314 00315 reference 00316 front() 00317 { 00318 return *begin(); 00319 } 00320 00321 reference 00322 back() 00323 { 00324 return *(--end()); 00325 } 00326 00327 size_type 00328 size() const 00329 { 00330 size_type size = 0; 00331 const_iterator item = begin(); 00332 while (item != end()) 00333 { 00334 ++size; 00335 ++item; 00336 } 00337 return size; 00338 } 00339 00340 bool 00341 empty() const 00342 { 00343 return (begin() == end()) != 0; 00344 } 00345 00346 void 00347 push_back(const value_type& data) 00348 { 00349 constructNode(data, end()); 00350 } 00351 00352 void 00353 push_front(const value_type& data) 00354 { 00355 constructNode(data, begin()); 00356 } 00357 00358 void 00359 pop_front() 00360 { 00361 erase(begin()); 00362 } 00363 00364 void 00365 pop_back() 00366 { 00367 erase(--end()); 00368 } 00369 00370 iterator 00371 insert(const iterator& pos, const value_type& value) 00372 { 00373 return iterator(constructNode(value,pos)); 00374 } 00375 00376 void 00377 erase(iterator pos) 00378 { 00379 assert(pos != end()); 00380 freeNode(pos.node()); 00381 } 00382 00383 void 00384 splice( 00385 iterator pos, 00386 #if defined(NDEBUG) 00387 ThisType& /* list */, 00388 #else 00389 ThisType& list, 00390 #endif 00391 iterator toInsert) 00392 { 00393 assert(m_memoryManager == list.m_memoryManager); 00394 00395 if (pos != toInsert) 00396 { 00397 Node & posNode = pos.node(); 00398 Node & toInsertNode = toInsert.node(); 00399 00400 toInsertNode.prev->next = toInsertNode.next; 00401 toInsertNode.next->prev = toInsertNode.prev; 00402 00403 toInsertNode.prev = posNode.prev; 00404 toInsertNode.next = &posNode; 00405 00406 posNode.prev->next = &toInsertNode; 00407 posNode.prev = &toInsertNode; 00408 } 00409 } 00410 00411 void 00412 splice( 00413 iterator pos, 00414 #if defined(NDEBUG) 00415 ThisType& /* list */, 00416 #else 00417 ThisType& list, 00418 #endif 00419 iterator toInsertFirst, 00420 iterator toInsertLast) 00421 { 00422 assert(m_memoryManager == list.m_memoryManager); 00423 00424 if (toInsertFirst != toInsertLast) 00425 { 00426 Node & posNode = pos.node(); 00427 Node & toInsertFirstNode = toInsertFirst.node(); 00428 Node & toInsertLastNode = *(toInsertLast.node().prev); 00429 00430 toInsertFirstNode.prev->next = toInsertLastNode.next; 00431 toInsertLastNode.next->prev = toInsertFirstNode.prev; 00432 00433 toInsertFirstNode.prev = posNode.prev; 00434 toInsertLastNode.next = &posNode; 00435 00436 posNode.prev->next = &toInsertFirstNode; 00437 posNode.prev = &toInsertLastNode; 00438 } 00439 } 00440 00441 void 00442 clear() 00443 { 00444 iterator pos = begin(); 00445 while (pos != end()) 00446 { 00447 freeNode(pos++.node()); 00448 } 00449 } 00450 00451 void swap(ThisType& theRHS) 00452 { 00453 #if defined(XALAN_NO_STD_NAMESPACE) 00454 ::swap(m_memoryManager, theRHS.m_memoryManager); 00455 ::swap(m_listHead, theRHS.m_listHead); 00456 ::swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr); 00457 #else 00458 XALAN_STD_QUALIFIER swap(m_memoryManager, theRHS.m_memoryManager); 00459 XALAN_STD_QUALIFIER swap(m_listHead, theRHS.m_listHead); 00460 XALAN_STD_QUALIFIER swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr); 00461 #endif 00462 } 00463 00464 00465 protected: 00466 00467 Node& constructNode(const value_type& data, iterator pos) 00468 { 00469 Node * newNode = 0; 00470 Node * nextFreeNode = 0; 00471 00472 if (m_freeListHeadPtr != 0) 00473 { 00474 newNode = m_freeListHeadPtr; 00475 nextFreeNode = m_freeListHeadPtr->next; 00476 } 00477 else 00478 { 00479 m_freeListHeadPtr = allocate(1); 00480 newNode = m_freeListHeadPtr; 00481 } 00482 00483 Constructor::construct(&newNode->value, data, *m_memoryManager); 00484 new (&newNode->prev) Node*(pos.node().prev); 00485 new (&newNode->next) Node*(&(pos.node())); 00486 00487 pos.node().prev->next = newNode; 00488 pos.node().prev = newNode; 00489 00490 m_freeListHeadPtr = nextFreeNode; 00491 00492 return *newNode; 00493 } 00494 00495 void freeNode(Node& node) 00496 { 00497 node.prev->next = node.next; 00498 node.next->prev = node.prev; 00499 00500 node.~Node(); 00501 node.prev = 0; 00502 node.next = m_freeListHeadPtr; 00503 m_freeListHeadPtr = &node; 00504 } 00505 00506 void destroyNode(Node& node) 00507 { 00508 assert(&node != m_listHead); 00509 node.~Node(); 00510 deallocate(&node); 00511 } 00512 00513 Node& getListHead() 00514 { 00515 if (0 == m_listHead) 00516 { 00517 m_listHead = allocate(1); 00518 m_listHead->next = m_listHead; 00519 m_listHead->prev = m_listHead; 00520 } 00521 00522 return *m_listHead; 00523 } 00524 00525 Node& getListHead() const 00526 { 00527 return const_cast<XalanList*>(this)->getListHead(); 00528 } 00529 00530 Node* 00531 allocate(size_type size) 00532 { 00533 const size_type theBytesNeeded = size * sizeof(Node); 00534 00535 assert(m_memoryManager != 0); 00536 00537 void* pointer = m_memoryManager->allocate(theBytesNeeded); 00538 00539 assert( pointer != 0 ); 00540 00541 return (Node*) pointer; 00542 } 00543 00544 00545 void 00546 deallocate(Node* pointer) 00547 { 00548 assert(m_memoryManager != 0); 00549 00550 m_memoryManager->deallocate(pointer); 00551 } 00552 00553 MemoryManager * m_memoryManager; 00554 00555 Node* m_listHead; 00556 00557 Node* m_freeListHeadPtr; 00558 00559 private: 00560 // not defined 00561 XalanList(); 00562 XalanList(const XalanList& theRhs); 00563 00564 XalanList& operator=(const XalanList& theRhs); 00565 00566 }; 00567 00568 00569 00570 XALAN_CPP_NAMESPACE_END 00571 00572 #endif // XALANLIST_HEADER_GUARD_1357924680
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
Xalan-C++ XSLT Processor Version 1.11 |
|