Xalan-C++ API Reference 1.12.0
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
42namespace XALAN_CPP_NAMESPACE {
43
44
45
46template <class Value>
48{
50 typedef Value& reference;
51 typedef Value* pointer;
52};
53
54template <class Value>
56{
58 typedef const Value& reference;
59 typedef const Value* pointer;
60};
61
62template<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
70
71 typedef std::bidirectional_iterator_tag iterator_category;
72
74
75 XalanListIteratorBase(Node& node) :
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;
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
132 {
133 return !operator==(theRhs);
134 }
135
137 {
138 return currentNode == theRhs.currentNode;
139 }
140
141 Node& node()
142 {
143 return *currentNode;
144 }
145
147};
148
149
150
151/**
152 * Xalan implementation of a doubly linked list
153 */
154template <class Type>
156{
157public:
158
159
162 typedef const value_type* const_pointer;
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 typedef std::reverse_iterator<iterator> reverse_iterator_;
190 typedef std::reverse_iterator<const_iterator> const_reverse_iterator_;
191
194
196
198 MemoryManager& theManager) :
199 m_memoryManager(&theManager),
200 m_listHead(0),
201 m_freeListHeadPtr(0)
202 {
203 }
204
206 {
207 if (m_listHead != 0)
208 {
209 iterator pos = begin();
210 while (pos != end())
211 {
212 destroyNode(pos++.node());
213 }
214
215 Node * freeNode = m_freeListHeadPtr;
216 while (freeNode != 0)
217 {
218 Node * nextNode = freeNode->next;
219 deallocate(freeNode);
220 freeNode = nextNode;
221 }
222
223 deallocate(m_listHead);
224 }
225 }
226
227 MemoryManager&
229 {
230 assert(m_memoryManager != 0 );
231
232 return *m_memoryManager;
233 }
234
235 const MemoryManager&
237 {
238 assert(m_memoryManager != 0 );
239
240 return *m_memoryManager;
241 }
242
243 iterator
245 {
246 return iterator(*(getListHead().next));
247 }
248
249 const_iterator
250 begin() const
251 {
252 return const_iterator(*(getListHead().next));
253 }
254
255 iterator
257 {
258 return iterator(getListHead());
259 }
260
261 const_iterator
262 end() const
263 {
264 return const_iterator(getListHead());
265 }
266
267 reverse_iterator
269 {
270 return reverse_iterator(end());
271 }
272
273 const_reverse_iterator
274 rbegin() const
275 {
276 return const_reverse_iterator(end());
277 }
278
279 reverse_iterator
281 {
282 return reverse_iterator(begin());
283 }
284
285 const_reverse_iterator
286 rend() const
287 {
288 return const_reverse_iterator(begin());
289 }
290
291 reference
293 {
294 return *begin();
295 }
296
297 reference
299 {
300 return *(--end());
301 }
302
304 size() const
305 {
306 size_type size = 0;
307 const_iterator item = begin();
308 while (item != end())
309 {
310 ++size;
311 ++item;
312 }
313 return size;
314 }
315
316 bool
317 empty() const
318 {
319 return (begin() == end()) != 0;
320 }
321
322 void
324 {
325 constructNode(data, end());
326 }
327
328 void
330 {
331 constructNode(data, begin());
332 }
333
334 void
336 {
337 erase(begin());
338 }
339
340 void
342 {
343 erase(--end());
344 }
345
346 iterator
347 insert(const iterator& pos, const value_type& value)
348 {
349 return iterator(constructNode(value,pos));
350 }
351
352 void
354 {
355 assert(pos != end());
356 freeNode(pos.node());
357 }
358
359 void
362#if defined(NDEBUG)
363 ThisType& /* list */,
364#else
365 ThisType& list,
366#endif
368 {
369 assert(m_memoryManager == list.m_memoryManager);
370
371 if (pos != toInsert)
372 {
373 Node & posNode = pos.node();
374 Node & toInsertNode = toInsert.node();
375
376 toInsertNode.prev->next = toInsertNode.next;
377 toInsertNode.next->prev = toInsertNode.prev;
378
379 toInsertNode.prev = posNode.prev;
380 toInsertNode.next = &posNode;
381
382 posNode.prev->next = &toInsertNode;
383 posNode.prev = &toInsertNode;
384 }
385 }
386
387 void
390#if defined(NDEBUG)
391 ThisType& /* list */,
392#else
393 ThisType& list,
394#endif
397 {
398 assert(m_memoryManager == list.m_memoryManager);
399
401 {
402 Node & posNode = pos.node();
404 Node & toInsertLastNode = *(toInsertLast.node().prev);
405
406 toInsertFirstNode.prev->next = toInsertLastNode.next;
407 toInsertLastNode.next->prev = toInsertFirstNode.prev;
408
409 toInsertFirstNode.prev = posNode.prev;
411
412 posNode.prev->next = &toInsertFirstNode;
414 }
415 }
416
417 void
419 {
420 iterator pos = begin();
421 while (pos != end())
422 {
423 freeNode(pos++.node());
424 }
425 }
426
428 {
429 std::swap(m_memoryManager, theRHS.m_memoryManager);
430 std::swap(m_listHead, theRHS.m_listHead);
431 std::swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr);
432 }
433
434
435protected:
436
438 {
439 Node * newNode = 0;
440 Node * nextFreeNode = 0;
441
442 if (m_freeListHeadPtr != 0)
443 {
444 newNode = m_freeListHeadPtr;
445 nextFreeNode = m_freeListHeadPtr->next;
446 }
447 else
448 {
449 m_freeListHeadPtr = allocate(1);
450 newNode = m_freeListHeadPtr;
451 }
452
453 Constructor::construct(&newNode->value, data, *m_memoryManager);
454 new (&newNode->prev) Node*(pos.node().prev);
455 new (&newNode->next) Node*(&(pos.node()));
456
457 pos.node().prev->next = newNode;
458 pos.node().prev = newNode;
459
460 m_freeListHeadPtr = nextFreeNode;
461
462 return *newNode;
463 }
464
465 void freeNode(Node& node)
466 {
467 node.prev->next = node.next;
468 node.next->prev = node.prev;
469
470 node.~Node();
471 node.prev = 0;
472 node.next = m_freeListHeadPtr;
473 m_freeListHeadPtr = &node;
474 }
475
476 void destroyNode(Node& node)
477 {
478 assert(&node != m_listHead);
479 node.~Node();
480 deallocate(&node);
481 }
482
484 {
485 if (0 == m_listHead)
486 {
487 m_listHead = allocate(1);
488 m_listHead->next = m_listHead;
489 m_listHead->prev = m_listHead;
490 }
491
492 return *m_listHead;
493 }
494
496 {
497 return const_cast<XalanList*>(this)->getListHead();
498 }
499
500 Node*
502 {
503 const size_type theBytesNeeded = size * sizeof(Node);
504
505 assert(m_memoryManager != 0);
506
507 void* pointer = m_memoryManager->allocate(theBytesNeeded);
508
509 assert( pointer != 0 );
510
511 return (Node*) pointer;
512 }
513
514
515 void
517 {
518 assert(m_memoryManager != 0);
519
520 m_memoryManager->deallocate(pointer);
521 }
522
523 MemoryManager * m_memoryManager;
524
526
528
529private:
530 // not defined
531 XalanList();
532 XalanList(const XalanList& theRhs);
533
534 XalanList& operator=(const XalanList& theRhs);
535
536};
537
538
539
540}
541
542#endif // XALANLIST_HEADER_GUARD_1357924680
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
Xalan implementation of a doubly linked list.
void deallocate(Node *pointer)
value_type * pointer
std::reverse_iterator< iterator > reverse_iterator_
XalanListIteratorBase< XalanListConstIteratorTraits< value_type >, Node > const_iterator
XalanListIteratorBase< XalanListIteratorTraits< value_type >, Node > iterator
void freeNode(Node &node)
reference back()
void erase(iterator pos)
const_reverse_iterator rbegin() const
size_type size() const
const value_type * const_pointer
bool empty() const
XalanList< value_type > ThisType
const_reverse_iterator rend() const
reference front()
void push_back(const value_type &data)
value_type & reference
void splice(iterator pos, ThisType &list, iterator toInsertFirst, iterator toInsertLast)
reverse_iterator rbegin()
const_iterator end() const
void destroyNode(Node &node)
const value_type & const_reference
reverse_iterator_ reverse_iterator
const MemoryManager & getMemoryManager() const
std::reverse_iterator< const_iterator > const_reverse_iterator_
void swap(ThisType &theRHS)
const_reverse_iterator_ const_reverse_iterator
Node & constructNode(const value_type &data, iterator pos)
Node & getListHead() const
MemoryManagedConstructionTraits< value_type >::Constructor Constructor
void splice(iterator pos, ThisType &list, iterator toInsert)
MemoryManager * m_memoryManager
Node * allocate(size_type size)
reverse_iterator rend()
XalanList(MemoryManager &theManager)
MemoryManager & getMemoryManager()
void push_front(const value_type &data)
iterator insert(const iterator &pos, const value_type &value)
const_iterator begin() const
void erase(XalanDOMString &theString)
Remove all elements from target string.
size_t size_type
Definition XalanMap.hpp:46
bool operator==(const XalanVector< Type > &theLHS, const XalanVector< Type > &theRHS)
std::bidirectional_iterator_tag iterator_category
Definition XalanList.hpp:71
bool operator!=(const XalanListIteratorBase &theRhs) const
XalanListIteratorBase operator--()
Definition XalanList.hpp:98
XalanListTraits::value_type value_type
Definition XalanList.hpp:65
reference operator*() const
XalanListIteratorBase(const iterator &theRhs)
Definition XalanList.hpp:80
XalanListIteratorBase operator-(difference_type decrement) const
const XalanListIteratorBase & operator=(const XalanListIteratorBase &theRhs)
bool operator==(const XalanListIteratorBase &theRhs) const
XalanListIteratorBase operator++()
Definition XalanList.hpp:85
XalanListIteratorBase< XalanListIteratorTraits< value_type >, Node > iterator
Definition XalanList.hpp:73
XalanListTraits::reference reference
Definition XalanList.hpp:66
XalanListIteratorBase operator++(int)
Definition XalanList.hpp:91
XalanListTraits::pointer pointer
Definition XalanList.hpp:67
Node(const value_type &theValue, Node &prevNode, Node &nextNode)