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