circlebuf.hh revision 12032:d218c2fe9440 
1/*
2 * Copyright (c) 2015 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Andreas Sandberg
38 */
39
40#ifndef __BASE_CIRCLEBUF_HH__
41#define __BASE_CIRCLEBUF_HH__
42
43#include <algorithm>
44#include <cassert>
45#include <vector>
46
47#include "base/misc.hh"
48#include "sim/serialize.hh"
49
50/**
51 * Circular buffer backed by a vector
52 *
53 * The data in the cricular buffer is stored in a standard
54 * vector. _start designates the first element in the buffer and _stop
55 * points to the last element + 1 (i.e., the position of the next
56 * insertion). The _stop index may be outside the range of the backing
57 * store, which means that the actual index must be calculated as
58 * _stop % capacity.
59 *
60 * Invariants:
61 * <ul>
62 *   <li>_start <= _stop
63 *   <li>_start < capacity
64 *   <li>_stop < 2 * capacity
65 * </ul>
66 */
67template<typename T>
68class CircleBuf
69{
70  public:
71    typedef T value_type;
72
73  public:
74    explicit CircleBuf(size_t size)
75        : buf(size), _start(0), _stop(0) {}
76
77    /** Is the buffer empty? */
78    bool empty() const { return _stop == _start; }
79    /**
80     * Return the maximum number of elements that can be stored in
81     * the buffer at any one time.
82     */
83    size_t capacity() const { return buf.size(); }
84    /** Return the number of elements stored in the buffer. */
85    size_t size() const { return _stop - _start; }
86
87    /**
88     * Remove all the elements in the buffer.
89     *
90     * Note: This does not actually remove elements from the backing
91     * store.
92     */
93    void flush() {
94        _start = 0;
95        _stop = 0;
96    }
97
98    /**
99     * Copy buffer contents without advancing the read pointer
100     *
101     * @param out Output iterator/pointer
102     * @param len Number of elements to copy
103     */
104    template <class OutputIterator>
105    void peek(OutputIterator out, size_t len) const {
106        peek(out, 0, len);
107    }
108
109    /**
110     * Copy buffer contents without advancing the read pointer
111     *
112     * @param out Output iterator/pointer
113     * @param offset Offset into the ring buffer
114     * @param len Number of elements to copy
115     */
116    template <class OutputIterator>
117    void peek(OutputIterator out, off_t offset, size_t len) const {
118        panic_if(offset + len > size(),
119                 "Trying to read past end of circular buffer.\n");
120
121        const off_t real_start((offset + _start) % buf.size());
122        if (real_start + len <= buf.size()) {
123            std::copy(buf.begin() + real_start,
124                      buf.begin() + real_start + len,
125                      out);
126        } else {
127            const size_t head_size(buf.size() - real_start);
128            const size_t tail_size(len - head_size);
129            std::copy(buf.begin() + real_start, buf.end(),
130                      out);
131            std::copy(buf.begin(), buf.begin() + tail_size,
132                      out + head_size);
133        }
134    }
135
136    /**
137     * Copy buffer contents and advance the read pointer
138     *
139     * @param out Output iterator/pointer
140     * @param len Number of elements to read
141     */
142    template <class OutputIterator>
143    void read(OutputIterator out, size_t len) {
144        peek(out, len);
145
146        _start += len;
147        normalize();
148    }
149
150    /**
151     * Add elements to the end of the ring buffers and advance.
152     *
153     * @param in Input iterator/pointer
154     * @param len Number of elements to read
155     */
156    template <class InputIterator>
157    void write(InputIterator in, size_t len) {
158        // Writes that are larger than the backing store are allowed,
159        // but only the last part of the buffer will be written.
160        if (len > buf.size()) {
161            in += len - buf.size();
162            len = buf.size();
163        }
164
165        const size_t next(_stop % buf.size());
166        const size_t head_len(std::min(buf.size() - next, len));
167
168        std::copy(in, in + head_len, buf.begin() + next);
169        std::copy(in + head_len, in + len, buf.begin());
170
171        _stop += len;
172        // We may have written past the old _start pointer. Readjust
173        // the _start pointer to remove the oldest entries in that
174        // case.
175        if (size() > buf.size())
176            _start = _stop - buf.size();
177
178        normalize();
179    }
180
181  protected:
182    /**
183     * Normalize the start and stop pointers to ensure that pointer
184     * invariants hold after updates.
185     */
186    void normalize() {
187        if (_start >= buf.size()) {
188            _stop -= buf.size();
189            _start -= buf.size();
190        }
191
192        assert(_start < buf.size());
193        assert(_stop < 2 * buf.size());
194        assert(_start <= _stop);
195    }
196
197  protected:
198    std::vector<value_type> buf;
199    size_t _start;
200    size_t _stop;
201
202};
203
204
205/**
206 * Simple FIFO implementation backed by a circular buffer.
207 *
208 * This class provides the same basic functionallity as the circular
209 * buffer with the folling differences:
210 * <ul>
211 *    <li>Writes are checked to ensure that overflows can't happen.
212 *    <li>Unserialization ensures that the data in the checkpoint fits
213 *        in the buffer.
214 * </ul>
215 */
216template<typename T>
217class Fifo
218{
219  public:
220    typedef T value_type;
221
222  public:
223    Fifo(size_t size)
224        : buf(size) {}
225
226    bool empty() const { return buf.empty(); }
227    size_t size() const { return buf.size(); }
228    size_t capacity() const { return buf.capacity(); }
229
230    void flush() { buf.flush(); }
231
232    template <class OutputIterator>
233    void peek(OutputIterator out, size_t len) const { buf.peek(out, len); }
234    template <class OutputIterator>
235    void read(OutputIterator out, size_t len) { buf.read(out, len); }
236
237    template <class InputIterator>
238    void write(InputIterator in, size_t len) {
239        panic_if(size() + len > capacity(),
240                 "Trying to overfill FIFO buffer.\n");
241        buf.write(in, len);
242    }
243
244  private:
245    CircleBuf<value_type> buf;
246};
247
248
249template <typename T>
250void
251arrayParamOut(CheckpointOut &cp, const std::string &name,
252              const CircleBuf<T> &param)
253{
254    std::vector<T> temp(param.size());
255    param.peek(temp.begin(), temp.size());
256    arrayParamOut(cp, name, temp);
257}
258
259template <typename T>
260void
261arrayParamIn(CheckpointIn &cp, const std::string &name,
262             CircleBuf<T> &param)
263{
264    std::vector<T> temp;
265    arrayParamIn(cp, name, temp);
266
267    param.flush();
268    param.write(temp.cbegin(), temp.size());
269}
270
271template <typename T>
272void
273arrayParamOut(CheckpointOut &cp, const std::string &name,
274              const Fifo<T> &param)
275{
276    std::vector<T> temp(param.size());
277    param.peek(temp.begin(), temp.size());
278    arrayParamOut(cp, name, temp);
279}
280
281template <typename T>
282void
283arrayParamIn(CheckpointIn &cp, const std::string &name,
284             Fifo<T> &param)
285{
286    std::vector<T> temp;
287    arrayParamIn(cp, name, temp);
288
289    fatal_if(param.capacity() < temp.size(),
290             "Trying to unserialize data into too small FIFO\n");
291
292    param.flush();
293    param.write(temp.cbegin(), temp.size());
294}
295
296#endif // __BASE_CIRCLEBUF_HH__
297