Line data    Source code

       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:
      38           0 :             unique() : queued_position(0) {}
      39             : 
      40           0 :             unique(unique const& x)
      41           0 :               : queued_position(x.queued_position) {}
      42             : 
      43           0 :             void swap(unique& x)
      44             :             {
      45           0 :                 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 
      53           0 :             dereference(MultiPass const& mp)
      54             :             {
      55           0 :                 queue_type& queue = mp.shared()->queued_elements;
      56           0 :                 typename queue_type::size_type size = queue.size();
      57             : 
      58           0 :                 BOOST_ASSERT(mp.queued_position <= size);
      59             : 
      60           0 :                 if (mp.queued_position == size)
      61             :                 {
      62             :                     // check if this is the only iterator
      63           0 :                     if (size >= threshold && MultiPass::is_unique(mp))
      64             :                     {
      65             :                         // free up the memory used by the queue.
      66           0 :                         queue.clear();
      67           0 :                         mp.queued_position = 0;
      68             :                     }
      69           0 :                     return MultiPass::get_input(mp);
      70             :                 }
      71             : 
      72           0 :                 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>
      79           0 :             static void increment(MultiPass& mp)
      80             :             {
      81           0 :                 queue_type& queue = mp.shared()->queued_elements;
      82           0 :                 typename queue_type::size_type size = queue.size();
      83             : 
      84           0 :                 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           0 :                 if (mp.queued_position == size)
      92             :                 {
      93             :                     // check if this is the only iterator
      94           0 :                     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           0 :                         queue.clear();
     100           0 :                         mp.queued_position = 0;
     101             :                     }
     102             :                     else
     103             :                     {
     104           0 :                         queue.push_back(MultiPass::get_input(mp));
     105           0 :                         ++mp.queued_position;
     106             :                     }
     107           0 :                     MultiPass::advance_input(mp);
     108             :                 }
     109             :                 else
     110             :                 {
     111           0 :                     ++mp.queued_position;
     112             :                 }
     113           0 :             }
     114             : 
     115             :             // called to forcibly clear the queue
     116             :             template <typename MultiPass>
     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>
     125           0 :             static bool is_eof(MultiPass const& mp)
     126             :             {
     127           0 :                 return mp.queued_position == mp.shared()->queued_elements.size() 
     128           0 :                     && MultiPass::input_at_eof(mp);
     129             :             }
     130             : 
     131             :             // called by operator==
     132             :             template <typename MultiPass>
     133           0 :             static bool equal_to(MultiPass const& mp, MultiPass const& x) 
     134             :             {
     135           0 :                 return mp.queued_position == x.queued_position;
     136             :             }
     137             : 
     138             :             // called by operator<
     139             :             template <typename MultiPass>
     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>
     146           0 :             static void destroy(MultiPass&) {}
     147             : 
     148             :         protected:
     149             :             mutable typename queue_type::size_type queued_position;
     150             :         }; 
     151             : 
     152             :         ///////////////////////////////////////////////////////////////////////
     153             :         template <typename Value>
     154           0 :         struct shared
     155             :         {
     156           0 :             shared() 
     157           0 :             {
     158           0 :                 queued_elements.reserve(threshold); 
     159           0 :             }
     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             :