git.sesse.net Git - casparcg/blob - dependencies/boost/boost/spirit/home/support/iterators/detail/fixed_size_queue.hpp

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