Boost logo

Boost-Commit :

From: droba_at_[hidden]
Date: 2008-06-18 17:54:06


Author: pavol_droba
Date: 2008-06-18 17:54:06 EDT (Wed, 18 Jun 2008)
New Revision: 46496
URL: http://svn.boost.org/trac/boost/changeset/46496

Log:
is_any_ofF performance improvements
tabs removed

Text files modified:
   trunk/boost/algorithm/string/classification.hpp | 4
   trunk/boost/algorithm/string/detail/classification.hpp | 160 ++++++++++++++++++++++++++++++++++++++-
   trunk/boost/algorithm/string/find.hpp | 2
   trunk/boost/algorithm/string/find_format.hpp | 2
   4 files changed, 159 insertions(+), 9 deletions(-)

Modified: trunk/boost/algorithm/string/classification.hpp
==============================================================================
--- trunk/boost/algorithm/string/classification.hpp (original)
+++ trunk/boost/algorithm/string/classification.hpp 2008-06-18 17:54:06 EDT (Wed, 18 Jun 2008)
@@ -202,8 +202,8 @@
             BOOST_STRING_TYPENAME range_value<RangeT>::type>
         is_any_of( const RangeT& Set )
         {
- return detail::is_any_ofF<
- BOOST_STRING_TYPENAME range_value<RangeT>::type>(as_literal(Set));
+ iterator_range<BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type> lit_set(as_literal(Set));
+ return detail::is_any_ofF<BOOST_STRING_TYPENAME range_value<RangeT>::type>(lit_set);
         }
 
         //! is_from_range predicate

Modified: trunk/boost/algorithm/string/detail/classification.hpp
==============================================================================
--- trunk/boost/algorithm/string/detail/classification.hpp (original)
+++ trunk/boost/algorithm/string/detail/classification.hpp 2008-06-18 17:54:06 EDT (Wed, 18 Jun 2008)
@@ -15,7 +15,6 @@
 #include <algorithm>
 #include <functional>
 #include <locale>
-#include <set>
 
 #include <boost/range/begin.hpp>
 #include <boost/range/end.hpp>
@@ -76,27 +75,178 @@
             struct is_any_ofF :
                 public predicate_facade<is_any_ofF<CharT> >
             {
+ private:
+ // set cannot operate on const value-type
+ typedef typename remove_const<CharT>::type set_value_type;
+ // Size of the static storage (size of pointer*2)
+ static const ::std::size_t FIXED_STORAGE_SIZE = sizeof(set_value_type*)*2;
+
+ public:
+ // Boost.Lambda support
+ template <class Args> struct sig { typedef bool type; };
+
+ // Constructor
+ template<typename RangeT>
+ is_any_ofF( const RangeT& Range ) : m_Size(0)
+ {
+ // Prepare storage
+ m_Storage.m_dynSet=0;
+
+ std::size_t Size=::boost::distance(Range);
+ m_Size=Size;
+ set_value_type* Storage=0;
+
+ if(m_Size<=FIXED_STORAGE_SIZE)
+ {
+ // Use fixed storage
+ Storage=&m_Storage.m_fixSet[0];
+ }
+ else
+ {
+ // Use dynamic storage
+ m_Storage.m_dynSet=new set_value_type[m_Size];
+ Storage=m_Storage.m_dynSet;
+ }
+
+ // Use fixed storage
+ ::std::copy(::boost::begin(Range), ::boost::end(Range), Storage);
+ ::std::sort(Storage, Storage+m_Size);
+ }
+
+ // Copy constructor
+ is_any_ofF(const is_any_ofF& Other) : m_Size(Other.m_Size)
+ {
+ // Prepare storage
+ m_Storage.m_dynSet=0;
+ const set_value_type* SrcStorage=0;
+ set_value_type* DestStorage=0;
+
+ if(m_Size<=FIXED_STORAGE_SIZE)
+ {
+ // Use fixed storage
+ DestStorage=&m_Storage.m_fixSet[0];
+ SrcStorage=&Other.m_Storage.m_fixSet[0];
+ }
+ else
+ {
+ // Use dynamic storage
+ m_Storage.m_dynSet=new set_value_type[m_Size];
+ DestStorage=m_Storage.m_dynSet;
+ SrcStorage=Other.m_Storage.m_dynSet;
+ }
+
+ // Use fixed storage
+ ::memcpy(DestStorage, SrcStorage, sizeof(set_value_type)*m_Size);
+ }
+
+ // Destructor
+ ~is_any_ofF()
+ {
+ if(m_Size>FIXED_STORAGE_SIZE && m_Storage.m_dynSet!=0)
+ {
+ delete m_Storage.m_dynSet;
+ }
+ }
+
+ // Assignment
+ is_any_ofF& operator=(const is_any_ofF& Other)
+ {
+ // Prepare storage
+ m_Storage.m_dynSet=0;
+ m_Size=Other.m_Size;
+ const set_value_type* SrcStorage=0;
+ set_value_type* DestStorage=0;
+
+ if(m_Size<=FIXED_STORAGE_SIZE)
+ {
+ // Use fixed storage
+ DestStorage=&m_Storage.m_fixSet[0];
+ SrcStorage=&Other.m_Storage.m_fixSet[0];
+ }
+ else
+ {
+ // Use dynamic storage
+ m_Storage.m_dynSet=new set_value_type[Size];
+ DestStorage=m_Storage.m_dynSet;
+ SrcStorage=Other.m_Storage.m_dynSet;
+ }
+
+ // Use fixed storage
+ ::memcpy(DestStorage, SrcStorage, sizeof(set_value_type)*m_Size);
+
+ return *this;
+ }
+
+ // Operation
+ template<typename Char2T>
+ bool operator()( Char2T Ch ) const
+ {
+ const set_value_type* Storage=
+ (m_Size<=FIXED_STORAGE_SIZE)
+ ? &m_Storage.m_fixSet[0]
+ : m_Storage.m_dynSet;
+
+ return ::std::binary_search(Storage, Storage+m_Size, Ch);
+ }
+
+ private:
+ // set cannot operate on const value-type
+ typedef typename remove_const<CharT>::type set_value_type;
+
+ // storage
+ // The actual used storage is selected on the type
+ union
+ {
+ set_value_type* m_dynSet;
+ set_value_type m_fixSet[FIXED_STORAGE_SIZE];
+ }
+ m_Storage;
+
+ // storage size
+ ::std::size_t m_Size;
+ };
+
+ // fixed size is_any_of functor
+ /*
+ returns true if the value is from the specified set
+ works on the fixed size set
+ */
+ template<typename CharT, unsigned int Size>
+ struct is_any_of_fixedF :
+ public predicate_facade<is_any_of_fixedF<CharT, Size> >
+ {
                 // Boost.Lambda support
                 template <class Args> struct sig { typedef bool type; };
 
                 // Constructor
                 template<typename RangeT>
- is_any_ofF( const RangeT& Range ) :
- m_Set( ::boost::begin(Range), ::boost::end(Range) ) {}
+ is_any_of_fixedF( const RangeT& Range )
+ {
+ BOOST_ASSERT(::boost::distance(Range)==Size);
+ // Copy up-to Size elements
+ ::std::size_t nIndex=0;
+ ::boost::range_const_iterator<RangeT>::type It=::boost::begin(Range);
+ while(nIndex<Size && It!=::boost::end(Range))
+ {
+ m_Set[nIndex]=*It;
+ }
+ ::std::sort(&m_Set[0], &m_Set[Size]);
+ }
 
                 // Operation
                 template<typename Char2T>
                 bool operator()( Char2T Ch ) const
                 {
- return m_Set.find(Ch)!=m_Set.end();
+ return ::std::binary_search(&m_Set[0], &m_Set[Size], Ch);
                 }
 
             private:
                 // set cannot operate on const value-type
                 typedef typename remove_const<CharT>::type set_value_type;
- std::set<set_value_type> m_Set;
+ set_value_type m_Set[Size];
             };
 
+
             // is_from_range functor
             /*
                 returns true if the value is from the specified range.

Modified: trunk/boost/algorithm/string/find.hpp
==============================================================================
--- trunk/boost/algorithm/string/find.hpp (original)
+++ trunk/boost/algorithm/string/find.hpp 2008-06-18 17:54:06 EDT (Wed, 18 Jun 2008)
@@ -55,7 +55,7 @@
         {
             iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(as_literal(Input));
 
- return Finder(::boost::begin(lit_input),::boost::end(lit_input));
+ return Finder(::boost::begin(lit_input),::boost::end(lit_input));
         }
 
 // find_first -----------------------------------------------//

Modified: trunk/boost/algorithm/string/find_format.hpp
==============================================================================
--- trunk/boost/algorithm/string/find_format.hpp (original)
+++ trunk/boost/algorithm/string/find_format.hpp 2008-06-18 17:54:06 EDT (Wed, 18 Jun 2008)
@@ -76,7 +76,7 @@
                 Output,
                 lit_input,
                 Formatter,
- Finder( ::boost::begin(lit_input), ::boost::end(lit_input) ) );
+ Finder( ::boost::begin(lit_input), ::boost::end(lit_input) ) );
         }
 
         //! Generic replace algorithm


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk