1 // Copyright (c) 2001 Daniel C. Nuffer
2 // Copyright (c) 2001-2010 Hartmut Kaiser
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 #if !defined(BOOST_SPIRIT_ITERATOR_SPLIT_DEQUE_POLICY_APR_06_2008_0138PM)
8 #define BOOST_SPIRIT_ITERATOR_SPLIT_DEQUE_POLICY_APR_06_2008_0138PM
10 #include <boost/spirit/home/support/iterators/multi_pass_fwd.hpp>
11 #include <boost/spirit/home/support/iterators/detail/multi_pass.hpp>
12 #include <boost/assert.hpp>
15 namespace boost { namespace spirit { namespace iterator_policies
17 ///////////////////////////////////////////////////////////////////////////
18 // class split_std_deque
20 // Implementation of the StoragePolicy used by multi_pass
21 // This stores all data in a std::vector (despite its name), and keeps an
22 // offset to the current position. It stores all the data unless there is
23 // only one iterator using the queue.
25 ///////////////////////////////////////////////////////////////////////////
26 struct split_std_deque
28 enum { threshold = 16 };
30 ///////////////////////////////////////////////////////////////////////
31 template <typename Value>
32 class unique //: public detail::default_storage_policy
35 typedef std::vector<Value> queue_type;
38 unique() : queued_position(0) {}
40 unique(unique const& x)
41 : queued_position(x.queued_position) {}
45 boost::swap(queued_position, x.queued_position);
48 // This is called when the iterator is dereferenced. It's a
49 // template method so we can recover the type of the multi_pass
50 // iterator and call advance_input and input_is_valid.
51 template <typename MultiPass>
52 static typename MultiPass::reference
53 dereference(MultiPass const& mp)
55 queue_type& queue = mp.shared()->queued_elements;
56 typename queue_type::size_type size = queue.size();
58 BOOST_ASSERT(mp.queued_position <= size);
60 if (mp.queued_position == size)
62 // check if this is the only iterator
63 if (size >= threshold && MultiPass::is_unique(mp))
65 // free up the memory used by the queue.
67 mp.queued_position = 0;
69 return MultiPass::get_input(mp);
72 return queue[mp.queued_position];
75 // This is called when the iterator is incremented. It's a template
76 // method so we can recover the type of the multi_pass iterator
77 // and call is_unique and advance_input.
78 template <typename MultiPass>
79 static void increment(MultiPass& mp)
81 queue_type& queue = mp.shared()->queued_elements;
82 typename queue_type::size_type size = queue.size();
84 BOOST_ASSERT(mp.queued_position <= size);
86 // // do not increment iterator as long as the current token is
88 // if (size > 0 && !MultiPass::input_is_valid(mp, queue[mp.queued_position-1]))
91 if (mp.queued_position == size)
93 // check if this is the only iterator
94 if (size >= threshold && MultiPass::is_unique(mp))
96 // free up the memory used by the queue. we avoid
97 // clearing the queue on every increment, though,
98 // because this would be too time consuming
100 mp.queued_position = 0;
104 queue.push_back(MultiPass::get_input(mp));
105 ++mp.queued_position;
107 MultiPass::advance_input(mp);
111 ++mp.queued_position;
115 // called to forcibly clear the queue
116 template <typename MultiPass>
117 static void clear_queue(MultiPass& mp)
119 mp.shared()->queued_elements.clear();
120 mp.queued_position = 0;
123 // called to determine whether the iterator is an eof iterator
124 template <typename MultiPass>
125 static bool is_eof(MultiPass const& mp)
127 return mp.queued_position == mp.shared()->queued_elements.size()
128 && MultiPass::input_at_eof(mp);
131 // called by operator==
132 template <typename MultiPass>
133 static bool equal_to(MultiPass const& mp, MultiPass const& x)
135 return mp.queued_position == x.queued_position;
138 // called by operator<
139 template <typename MultiPass>
140 static bool less_than(MultiPass const& mp, MultiPass const& x)
142 return mp.queued_position < x.queued_position;
145 template <typename MultiPass>
146 static void destroy(MultiPass&) {}
149 mutable typename queue_type::size_type queued_position;
152 ///////////////////////////////////////////////////////////////////////
153 template <typename Value>
158 queued_elements.reserve(threshold);
161 typedef std::vector<Value> queue_type;
162 queue_type queued_elements;
165 }; // split_std_deque
In the beginning the Universe was created. This has made a lot of
people very angry and has been widely regarded as a bad move.
Douglas Adams