Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.10

XalanList.hpp
Go to the documentation of this file.
1 /*
2  * Copyright 1999-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
21 #if !defined(XALANLIST_HEADER_GUARD_1357924680)
22 #define XALANLIST_HEADER_GUARD_1357924680
23 
24 
25 
26 // Base include file. Must be first.
28 
29 
30 
31 #include <cstddef>
32 #include <algorithm>
33 #include <cassert>
34 #include <new>
35 #include <iterator>
36 #include <stdexcept>
37 
38 
39 
41 
42 
43 
44 XALAN_CPP_NAMESPACE_BEGIN
45 
46 
47 
48 template <class Value>
50 {
51  typedef Value value_type;
52  typedef Value& reference;
53  typedef Value* pointer;
54 };
55 
56 template <class Value>
58 {
59  typedef Value value_type;
60  typedef const Value& reference;
61  typedef const Value* pointer;
62 };
63 
64 template<class XalanListTraits, class Node>
66 {
67  typedef typename XalanListTraits::value_type value_type;
68  typedef typename XalanListTraits::reference reference;
69  typedef typename XalanListTraits::pointer pointer;
70 
71  typedef ptrdiff_t difference_type;
72 
73  typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category;
74 
76 
78  currentNode(&node)
79  {
80  }
81 
83  currentNode(theRhs.currentNode)
84  {
85  }
86 
88  {
89  currentNode = currentNode->next;
90  return *this;
91  }
92 
94  {
95  Node& origNode = *currentNode;
96  currentNode = currentNode->next;
97  return XalanListIteratorBase(origNode);
98  }
99 
101  {
102  currentNode = currentNode->prev;
103  return *this;
104  }
105 
107  {
108  Node* node = currentNode;
109  while (decrement > 0)
110  {
111  node = node->prev;
112  --decrement;
113  };
114  return XalanListIteratorBase(*node);
115  }
116 
118  {
119  return currentNode->value;
120  }
121 
123  {
124  return &currentNode->value;
125  }
126 
128  {
129  currentNode = theRhs.currentNode;
130  return *this;
131  }
132 
133  bool operator!=(const XalanListIteratorBase& theRhs) const
134  {
135  return !operator==(theRhs);
136  }
137 
138  bool operator==(const XalanListIteratorBase& theRhs) const
139  {
140  return currentNode == theRhs.currentNode;
141  }
142 
143  Node& node()
144  {
145  return *currentNode;
146  }
147 
148  Node* currentNode;
149 };
150 
151 
152 
156 template <class Type>
158 {
159 public:
160 
161 
162  typedef Type value_type;
163  typedef value_type* pointer;
164  typedef const value_type* const_pointer;
166  typedef const value_type& const_reference;
167  typedef size_t size_type;
168 
170 
171  struct Node
172  {
174  const value_type & theValue,
175  Node& prevNode,
176  Node& nextNode) :
177  value(theValue),
178  prev(&prevNode),
179  next(&nextNode)
180  {
181  }
182 
186  };
187 
189 
191 
192 #if defined(XALAN_HAS_STD_ITERATORS)
193  typedef XALAN_STD_QUALIFIER reverse_iterator<iterator> reverse_iterator_;
194  typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator> const_reverse_iterator_;
195 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
196  typedef XALAN_STD_QUALIFIER reverse_iterator<
197  iterator,
198  XALAN_STD_QUALIFIER bidirectional_iterator_tag,
200  typedef XALAN_STD_QUALIFIER reverse_iterator<
202  XALAN_STD_QUALIFIER bidirectional_iterator_tag,
204 #else
207 #endif
208 
211 
213 
215  MemoryManagerType& theManager) :
216  m_memoryManager(&theManager),
217  m_listHead(0),
219  {
220  }
221 
223  {
224  if (m_listHead != 0)
225  {
226  iterator pos = begin();
227  while (pos != end())
228  {
229  destroyNode(pos++.node());
230  }
231 
232  Node * freeNode = m_freeListHeadPtr;
233  while (freeNode != 0)
234  {
235  Node * nextNode = freeNode->next;
236  deallocate(freeNode);
237  freeNode = nextNode;
238  }
239 
241  }
242  }
243 
246  {
247  assert(m_memoryManager != 0 );
248 
249  return *m_memoryManager;
250  }
251 
252  const MemoryManagerType&
254  {
255  assert(m_memoryManager != 0 );
256 
257  return *m_memoryManager;
258  }
259 
260  iterator
262  {
263  return iterator(*(getListHead().next));
264  }
265 
267  begin() const
268  {
269  return const_iterator(*(getListHead().next));
270  }
271 
272  iterator
273  end()
274  {
275  return iterator(getListHead());
276  }
277 
279  end() const
280  {
281  return const_iterator(getListHead());
282  }
283 
286  {
287  return reverse_iterator(end());
288  }
289 
291  rbegin() const
292  {
293  return const_reverse_iterator(end());
294  }
295 
298  {
299  return reverse_iterator(begin());
300  }
301 
303  rend() const
304  {
305  return const_reverse_iterator(begin());
306  }
307 
308  reference
310  {
311  return *begin();
312  }
313 
314  reference
316  {
317  return *(--end());
318  }
319 
320  size_type
321  size() const
322  {
323  size_type size = 0;
324  const_iterator item = begin();
325  while (item != end())
326  {
327  ++size;
328  ++item;
329  }
330  return size;
331  }
332 
333  bool
334  empty() const
335  {
336  return (begin() == end()) != 0;
337  }
338 
339  void
340  push_back(const value_type& data)
341  {
342  constructNode(data, end());
343  }
344 
345  void
346  push_front(const value_type& data)
347  {
348  constructNode(data, begin());
349  }
350 
351  void
353  {
354  erase(begin());
355  }
356 
357  void
359  {
360  erase(--end());
361  }
362 
363  iterator
364  insert(const iterator& pos, const value_type& value)
365  {
366  return iterator(constructNode(value,pos));
367  }
368 
369  void
371  {
372  assert(pos != end());
373  freeNode(pos.node());
374  }
375 
376  void
378  iterator pos,
379 #if defined(NDEBUG)
380  ThisType& /* list */,
381 #else
382  ThisType& list,
383 #endif
384  iterator toInsert)
385  {
386  assert(m_memoryManager == list.m_memoryManager);
387 
388  if (pos != toInsert)
389  {
390  Node & posNode = pos.node();
391  Node & toInsertNode = toInsert.node();
392 
393  toInsertNode.prev->next = toInsertNode.next;
394  toInsertNode.next->prev = toInsertNode.prev;
395 
396  toInsertNode.prev = posNode.prev;
397  toInsertNode.next = &posNode;
398 
399  posNode.prev->next = &toInsertNode;
400  posNode.prev = &toInsertNode;
401  }
402  }
403 
404  void
406  iterator pos,
407 #if defined(NDEBUG)
408  ThisType& /* list */,
409 #else
410  ThisType& list,
411 #endif
412  iterator toInsertFirst,
413  iterator toInsertLast)
414  {
415  assert(m_memoryManager == list.m_memoryManager);
416 
417  if (toInsertFirst != toInsertLast)
418  {
419  Node & posNode = pos.node();
420  Node & toInsertFirstNode = toInsertFirst.node();
421  Node & toInsertLastNode = *(toInsertLast.node().prev);
422 
423  toInsertFirstNode.prev->next = toInsertLastNode.next;
424  toInsertLastNode.next->prev = toInsertFirstNode.prev;
425 
426  toInsertFirstNode.prev = posNode.prev;
427  toInsertLastNode.next = &posNode;
428 
429  posNode.prev->next = &toInsertFirstNode;
430  posNode.prev = &toInsertLastNode;
431  }
432  }
433 
434  void
436  {
437  iterator pos = begin();
438  while (pos != end())
439  {
440  freeNode(pos++.node());
441  }
442  }
443 
444  void swap(ThisType& theRHS)
445  {
446  #if defined(XALAN_NO_STD_NAMESPACE)
448  ::swap(m_listHead, theRHS.m_listHead);
450  #else
451  XALAN_STD_QUALIFIER swap(m_memoryManager, theRHS.m_memoryManager);
452  XALAN_STD_QUALIFIER swap(m_listHead, theRHS.m_listHead);
453  XALAN_STD_QUALIFIER swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr);
454  #endif
455  }
456 
457 
458 protected:
459 
460  Node& constructNode(const value_type& data, iterator pos)
461  {
462  Node * newNode = 0;
463  Node * nextFreeNode = 0;
464 
465  if (m_freeListHeadPtr != 0)
466  {
467  newNode = m_freeListHeadPtr;
468  nextFreeNode = m_freeListHeadPtr->next;
469  }
470  else
471  {
473  newNode = m_freeListHeadPtr;
474  }
475 
476  Constructor::construct(&newNode->value, data, *m_memoryManager);
477  new (&newNode->prev) Node*(pos.node().prev);
478  new (&newNode->next) Node*(&(pos.node()));
479 
480  pos.node().prev->next = newNode;
481  pos.node().prev = newNode;
482 
483  m_freeListHeadPtr = nextFreeNode;
484 
485  return *newNode;
486  }
487 
488  void freeNode(Node& node)
489  {
490  node.prev->next = node.next;
491  node.next->prev = node.prev;
492 
493  node.~Node();
494  node.prev = 0;
495  node.next = m_freeListHeadPtr;
496  m_freeListHeadPtr = &node;
497  }
498 
499  void destroyNode(Node& node)
500  {
501  assert(&node != m_listHead);
502  node.~Node();
503  deallocate(&node);
504  }
505 
506  Node& getListHead()
507  {
508  if (0 == m_listHead)
509  {
510  m_listHead = allocate(1);
513  }
514 
515  return *m_listHead;
516  }
517 
518  Node& getListHead() const
519  {
520  return const_cast<XalanList*>(this)->getListHead();
521  }
522 
523  Node*
525  {
526  const size_type theBytesNeeded = size * sizeof(Node);
527 
528  assert(m_memoryManager != 0);
529 
530  void* pointer = m_memoryManager->allocate(theBytesNeeded);
531 
532  assert( pointer != 0 );
533 
534  return (Node*) pointer;
535  }
536 
537 
538  void
540  {
541  assert(m_memoryManager != 0);
542 
543  m_memoryManager->deallocate(pointer);
544  }
545 
547 
548  Node* m_listHead;
549 
551 
552 private:
553  // not defined
554  XalanList();
555  XalanList(const XalanList& theRhs);
556 
557  XalanList& operator=(const XalanList& theRhs);
558 
559 };
560 
561 
562 
563 XALAN_CPP_NAMESPACE_END
564 
565 #endif // XALANLIST_HEADER_GUARD_1357924680
const_reverse_iterator_ const_reverse_iterator
Definition: XalanList.hpp:210
XalanListIteratorBase operator-(difference_type decrement) const
Definition: XalanList.hpp:106
bool empty() const
Definition: XalanList.hpp:334
Type value_type
Definition: XalanList.hpp:162
Definition: XalanList.hpp:49
MemoryManagerType & getMemoryManager()
Definition: XalanList.hpp:245
Node & constructNode(const value_type &data, iterator pos)
Definition: XalanList.hpp:460
void pop_back()
Definition: XalanList.hpp:358
XALAN_CPP_NAMESPACE_BEGIN typedef XERCES_CPP_NAMESPACE_QUALIFIER MemoryManager MemoryManagerType
Definition: XalanMemoryManagement.hpp:39
void push_front(const value_type &data)
Definition: XalanList.hpp:346
const_iterator begin() const
Definition: XalanList.hpp:267
XalanListIteratorBase(Node &node)
Definition: XalanList.hpp:77
value_type * pointer
Definition: XalanList.hpp:163
XalanListIteratorBase< XalanListConstIteratorTraits< value_type >, Node > const_iterator
Definition: XalanList.hpp:190
XALAN_STD_QUALIFIER reverse_iterator< const_iterator, value_type, const_reference > const_reverse_iterator_
Definition: XalanList.hpp:206
Node & getListHead()
Definition: XalanList.hpp:506
XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category
Definition: XalanList.hpp:73
XalanListIteratorBase< XalanListIteratorTraits< value_type >, Node > iterator
Definition: XalanList.hpp:75
void pop_front()
Definition: XalanList.hpp:352
XalanList(MemoryManagerType &theManager)
Definition: XalanList.hpp:214
iterator end()
Definition: XalanList.hpp:273
const_reverse_iterator rend() const
Definition: XalanList.hpp:303
Node & node()
Definition: XalanList.hpp:143
reverse_iterator_ reverse_iterator
Definition: XalanList.hpp:209
bool operator!=(const XalanListIteratorBase &theRhs) const
Definition: XalanList.hpp:133
Node * next
Definition: XalanList.hpp:185
Definition: XalanList.hpp:171
reference front()
Definition: XalanList.hpp:309
Definition: XalanMemoryManagement.hpp:430
Value & reference
Definition: XalanList.hpp:52
const Value & reference
Definition: XalanList.hpp:60
pointer operator->() const
Definition: XalanList.hpp:122
value_type value
Definition: XalanList.hpp:183
reverse_iterator rend()
Definition: XalanList.hpp:297
XalanListIteratorBase(const iterator &theRhs)
Definition: XalanList.hpp:82
const_reverse_iterator rbegin() const
Definition: XalanList.hpp:291
Node * allocate(size_type size)
Definition: XalanList.hpp:524
XalanListIteratorBase< XalanListIteratorTraits< value_type >, Node > iterator
Definition: XalanList.hpp:188
Node & getListHead() const
Definition: XalanList.hpp:518
reference operator*() const
Definition: XalanList.hpp:117
iterator begin()
Definition: XalanList.hpp:261
void splice(iterator pos, ThisType &list, iterator toInsert)
Definition: XalanList.hpp:377
XalanListTraits::pointer pointer
Definition: XalanList.hpp:69
void destroyNode(Node &node)
Definition: XalanList.hpp:499
value_type & reference
Definition: XalanList.hpp:165
void clear()
Definition: XalanList.hpp:435
XALAN_STD_QUALIFIER reverse_iterator< iterator, value_type > reverse_iterator_
Definition: XalanList.hpp:205
const_iterator end() const
Definition: XalanList.hpp:279
Xalan implementation of a doubly linked list.
Definition: XalanList.hpp:157
static C * construct(C *address, MemoryManager &)
Definition: XalanMemoryManagement.hpp:434
XalanListTraits::value_type value_type
Definition: XalanList.hpp:67
size_t size_type
Definition: XalanList.hpp:167
ptrdiff_t difference_type
Definition: XalanList.hpp:71
const MemoryManagerType & getMemoryManager() const
Definition: XalanList.hpp:253
XalanListIteratorBase operator++()
Definition: XalanList.hpp:87
Node * m_freeListHeadPtr
Definition: XalanList.hpp:550
Node * prev
Definition: XalanList.hpp:184
MemoryManagerType * m_memoryManager
Definition: XalanList.hpp:546
XalanList< value_type > ThisType
Definition: XalanList.hpp:169
void push_back(const value_type &data)
Definition: XalanList.hpp:340
void splice(iterator pos, ThisType &list, iterator toInsertFirst, iterator toInsertLast)
Definition: XalanList.hpp:405
XalanListIteratorBase operator--()
Definition: XalanList.hpp:100
reference back()
Definition: XalanList.hpp:315
void swap(ThisType &theRHS)
Definition: XalanList.hpp:444
bool operator==(const XalanListIteratorBase &theRhs) const
Definition: XalanList.hpp:138
Value value_type
Definition: XalanList.hpp:59
Node * currentNode
Definition: XalanList.hpp:148
XalanListIteratorBase operator++(int)
Definition: XalanList.hpp:93
Value * pointer
Definition: XalanList.hpp:53
const Value * pointer
Definition: XalanList.hpp:61
MemoryManagedConstructionTraits< value_type >::Constructor Constructor
Definition: XalanList.hpp:212
XalanListTraits::reference reference
Definition: XalanList.hpp:68
const XalanListIteratorBase & operator=(const XalanListIteratorBase &theRhs)
Definition: XalanList.hpp:127
void deallocate(Node *pointer)
Definition: XalanList.hpp:539
reverse_iterator rbegin()
Definition: XalanList.hpp:285
Definition: XalanList.hpp:57
iterator insert(const iterator &pos, const value_type &value)
Definition: XalanList.hpp:364
Definition: XalanList.hpp:65
~XalanList()
Definition: XalanList.hpp:222
Node * m_listHead
Definition: XalanList.hpp:548
void freeNode(Node &node)
Definition: XalanList.hpp:488
Value value_type
Definition: XalanList.hpp:51
const value_type * const_pointer
Definition: XalanList.hpp:164
const value_type & const_reference
Definition: XalanList.hpp:166
size_type size() const
Definition: XalanList.hpp:321
void erase(iterator pos)
Definition: XalanList.hpp:370
Node(const value_type &theValue, Node &prevNode, Node &nextNode)
Definition: XalanList.hpp:173

Interpreting class diagrams

Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.

dot

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

Apache Logo