circlebuf.hh (12334:e0ab29a34764) circlebuf.hh (13483:0d5d061d974f)
1/*
1/*
2 * Copyright (c) 2015 ARM Limited
2 * Copyright (c) 2015,2017-2018 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

--- 28 unchanged lines hidden (view full) ---

39
40#ifndef __BASE_CIRCLEBUF_HH__
41#define __BASE_CIRCLEBUF_HH__
42
43#include <algorithm>
44#include <cassert>
45#include <vector>
46
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

--- 28 unchanged lines hidden (view full) ---

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/circular_queue.hh"
47#include "base/logging.hh"
48#include "sim/serialize.hh"
49
50/**
48#include "base/logging.hh"
49#include "sim/serialize.hh"
50
51/**
51 * Circular buffer backed by a vector
52 * Circular buffer backed by a vector though a CircularQueue.
52 *
53 * The data in the cricular buffer is stored in a standard
53 *
54 * 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.
55 * vector.
59 *
56 *
60 * Invariants:
61 * <ul>
62 * <li>_start <= _stop
63 * <li>_start < capacity
64 * <li>_stop < 2 * capacity
65 * </ul>
66 */
67template<typename T>
57 */
58template<typename T>
68class CircleBuf
59class CircleBuf : public CircularQueue<T>
69{
70 public:
60{
61 public:
71 typedef T value_type;
72
73 public:
74 explicit CircleBuf(size_t size)
62 explicit CircleBuf(size_t size)
75 : buf(size), _start(0), _stop(0) {}
63 : CircularQueue<T>(size) {}
64 using CircularQueue<T>::empty;
65 using CircularQueue<T>::size;
66 using CircularQueue<T>::capacity;
67 using CircularQueue<T>::begin;
68 using CircularQueue<T>::end;
69 using CircularQueue<T>::pop_front;
70 using CircularQueue<T>::advance_tail;
76
71
77 /** Is the buffer empty? */
78 bool empty() const { return _stop == _start; }
79 /**
72 /**
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);

--- 6 unchanged lines hidden (view full) ---

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
73 * Copy buffer contents without advancing the read pointer
74 *
75 * @param out Output iterator/pointer
76 * @param len Number of elements to copy
77 */
78 template <class OutputIterator>
79 void peek(OutputIterator out, size_t len) const {
80 peek(out, 0, len);

--- 6 unchanged lines hidden (view full) ---

87 * @param offset Offset into the ring buffer
88 * @param len Number of elements to copy
89 */
90 template <class OutputIterator>
91 void peek(OutputIterator out, off_t offset, size_t len) const {
92 panic_if(offset + len > size(),
93 "Trying to read past end of circular buffer.\n");
94
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 }
95 std::copy(begin() + offset, begin() + offset + len, out);
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);
96 }
97
98 /**
99 * Copy buffer contents and advance the read pointer
100 *
101 * @param out Output iterator/pointer
102 * @param len Number of elements to read
103 */
104 template <class OutputIterator>
105 void read(OutputIterator out, size_t len) {
106 peek(out, len);
145
146 _start += len;
147 normalize();
107 pop_front(len);
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.
108 }
109
110 /**
111 * Add elements to the end of the ring buffers and advance.
112 *
113 * @param in Input iterator/pointer
114 * @param len Number of elements to read
115 */
116 template <class InputIterator>
117 void write(InputIterator in, size_t len) {
118 // Writes that are larger than the backing store are allowed,
119 // 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();
120 if (len > capacity()) {
121 in += len - capacity();
122 len = capacity();
163 }
164
123 }
124
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();
125 std::copy(in, in + len, end());
126 advance_tail(len);
179 }
127 }
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
128};
129
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

--- 84 unchanged lines hidden --- 		130/**
131 * Simple FIFO implementation backed by a circular buffer.
132 *
133 * This class provides the same basic functionallity as the circular
134 * buffer with the folling differences:
135 * <ul>
136 * <li>Writes are checked to ensure that overflows can't happen.
137 * <li>Unserialization ensures that the data in the checkpoint fits

--- 84 unchanged lines hidden ---