ceph/src/boost/boost/compute/algorithm/search.hpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2014 Roshan <thisisroshansmail@gmail.com>
   3 //
   4 // Distributed under the Boost Software License, Version 1.0
   5 // See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt
   7 //
   8 // See http://boostorg.github.com/compute for more information.
   9 //---------------------------------------------------------------------------//
  10
  11 #ifndef BOOST_COMPUTE_ALGORITHM_SEARCH_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_SEARCH_HPP
  13
  14 #include <boost/static_assert.hpp>
  15
  16 #include <boost/compute/algorithm/detail/search_all.hpp>
  17 #include <boost/compute/algorithm/find.hpp>
  18 #include <boost/compute/container/vector.hpp>
  19 #include <boost/compute/detail/iterator_range_size.hpp>
  20 #include <boost/compute/detail/meta_kernel.hpp>
  21 #include <boost/compute/system.hpp>
  22 #include <boost/compute/type_traits/is_device_iterator.hpp>
  23
  24 namespace boost {
  25 namespace compute {
  26
  27 ///
  28 /// \brief Substring matching algorithm
  29 ///
  30 /// Searches for the first match of the pattern [p_first, p_last)
  31 /// in text [t_first, t_last).
  32 /// \return Iterator pointing to beginning of first occurrence
  33 ///
  34 /// \param t_first Iterator pointing to start of text
  35 /// \param t_last Iterator pointing to end of text
  36 /// \param p_first Iterator pointing to start of pattern
  37 /// \param p_last Iterator pointing to end of pattern
  38 /// \param queue Queue on which to execute
  39 ///
  40 /// Space complexity: \Omega(distance(\p t_first, \p t_last))
  41 template<class TextIterator, class PatternIterator>
  42 inline TextIterator search(TextIterator t_first,
  43                            TextIterator t_last,
  44                            PatternIterator p_first,
  45                            PatternIterator p_last,
  46                            command_queue &queue = system::default_queue())
  47 {
  48     BOOST_STATIC_ASSERT(is_device_iterator<TextIterator>::value);
  49     BOOST_STATIC_ASSERT(is_device_iterator<PatternIterator>::value);
  50
  51     // there is no need to check if pattern starts at last n - 1 indices
  52     vector<uint_> matching_indices(
  53         detail::iterator_range_size(t_first, t_last)
  54             - detail::iterator_range_size(p_first, p_last) + 1,
  55         queue.get_context()
  56     );
  57
  58     // search_kernel puts value 1 at every index in vector where pattern starts at
  59     detail::search_kernel<PatternIterator,
  60                           TextIterator,
  61                           vector<uint_>::iterator> kernel;
  62
  63     kernel.set_range(p_first, p_last, t_first, t_last, matching_indices.begin());
  64     kernel.exec(queue);
  65
  66     vector<uint_>::iterator index = ::boost::compute::find(
  67         matching_indices.begin(), matching_indices.end(), uint_(1), queue
  68     );
  69
  70     // pattern was not found
  71     if(index == matching_indices.end())
  72         return t_last;
  73
  74     return t_first + detail::iterator_range_size(matching_indices.begin(), index);
  75 }
  76
  77 } //end compute namespace
  78 } //end boost namespace
  79
  80 #endif // BOOST_COMPUTE_ALGORITHM_SEARCH_HPP