Pyrogenesis  trunk
ring_buf.h
Go to the documentation of this file.
1 /* Copyright (C) 2011 Wildfire Games.
2  *
3  * Permission is hereby granted, free of charge, to any person obtaining
4  * a copy of this software and associated documentation files (the
5  * "Software"), to deal in the Software without restriction, including
6  * without limitation the rights to use, copy, modify, merge, publish,
7  * distribute, sublicense, and/or sell copies of the Software, and to
8  * permit persons to whom the Software is furnished to do so, subject to
9  * the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included
12  * in all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21  */
22 
23 /*
24  * static array, accessible modulo n
25  */
26 
27 #ifndef INCLUDED_ADTS_RING_BUF
28 #define INCLUDED_ADTS_RING_BUF
29 
30 template<class T, size_t n> class RingBuf
31 {
32  size_t size_; // # of entries in buffer
33  size_t head; // index of oldest item
34  size_t tail; // index of newest item
35  T data[n];
36 
37 public:
38  RingBuf() : data() { clear(); }
39  void clear() { size_ = 0; head = 0; tail = n-1; }
40 
41  size_t size() const { return size_; }
42  bool empty() const { return size_ == 0; }
43 
44  const T& operator[](int ofs) const
45  {
46  ENSURE(!empty());
47  size_t idx = (size_t)(head + ofs);
48  return data[idx % n];
49  }
50  T& operator[](int ofs)
51  {
52  ENSURE(!empty());
53  size_t idx = (size_t)(head + ofs);
54  return data[idx % n];
55  }
56 
57  T& front()
58  {
59  ENSURE(!empty());
60  return data[head];
61  }
62  const T& front() const
63  {
64  ENSURE(!empty());
65  return data[head];
66  }
67  T& back()
68  {
69  ENSURE(!empty());
70  return data[tail];
71  }
72  const T& back() const
73  {
74  ENSURE(!empty());
75  return data[tail];
76  }
77 
78  void push_back(const T& item)
79  {
80  if(size_ < n)
81  size_++;
82  // do not complain - overwriting old values is legit
83  // (e.g. sliding window).
84  else
85  head = (head + 1) % n;
86 
87  tail = (tail + 1) % n;
88  data[tail] = item;
89  }
90 
91  void pop_front()
92  {
93  if(size_ != 0)
94  {
95  size_--;
96  head = (head + 1) % n;
97  }
98  else
99  DEBUG_WARN_ERR(ERR::LOGIC); // underflow
100  }
101 
102  class iterator
103  {
104  public:
105  typedef std::random_access_iterator_tag iterator_category;
106  typedef T value_type;
107  typedef ptrdiff_t difference_type;
108  typedef T* pointer;
109  typedef T& reference;
110 
111  iterator() : data(0), pos(0)
112  {}
113  iterator(T* data_, size_t pos_) : data(data_), pos(pos_)
114  {}
115  T& operator[](int idx) const
116  { return data[(pos+idx) % n]; }
117  T& operator*() const
118  { return data[pos % n]; }
119  T* operator->() const
120  { return &**this; }
122  { ++pos; return (*this); }
123  iterator operator++(int) // post
124  { iterator tmp = *this; ++*this; return tmp; }
125  bool operator==(const iterator& rhs) const
126  { return data == rhs.data && pos == rhs.pos; }
127  bool operator!=(const iterator& rhs) const
128  { return !(*this == rhs); }
129  bool operator<(const iterator& rhs) const
130  { return (pos < rhs.pos); }
131  iterator& operator+=(difference_type ofs)
132  { pos += ofs; return *this; }
133  iterator& operator-=(difference_type ofs)
134  { return (*this += -ofs); }
135  iterator operator+(difference_type ofs) const
136  { iterator tmp = *this; return (tmp += ofs); }
137  iterator operator-(difference_type ofs) const
138  { iterator tmp = *this; return (tmp -= ofs); }
139  difference_type operator-(const iterator right) const
140  { return (difference_type)(pos - right.pos); }
141 
142  protected:
143  T* data;
144  size_t pos;
145  // not mod-N so that begin != end when buffer is full.
146  };
147 
149  {
150  public:
151  typedef std::random_access_iterator_tag iterator_category;
152  typedef T value_type;
153  typedef ptrdiff_t difference_type;
154  typedef const T* pointer;
155  typedef const T& reference;
156 
157  const_iterator() : data(0), pos(0)
158  {}
159  const_iterator(const T* data_, size_t pos_) : data(data_), pos(pos_)
160  {}
161  const T& operator[](int idx) const
162  { return data[(pos+idx) % n]; }
163  const T& operator*() const
164  { return data[pos % n]; }
165  const T* operator->() const
166  { return &**this; }
168  { ++pos; return (*this); }
170  { const_iterator tmp = *this; ++*this; return tmp; }
171  bool operator==(const const_iterator& rhs) const
172  { return data == rhs.data && pos == rhs.pos; }
173  bool operator!=(const const_iterator& rhs) const
174  { return !(*this == rhs); }
175  bool operator<(const const_iterator& rhs) const
176  { return (pos < rhs.pos); }
177  iterator& operator+=(difference_type ofs)
178  { pos += ofs; return *this; }
179  iterator& operator-=(difference_type ofs)
180  { return (*this += -ofs); }
181  iterator operator+(difference_type ofs) const
182  { iterator tmp = *this; return (tmp += ofs); }
183  iterator operator-(difference_type ofs) const
184  { iterator tmp = *this; return (tmp -= ofs); }
185  difference_type operator-(const iterator right) const
186  { return (difference_type)(pos - right.pos); }
187 
188  protected:
189  const T* data;
190  size_t pos;
191  // not mod-N so that begin != end when buffer is full.
192  };
193 
195  {
196  return iterator(data, head);
197  }
198  const_iterator begin() const
199  {
200  return const_iterator(data, head);
201  }
203  {
204  return iterator(data, head+size_);
205  }
206  const_iterator end() const
207  {
208  return const_iterator(data, head+size_);
209  }
210 };
211 
212 #endif // #ifndef INCLUDED_ADTS_RING_BUF
size_t pos
Definition: ring_buf.h:190
const Status LOGIC
Definition: status.h:407
bool operator!=(const iterator &rhs) const
Definition: ring_buf.h:127
T * pointer
Definition: ring_buf.h:108
size_t size() const
Definition: ring_buf.h:41
const_iterator(const T *data_, size_t pos_)
Definition: ring_buf.h:159
T * operator->() const
Definition: ring_buf.h:119
const T & operator[](int idx) const
Definition: ring_buf.h:161
const T * operator->() const
Definition: ring_buf.h:165
T & operator*() const
Definition: ring_buf.h:117
bool operator!=(const const_iterator &rhs) const
Definition: ring_buf.h:173
ptrdiff_t difference_type
Definition: ring_buf.h:153
bool operator==(const const_iterator &rhs) const
Definition: ring_buf.h:171
const T & operator[](int ofs) const
Definition: ring_buf.h:44
bool operator<(const const_iterator &rhs) const
Definition: ring_buf.h:175
Definition: ring_buf.h:148
const_iterator begin() const
Definition: ring_buf.h:198
std::random_access_iterator_tag iterator_category
Definition: ring_buf.h:105
iterator & operator-=(difference_type ofs)
Definition: ring_buf.h:133
void clear()
Definition: ring_buf.h:39
T * data
Definition: ring_buf.h:143
const T * data
Definition: ring_buf.h:189
const T * pointer
Definition: ring_buf.h:154
iterator operator-(difference_type ofs) const
Definition: ring_buf.h:137
std::random_access_iterator_tag iterator_category
Definition: ring_buf.h:151
const_iterator end() const
Definition: ring_buf.h:206
void push_back(const T &item)
Definition: ring_buf.h:78
const_iterator operator++(int)
Definition: ring_buf.h:169
ptrdiff_t difference_type
Definition: ring_buf.h:107
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:290
iterator & operator+=(difference_type ofs)
Definition: ring_buf.h:131
RingBuf()
Definition: ring_buf.h:38
iterator begin()
Definition: ring_buf.h:194
T & reference
Definition: ring_buf.h:109
const T & reference
Definition: ring_buf.h:155
iterator operator+(difference_type ofs) const
Definition: ring_buf.h:135
iterator & operator-=(difference_type ofs)
Definition: ring_buf.h:179
size_t pos
Definition: ring_buf.h:144
difference_type operator-(const iterator right) const
Definition: ring_buf.h:185
const T & back() const
Definition: ring_buf.h:72
iterator end()
Definition: ring_buf.h:202
iterator(T *data_, size_t pos_)
Definition: ring_buf.h:113
T value_type
Definition: ring_buf.h:106
#define T(string_literal)
Definition: secure_crt.cpp:77
iterator operator+(difference_type ofs) const
Definition: ring_buf.h:181
iterator operator-(difference_type ofs) const
Definition: ring_buf.h:183
size_t size_
Definition: ring_buf.h:32
#define DEBUG_WARN_ERR(status)
display the error dialog with text corresponding to the given error code.
Definition: debug.h:339
T & operator[](int ofs)
Definition: ring_buf.h:50
const T & operator*() const
Definition: ring_buf.h:163
const_iterator()
Definition: ring_buf.h:157
difference_type operator-(const iterator right) const
Definition: ring_buf.h:139
const_iterator & operator++()
Definition: ring_buf.h:167
T value_type
Definition: ring_buf.h:152
iterator & operator++()
Definition: ring_buf.h:121
bool empty() const
Definition: ring_buf.h:42
iterator & operator+=(difference_type ofs)
Definition: ring_buf.h:177
Definition: ring_buf.h:102
T & operator[](int idx) const
Definition: ring_buf.h:115
size_t head
Definition: ring_buf.h:33
size_t tail
Definition: ring_buf.h:34
iterator operator++(int)
Definition: ring_buf.h:123
void pop_front()
Definition: ring_buf.h:91
bool operator==(const iterator &rhs) const
Definition: ring_buf.h:125
iterator()
Definition: ring_buf.h:111
T & front()
Definition: ring_buf.h:57
Definition: ring_buf.h:30
const T & front() const
Definition: ring_buf.h:62
bool operator<(const iterator &rhs) const
Definition: ring_buf.h:129
T & back()
Definition: ring_buf.h:67
T data[n]
Definition: ring_buf.h:35