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 
76  currentNode(&node)
77  {
78  }
79 
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 
105  {
106  Node* node = currentNode;
107  while (decrement > 0)
108  {
109  node = node->prev;
110  --decrement;
111  };
112  return XalanListIteratorBase(*node);
113  }
114 
116  {
117  return currentNode->value;
118  }
119 
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;
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 
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,
200 
201  typedef XALAN_STD_QUALIFIER reverse_iterator<
203  iterator_category,
205 #else
206  typedef XALAN_STD_QUALIFIER reverse_iterator<
207  iterator,
209 
210  typedef XALAN_STD_QUALIFIER reverse_iterator<
212  value_type,
214 #endif
215 
218 
220 
222  MemoryManager& theManager) :
223  m_memoryManager(&theManager),
224  m_listHead(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 
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 
274  begin() const
275  {
276  return const_iterator(*(getListHead().next));
277  }
278 
279  iterator
280  end()
281  {
282  return iterator(getListHead());
283  }
284 
286  end() const
287  {
288  return const_iterator(getListHead());
289  }
290 
293  {
294  return reverse_iterator(end());
295  }
296 
298  rbegin() const
299  {
300  return const_reverse_iterator(end());
301  }
302 
305  {
306  return reverse_iterator(begin());
307  }
308 
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
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)
455  ::swap(m_listHead, theRHS.m_listHead);
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  {
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);
520  }
521 
522  return *m_listHead;
523  }
524 
525  Node& getListHead() const
526  {
527  return const_cast<XalanList*>(this)->getListHead();
528  }
529 
530  Node*
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
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

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