ceph/src/boost/boost/spirit/home/x3/string/detail/tst.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2014 Joel de Guzman
   3
   4     Distributed under the Boost Software License, Version 1.0. (See accompanying
   5     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 ==============================================================================*/
   7 #if !defined(BOOST_SPIRIT_X3_TST_MARCH_09_2007_0905AM)
   8 #define BOOST_SPIRIT_X3_TST_MARCH_09_2007_0905AM
   9
  10 #include <boost/call_traits.hpp>
  11 #include <boost/detail/iterator.hpp>
  12 #include <boost/assert.hpp>
  13
  14 namespace boost { namespace spirit { namespace x3 { namespace detail
  15 {
  16     // This file contains low level TST routines, not for
  17     // public consumption.
  18
  19     template <typename Char, typename T>
  20     struct tst_node
  21     {
  22         tst_node(Char id)
  23           : id(id), data(0), lt(0), eq(0), gt(0)
  24         {
  25         }
  26
  27         template <typename Alloc>
  28         static void
  29         destruct_node(tst_node* p, Alloc* alloc)
  30         {
  31             if (p)
  32             {
  33                 if (p->data)
  34                     alloc->delete_data(p->data);
  35                 destruct_node(p->lt, alloc);
  36                 destruct_node(p->eq, alloc);
  37                 destruct_node(p->gt, alloc);
  38                 alloc->delete_node(p);
  39             }
  40         }
  41
  42         template <typename Alloc>
  43         static tst_node*
  44         clone_node(tst_node* p, Alloc* alloc)
  45         {
  46             if (p)
  47             {
  48                 tst_node* clone = alloc->new_node(p->id);
  49                 if (p->data)
  50                     clone->data = alloc->new_data(*p->data);
  51                 clone->lt = clone_node(p->lt, alloc);
  52                 clone->eq = clone_node(p->eq, alloc);
  53                 clone->gt = clone_node(p->gt, alloc);
  54                 return clone;
  55             }
  56             return 0;
  57         }
  58
  59         template <typename Iterator, typename CaseCompare>
  60         static T*
  61         find(tst_node* start, Iterator& first, Iterator last, CaseCompare comp)
  62         {
  63             if (first == last)
  64                 return 0;
  65
  66             Iterator i = first;
  67             Iterator latest = first;
  68             tst_node* p = start;
  69             T* found = 0;
  70
  71             while (p && i != last)
  72             {
  73                 int32_t c = comp(*i,p->id);
  74                 if (c == 0)
  75                 {
  76                     if (p->data)
  77                     {
  78                         found = p->data;
  79                         latest = i;
  80                     }
  81                     p = p->eq;
  82                     i++;
  83                 }
  84                 else if (c < 0)
  85                 {
  86                     p = p->lt;
  87                 }
  88                 else
  89                 {
  90                     p = p->gt;
  91                 }
  92             }
  93
  94             if (found)
  95                 first = ++latest; // one past the last matching char
  96             return found;
  97         }
  98
  99         template <typename Iterator, typename Alloc>
 100         static T*
 101         add(
 102             tst_node*& start
 103           , Iterator first
 104           , Iterator last
 105           , typename boost::call_traits<T>::param_type val
 106           , Alloc* alloc)
 107         {
 108             if (first == last)
 109                 return 0;
 110
 111             tst_node** pp = &start;
 112             for (;;)
 113             {
 114                 typename
 115                     boost::detail::iterator_traits<Iterator>::value_type
 116                 c = *first;
 117
 118                 if (*pp == 0)
 119                     *pp = alloc->new_node(c);
 120                 tst_node* p = *pp;
 121
 122                 if (c == p->id)
 123                 {
 124                     if (++first == last)
 125                     {
 126                         if (p->data == 0)
 127                             p->data = alloc->new_data(val);
 128                         return p->data;
 129                     }
 130                     pp = &p->eq;
 131                 }
 132                 else if (c < p->id)
 133                 {
 134                     pp = &p->lt;
 135                 }
 136                 else
 137                 {
 138                     pp = &p->gt;
 139                 }
 140             }
 141         }
 142
 143         template <typename Iterator, typename Alloc>
 144         static void
 145         remove(tst_node*& p, Iterator first, Iterator last, Alloc* alloc)
 146         {
 147             if (p == 0 || first == last)
 148                 return;
 149
 150             typename
 151                 boost::detail::iterator_traits<Iterator>::value_type
 152             c = *first;
 153
 154             if (c == p->id)
 155             {
 156                 if (++first == last)
 157                 {
 158                     if (p->data)
 159                     {
 160                         alloc->delete_data(p->data);
 161                         p->data = 0;
 162                     }
 163                 }
 164                 remove(p->eq, first, last, alloc);
 165             }
 166             else if (c < p->id)
 167             {
 168                 remove(p->lt, first, last, alloc);
 169             }
 170             else
 171             {
 172                 remove(p->gt, first, last, alloc);
 173             }
 174
 175             if (p->data == 0 && p->lt == 0 && p->eq == 0 && p->gt == 0)
 176             {
 177                 alloc->delete_node(p);
 178                 p = 0;
 179             }
 180         }
 181
 182         template <typename F>
 183         static void
 184         for_each(tst_node* p, std::basic_string<Char> prefix, F f)
 185         {
 186             if (p)
 187             {
 188                 for_each(p->lt, prefix, f);
 189                 std::basic_string<Char> s = prefix + p->id;
 190                 for_each(p->eq, s, f);
 191                 if (p->data)
 192                     f(s, *p->data);
 193                 for_each(p->gt, prefix, f);
 194             }
 195         }
 196
 197         Char id;        // the node's identity character
 198         T* data;        // optional data
 199         tst_node* lt;   // left pointer
 200         tst_node* eq;   // middle pointer
 201         tst_node* gt;   // right pointer
 202     };
 203 }}}}
 204
 205 #endif