Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.11


XalanDeque.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(XALANDEQUE_HEADER_GUARD_1357924680)
20 #define XALANDEQUE_HEADER_GUARD_1357924680
21 
22 
23 
24 // Base include file. Must be first.
26 
27 
28 
31 
32 
33 
34 XALAN_CPP_NAMESPACE_BEGIN
35 
36 
37 
38 template <class Value>
40 {
41  typedef Value value_type;
42  typedef Value& reference;
43  typedef Value* pointer;
44  typedef const Value& const_reference;
45 };
46 
47 template <class Value>
49 {
50  typedef Value value_type;
51  typedef const Value& reference;
52  typedef const Value* pointer;
53  typedef const Value& const_reference;
54 };
55 
56 template <class Traits, class XalanDeque>
58 {
59 public:
60 
61  typedef size_t size_type;
62  typedef typename Traits::value_type value_type;
63  typedef typename Traits::reference reference;
64  typedef typename Traits::pointer pointer;
65  typedef typename Traits::const_reference const_reference;
66  typedef ptrdiff_t difference_type;
67 
68  typedef XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category;
69 
70  // The non-const iterator type. In the case of the non-const instatiation, this
71  // is the same type.
73 
74  // The const version needs access to our private data members for copy construction and
75  // assignment. For the const instantiation, this is a superfluous friend declaration,
76  // since it's the same type as the class itself.
78 
80  XalanDeque* deque,
81  size_type pos) :
82  m_deque(deque),
83  m_pos(pos)
84  {
85  }
86 
87  // This is standard copy-construction for the non-const iterator type. For the
88  // const iterator type, this is copy construction from the non-const type, and the
89  // compiler will generate the standard copy constructor.
90  XalanDequeIterator(const Iterator& iterator) :
91  m_deque(iterator.m_deque),
92  m_pos(iterator.m_pos)
93  {
94  }
95 
96  // This is the standard assignment operator for the non-const iterator type.
97  // For the const iterator type, this is the assignment operator from the
98  // non-const type, and the compiler will generate the standard assignment
99  // operator.
101  operator=(const Iterator& iterator)
102  {
103  m_deque = iterator.m_deque;
104  m_pos = iterator.m_pos;
105 
106  return *this;
107  }
108 
111  {
112  ++m_pos;
113 
114  return *this;
115  }
116 
119  {
120  XalanDequeIterator temp = *this;
121  ++m_pos;
122 
123  return temp;
124  }
125 
128  {
129  --m_pos;
130 
131  return *this;
132  }
133 
134  pointer
136  {
137  return &(*m_deque[m_pos]);
138  }
139 
140  reference
142  {
143  return (*m_deque)[m_pos];
144  }
145 
146  const_reference
147  operator*() const
148  {
149  return (*m_deque)[m_pos];
150  }
151 
153  operator+(difference_type difference) const
154  {
155  return XalanDequeIterator(m_deque, m_pos + difference);
156  }
157 
159  operator-(difference_type difference) const
160  {
161  return XalanDequeIterator(m_deque, m_pos - difference);
162  }
163 
164  difference_type
165  operator-(const XalanDequeIterator& theRHS) const
166  {
167  return m_pos - theRHS.m_pos;
168  }
169 
170  bool
171  operator==(const XalanDequeIterator& theRHS) const
172  {
173  return theRHS.m_deque == m_deque &&
174  theRHS.m_pos == m_pos;
175  }
176 
177  bool
178  operator!=(const XalanDequeIterator& theRHS) const
179  {
180  return !(theRHS == *this);
181  }
182 
183  bool
184  operator<(const XalanDequeIterator& theRHS) const
185  {
186  return m_pos < theRHS.m_pos;
187  }
188 
189 private:
190 
191  XalanDeque* m_deque;
192 
193  size_type m_pos;
194 };
195 
196 /**
197  * Xalan implementation of deque
198  */
199 template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> >
201 {
202 public:
203 
204  typedef size_t size_type;
205 
206  typedef Type value_type;
207  typedef Type& reference;
208  typedef const Type& const_reference;
209 
212 
214 
217 
218 #if defined(XALAN_HAS_STD_ITERATORS)
219  typedef XALAN_STD_QUALIFIER reverse_iterator<iterator> reverse_iterator_;
220  typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator> const_reverse_iterator_;
221 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
222  typedef typename iterator::iterator_category iterator_category;
223 
224  // This is a specific case for the Rogue Wave STL on Solaris.
225  typedef XALAN_STD_QUALIFIER reverse_iterator<
226  iterator,
227  iterator_category,
228  value_type> reverse_iterator_;
229 
230  typedef XALAN_STD_QUALIFIER reverse_iterator<
231  const_iterator,
232  iterator_category,
233  const value_type> const_reverse_iterator_;
234 #else
235  typedef XALAN_STD_QUALIFIER reverse_iterator<
236  iterator,
237  value_type> reverse_iterator_;
238 
239  typedef XALAN_STD_QUALIFIER reverse_iterator<
240  const_iterator,
241  value_type,
242  const_reference> const_reverse_iterator_;
243 #endif
244 
245  typedef reverse_iterator_ reverse_iterator;
246  typedef const_reverse_iterator_ const_reverse_iterator;
247 
248  typedef typename ConstructionTraits::Constructor Constructor;
249  typedef typename Constructor::ConstructableType ConstructableType;
250 
252  MemoryManager& memoryManager,
253  size_type initialSize = 0,
254  size_type blockSize = 10) :
255  m_memoryManager(&memoryManager),
256  m_blockSize(blockSize),
257  m_blockIndex(memoryManager,
258  initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)),
259  m_freeBlockVector(memoryManager)
260  {
261  const ConstructableType defaultValue(*m_memoryManager);
262 
263  XALAN_USING_STD(fill_n)
264  XALAN_USING_STD(back_inserter)
265 
266  fill_n(
267  back_inserter(*this),
268  initialSize,
269  defaultValue.value);
270  }
271 
273  const XalanDeque& theRHS,
274  MemoryManager& theMemoryManager) :
275  m_memoryManager(&theMemoryManager),
276  m_blockSize(theRHS.m_blockSize),
277  m_blockIndex(*theRHS.m_memoryManager,
278  theRHS.size() / theRHS.m_blockSize + (theRHS.size() % theRHS.m_blockSize == 0 ? 0 : 1)),
279  m_freeBlockVector(theMemoryManager)
280  {
281  XALAN_USING_STD(copy)
282  XALAN_USING_STD(back_inserter)
283 
284  copy(
285  theRHS.begin(),
286  theRHS.end(),
287  back_inserter(*this));
288  }
289 
290  static XalanDeque*
292  MemoryManager& theManager,
293  size_type initialSize = 0,
294  size_type blockSize = 10)
295  {
296  XalanAllocationGuard theGuard(theManager, theManager.allocate(sizeof(ThisType)));
297 
298  ThisType* const theResult =
299  new (theGuard.get()) ThisType(theManager, initialSize, blockSize);
300 
301  theGuard.release();
302 
303  return theResult;
304  }
305 
307  {
308  destroyBlockList(m_freeBlockVector);
309 
310  destroyBlockList(m_blockIndex);
311  }
312 
313  iterator
315  {
316  return iterator(this, 0);
317  }
318 
319  const_iterator
320  begin() const
321  {
322  return const_iterator(const_cast<XalanDeque*>(this), 0);
323  }
324 
325  iterator
326  end()
327  {
328  return iterator(this, size());
329  }
330 
331  const_iterator
332  end() const
333  {
334  return const_iterator(const_cast<XalanDeque*>(this), size());
335  }
336 
337  const_reverse_iterator
338  rbegin() const
339  {
340  return const_reverse_iterator(end());
341  }
342 
343  const_reverse_iterator
344  rend() const
345  {
346  return const_reverse_iterator(begin());
347  }
348 
349  bool
350  empty() const
351  {
352  return m_blockIndex.empty();
353  }
354 
355  size_type
356  size() const
357  {
358  if (m_blockIndex.empty())
359  {
360  return 0;
361  }
362  else
363  {
364  return (m_blockIndex.size() - 1) * m_blockSize
365  + m_blockIndex.back()->size();
366  }
367  }
368 
369  value_type&
371  {
372  return m_blockIndex.back()->back();
373  }
374 
375  value_type&
376  operator[](size_type index)
377  {
378  BlockType& block = *m_blockIndex[index / m_blockSize];
379 
380  return block[index % m_blockSize];
381  }
382 
383  const value_type&
384  operator[](size_type index) const
385  {
386  BlockType& block = *m_blockIndex[index / m_blockSize];
387 
388  return block[index % m_blockSize];
389  }
390 
391  void
393  {
394  typename BlockIndexType::iterator iter = m_blockIndex.begin();
395 
396  m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size());
397 
398  while (iter != m_blockIndex.end())
399  {
400  (*iter)->clear();
401  m_freeBlockVector.push_back(*iter);
402  ++iter;
403  }
404 
405  m_blockIndex.clear();
406  }
407 
408  void
409  push_back(const value_type& value)
410  {
411  if (m_blockIndex.empty() ||
412  m_blockIndex.back()->size() >= m_blockSize)
413  {
414  pushNewIndexBlock();
415  }
416 
417  m_blockIndex.back()->push_back(value);
418  }
419 
420  void
422  {
423  assert(!empty());
424 
425  BlockType& lastBlock = *m_blockIndex.back();
426  lastBlock.pop_back();
427 
428  if (lastBlock.empty())
429  {
430  m_freeBlockVector.push_back(&lastBlock);
431  m_blockIndex.pop_back();
432  }
433  }
434 
435  void
436  resize(size_type newSize)
437  {
438  const ConstructableType defaultValue(*m_memoryManager);
439 
440  if (newSize > size())
441  {
442  for (size_type i = 0; i < newSize - size(); ++i)
443  {
444  push_back(defaultValue.value);
445  }
446  }
447  else
448  {
449  for (size_type i = 0; i < size() - newSize; ++i)
450  {
451  pop_back();
452  }
453  }
454  }
455 
456  void
457  swap(XalanDeque& theRHS)
458  {
459  MemoryManager* const temp = m_memoryManager;
460  m_memoryManager = theRHS.m_memoryManager;
461  theRHS.m_memoryManager = temp;
462 
463  theRHS.m_blockIndex.swap(m_blockIndex);
464  theRHS.m_freeBlockVector.swap(m_freeBlockVector);
465  }
466 
467  XalanDeque&
468  operator=(const XalanDeque& theRHS)
469  {
470  if (this != &theRHS)
471  {
472  XALAN_USING_STD(copy)
473  XALAN_USING_STD(back_inserter)
474 
475  clear();
476 
477  copy(
478  theRHS.begin(),
479  theRHS.end(),
480  back_inserter(*this));
481  }
482 
483  return *this;
484  }
485 
486  MemoryManager&
488  {
489  assert (m_memoryManager != 0);
490 
491  return *m_memoryManager;
492  }
493 
494 private:
495 
496  void
497  pushNewIndexBlock()
498  {
499  // Allocate space first, so we don't have to worry
500  // about an out-of-memory error once we've constructed
501  // the new block.
502  m_blockIndex.push_back(0);
503 
504  if (m_freeBlockVector.empty())
505  {
507  *m_memoryManager,
508  m_blockIndex.back(),
509  *m_memoryManager,
510  m_blockSize);
511  }
512  else
513  {
514  m_blockIndex.back() = m_freeBlockVector.back();
515 
516  // Now that ownership has been transfered, pop
517  // it off the free list.
518  m_freeBlockVector.pop_back();
519  }
520 
521  assert(m_blockIndex.back() != 0);
522  }
523 
524  void
525  destroyBlockList(BlockIndexType& theBlockIndex)
526  {
527  typename BlockIndexType::iterator iter =
528  theBlockIndex.begin();
529 
530  while (iter != theBlockIndex.end())
531  {
532  // Normally, we should be able to just call
533  // the version of XalanDestroy() that accepts
534  // a pointer, but Visual Studio 6 has issues
535  // with partial ordering, so we're stuck with
536  // this for now.
537  if (*iter != 0)
538  {
539  XalanDestroy(*m_memoryManager, **iter);
540  }
541 
542  ++iter;
543  }
544  }
545 
546  MemoryManager* m_memoryManager;
547 
548  const size_type m_blockSize;
549 
550  BlockIndexType m_blockIndex;
551  BlockIndexType m_freeBlockVector;
552 
553 
554  // These are not implemented
555  XalanDeque();
556 
557  XalanDeque(const XalanDeque&);
558 };
559 
560 
561 
562 XALAN_CPP_NAMESPACE_END
563 
564 
565 
566 #endif // XALANDEQUE_HEADER_GUARD_1357924680
567 
bool operator!=(const XalanDequeIterator &theRHS) const
Definition: XalanDeque.hpp:178
XalanVector< BlockType * > BlockIndexType
Definition: XalanDeque.hpp:211
XalanDequeIterator(const Iterator &iterator)
Definition: XalanDeque.hpp:90
Traits::pointer pointer
Definition: XalanDeque.hpp:64
XalanDeque(MemoryManager &memoryManager, size_type initialSize=0, size_type blockSize=10)
Definition: XalanDeque.hpp:251
XalanDequeIterator< XalanDequeIteratorTraits< value_type >, XalanDeque > Iterator
Definition: XalanDeque.hpp:72
iterator end()
bool empty() const
Definition: XalanDeque.hpp:350
size_type size() const
Definition: XalanDeque.hpp:356
XalanDequeIterator operator+(difference_type difference) const
Definition: XalanDeque.hpp:153
XalanDequeIterator operator-(difference_type difference) const
Definition: XalanDeque.hpp:159
value_type & back()
Definition: XalanDeque.hpp:370
XalanDequeIterator & operator--()
Definition: XalanDeque.hpp:127
const_reverse_iterator rbegin() const
Definition: XalanDeque.hpp:338
void resize(size_type newSize)
Definition: XalanDeque.hpp:436
Traits::const_reference const_reference
Definition: XalanDeque.hpp:65
XalanDequeIterator< XalanDequeConstIteratorTraits< value_type >, ThisType > const_iterator
Definition: XalanDeque.hpp:216
Traits::value_type value_type
Definition: XalanDeque.hpp:62
XalanDeque & operator=(const XalanDeque &theRHS)
Definition: XalanDeque.hpp:468
XalanDequeIterator operator++(int)
Definition: XalanDeque.hpp:118
void push_back(const value_type &value)
Definition: XalanDeque.hpp:409
bool operator==(const XalanDequeIterator &theRHS) const
Definition: XalanDeque.hpp:171
void clear(XalanDOMString &theString)
Remove all elements from target string.
difference_type operator-(const XalanDequeIterator &theRHS) const
Definition: XalanDeque.hpp:165
void pop_back()
static XalanDeque * create(MemoryManager &theManager, size_type initialSize=0, size_type blockSize=10)
Definition: XalanDeque.hpp:291
Type & reference
Definition: XalanDeque.hpp:207
XalanVector< Type, ConstructionTraits > BlockType
Definition: XalanDeque.hpp:210
XalanDequeIterator & operator=(const Iterator &iterator)
Definition: XalanDeque.hpp:101
value_type & operator[](size_type index)
Definition: XalanDeque.hpp:376
const value_type & operator[](size_type index) const
Definition: XalanDeque.hpp:384
iterator begin()
size_t size_type
Definition: XalanDeque.hpp:204
ptrdiff_t difference_type
Definition: XalanDeque.hpp:66
const Value & const_reference
Definition: XalanDeque.hpp:44
Traits::reference reference
Definition: XalanDeque.hpp:63
const Type & const_reference
Definition: XalanDeque.hpp:208
XalanDeque< Type, ConstructionTraits > ThisType
Definition: XalanDeque.hpp:213
const_iterator end() const
Definition: XalanDeque.hpp:332
bool empty() const
void XalanDestroy(Type &theArg)
const_reverse_iterator_ const_reverse_iterator
Definition: XalanDeque.hpp:246
XALAN_STD_QUALIFIER reverse_iterator< const_iterator, value_type, const_reference > const_reverse_iterator_
Definition: XalanDeque.hpp:242
pointer operator->()
Definition: XalanDeque.hpp:135
XALAN_STD_QUALIFIER reverse_iterator< iterator, value_type > reverse_iterator_
Definition: XalanDeque.hpp:237
bool operator<(const ElemAttributeSet &theLHS, const ElemAttributeSet &theRHS)
void swap(XalanDeque &theRHS)
Definition: XalanDeque.hpp:457
XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category
Definition: XalanDeque.hpp:68
reference operator*()
Definition: XalanDeque.hpp:141
void clear()
Definition: XalanDeque.hpp:392
XalanDequeIterator< XalanDequeIteratorTraits< value_type >, ThisType > iterator
Definition: XalanDeque.hpp:215
MemoryManager & getMemoryManager()
Definition: XalanDeque.hpp:487
XalanDeque(const XalanDeque &theRHS, MemoryManager &theMemoryManager)
Definition: XalanDeque.hpp:272
XalanDequeIterator(XalanDeque *deque, size_type pos)
Definition: XalanDeque.hpp:79
void swap(ThisType &theOther)
XalanDequeIterator & operator++()
Definition: XalanDeque.hpp:110
Type value_type
Definition: XalanDeque.hpp:206
ConstructionTraits::Constructor Constructor
Definition: XalanDeque.hpp:248
iterator end()
Definition: XalanDeque.hpp:326
Type * XalanConstruct(MemoryManager &theMemoryManager, Type *&theInstance)
const_iterator begin() const
Definition: XalanDeque.hpp:320
void pop_back()
Definition: XalanDeque.hpp:421
Constructor::ConstructableType ConstructableType
Definition: XalanDeque.hpp:249
iterator begin()
Definition: XalanDeque.hpp:314
const_reference operator*() const
Definition: XalanDeque.hpp:147
Xalan implementation of deque.
Definition: XalanDeque.hpp:200
const_reverse_iterator rend() const
Definition: XalanDeque.hpp:344

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