Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.11


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

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.11
Copyright © 1999-2012 The Apache Software Foundation.
All Rights Reserved.

Apache Logo