boost/boost/regex/v4/regex_stack.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   4  * John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost Software License, Version 1.0. (See accompanying file
   8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         regex_stack.hpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Implements customised internal regex stacks.
  17   *                Note this is an internal header file included
  18   *                by regex.hpp, do not include on its own.
  19   */
  20
  21 #ifndef BOOST_REGEX_STACK_HPP
  22 #define BOOST_REGEX_STACK_HPP
  23
  24 #ifndef BOOST_REGEX_CONFIG_HPP
  25 #include <boost/regex/config.hpp>
  26 #endif
  27 #ifndef BOOST_REGEX_RAW_BUFFER_HPP
  28 #include <boost/regex/v4/regex_raw_buffer.hpp>
  29 #endif
  30
  31 namespace boost{
  32    namespace re_detail{
  33
  34 #ifdef BOOST_HAS_ABI_HEADERS
  35 #  include BOOST_ABI_PREFIX
  36 #endif
  37
  38 //
  39 // class jstack
  40 // simplified stack optimised for push/peek/pop
  41 // operations, we could use std::stack<std::vector<T>> instead...
  42 //
  43 template <class T, class Allocator = BOOST_DEFAULT_ALLOCATOR(T) >
  44 class jstack
  45 {
  46 public:
  47    typedef typename boost::detail::rebind_allocator<unsigned char, Allocator>::type allocator_type;
  48 private:
  49    typedef typename boost::detail::rebind_allocator<T, Allocator>::type             T_alloc_type;
  50    typedef typename T_alloc_type::size_type                              size_type;
  51    typedef T value_type;
  52    struct node
  53    {
  54       node* next;
  55       T* start;  // first item
  56       T* end;    // last item
  57       T* last;   // end of storage
  58    };
  59
  60    //
  61    // empty base member optimisation:
  62    struct data : public allocator_type
  63    {
  64       padding buf[(sizeof(T) * 16 + sizeof(padding) - 1) / sizeof(padding)];
  65       data(const Allocator& a) : allocator_type(a){}
  66    };
  67
  68    data alloc_inst;
  69    mutable node* m_stack;
  70    mutable node* unused;
  71    node base;
  72    size_type block_size;
  73
  74    void BOOST_REGEX_CALL pop_aux()const;
  75    void BOOST_REGEX_CALL push_aux();
  76
  77 public:
  78    jstack(size_type n = 64, const Allocator& a = Allocator());
  79
  80    ~jstack();
  81
  82    node* BOOST_REGEX_CALL get_node()
  83    {
  84       node* new_stack = reinterpret_cast<node*>(alloc_inst.allocate(sizeof(node) + sizeof(T) * block_size));
  85       BOOST_REGEX_NOEH_ASSERT(new_stack)
  86       new_stack->last = reinterpret_cast<T*>(new_stack+1);
  87       new_stack->start = new_stack->end = new_stack->last + block_size;
  88       new_stack->next = 0;
  89       return new_stack;
  90    }
  91
  92    bool BOOST_REGEX_CALL empty()
  93    {
  94       return (m_stack->start == m_stack->end) && (m_stack->next == 0);
  95    }
  96
  97    bool BOOST_REGEX_CALL good()
  98    {
  99       return (m_stack->start != m_stack->end) || (m_stack->next != 0);
 100    }
 101
 102    T& BOOST_REGEX_CALL peek()
 103    {
 104       if(m_stack->start == m_stack->end)
 105          pop_aux();
 106       return *m_stack->end;
 107    }
 108
 109    const T& BOOST_REGEX_CALL peek()const
 110    {
 111       if(m_stack->start == m_stack->end)
 112          pop_aux();
 113       return *m_stack->end;
 114    }
 115
 116    void BOOST_REGEX_CALL pop()
 117    {
 118       if(m_stack->start == m_stack->end)
 119          pop_aux();
 120       ::boost::re_detail::pointer_destroy(m_stack->end);
 121       ++(m_stack->end);
 122    }
 123
 124    void BOOST_REGEX_CALL pop(T& t)
 125    {
 126       if(m_stack->start == m_stack->end)
 127          pop_aux();
 128       t = *m_stack->end;
 129       ::boost::re_detail::pointer_destroy(m_stack->end);
 130       ++(m_stack->end);
 131    }
 132
 133    void BOOST_REGEX_CALL push(const T& t)
 134    {
 135       if(m_stack->end == m_stack->last)
 136          push_aux();
 137       --(m_stack->end);
 138       pointer_construct(m_stack->end, t);
 139    }
 140
 141 };
 142
 143 template <class T, class Allocator>
 144 jstack<T, Allocator>::jstack(size_type n, const Allocator& a)
 145     : alloc_inst(a)
 146 {
 147   unused = 0;
 148   block_size = n;
 149   m_stack = &base;
 150   base.last = reinterpret_cast<T*>(alloc_inst.buf);
 151   base.end = base.start = base.last + 16;
 152   base.next = 0;
 153 }
 154
 155 template <class T, class Allocator>
 156 void BOOST_REGEX_CALL jstack<T, Allocator>::push_aux()
 157 {
 158    // make sure we have spare space on TOS:
 159    register node* new_node;
 160    if(unused)
 161    {
 162       new_node = unused;
 163       unused = new_node->next;
 164       new_node->next = m_stack;
 165       m_stack = new_node;
 166    }
 167    else
 168    {
 169       new_node = get_node();
 170       new_node->next = m_stack;
 171       m_stack = new_node;
 172    }
 173 }
 174
 175 template <class T, class Allocator>
 176 void BOOST_REGEX_CALL jstack<T, Allocator>::pop_aux()const
 177 {
 178    // make sure that we have a valid item
 179    // on TOS:
 180    BOOST_ASSERT(m_stack->next);
 181    register node* p = m_stack;
 182    m_stack = p->next;
 183    p->next = unused;
 184    unused = p;
 185 }
 186
 187 template <class T, class Allocator>
 188 jstack<T, Allocator>::~jstack()
 189 {
 190    node* condemned;
 191    while(good())
 192       pop();
 193    while(unused)
 194    {
 195       condemned = unused;
 196       unused = unused->next;
 197       alloc_inst.deallocate(reinterpret_cast<unsigned char*>(condemned), sizeof(node) + sizeof(T) * block_size);
 198    }
 199    while(m_stack != &base)
 200    {
 201       condemned = m_stack;
 202       m_stack = m_stack->next;
 203       alloc_inst.deallocate(reinterpret_cast<unsigned char*>(condemned), sizeof(node) + sizeof(T) * block_size);
 204    }
 205 }
 206
 207 #ifdef BOOST_HAS_ABI_HEADERS
 208 #  include BOOST_ABI_SUFFIX
 209 #endif
 210
 211 } // namespace re_detail
 212 } // namespace boost
 213
 214 #endif
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225