| Line | Branch | Decision | Exec | Source |
|---|---|---|---|---|
| 1 | /** | |||
| 2 | * @file cyclic_buffer.h | |||
| 3 | * @brief A cyclic buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. | |||
| 4 | * | |||
| 5 | * http://en.wikipedia.org/wiki/Circular_buffer | |||
| 6 | * | |||
| 7 | * @date Dec 8, 2013 | |||
| 8 | * @author Andrey Belomutskiy, Daniel Hill | |||
| 9 | * | |||
| 10 | * Daniel Hill - Modified to use C++ - Mar 2, 2014 | |||
| 11 | */ | |||
| 12 | ||||
| 13 | #pragma once | |||
| 14 | ||||
| 15 | #include <limits> | |||
| 16 | #include <string.h> | |||
| 17 | #include <stdint.h> | |||
| 18 | ||||
| 19 | static const short CB_MAX_SIZE = 128; | |||
| 20 | ||||
| 21 | template<typename T, size_t maxSize = CB_MAX_SIZE> | |||
| 22 | class cyclic_buffer | |||
| 23 | { | |||
| 24 | public: | |||
| 25 | cyclic_buffer(); | |||
| 26 | explicit cyclic_buffer(int size); | |||
| 27 | ||||
| 28 | public: | |||
| 29 | void add(T value); | |||
| 30 | T get(int index) const; | |||
| 31 | T sum(size_t length) const; | |||
| 32 | T maxValue(size_t length) const; | |||
| 33 | T minValue(size_t length) const; | |||
| 34 | void setSize(size_t size); | |||
| 35 | bool contains(T value) const; | |||
| 36 | int getSize() const; | |||
| 37 | int getCount() const; | |||
| 38 | void clear(); | |||
| 39 | T elements[maxSize]; | |||
| 40 | uint16_t currentIndex; | |||
| 41 | ||||
| 42 | protected: | |||
| 43 | uint16_t size; | |||
| 44 | /** | |||
| 45 | * number of elements added into this buffer, would be eventually bigger then size | |||
| 46 | */ | |||
| 47 | size_t count; | |||
| 48 | }; | |||
| 49 | ||||
| 50 | template<typename T, size_t maxSize> | |||
| 51 | 1454 | cyclic_buffer<T, maxSize>::cyclic_buffer() : cyclic_buffer(maxSize) { | ||
| 52 | 1454 | } | ||
| 53 | ||||
| 54 | template<typename T, size_t maxSize> | |||
| 55 | 1454 | cyclic_buffer<T, maxSize>::cyclic_buffer(int p_size) { | ||
| 56 | 1454 | setSize(p_size); | ||
| 57 | 1454 | } | ||
| 58 | ||||
| 59 | template<typename T, size_t maxSize> | |||
| 60 | 75276 | void cyclic_buffer<T, maxSize>::add(T value) { | ||
| 61 | // Too lazy to make this thread safe, but at the very least let's never let currentIndex | |||
| 62 | // become invalid. And yes I did see a crash due to an overrun here. | |||
| 63 | 75276 | uint16_t idx = currentIndex; | ||
| 64 | ||||
| 65 | 75276 | ((T &)elements[idx]) = value; | ||
| 66 | ||||
| 67 |
10/14cyclic_buffer<unsigned char, 76ul>::add(unsigned char):
✗ Branch 0 not taken.
✓ Branch 1 taken 282 times.
cyclic_buffer<CanRxMessage, 8ul>::add(CanRxMessage):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
cyclic_buffer<int, 128ul>::add(int):
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 5059 times.
cyclic_buffer<int, 4ul>::add(int):
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 6 times.
cyclic_buffer<float, 128ul>::add(float):
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 991 times.
cyclic_buffer<double, 720ul>::add(double):
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 68642 times.
cyclic_buffer<CANTxFrame, 1024ul>::add(CANTxFrame):
✗ Branch 0 not taken.
✓ Branch 1 taken 73 times.
|
10/14cyclic_buffer<unsigned char, 76ul>::add(unsigned char):
✗ Decision 'true' not taken.
✓ Decision 'false' taken 282 times.
cyclic_buffer<CanRxMessage, 8ul>::add(CanRxMessage):
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
cyclic_buffer<int, 128ul>::add(int):
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 5059 times.
cyclic_buffer<int, 4ul>::add(int):
✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 6 times.
cyclic_buffer<float, 128ul>::add(float):
✓ Decision 'true' taken 122 times.
✓ Decision 'false' taken 991 times.
cyclic_buffer<double, 720ul>::add(double):
✓ Decision 'true' taken 74 times.
✓ Decision 'false' taken 68642 times.
cyclic_buffer<CANTxFrame, 1024ul>::add(CANTxFrame):
✗ Decision 'true' not taken.
✓ Decision 'false' taken 73 times.
|
75276 | if (++idx == size) { |
| 68 | 223 | idx = 0; | ||
| 69 | } | |||
| 70 | 75276 | currentIndex = idx; | ||
| 71 | ||||
| 72 | 75276 | count = count + 1; | ||
| 73 | 75276 | } | ||
| 74 | ||||
| 75 | // todo: something is weird see 'TEST(CyclicBuffer, Contains)' see https://github.com/rusefi/rusefi/issues/4455 | |||
| 76 | template<typename T, size_t maxSize> | |||
| 77 | 17 | bool cyclic_buffer<T, maxSize>::contains(T value) const { | ||
| 78 |
4/4cyclic_buffer<int, 128ul>::contains(int) const:
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 time.
cyclic_buffer<int, 4ul>::contains(int) const:
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 11 times.
|
4/4cyclic_buffer<int, 128ul>::contains(int) const:
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 time.
cyclic_buffer<int, 4ul>::contains(int) const:
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 11 times.
|
36 | for (int i = 0; i < currentIndex ; i++) { |
| 79 |
4/4cyclic_buffer<int, 128ul>::contains(int) const:
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
cyclic_buffer<int, 4ul>::contains(int) const:
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 18 times.
|
4/4cyclic_buffer<int, 128ul>::contains(int) const:
✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 1 time.
cyclic_buffer<int, 4ul>::contains(int) const:
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 18 times.
|
24 | if (elements[i] == value) { |
| 80 | 5 | return true; | ||
| 81 | } | |||
| 82 | } | |||
| 83 | 12 | return false; | ||
| 84 | } | |||
| 85 | ||||
| 86 | template<typename T, size_t maxSize> | |||
| 87 | 2137 | void cyclic_buffer<T, maxSize>::setSize(size_t p_size) { | ||
| 88 | 2137 | clear(); | ||
| 89 | 2137 | size = p_size < maxSize ? p_size : maxSize; | ||
| 90 | 2137 | } | ||
| 91 | ||||
| 92 | template<typename T, size_t maxSize> | |||
| 93 | 1498 | int cyclic_buffer<T, maxSize>::getSize() const { | ||
| 94 | 1498 | return size; | ||
| 95 | } | |||
| 96 | ||||
| 97 | template<typename T, size_t maxSize> | |||
| 98 | 1684 | int cyclic_buffer<T, maxSize>::getCount() const { | ||
| 99 | 1684 | return count; | ||
| 100 | } | |||
| 101 | ||||
| 102 | template<typename T, size_t maxSize> | |||
| 103 | 5000 | T cyclic_buffer<T, maxSize>::get(int index) const { | ||
| 104 |
2/4cyclic_buffer<float, 128ul>::get(int) const:
✓ Branch 0 taken 2609 times.
✓ Branch 1 taken 5000 times.
cyclic_buffer<double, 720ul>::get(int) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
2/4cyclic_buffer<float, 128ul>::get(int) const:
✓ Decision 'true' taken 2609 times.
✓ Decision 'false' taken 5000 times.
cyclic_buffer<double, 720ul>::get(int) const:
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
|
7609 | while (index < 0) { |
| 105 | 2609 | index += size; | ||
| 106 | } | |||
| 107 |
1/4cyclic_buffer<float, 128ul>::get(int) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 5000 times.
cyclic_buffer<double, 720ul>::get(int) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
1/4cyclic_buffer<float, 128ul>::get(int) const:
✗ Decision 'true' not taken.
✓ Decision 'false' taken 5000 times.
cyclic_buffer<double, 720ul>::get(int) const:
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
|
5000 | while (index >= size) { |
| 108 | ✗ | index -= size; | ||
| 109 | } | |||
| 110 | 5000 | return elements[index]; | ||
| 111 | } | |||
| 112 | ||||
| 113 | template<typename T, size_t maxSize> | |||
| 114 | 2 | T cyclic_buffer<T, maxSize>::maxValue(size_t length) const { | ||
| 115 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 1 time.
|
2 | if (length > count) { |
| 116 | // not enough data in buffer | |||
| 117 | 1 | length = count; | ||
| 118 | } | |||
| 119 | 2 | int ci = currentIndex; // local copy to increase thread-safety | ||
| 120 | 2 | T result = std::numeric_limits<T>::min(); | ||
| 121 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 2 times.
|
2/2✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 2 times.
|
9 | for (size_t i = 0; i < length; ++i) { |
| 122 | 7 | int index = ci - i - 1; | ||
| 123 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7 times.
|
7 | while (index < 0) { |
| 124 | ✗ | index += size; | ||
| 125 | } | |||
| 126 | ||||
| 127 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 5 times.
|
2/2✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 5 times.
|
7 | if (elements[index] > result) { |
| 128 | 2 | result = elements[index]; | ||
| 129 | } | |||
| 130 | } | |||
| 131 | 2 | return result; | ||
| 132 | } | |||
| 133 | ||||
| 134 | template<typename T, size_t maxSize> | |||
| 135 | 2 | T cyclic_buffer<T, maxSize>::minValue(size_t length) const { | ||
| 136 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 1 time.
|
2 | if (length > count) { |
| 137 | 1 | length = count; | ||
| 138 | } | |||
| 139 | 2 | int ci = currentIndex; // local copy to increase thread-safety | ||
| 140 | 2 | T result = std::numeric_limits<T>::max(); | ||
| 141 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 2 times.
|
2/2✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 2 times.
|
9 | for (size_t i = 0; i < length; ++i) { |
| 142 | 7 | int index = ci - i - 1; | ||
| 143 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7 times.
|
7 | while (index < 0) { |
| 144 | ✗ | index += size; | ||
| 145 | } | |||
| 146 | ||||
| 147 |
1/2✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
|
1/2✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
|
7 | if (elements[index] < result) { |
| 148 | 7 | result = elements[index]; | ||
| 149 | } | |||
| 150 | } | |||
| 151 | 2 | return result; | ||
| 152 | } | |||
| 153 | ||||
| 154 | template<typename T, size_t maxSize> | |||
| 155 | 2 | T cyclic_buffer<T, maxSize>::sum(size_t length) const { | ||
| 156 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
|
2/2✓ Decision 'true' taken 1 time.
✓ Decision 'false' taken 1 time.
|
2 | if (length > count) { |
| 157 | 1 | length = count; | ||
| 158 | } | |||
| 159 | ||||
| 160 | 2 | int ci = currentIndex; // local copy to increase thread-safety | ||
| 161 | 2 | T result = 0; | ||
| 162 | ||||
| 163 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
|
2/2✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 2 times.
|
5 | for (size_t i = 0; i < length; ++i) { |
| 164 | 3 | int index = ci - i - 1; | ||
| 165 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 3 times.
|
3 | while (index < 0) { |
| 166 | ✗ | index += size; | ||
| 167 | } | |||
| 168 | ||||
| 169 | 3 | result += elements[index]; | ||
| 170 | } | |||
| 171 | ||||
| 172 | 2 | return result; | ||
| 173 | } | |||
| 174 | ||||
| 175 | template<typename T, size_t maxSize> | |||
| 176 | 3768 | void cyclic_buffer<T, maxSize>::clear() { | ||
| 177 | 3768 | memset((void*) elements, 0, sizeof(elements)); // I would usually use static_cast, but due to the elements being volatile we cannot. | ||
| 178 | 3768 | count = 0; | ||
| 179 | 3768 | currentIndex = 0; | ||
| 180 | 3768 | } | ||
| 181 |