ceph/src/boost/libs/xpressive/include/boost/xpressive/detail/utility/sequence_stack.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // sequence_stack.hpp
   3 //
   4 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   5 //  Software License, Version 1.0. (See accompanying file
   6 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   7
   8 #ifndef BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005
   9 #define BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005
  10
  11 // MS compatible compilers support #pragma once
  12 #if defined(_MSC_VER)
  13 # pragma once
  14 # pragma warning(push)
  15 # pragma warning(disable : 4127) // conditional expression constant
  16 #endif
  17
  18 #include <algorithm>
  19 #include <functional>
  20
  21 namespace boost { namespace xpressive { namespace detail
  22 {
  23
  24 struct fill_t {} const fill = {};
  25
  26 //////////////////////////////////////////////////////////////////////////
  27 // sequence_stack
  28 //
  29 //   For storing a stack of sequences of type T, where each sequence
  30 //   is guaranteed to be stored in contiguous memory.
  31 template<typename T>
  32 struct sequence_stack
  33 {
  34     struct allocate_guard_t;
  35     friend struct allocate_guard_t;
  36     struct allocate_guard_t
  37     {
  38         std::size_t i;
  39         T *p;
  40         bool dismissed;
  41         ~allocate_guard_t()
  42         {
  43             if(!this->dismissed)
  44                 sequence_stack::deallocate(this->p, this->i);
  45         }
  46     };
  47 private:
  48     static T *allocate(std::size_t size, T const &t)
  49     {
  50         allocate_guard_t guard = {0, (T *)::operator new(size * sizeof(T)), false};
  51
  52         for(; guard.i < size; ++guard.i)
  53             ::new((void *)(guard.p + guard.i)) T(t);
  54         guard.dismissed = true;
  55
  56         return guard.p;
  57     }
  58
  59     static void deallocate(T *p, std::size_t i)
  60     {
  61         while(i-- > 0)
  62             (p+i)->~T();
  63         ::operator delete(p);
  64     }
  65
  66     struct chunk
  67     {
  68         chunk(std::size_t size, T const &t, std::size_t count, chunk *back, chunk *next)
  69           : begin_(allocate(size, t))
  70           , curr_(begin_ + count)
  71           , end_(begin_ + size)
  72           , back_(back)
  73           , next_(next)
  74         {
  75             if(this->back_)
  76                 this->back_->next_ = this;
  77             if(this->next_)
  78                 this->next_->back_ = this;
  79         }
  80
  81         ~chunk()
  82         {
  83             deallocate(this->begin_, this->size());
  84         }
  85
  86         std::size_t size() const
  87         {
  88             return static_cast<std::size_t>(this->end_ - this->begin_);
  89         }
  90
  91         T *const begin_, *curr_, *const end_;
  92         chunk *back_, *next_;
  93
  94     private:
  95         chunk &operator =(chunk const &);
  96     };
  97
  98     chunk *current_chunk_;
  99
 100     // Cache these for faster access
 101     T *begin_;
 102     T *curr_;
 103     T *end_;
 104
 105     T *grow_(std::size_t count, T const &t)
 106     {
 107         if(this->current_chunk_)
 108         {
 109             // write the cached value of current into the expr.
 110             // OK to do this even if later statements throw.
 111             this->current_chunk_->curr_ = this->curr_;
 112
 113             // Do we have a expr with enough available memory already?
 114             if(this->current_chunk_->next_ && count <= this->current_chunk_->next_->size())
 115             {
 116                 this->current_chunk_ = this->current_chunk_->next_;
 117                 this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_ + count;
 118                 this->end_ = this->current_chunk_->end_;
 119                 this->begin_ = this->current_chunk_->begin_;
 120                 std::fill_n(this->begin_, count, t);
 121                 return this->begin_;
 122             }
 123
 124             // grow exponentially
 125             std::size_t new_size = (std::max)(
 126                 count
 127               , static_cast<std::size_t>(static_cast<double>(this->current_chunk_->size()) * 1.5)
 128             );
 129
 130             // Create a new expr and insert it into the list
 131             this->current_chunk_ = new chunk(new_size, t, count, this->current_chunk_, this->current_chunk_->next_);
 132         }
 133         else
 134         {
 135             // first chunk is 256
 136             std::size_t new_size = (std::max)(count, static_cast<std::size_t>(256U));
 137
 138             // Create a new expr and insert it into the list
 139             this->current_chunk_ = new chunk(new_size, t, count, 0, 0);
 140         }
 141
 142         this->begin_ = this->current_chunk_->begin_;
 143         this->curr_ = this->current_chunk_->curr_;
 144         this->end_ = this->current_chunk_->end_;
 145         return this->begin_;
 146     }
 147
 148     void unwind_chunk_()
 149     {
 150         // write the cached value of curr_ into current_chunk_
 151         this->current_chunk_->curr_ = this->begin_;
 152         // make the previous chunk the current
 153         this->current_chunk_ = this->current_chunk_->back_;
 154
 155         // update the cache
 156         this->begin_ = this->current_chunk_->begin_;
 157         this->curr_ = this->current_chunk_->curr_;
 158         this->end_ = this->current_chunk_->end_;
 159     }
 160
 161     bool in_current_chunk(T *ptr) const
 162     {
 163         return !std::less<void*>()(ptr, this->begin_) && std::less<void*>()(ptr, this->end_);
 164     }
 165
 166 public:
 167     sequence_stack()
 168       : current_chunk_(0)
 169       , begin_(0)
 170       , curr_(0)
 171       , end_(0)
 172     {
 173     }
 174
 175     ~sequence_stack()
 176     {
 177         this->clear();
 178     }
 179
 180     // walk to the front of the linked list
 181     void unwind()
 182     {
 183         if(this->current_chunk_)
 184         {
 185             while(this->current_chunk_->back_)
 186             {
 187                 this->current_chunk_->curr_ = this->current_chunk_->begin_;
 188                 this->current_chunk_ = this->current_chunk_->back_;
 189             }
 190
 191             this->begin_ = this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_;
 192             this->end_ = this->current_chunk_->end_;
 193         }
 194     }
 195
 196     void clear()
 197     {
 198         // walk to the front of the list
 199         this->unwind();
 200
 201         // delete the list
 202         for(chunk *next; this->current_chunk_; this->current_chunk_ = next)
 203         {
 204             next = this->current_chunk_->next_;
 205             delete this->current_chunk_;
 206         }
 207
 208         this->begin_ = this->curr_ = this->end_ = 0;
 209     }
 210
 211     T *push_sequence(std::size_t count, T const &t)
 212     {
 213         // This is the ptr to return
 214         T *ptr = this->curr_;
 215
 216         // Advance the high-water mark
 217         this->curr_ += count;
 218
 219         // Check to see if we have overflowed this buffer
 220         if(std::less<void*>()(this->end_, this->curr_))
 221         {
 222             // oops, back this out.
 223             this->curr_ = ptr;
 224
 225             // allocate a new block and return a ptr to the new memory
 226             return this->grow_(count, t);
 227         }
 228
 229         return ptr;
 230     }
 231
 232     T *push_sequence(std::size_t count, T const &t, fill_t)
 233     {
 234         T *ptr = this->push_sequence(count, t);
 235         std::fill_n(ptr, count, t);
 236         return ptr;
 237     }
 238
 239     void unwind_to(T *ptr)
 240     {
 241         while(!this->in_current_chunk(ptr))
 242         {
 243             // completely unwind the current chunk, move to the previous chunk
 244             this->unwind_chunk_();
 245         }
 246         this->current_chunk_->curr_ = this->curr_ = ptr;
 247     }
 248
 249     // shrink-to-fit: remove any unused nodes in the chain
 250     void conserve()
 251     {
 252         if(this->current_chunk_)
 253         {
 254             for(chunk *next; this->current_chunk_->next_; this->current_chunk_->next_ = next)
 255             {
 256                 next = this->current_chunk_->next_->next_;
 257                 delete this->current_chunk_->next_;
 258             }
 259         }
 260     }
 261 };
 262
 263 }}} // namespace boost::xpressive::detail
 264
 265 #if defined(_MSC_VER)
 266 # pragma warning(pop)
 267 #endif
 268
 269 #endif