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