ceph/src/boost/boost/spirit/home/classic/iterator/fixed_size_queue.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001, Daniel C. Nuffer
   3     Copyright (c) 2003, Hartmut Kaiser
   4     http://spirit.sourceforge.net/
   5
   6   Distributed under the Boost Software License, Version 1.0. (See accompanying
   7   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8 =============================================================================*/
   9 #ifndef FIXED_SIZE_QUEUE
  10 #define FIXED_SIZE_QUEUE
  11
  12 #include <cstdlib>
  13 #include <iterator>
  14 #include <cstddef>
  15
  16 #include <boost/spirit/home/classic/namespace.hpp>
  17 #include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
  18
  19 // FIXES for broken compilers
  20 #include <boost/config.hpp>
  21 #include <boost/iterator_adaptors.hpp>
  22
  23 #define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
  24     BOOST_SPIRIT_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
  25     /**/
  26
  27 ///////////////////////////////////////////////////////////////////////////////
  28 namespace boost { namespace spirit {
  29
  30 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
  31
  32 ///////////////////////////////////////////////////////////////////////////////
  33 namespace impl {
  34
  35 #if !defined(BOOST_ITERATOR_ADAPTORS_VERSION) || \
  36     BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
  37 #error "Please use at least Boost V1.31.0 while compiling the fixed_size_queue class!"
  38 #else // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
  39
  40 template <typename QueueT, typename T, typename PointerT>
  41 class fsq_iterator
  42 :   public boost::iterator_adaptor<
  43         fsq_iterator<QueueT, T, PointerT>,
  44         PointerT,
  45         T,
  46         std::random_access_iterator_tag
  47     >
  48 {
  49 public:
  50     typedef typename QueueT::position_t position;
  51     typedef boost::iterator_adaptor<
  52             fsq_iterator<QueueT, T, PointerT>, PointerT, T,
  53             std::random_access_iterator_tag
  54         > base_t;
  55
  56     fsq_iterator() {}
  57     fsq_iterator(position const &p_) : p(p_) {}
  58
  59     position const &get_position() const { return p; }
  60
  61 private:
  62     friend class boost::iterator_core_access;
  63
  64     typename base_t::reference dereference() const
  65     {
  66         return p.self->m_queue[p.pos];
  67     }
  68
  69     void increment()
  70     {
  71         ++p.pos;
  72         if (p.pos == QueueT::MAX_SIZE+1)
  73             p.pos = 0;
  74     }
  75
  76     void decrement()
  77     {
  78         if (p.pos == 0)
  79             p.pos = QueueT::MAX_SIZE;
  80         else
  81             --p.pos;
  82     }
  83
  84     template <
  85         typename OtherDerivedT, typename OtherIteratorT,
  86         typename V, typename C, typename R, typename D
  87     >
  88     bool equal(iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
  89         const &x) const
  90     {
  91         position const &rhs_pos =
  92             static_cast<OtherDerivedT const &>(x).get_position();
  93         return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
  94     }
  95
  96     template <
  97         typename OtherDerivedT, typename OtherIteratorT,
  98         typename V, typename C, typename R, typename D
  99     >
 100     typename base_t::difference_type distance_to(
 101         iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
 102         const &x) const
 103     {
 104         typedef typename base_t::difference_type diff_t;
 105
 106         position const &p2 =
 107             static_cast<OtherDerivedT const &>(x).get_position();
 108         std::size_t pos1 = p.pos;
 109         std::size_t pos2 = p2.pos;
 110
 111         // Undefined behaviour if the iterators come from different
 112         //  containers
 113         BOOST_SPIRIT_ASSERT(p.self == p2.self);
 114
 115         if (pos1 < p.self->m_head)
 116             pos1 += QueueT::MAX_SIZE;
 117         if (pos2 < p2.self->m_head)
 118             pos2 += QueueT::MAX_SIZE;
 119
 120         if (pos2 > pos1)
 121             return diff_t(pos2 - pos1);
 122         else
 123             return -diff_t(pos1 - pos2);
 124     }
 125
 126     void advance(typename base_t::difference_type n)
 127     {
 128         // Notice that we don't care values of n that can
 129         //  wrap around more than one time, since it would
 130         //  be undefined behaviour anyway (going outside
 131         //  the begin/end range). Negative wrapping is a bit
 132         //  cumbersome because we don't want to case p.pos
 133         //  to signed.
 134         if (n < 0)
 135         {
 136             n = -n;
 137             if (p.pos < (std::size_t)n)
 138                 p.pos = QueueT::MAX_SIZE+1 - (n - p.pos);
 139             else
 140                 p.pos -= n;
 141         }
 142         else
 143         {
 144             p.pos += n;
 145             if (p.pos >= QueueT::MAX_SIZE+1)
 146                 p.pos -= QueueT::MAX_SIZE+1;
 147         }
 148     }
 149
 150 private:
 151     position p;
 152 };
 153
 154 #endif // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
 155
 156 ///////////////////////////////////////////////////////////////////////////////
 157 } /* namespace impl */
 158
 159 template <typename T, std::size_t N>
 160 class fixed_size_queue
 161 {
 162 private:
 163     struct position
 164     {
 165         fixed_size_queue* self;
 166         std::size_t pos;
 167
 168         position() : self(0), pos(0) {}
 169
 170         // The const_cast here is just to avoid to have two different
 171         //  position structures for the const and non-const case.
 172         // The const semantic is guaranteed by the iterator itself
 173         position(const fixed_size_queue* s, std::size_t p)
 174             : self(const_cast<fixed_size_queue*>(s)), pos(p)
 175         {}
 176     };
 177
 178 public:
 179     // Declare the iterators
 180     typedef impl::fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
 181     typedef impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
 182         const_iterator;
 183     typedef position position_t;
 184
 185     friend class impl::fsq_iterator<fixed_size_queue<T, N>, T, T*>;
 186     friend class impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>;
 187
 188     fixed_size_queue();
 189     fixed_size_queue(const fixed_size_queue& x);
 190     fixed_size_queue& operator=(const fixed_size_queue& x);
 191     ~fixed_size_queue();
 192
 193     void push_back(const T& e);
 194     void push_front(const T& e);
 195     void serve(T& e);
 196     void pop_front();
 197
 198     bool empty() const
 199     {
 200         return m_size == 0;
 201     }
 202
 203     bool full() const
 204     {
 205         return m_size == N;
 206     }
 207
 208     iterator begin()
 209     {
 210         return iterator(position(this, m_head));
 211     }
 212
 213     const_iterator begin() const
 214     {
 215         return const_iterator(position(this, m_head));
 216     }
 217
 218     iterator end()
 219     {
 220         return iterator(position(this, m_tail));
 221     }
 222
 223     const_iterator end() const
 224     {
 225         return const_iterator(position(this, m_tail));
 226     }
 227
 228     std::size_t size() const
 229     {
 230         return m_size;
 231     }
 232
 233     T& front()
 234     {
 235         return m_queue[m_head];
 236     }
 237
 238     const T& front() const
 239     {
 240         return m_queue[m_head];
 241     }
 242
 243 private:
 244     // Redefine the template parameters to avoid using partial template
 245     //  specialization on the iterator policy to extract N.
 246     BOOST_STATIC_CONSTANT(std::size_t, MAX_SIZE = N);
 247
 248     std::size_t m_head;
 249     std::size_t m_tail;
 250     std::size_t m_size;
 251     T m_queue[N+1];
 252 };
 253
 254 template <typename T, std::size_t N>
 255 inline
 256 fixed_size_queue<T, N>::fixed_size_queue()
 257     : m_head(0)
 258     , m_tail(0)
 259     , m_size(0)
 260 {
 261     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 262     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 263     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 264     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 265 }
 266
 267 template <typename T, std::size_t N>
 268 inline
 269 fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
 270     : m_head(x.m_head)
 271     , m_tail(x.m_tail)
 272     , m_size(x.m_size)
 273 {
 274     copy(x.begin(), x.end(), begin());
 275     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 276     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 277     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 278     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 279 }
 280
 281 template <typename T, std::size_t N>
 282 inline fixed_size_queue<T, N>&
 283 fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
 284 {
 285     if (this != &x)
 286     {
 287         m_head = x.m_head;
 288         m_tail = x.m_tail;
 289         m_size = x.m_size;
 290         copy(x.begin(), x.end(), begin());
 291     }
 292     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 293     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 294     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 295     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 296
 297     return *this;
 298 }
 299
 300 template <typename T, std::size_t N>
 301 inline
 302 fixed_size_queue<T, N>::~fixed_size_queue()
 303 {
 304     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 305     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 306     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 307     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 308 }
 309
 310 template <typename T, std::size_t N>
 311 inline void
 312 fixed_size_queue<T, N>::push_back(const T& e)
 313 {
 314     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 315     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 316     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 317     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 318
 319     BOOST_SPIRIT_ASSERT(!full());
 320
 321     m_queue[m_tail] = e;
 322     ++m_size;
 323     ++m_tail;
 324     if (m_tail == N+1)
 325         m_tail = 0;
 326
 327
 328     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 329     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 330     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 331     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 332 }
 333
 334 template <typename T, std::size_t N>
 335 inline void
 336 fixed_size_queue<T, N>::push_front(const T& e)
 337 {
 338     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 339     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 340     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 341     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 342
 343     BOOST_SPIRIT_ASSERT(!full());
 344
 345     if (m_head == 0)
 346         m_head = N;
 347     else
 348         --m_head;
 349
 350     m_queue[m_head] = e;
 351     ++m_size;
 352
 353     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 354     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 355     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 356     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 357 }
 358
 359
 360 template <typename T, std::size_t N>
 361 inline void
 362 fixed_size_queue<T, N>::serve(T& e)
 363 {
 364     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 365     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 366     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 367     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 368
 369     e = m_queue[m_head];
 370     pop_front();
 371 }
 372
 373
 374
 375 template <typename T, std::size_t N>
 376 inline void
 377 fixed_size_queue<T, N>::pop_front()
 378 {
 379     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 380     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 381     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 382     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 383
 384     ++m_head;
 385     if (m_head == N+1)
 386         m_head = 0;
 387     --m_size;
 388
 389     BOOST_SPIRIT_ASSERT(m_size <= N+1);
 390     BOOST_SPIRIT_ASSERT_FSQ_SIZE;
 391     BOOST_SPIRIT_ASSERT(m_head <= N+1);
 392     BOOST_SPIRIT_ASSERT(m_tail <= N+1);
 393 }
 394
 395 ///////////////////////////////////////////////////////////////////////////////
 396 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
 397
 398 }} // namespace BOOST_SPIRIT_CLASSIC_NS
 399
 400 #undef BOOST_SPIRIT_ASSERT_FSQ_SIZE
 401
 402 #endif