Subject: [Boost-commit] svn:boost r57174 - in trunk/boost/xpressive/detail: . core
From: eric_at_[hidden]
Date: 2009-10-27 09:22:11
Author: eric_niebler
Date: 2009-10-27 09:22:09 EDT (Tue, 27 Oct 2009)
New Revision: 57174
URL: http://svn.boost.org/trac/boost/changeset/57174
Log:
nested results uses a custom list type that allows incomplete types, does no dynamic allocation in the default constructor, and has a guarnteed O(1) splice; fixes #3278
Added:
trunk/boost/xpressive/detail/core/list.hpp (contents, props changed)
Text files modified:
trunk/boost/xpressive/detail/core/results_cache.hpp | 180 +++++++++++++++++++--------------------
trunk/boost/xpressive/detail/detail_fwd.hpp | 3
2 files changed, 89 insertions(+), 94 deletions(-)
Added: trunk/boost/xpressive/detail/core/list.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/xpressive/detail/core/list.hpp 2009-10-27 09:22:09 EDT (Tue, 27 Oct 2009)
@@ -0,0 +1,255 @@
+///////////////////////////////////////////////////////////////////////////////
+// list.hpp
+// A simple implementation of std::list that allows incomplete
+// types, does no dynamic allocation in the default constructor,
+// and has a guarnteed O(1) splice.
+//
+// Copyright 2009 Eric Niebler. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
+#define BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
+
+// MS compatible compilers support #pragma once
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <cstddef>
+#include <iterator>
+#include <algorithm>
+#include <boost/assert.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+
+namespace boost { namespace xpressive { namespace detail
+{
+
+ ///////////////////////////////////////////////////////////////////////////////
+ // list
+ //
+ template<typename T>
+ struct list
+ {
+ private:
+ struct node_base
+ {
+ node_base *_prev;
+ node_base *_next;
+ };
+
+ struct node : node_base
+ {
+ explicit node(T const &value = T())
+ : _value(value)
+ {}
+
+ T _value;
+ };
+
+ node_base _sentry;
+
+ public:
+ struct iterator
+ : boost::iterator_facade<iterator, T, std::bidirectional_iterator_tag>
+ {
+ explicit iterator(node_base *n = 0) : _node(n) {}
+ private:
+ friend struct list<T>;
+ friend class boost::iterator_core_access;
+ T &dereference() const { return static_cast<node *>(_node)->_value; }
+ void increment() { _node = _node->_next; }
+ void decrement() { _node = _node->_prev; }
+ bool equal(iterator it) const { return _node == it._node; }
+ node_base *_node;
+ };
+
+ struct const_iterator
+ : boost::iterator_facade<const_iterator, T, std::bidirectional_iterator_tag, T const &>
+ {
+ const_iterator(iterator it) : _node(it._node) {}
+ explicit const_iterator(node_base const *n = 0) : _node(n) {}
+ private:
+ friend struct list<T>;
+ friend class boost::iterator_core_access;
+ T const &dereference() const { return static_cast<node const *>(_node)->_value; }
+ void increment() { _node = _node->_next; }
+ void decrement() { _node = _node->_prev; }
+ bool equal(const_iterator it) const { return _node == it._node; }
+ node_base const *_node;
+ };
+
+ typedef T *pointer;
+ typedef T const *const_pointer;
+ typedef T &reference;
+ typedef T const &const_reference;
+ typedef std::size_t size_type;
+
+ list()
+ {
+ _sentry._next = _sentry._prev = &_sentry;
+ }
+
+ list(list<T> const &that)
+ {
+ _sentry._next = _sentry._prev = &_sentry;
+ const_iterator it = that.begin(), e = that.end();
+ for( ; it != e; ++it)
+ push_back(*it);
+ }
+
+ list &operator =(list<T> const &that)
+ {
+ list<T>(that).swap(*this);
+ return *this;
+ }
+
+ ~list()
+ {
+ clear();
+ }
+
+ void clear()
+ {
+ while(!empty())
+ pop_front();
+ }
+
+ void swap(list<T> &that) // throw()
+ {
+ list<T> tmp;
+ tmp.splice(tmp.begin(), *this); // move this to tmp
+ splice(begin(), that); // move that to this
+ that.splice(that.begin(), tmp); // move tmp to that
+ }
+
+ void push_front(T const &t)
+ {
+ node *new_node = new node(t);
+
+ new_node->_next = _sentry._next;
+ new_node->_prev = &_sentry;
+
+ _sentry._next->_prev = new_node;
+ _sentry._next = new_node;
+ }
+
+ void push_back(T const &t)
+ {
+ node *new_node = new node(t);
+
+ new_node->_next = &_sentry;
+ new_node->_prev = _sentry._prev;
+
+ _sentry._prev->_next = new_node;
+ _sentry._prev = new_node;
+ }
+
+ void pop_front()
+ {
+ BOOST_ASSERT(!empty());
+ node *old_node = static_cast<node *>(_sentry._next);
+ _sentry._next = old_node->_next;
+ _sentry._next->_prev = &_sentry;
+ delete old_node;
+ }
+
+ void pop_back()
+ {
+ BOOST_ASSERT(!empty());
+ node *old_node = static_cast<node *>(_sentry._prev);
+ _sentry._prev = old_node->_prev;
+ _sentry._prev->_next = &_sentry;
+ delete old_node;
+ }
+
+ bool empty() const
+ {
+ return _sentry._next == &_sentry;
+ }
+
+ void splice(iterator it, list<T> &x)
+ {
+ if(!x.empty())
+ {
+ x._sentry._prev->_next = it._node;
+ x._sentry._next->_prev = it._node->_prev;
+
+ it._node->_prev->_next = x._sentry._next;
+ it._node->_prev = x._sentry._prev;
+
+ x._sentry._prev = x._sentry._next = &x._sentry;
+ }
+ }
+
+ void splice(iterator it, list<T> &, iterator xit)
+ {
+ xit._node->_prev->_next = xit._node->_next;
+ xit._node->_next->_prev = xit._node->_prev;
+
+ xit._node->_next = it._node;
+ xit._node->_prev = it._node->_prev;
+
+ it._node->_prev->_next = xit._node;
+ it._node->_prev = xit._node;
+ }
+
+ reference front()
+ {
+ BOOST_ASSERT(!empty());
+ return static_cast<node *>(_sentry._next)->_value;
+ }
+
+ const_reference front() const
+ {
+ BOOST_ASSERT(!empty());
+ return static_cast<node *>(_sentry._next)->_value;
+ }
+
+ reference back()
+ {
+ BOOST_ASSERT(!empty());
+ return static_cast<node *>(_sentry._prev)->_value;
+ }
+
+ const_reference back() const
+ {
+ BOOST_ASSERT(!empty());
+ return static_cast<node *>(_sentry._prev)->_value;
+ }
+
+ iterator begin()
+ {
+ return iterator(_sentry._next);
+ }
+
+ const_iterator begin() const
+ {
+ return const_iterator(_sentry._next);
+ }
+
+ iterator end()
+ {
+ return iterator(&_sentry);
+ }
+
+ const_iterator end() const
+ {
+ return const_iterator(&_sentry);
+ }
+
+ size_type size() const
+ {
+ return static_cast<size_type>(std::distance(begin(), end()));
+ }
+ };
+
+ template<typename T>
+ void swap(list<T> &lhs, list<T> &rhs)
+ {
+ lhs.swap(rhs);
+ }
+
+}}} // namespace boost::xpressive::detail
+
+#endif
Modified: trunk/boost/xpressive/detail/core/results_cache.hpp
==============================================================================
--- trunk/boost/xpressive/detail/core/results_cache.hpp (original)
+++ trunk/boost/xpressive/detail/core/results_cache.hpp 2009-10-27 09:22:09 EDT (Tue, 27 Oct 2009)
@@ -13,129 +13,121 @@
# pragma once
#endif
-#include <list>
+#include <cstddef>
#include <boost/detail/workaround.hpp>
#include <boost/assert.hpp>
#include <boost/xpressive/detail/detail_fwd.hpp>
+#include <boost/xpressive/detail/core/list.hpp>
#include <boost/xpressive/detail/core/access.hpp>
#include <boost/xpressive/match_results.hpp>
namespace boost { namespace xpressive { namespace detail
{
-///////////////////////////////////////////////////////////////////////////////
-// nested_results
-// BUGBUG by using std::list, it makes construction of of an empty nested_results
-// incur a dynamic allocation. As a result, construction an empty match_results is
-// likewise not free. FIXME.
-#if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3206))
-template<typename BidiIter>
-struct nested_results
- : std::list<match_results<BidiIter> >
-{
- friend struct results_cache<BidiIter>;
- friend struct match_results<BidiIter>;
-};
-#else
-template<typename BidiIter>
-struct nested_results
- : private std::list<match_results<BidiIter> >
-{
- friend struct results_cache<BidiIter>;
- friend struct xpressive::match_results<BidiIter>;
- typedef std::list<xpressive::match_results<BidiIter> > base_type;
-
- using base_type::iterator;
- using base_type::const_iterator;
- #if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB , == 1)
- // old Dinkumware doesn't expose pointer typedefs
- typedef base_type::value_type *pointer;
- typedef base_type::value_type const *const_pointer;
+ ///////////////////////////////////////////////////////////////////////////////
+ // nested_results
+ #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3206))
+ template<typename BidiIter>
+ struct nested_results
+ : detail::list<match_results<BidiIter> >
+ {
+ friend struct results_cache<BidiIter>;
+ friend struct match_results<BidiIter>;
+ };
#else
- using base_type::pointer;
- using base_type::const_pointer;
+ template<typename BidiIter>
+ struct nested_results
+ : private detail::list<match_results<BidiIter> >
+ {
+ friend struct results_cache<BidiIter>;
+ friend struct xpressive::match_results<BidiIter>;
+ typedef list<xpressive::match_results<BidiIter> > base_type;
+
+ using base_type::iterator;
+ using base_type::const_iterator;
+ using base_type::pointer;
+ using base_type::const_pointer;
+ using base_type::reference;
+ using base_type::const_reference;
+ using base_type::size_type;
+ using base_type::begin;
+ using base_type::end;
+ using base_type::size;
+ using base_type::empty;
+ using base_type::front;
+ using base_type::back;
+ };
#endif
- using base_type::reference;
- using base_type::const_reference;
- using base_type::size_type;
- using base_type::begin;
- using base_type::end;
- using base_type::size;
- using base_type::empty;
- using base_type::front;
- using base_type::back;
-};
-#endif
-
-///////////////////////////////////////////////////////////////////////////////
-// results_cache
-//
-// cache storage for reclaimed match_results structs
-template<typename BidiIter>
-struct results_cache
-{
- typedef core_access<BidiIter> access;
- match_results<BidiIter> &append_new(nested_results<BidiIter> &out)
+ ///////////////////////////////////////////////////////////////////////////////
+ // results_cache
+ //
+ // cache storage for reclaimed match_results structs
+ template<typename BidiIter>
+ struct results_cache
{
- if(this->cache_.empty())
- {
- out.push_back(match_results<BidiIter>());
- }
- else
+ typedef core_access<BidiIter> access;
+
+ match_results<BidiIter> &append_new(nested_results<BidiIter> &out)
{
- BOOST_ASSERT(access::get_nested_results(this->cache_.back()).empty());
- out.splice(out.end(), this->cache_, --this->cache_.end());
+ if(this->cache_.empty())
+ {
+ out.push_back(match_results<BidiIter>());
+ }
+ else
+ {
+ BOOST_ASSERT(access::get_nested_results(this->cache_.back()).empty());
+ out.splice(out.end(), this->cache_, --this->cache_.end());
+ }
+ return out.back();
}
- return out.back();
- }
- // move the last match_results struct into the cache
- void reclaim_last(nested_results<BidiIter> &out)
- {
- BOOST_ASSERT(!out.empty());
- // first, reclaim any nested results
- nested_results<BidiIter> &nested = access::get_nested_results(out.back());
- if(!nested.empty())
+ // move the last match_results struct into the cache
+ void reclaim_last(nested_results<BidiIter> &out)
{
- this->reclaim_all(nested);
+ BOOST_ASSERT(!out.empty());
+ // first, reclaim any nested results
+ nested_results<BidiIter> &nested = access::get_nested_results(out.back());
+ if(!nested.empty())
+ {
+ this->reclaim_all(nested);
+ }
+ // then, reclaim the last match_results
+ this->cache_.splice(this->cache_.end(), out, --out.end());
}
- // then, reclaim the last match_results
- this->cache_.splice(this->cache_.end(), out, --out.end());
- }
- // move the last n match_results structs into the cache
- void reclaim_last_n(nested_results<BidiIter> &out, std::size_t count)
- {
- for(; 0 != count; --count)
+ // move the last n match_results structs into the cache
+ void reclaim_last_n(nested_results<BidiIter> &out, std::size_t count)
{
- this->reclaim_last(out);
+ for(; 0 != count; --count)
+ {
+ this->reclaim_last(out);
+ }
}
- }
- void reclaim_all(nested_results<BidiIter> &out)
- {
- typedef typename nested_results<BidiIter>::iterator iter_type;
-
- // first, recursively reclaim all the nested results
- for(iter_type begin = out.begin(); begin != out.end(); ++begin)
+ void reclaim_all(nested_results<BidiIter> &out)
{
- nested_results<BidiIter> &nested = access::get_nested_results(*begin);
+ typedef typename nested_results<BidiIter>::iterator iter_type;
- if(!nested.empty())
+ // first, recursively reclaim all the nested results
+ for(iter_type begin = out.begin(); begin != out.end(); ++begin)
{
- this->reclaim_all(nested);
+ nested_results<BidiIter> &nested = access::get_nested_results(*begin);
+
+ if(!nested.empty())
+ {
+ this->reclaim_all(nested);
+ }
}
- }
- // next, reclaim the results themselves
- this->cache_.splice(this->cache_.end(), out);
- }
+ // next, reclaim the results themselves
+ this->cache_.splice(this->cache_.end(), out);
+ }
-private:
+ private:
- nested_results<BidiIter> cache_;
-};
+ nested_results<BidiIter> cache_;
+ };
}}} // namespace boost::xpressive::detail
Modified: trunk/boost/xpressive/detail/detail_fwd.hpp
==============================================================================
--- trunk/boost/xpressive/detail/detail_fwd.hpp (original)
+++ trunk/boost/xpressive/detail/detail_fwd.hpp 2009-10-27 09:22:09 EDT (Tue, 27 Oct 2009)
@@ -287,6 +287,9 @@
template<typename BidiIter>
struct sub_match_impl;
+ template<typename T>
+ struct list;
+
template<typename BidiIter>
struct results_cache;