1 // Copyright (c) 2001 Daniel C. Nuffer 2 // Copyright (c) 2001-2011 Hartmut Kaiser 3 // 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) 6 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 9 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> 13 #include <vector> 14 15 namespace boost { namespace spirit { namespace iterator_policies 16 { 17 /////////////////////////////////////////////////////////////////////////// 18 // class split_std_deque 19 // 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. 24 // 25 /////////////////////////////////////////////////////////////////////////// 26 struct split_std_deque 27 { 28 enum { threshold = 16 }; 29 30 /////////////////////////////////////////////////////////////////////// 31 template <typename Value> 32 class unique //: public detail::default_storage_policy 33 { 34 private: 35 typedef std::vector<Value> queue_type; 36 37 protected: unique()38 unique() : queued_position(0) {} 39 unique(unique const & x)40 unique(unique const& x) 41 : queued_position(x.queued_position) {} 42 swap(unique & x)43 void swap(unique& x) 44 { 45 boost::swap(queued_position, x.queued_position); 46 } 47 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 dereference(MultiPass const & mp)53 dereference(MultiPass const& mp) 54 { 55 queue_type& queue = mp.shared()->queued_elements; 56 typename queue_type::size_type size = queue.size(); 57 58 BOOST_ASSERT(mp.queued_position <= size); 59 60 if (mp.queued_position == size) 61 { 62 // check if this is the only iterator 63 if (size >= threshold && MultiPass::is_unique(mp)) 64 { 65 // free up the memory used by the queue. 66 queue.clear(); 67 mp.queued_position = 0; 68 } 69 return MultiPass::get_input(mp); 70 } 71 72 return queue[mp.queued_position]; 73 } 74 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> increment(MultiPass & mp)79 static void increment(MultiPass& mp) 80 { 81 queue_type& queue = mp.shared()->queued_elements; 82 typename queue_type::size_type size = queue.size(); 83 84 BOOST_ASSERT(mp.queued_position <= size); 85 86 // // do not increment iterator as long as the current token is 87 // // invalid 88 // if (size > 0 && !MultiPass::input_is_valid(mp, queue[mp.queued_position-1])) 89 // return; 90 91 if (mp.queued_position == size) 92 { 93 // check if this is the only iterator 94 if (size >= threshold && MultiPass::is_unique(mp)) 95 { 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 99 queue.clear(); 100 mp.queued_position = 0; 101 } 102 else 103 { 104 queue.push_back(MultiPass::get_input(mp)); 105 ++mp.queued_position; 106 } 107 MultiPass::advance_input(mp); 108 } 109 else 110 { 111 ++mp.queued_position; 112 } 113 } 114 115 // called to forcibly clear the queue 116 template <typename MultiPass> clear_queue(MultiPass & mp)117 static void clear_queue(MultiPass& mp) 118 { 119 mp.shared()->queued_elements.clear(); 120 mp.queued_position = 0; 121 } 122 123 // called to determine whether the iterator is an eof iterator 124 template <typename MultiPass> is_eof(MultiPass const & mp)125 static bool is_eof(MultiPass const& mp) 126 { 127 return mp.queued_position == mp.shared()->queued_elements.size() 128 && MultiPass::input_at_eof(mp); 129 } 130 131 // called by operator== 132 template <typename MultiPass> equal_to(MultiPass const & mp,MultiPass const & x)133 static bool equal_to(MultiPass const& mp, MultiPass const& x) 134 { 135 return mp.queued_position == x.queued_position; 136 } 137 138 // called by operator< 139 template <typename MultiPass> less_than(MultiPass const & mp,MultiPass const & x)140 static bool less_than(MultiPass const& mp, MultiPass const& x) 141 { 142 return mp.queued_position < x.queued_position; 143 } 144 145 template <typename MultiPass> destroy(MultiPass &)146 static void destroy(MultiPass&) {} 147 148 protected: 149 mutable typename queue_type::size_type queued_position; 150 }; 151 152 /////////////////////////////////////////////////////////////////////// 153 template <typename Value> 154 struct shared 155 { sharedboost::spirit::iterator_policies::split_std_deque::shared156 shared() 157 { 158 queued_elements.reserve(threshold); 159 } 160 161 typedef std::vector<Value> queue_type; 162 queue_type queued_elements; 163 }; 164 165 }; // split_std_deque 166 167 }}} 168 169 #endif 170 171