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_FIXED_SIZE_QUEUE_POLICY_MAR_16_2007_1134AM) 8 #define BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_POLICY_MAR_16_2007_1134AM 9 10 #include <boost/spirit/home/support/iterators/detail/multi_pass.hpp> 11 #include <boost/spirit/home/support/iterators/detail/fixed_size_queue.hpp> 12 #include <boost/assert.hpp> 13 #include <cstdlib> 14 15 namespace boost { namespace spirit { namespace iterator_policies 16 { 17 /////////////////////////////////////////////////////////////////////////// 18 // class fixed_size_queue 19 // Implementation of the StoragePolicy used by multi_pass 20 // fixed_size_queue keeps a circular buffer (implemented by 21 // boost::spirit::fixed_size_queue class) that is size N+1 and stores N 22 // elements. 23 // 24 // It is up to the user to ensure that there is enough look ahead for 25 // their grammar. Currently there is no way to tell if an iterator is 26 // pointing to forgotten data. The leading iterator will put an item in 27 // the queue and remove one when it is incremented. No dynamic allocation 28 // is done, except on creation of the queue (fixed_size_queue constructor). 29 /////////////////////////////////////////////////////////////////////////// 30 template <std::size_t N> 31 struct fixed_size_queue 32 { 33 /////////////////////////////////////////////////////////////////////// 34 template <typename Value> 35 class unique : public detail::default_storage_policy 36 { 37 private: 38 typedef detail::fixed_size_queue<Value, N> queue_type; 39 40 protected: unique()41 unique() {} 42 unique(unique const & x)43 unique(unique const& x) 44 : queued_position(x.queued_position) {} 45 swap(unique & x)46 void swap(unique& x) 47 { 48 boost::swap(queued_position, x.queued_position); 49 } 50 51 // This is called when the iterator is dereferenced. It's a 52 // template method so we can recover the type of the multi_pass 53 // iterator and access the m_input data member. 54 template <typename MultiPass> 55 static typename MultiPass::reference dereference(MultiPass const & mp)56 dereference(MultiPass const& mp) 57 { 58 if (!mp.queued_position.get_position().is_initialized()) 59 mp.queued_position.get_position().set_queue(&mp.shared()->queued_elements); 60 61 if (mp.queued_position == mp.shared()->queued_elements.end()) 62 return MultiPass::get_input(mp); 63 64 return *mp.queued_position; 65 } 66 67 // This is called when the iterator is incremented. It's a 68 // template method so we can recover the type of the multi_pass 69 // iterator and access the m_input data member. 70 template <typename MultiPass> increment(MultiPass & mp)71 static void increment(MultiPass& mp) 72 { 73 if (!mp.queued_position.get_position().is_initialized()) 74 mp.queued_position.get_position().set_queue(&mp.shared()->queued_elements); 75 76 if (mp.queued_position == mp.shared()->queued_elements.end()) 77 { 78 // don't let the queue get larger than N 79 if (mp.shared()->queued_elements.size() >= N) 80 mp.shared()->queued_elements.pop_front(); 81 82 mp.shared()->queued_elements.push_back( 83 MultiPass::get_input(mp)); 84 MultiPass::advance_input(mp); 85 } 86 ++mp.queued_position; 87 } 88 89 // clear_queue is a no-op 90 91 // called to determine whether the iterator is an eof iterator 92 template <typename MultiPass> is_eof(MultiPass const & mp)93 static bool is_eof(MultiPass const& mp) 94 { 95 return mp.queued_position == mp.shared()->queued_elements.end() && 96 MultiPass::input_at_eof(mp); 97 } 98 99 // called by operator== 100 template <typename MultiPass> equal_to(MultiPass const & mp,MultiPass const & x)101 static bool equal_to(MultiPass const& mp, MultiPass const& x) 102 { 103 return mp.queued_position == x.queued_position; 104 } 105 106 // called by operator< 107 template <typename MultiPass> less_than(MultiPass const & mp,MultiPass const & x)108 static bool less_than(MultiPass const& mp, MultiPass const& x) 109 { 110 return mp.queued_position < x.queued_position; 111 } 112 113 protected: 114 mutable typename queue_type::iterator queued_position; 115 }; 116 117 /////////////////////////////////////////////////////////////////////// 118 template <typename Value> 119 struct shared 120 { 121 typedef detail::fixed_size_queue<Value, N> queue_type; 122 queue_type queued_elements; 123 }; 124 }; 125 126 }}} 127 128 #endif 129