Line data Source code
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 3 : RingBuf() : data() { clear(); }
39 3 : void clear() { size_ = 0; head = 0; tail = n-1; }
40 :
41 1003 : size_t size() const { return size_; }
42 151 : 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 149 : T& front()
58 : {
59 149 : ENSURE(!empty());
60 149 : 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 898 : void push_back(const T& item)
79 : {
80 898 : if(size_ < n)
81 496 : size_++;
82 : // do not complain - overwriting old values is legit
83 : // (e.g. sliding window).
84 : else
85 402 : head = (head + 1) % n;
86 :
87 898 : tail = (tail + 1) % n;
88 898 : data[tail] = item;
89 898 : }
90 :
91 448 : void pop_front()
92 : {
93 448 : if(size_ != 0)
94 : {
95 448 : size_--;
96 448 : head = (head + 1) % n;
97 : }
98 : else
99 0 : DEBUG_WARN_ERR(ERR::LOGIC); // underflow
100 448 : }
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 2000 : iterator(T* data_, size_t pos_) : data(data_), pos(pos_)
114 2000 : {}
115 : T& operator[](int idx) const
116 : { return data[(pos+idx) % n]; }
117 44434 : T& operator*() const
118 44434 : { return data[pos % n]; }
119 : T* operator->() const
120 : { return &**this; }
121 44434 : iterator& operator++() // pre
122 44434 : { ++pos; return (*this); }
123 : iterator operator++(int) // post
124 : { iterator tmp = *this; ++*this; return tmp; }
125 45434 : bool operator==(const iterator& rhs) const
126 45434 : { return data == rhs.data && pos == rhs.pos; }
127 45434 : bool operator!=(const iterator& rhs) const
128 45434 : { 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 :
148 : class const_iterator
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 0 : const_iterator(const T* data_, size_t pos_) : data(data_), pos(pos_)
160 0 : {}
161 : const T& operator[](int idx) const
162 : { return data[(pos+idx) % n]; }
163 0 : const T& operator*() const
164 0 : { return data[pos % n]; }
165 : const T* operator->() const
166 : { return &**this; }
167 0 : const_iterator& operator++() // pre
168 0 : { ++pos; return (*this); }
169 : const_iterator operator++(int) // post
170 : { const_iterator tmp = *this; ++*this; return tmp; }
171 0 : bool operator==(const const_iterator& rhs) const
172 0 : { return data == rhs.data && pos == rhs.pos; }
173 0 : bool operator!=(const const_iterator& rhs) const
174 0 : { 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 :
194 1000 : iterator begin()
195 : {
196 1000 : return iterator(data, head);
197 : }
198 0 : const_iterator begin() const
199 : {
200 0 : return const_iterator(data, head);
201 : }
202 1000 : iterator end()
203 : {
204 1000 : return iterator(data, head+size_);
205 : }
206 0 : const_iterator end() const
207 : {
208 0 : return const_iterator(data, head+size_);
209 : }
210 : };
211 :
212 : #endif // #ifndef INCLUDED_ADTS_RING_BUF
|
