[Boost-commit] svn:boost r57174 - in trunk/boost/xpressive/detail: . core

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;