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{
49 typedef Value value_type;
50 typedef Value& reference;
51 typedef Value* pointer;
52};
53
54template <class Value>
56{
57 typedef Value value_type;
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
69 typedef ptrdiff_t difference_type;
70
71 typedef std::bidirectional_iterator_tag iterator_category;
72
74
77 {
78 }
79
82 {
83 }
84
86 {
88 return *this;
89 }
90
92 {
93 Node& origNode = *currentNode;
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 };
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
147};
148
149
150
151/**
152 * Xalan implementation of a doubly linked list
153 */
154template <class Type>
156{
157public:
158
159
160 typedef Type value_type;
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),
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
216 while (freeNode != 0)
217 {
218 Node * nextNode = freeNode->next;
220 freeNode = nextNode;
221 }
222
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 {
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
361 iterator pos,
362#if defined(NDEBUG)
363 ThisType& /* list */,
364#else
365 ThisType& list,
366#endif
367 iterator toInsert)
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
389 iterator pos,
390#if defined(NDEBUG)
391 ThisType& /* list */,
392#else
393 ThisType& list,
394#endif
395 iterator toInsertFirst,
396 iterator toInsertLast)
397 {
398 assert(m_memoryManager == list.m_memoryManager);
399
400 if (toInsertFirst != toInsertLast)
401 {
402 Node & posNode = pos.node();
403 Node & toInsertFirstNode = toInsertFirst.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;
410 toInsertLastNode.next = &posNode;
411
412 posNode.prev->next = &toInsertFirstNode;
413 posNode.prev = &toInsertLastNode;
414 }
415 }
416
417 void
419 {
420 iterator pos = begin();
421 while (pos != end())
422 {
423 freeNode(pos++.node());
424 }
425 }
426
427 void swap(ThisType& theRHS)
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
437 Node& constructNode(const value_type& data, iterator pos)
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 {
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
495 Node& getListHead() const
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
std::reverse_iterator< iterator > reverse_iterator_
XalanListIteratorBase< XalanListConstIteratorTraits< value_type >, Node > const_iterator
XalanListIteratorBase< XalanListIteratorTraits< value_type >, Node > iterator
reference back()
const_reverse_iterator rbegin() const
size_type size() const
bool empty() const
const_reverse_iterator rend() const
reference front()
void push_back(const value_type &data)
void splice(iterator pos, ThisType &list, iterator toInsertFirst, iterator toInsertLast)
reverse_iterator rbegin()
const_iterator end() const
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)
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
size_t size_type
Definition XalanMap.hpp:46
static C * construct(C *address, MemoryManager &)
ConstructWithNoMemoryManager< C > Constructor
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)
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)