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

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