[Boost-commit] svn:boost r39955 - in trunk: boost/xpressive/detail/core boost/xpressive/detail/utility libs/xpressive/doc

From: eric_at_[hidden]
Date: 2007-10-12 00:31:13

Author: eric_niebler
Date: 2007-10-12 00:31:10 EDT (Fri, 12 Oct 2007)
New Revision: 39955
URL: http://svn.boost.org/trac/boost/changeset/39955

Log:
reenable self-adjusting TST if BOOST_DISABLE_THREADS is defined
Text files modified: 
   trunk/boost/xpressive/detail/core/linker.hpp     |     2                                         
   trunk/boost/xpressive/detail/utility/symbols.hpp |    69 +++++++++++++++++++++++++++++++++++---- 
   trunk/libs/xpressive/doc/symbols.qbk             |     7 ++-                                     
   3 files changed, 67 insertions(+), 11 deletions(-)

Modified: trunk/boost/xpressive/detail/core/linker.hpp
==============================================================================
--- trunk/boost/xpressive/detail/core/linker.hpp	(original)
+++ trunk/boost/xpressive/detail/core/linker.hpp	2007-10-12 00:31:10 EDT (Fri, 12 Oct 2007)
@@ -278,7 +278,7 @@
 #if BOOST_VERSION >= 103500
         fusion::for_each(alternates.derived(), alt_link_pred(this, peeker, next));
 #else
-        fusion::for_each(alternates.base(), alt_link_pred(this, peeker, next));
+        fusion::for_each(alternates.cast(), alt_link_pred(this, peeker, next));
 #endif
     }
 

Modified: trunk/boost/xpressive/detail/utility/symbols.hpp
==============================================================================
--- trunk/boost/xpressive/detail/utility/symbols.hpp	(original)
+++ trunk/boost/xpressive/detail/utility/symbols.hpp	2007-10-12 00:31:10 EDT (Fri, 12 Oct 2007)
@@ -1,12 +1,17 @@
 ///////////////////////////////////////////////////////////////////////////////
 /// \file symbols.hpp
 ///   Contains the Ternary Search Trie implementation.
-/// Based on the following paper:
+/// Based on the following papers:
 /// J. Bentley and R. Sedgewick. (1998) Ternary search trees. Dr. Dobbs Journal
+/// G. Badr and B.J. Oommen. (2005) Self-Adjusting of Ternary Search Tries Using
+///     Conditional Rotations and Randomized Heuristics
 //
-//  Copyright 2007 David Jenkins. 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)
+//  Copyright 2007 David Jenkins.
+//  Copyright 2007 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_SYMBOLS_HPP_DRJ_06_11_2007
 #define BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
@@ -16,7 +21,7 @@
 # pragma once
 #endif
 
-#include <boost/range/iterator.hpp>
+#include <boost/range/result_iterator.hpp>
 #include <boost/range/begin.hpp>
 #include <boost/range/end.hpp>
 #include <boost/shared_ptr.hpp>
@@ -33,8 +38,8 @@
         typedef typename range_value<Map>::type::first_type key_type;
         typedef typename range_value<Map>::type::second_type value_type;
         typedef typename range_value<key_type>::type char_type;
-        typedef typename range_iterator<Map const>::type iterator;
-        typedef typename range_iterator<key_type const>::type key_iterator;
+        typedef typename range_result_iterator<Map const>::type iterator;
+        typedef typename range_result_iterator<key_type const>::type key_iterator;
         typedef value_type const *result_type;
 
         // copies of this symbol table share the TST
@@ -79,6 +84,9 @@
               , lo(0)
               , eq(0)
               , hi(0)
+              #ifdef BOOST_DISABLE_THREADS
+              , tau(0)
+              #endif
             {}
 
             ~node()
@@ -95,6 +103,9 @@
                 std::swap(lo, that.lo);
                 std::swap(eq, that.eq);
                 std::swap(hi, that.hi);
+                #ifdef BOOST_DISABLE_THREADS
+                std::swap(tau, that.tau);
+                #endif
             }
 
             char_type ch;
@@ -105,6 +116,7 @@
                 result_type result;
             };
             node* hi;
+            long tau;
         };
 
         ///////////////////////////////////////////////////////////////////////////////
@@ -148,6 +160,41 @@
             return p;
         }
 
+        #ifdef BOOST_DISABLE_THREADS
+        ///////////////////////////////////////////////////////////////////////////////
+        // conditional rotation : the goal is to minimize the overall
+        //     weighted path length of each binary search tree
+        // 
+        bool const cond_rotation(bool left, node* const i, node* const j) const
+        {
+            // don't rotate top node in binary search tree
+            if (i == j)
+                return false;
+            // calculate psi (the rotation condition)
+            node* const k = (left ? i->hi : i->lo);
+            long psi = 2*i->tau - j->tau - (k ? k->tau : 0);
+            if (psi <= 0)
+                return false;
+
+            // recalculate the tau values
+            j->tau += -i->tau + (k ? k->tau : 0);
+            i->tau +=  j->tau - (k ? k->tau : 0);
+            // fixup links and swap nodes
+            if (left)
+            {
+                j->lo = k;
+                i->hi = i;
+            }
+            else
+            {
+                j->hi = k;
+                i->lo = i;
+            }
+            (*i).swap(*j);
+            return true;
+        }
+        #endif
+
         ///////////////////////////////////////////////////////////////////////////////
         // search : find a string in the TST
         // 
@@ -160,8 +207,16 @@
             char_type c1 = (begin != end ? trans(*begin) : 0);
             while(p)
             {
+                #ifdef BOOST_DISABLE_THREADS
+                ++p->tau;
+                #endif
                 if(c1 == p->ch)
                 {
+                    // conditional rotation test
+                    #ifdef BOOST_DISABLE_THREADS
+                    if (this->cond_rotation(left, p, p2))
+                        p = p2;
+                    #endif
                     if (0 == p->ch)
                     {
                         // it's a match!

Modified: trunk/libs/xpressive/doc/symbols.qbk
==============================================================================
--- trunk/libs/xpressive/doc/symbols.qbk	(original)
+++ trunk/libs/xpressive/doc/symbols.qbk	2007-10-12 00:31:10 EDT (Fri, 12 Oct 2007)
@@ -9,7 +9,7 @@
 
 [h2 Overview]
 
-Symbol tables can be built into Xpressive regular expressions with just a 
+Symbol tables can be built into xpressive regular expressions with just a 
 `std::map<>`. The map keys are the strings to be matched and the map values are
 the data to be returned to your semantic action. Xpressive attributes, named
 `a1`, `a2`, through `a9`, hold the value corresponding to a matching key so
@@ -18,7 +18,7 @@
 
 [h2 Symbol Tables]
 
-An Xpressive symbol table is just a `std::map<>`, where the key is a string type
+An xpressive symbol table is just a `std::map<>`, where the key is a string type
 and the value can be anything. For example, the following regular expression
 matches a key from map1 and assigns the corresponding value to the attribute
 `a1`. Then, in the semantic action, it assigns the value stored in attribute
@@ -102,7 +102,8 @@
 even have different types.
 
 [note Xpressive builds a hidden ternary search trie from the map so it can
-search quickly. The hidden ternary search trie is "self adjusting", so after each
+search quickly. If BOOST_DISABLE_THREADS is defined,
+the hidden ternary search trie "self adjusts", so after each
 search it restructures itself to improve the efficiency of future searches
 based on the frequency of previous searches.]