ceph/src/boost/boost/spirit/home/classic/symbols/impl/tst.ipp

   1 /*=============================================================================
   2     Copyright (c) 2001-2003 Joel de Guzman
   3     http://spirit.sourceforge.net/
   4
   5     Use, modification and distribution is subject to the Boost Software
   6     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7     http://www.boost.org/LICENSE_1_0.txt)
   8 =============================================================================*/
   9 #ifndef BOOST_SPIRIT_TST_IPP
  10 #define BOOST_SPIRIT_TST_IPP
  11
  12 ///////////////////////////////////////////////////////////////////////////////
  13 #include <boost/move/unique_ptr.hpp>
  14 #include <boost/spirit/home/classic/core/assert.hpp>
  15
  16 ///////////////////////////////////////////////////////////////////////////////
  17 namespace boost { namespace spirit {
  18
  19 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
  20
  21     namespace impl
  22     {
  23
  24 ///////////////////////////////////////////////////////////////////////////////
  25 //
  26 //  tst class
  27 //
  28 //      Ternary Search Tree implementation. The data structure is faster than
  29 //      hashing for many typical search problems especially when the search
  30 //      interface is iterator based. Searching for a string of length k in a
  31 //      ternary search tree with n strings will require at most O(log n+k)
  32 //      character comparisons. TSTs are many times faster than hash tables
  33 //      for unsuccessful searches since mismatches are discovered earlier
  34 //      after examining only a few characters. Hash tables always examine an
  35 //      entire key when searching.
  36 //
  37 //      For details see http://www.cs.princeton.edu/~rs/strings/.
  38 //
  39 //      *** This is a low level class and is
  40 //          not meant for public consumption ***
  41 //
  42 ///////////////////////////////////////////////////////////////////////////////
  43     template <typename T, typename CharT>
  44     struct tst_node
  45     {
  46         tst_node(CharT value_)
  47         : value(value_)
  48         , left(0)
  49         , right(0)
  50         { middle.link = 0; }
  51
  52         ~tst_node()
  53         {
  54             delete left;
  55             delete right;
  56             if (value)
  57                 delete middle.link;
  58             else
  59                 delete middle.data;
  60         }
  61
  62         tst_node*
  63         clone() const
  64         {
  65             boost::movelib::unique_ptr<tst_node> copy(new tst_node(value));
  66
  67             if (left)
  68                 copy->left = left->clone();
  69             if (right)
  70                 copy->right = right->clone();
  71
  72             if (value && middle.link)
  73             {
  74                 copy->middle.link = middle.link->clone();
  75             }
  76             else
  77             {
  78                 boost::movelib::unique_ptr<T> mid_data(new T(*middle.data));
  79                 copy->middle.data = mid_data.release();
  80             }
  81
  82             return copy.release();
  83         }
  84
  85         union center {
  86
  87             tst_node*   link;
  88             T*          data;
  89         };
  90
  91         CharT       value;
  92         tst_node*   left;
  93         center      middle;
  94         tst_node*   right;
  95     };
  96
  97     ///////////////////////////////////////////////////////////////////////////
  98     template <typename T, typename CharT>
  99     class tst
 100     {
 101     public:
 102
 103         struct search_info
 104         {
 105             T*          data;
 106             std::size_t length;
 107         };
 108
 109         tst()
 110         : root(0) {}
 111
 112         tst(tst const& other)
 113         : root(other.root ? other.root->clone() : 0) {}
 114
 115         ~tst()
 116         { delete root; }
 117
 118         tst&
 119         operator=(tst const& other)
 120         {
 121             if (this != &other)
 122             {
 123                 node_t* new_root = other.root ? other.root->clone() : 0;
 124                 delete root;
 125                 root = new_root;
 126             }
 127             return *this;
 128         }
 129
 130         template <typename IteratorT>
 131         T* add(IteratorT first, IteratorT const& last, T const& data)
 132         {
 133             if (first == last)
 134                 return 0;
 135
 136             node_t**  np = &root;
 137             CharT   ch = *first;
 138
 139             BOOST_SPIRIT_ASSERT((first == last || ch != 0)
 140                 && "Won't add string containing null character");
 141
 142             for (;;)
 143             {
 144                 if (*np == 0 || ch == 0)
 145                 {
 146                     node_t* right = 0;
 147                     if (np != 0)
 148                         right = *np;
 149                     *np = new node_t(ch);
 150                     if (right)
 151                         (**np).right = right;
 152                 }
 153
 154                 if (ch < (**np).value)
 155                 {
 156                     np = &(**np).left;
 157                 }
 158                 else
 159                 {
 160                     if (ch == (**np).value)
 161                     {
 162                         if (ch == 0)
 163                         {
 164                             if ((**np).middle.data == 0)
 165                             {
 166                                 (**np).middle.data = new T(data);
 167                                 return (**np).middle.data;
 168                             }
 169                             else
 170                             {
 171                                 //  re-addition is disallowed
 172                                 return 0;
 173                             }
 174                        }
 175                         ++first;
 176                         ch = (first == last) ? CharT(0) : *first;
 177                         BOOST_SPIRIT_ASSERT((first == last || ch != 0)
 178                             && "Won't add string containing null character");
 179                         np = &(**np).middle.link;
 180                     }
 181                     else
 182                     {
 183                         np = &(**np).right;
 184                     }
 185                 }
 186             }
 187         }
 188
 189         template <typename ScannerT>
 190         search_info find(ScannerT const& scan) const
 191         {
 192             search_info result = { 0, 0 };
 193             if (scan.at_end()) {
 194                 return result;
 195             }
 196
 197             typedef typename ScannerT::iterator_t iterator_t;
 198             node_t*     np = root;
 199             CharT       ch = *scan;
 200             iterator_t  save = scan.first;
 201             iterator_t  latest = scan.first;
 202             std::size_t latest_len = 0;
 203
 204             while (np)
 205             {
 206
 207                 if (ch < np->value) // => go left!
 208                 {
 209                     if (np->value == 0)
 210                     {
 211                         result.data = np->middle.data;
 212                         if (result.data)
 213                         {
 214                             latest = scan.first;
 215                             latest_len = result.length;
 216                         }
 217                     }
 218
 219                     np = np->left;
 220                 }
 221                 else if (ch == np->value) // => go middle!
 222                 {
 223                     // Matching the null character is not allowed.
 224                     if (np->value == 0)
 225                     {
 226                         result.data = np->middle.data;
 227                         if (result.data)
 228                         {
 229                             latest = scan.first;
 230                             latest_len = result.length;
 231                         }
 232                         break;
 233                     }
 234
 235                     ++scan;
 236                     ch = scan.at_end() ? CharT(0) : *scan;
 237                     np = np->middle.link;
 238                     ++result.length;
 239                 }
 240                 else // (ch > np->value) => go right!
 241                 {
 242                     if (np->value == 0)
 243                     {
 244                         result.data = np->middle.data;
 245                         if (result.data)
 246                         {
 247                             latest = scan.first;
 248                             latest_len = result.length;
 249                         }
 250                     }
 251
 252                     np = np->right;
 253                 }
 254             }
 255
 256             if (result.data == 0)
 257             {
 258                 scan.first = save;
 259             }
 260             else
 261             {
 262                 scan.first = latest;
 263                 result.length = latest_len;
 264             }
 265             return result;
 266         }
 267
 268     private:
 269
 270         typedef tst_node<T, CharT> node_t;
 271         node_t* root;
 272     };
 273
 274 ///////////////////////////////////////////////////////////////////////////////
 275     } // namespace impl
 276
 277 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
 278
 279 }} // namespace boost::spirit
 280
 281 #endif