|
|
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