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