ceph/src/boost/tools/quickbook/src/symbols.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2003 Joel de Guzman
   3     Copyright (c) 2011 Daniel James
   4     http://spirit.sourceforge.net/
   5
   6     Use, modification and distribution is subject to the Boost Software
   7     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8     http://www.boost.org/LICENSE_1_0.txt)
   9 =============================================================================*/
  10 #ifndef QUICKBOOK_SYMBOLS_IPP
  11 #define QUICKBOOK_SYMBOLS_IPP
  12
  13 ///////////////////////////////////////////////////////////////////////////////
  14
  15 #include <boost/spirit/home/classic/symbols.hpp>
  16 #include <boost/intrusive_ptr.hpp>
  17 #include <boost/scoped_ptr.hpp>
  18
  19 ///////////////////////////////////////////////////////////////////////////////
  20 namespace quickbook
  21 {
  22
  23 ///////////////////////////////////////////////////////////////////////////////
  24 //
  25 //  tst class
  26 //
  27 //      This it the Ternary Search Tree from
  28 //      <boost/spirit/home/classic/symbols/impl/tst.ipp> adapted to be cheap
  29 //      to copy.
  30 //
  31 //      Ternary Search Tree implementation. The data structure is faster than
  32 //      hashing for many typical search problems especially when the search
  33 //      interface is iterator based. Searching for a string of length k in a
  34 //      ternary search tree with n strings will require at most O(log n+k)
  35 //      character comparisons. TSTs are many times faster than hash tables
  36 //      for unsuccessful searches since mismatches are discovered earlier
  37 //      after examining only a few characters. Hash tables always examine an
  38 //      entire key when searching.
  39 //
  40 //      For details see http://www.cs.princeton.edu/~rs/strings/.
  41 //
  42 //      *** This is a low level class and is
  43 //          not meant for public consumption ***
  44 //
  45 ///////////////////////////////////////////////////////////////////////////////
  46
  47     template <typename T, typename CharT>
  48     struct tst_node
  49     {
  50         tst_node(CharT value_)
  51         : reference_count(0)
  52         , left()
  53         , middle()
  54         , right()
  55         , data()
  56         , value(value_)
  57         {
  58         }
  59
  60         tst_node(tst_node const& other)
  61         : reference_count(0)
  62         , left(other.left)
  63         , middle(other.middle)
  64         , right(other.right)
  65         , data(other.data ? new T(*other.data) : 0)
  66         , value(other.value)
  67         {
  68         }
  69
  70         // If you fancy a slight improvement in memory use,
  71         // reference_count + value could probably be packed
  72         // in the space for a single int.
  73         int reference_count;
  74         boost::intrusive_ptr<tst_node> left;
  75         boost::intrusive_ptr<tst_node> middle;
  76         boost::intrusive_ptr<tst_node> right;
  77         boost::scoped_ptr<T> data;
  78         CharT value;
  79     private:
  80         tst_node& operator=(tst_node const&);
  81     };
  82
  83     template <typename T, typename CharT>
  84     void intrusive_ptr_add_ref(tst_node<T, CharT>* ptr)
  85         { ++ptr->reference_count; }
  86
  87     template <typename T, typename CharT>
  88     void intrusive_ptr_release(tst_node<T, CharT>* ptr)
  89         { if(--ptr->reference_count == 0) delete ptr; }
  90
  91
  92     ///////////////////////////////////////////////////////////////////////////
  93     template <typename T, typename CharT>
  94     class tst
  95     {
  96         typedef tst_node<T, CharT> node_t;
  97         typedef boost::intrusive_ptr<node_t> node_ptr;
  98         node_ptr root;
  99
 100     public:
 101
 102         struct search_info
 103         {
 104             T*          data;
 105             std::size_t length;
 106         };
 107
 108         void swap(tst& other)
 109         {
 110             root.swap(other.root);
 111         }
 112
 113         // Adds symbol to ternary search tree.
 114         // If it already exists, then replace it with new value.
 115         //
 116         // pre: first != last
 117         template <typename IteratorT>
 118         T* add(IteratorT first, IteratorT const& last, T const& data)
 119         {
 120             assert (first != last);
 121
 122             node_ptr* np = &root;
 123             CharT ch = *first;
 124
 125             for(;;)
 126             {
 127                 if (!*np)
 128                 {
 129                     *np = new node_t(ch);
 130                 }
 131                 else if ((*np)->reference_count > 1)
 132                 {
 133                     *np = new node_t(**np);
 134                 }
 135
 136                 if (ch < (*np)->value)
 137                 {
 138                     np = &(*np)->left;
 139                 }
 140                 else if (ch == (*np)->value)
 141                 {
 142                     ++first;
 143                     if (first == last) break;
 144                     ch = *first;
 145                     np = &(*np)->middle;
 146                 }
 147                 else
 148                 {
 149                     np = &(*np)->right;
 150                 }
 151             }
 152
 153             boost::scoped_ptr<T> new_data(new T(data));
 154             boost::swap((*np)->data, new_data);
 155             return (*np)->data.get();
 156         }
 157
 158         template <typename ScannerT>
 159         search_info find(ScannerT const& scan) const
 160         {
 161             search_info result = { 0, 0 };
 162             if (scan.at_end()) {
 163                 return result;
 164             }
 165
 166             typedef typename ScannerT::iterator_t iterator_t;
 167             node_ptr    np = root;
 168             CharT       ch = *scan;
 169             iterator_t  latest = scan.first;
 170             std::size_t length = 0;
 171
 172             while (np)
 173             {
 174                 if (ch < np->value) // => go left!
 175                 {
 176                     np = np->left;
 177                 }
 178                 else if (ch == np->value) // => go middle!
 179                 {
 180                     ++scan;
 181                     ++length;
 182
 183                     // Found a potential match.
 184                     if (np->data.get())
 185                     {
 186                         result.data = np->data.get();
 187                         result.length = length;
 188                         latest = scan.first;
 189                     }
 190
 191                     if (scan.at_end()) break;
 192                     ch = *scan;
 193                     np = np->middle;
 194                 }
 195                 else // (ch > np->value) => go right!
 196                 {
 197                     np = np->right;
 198                 }
 199             }
 200
 201             scan.first = latest;
 202             return result;
 203         }
 204     };
 205
 206     typedef boost::spirit::classic::symbols<
 207         std::string,
 208         char,
 209         quickbook::tst<std::string, char>
 210     > string_symbols;
 211 } // namespace quickbook
 212
 213 #endif