I have a buffer implemented as a fixed-size std::vector with two begin and end pointers dedicated for delimiting the low and the high boundary for the values in the ring buffer.
The first inserted value gets the index 0 in the vector. The next values gets assigned as indexes, the difference with the value pointed by the begin pointer.
Example with a buffer of size 5:
empty buffer:
|0|0|0|0|0|
begin = end = nullptr
add value 3:
|3|0|0|0|0|
begin = end -> pointing to the index 0
add value 5:
|3|0|5|0|0|
begin -> pointing to the index 0
end -> pointing to the index 2
add value 2:
|3|0|5|0|2|
begin -> pointing to the index 4
end -> pointing to the index 2
When it's not possible to insert the value (e.g. adding value 7 would conflict with value 2), the function responsible for finding the index must return -1.
Here is my implementation:
#include <vector>
#include <array>
#include <cassert>
#include <inttypes.h>
using Value = uint64_t;
struct Entry
{
Value value;
};
auto absolute(Value lhs, Value rhs) -> Value
{
return (lhs > rhs) ? lhs - rhs : rhs - lhs;
}
auto find_index(std::vector<Entry> *entries, Entry **begin, Entry **end, Value value) -> int64_t
{
if (*begin == nullptr)
{
*begin = *end = entries->data();
return 0;
}
const auto fully_overlaps = (absolute((*end)->value, value) / entries->size()) > 0;
if (fully_overlaps)
{
return -1;
}
const int64_t begin_index = *begin - entries->data();
if ((*begin)->value <= value && value <= (*end)->value)
{
auto deviation = value - (*begin)->value;
auto value_index = (begin_index + deviation) % entries->size();
return static_cast<int64_t>(value_index);
}
auto deviation = absolute((*begin)->value, value) % entries->size();
auto pushing_low_boundary = value < (*begin)->value;
auto new_value_indexes = std::array<uint64_t, 2>{
(begin_index + deviation),
(begin_index + entries->size() - deviation)};
auto value_index = new_value_indexes[static_cast<uint8_t>(pushing_low_boundary)] % entries->size();
const int64_t end_index = *end - entries->data();
if (end_index < begin_index)
{
if (value_index <= end_index)
{
return -1;
}
if (value_index >= begin_index)
{
return -1;
}
goto value_index_is_valid;
}
if (begin_index < end_index)
{
if (value_index < begin_index)
{
goto test_boundary_collision;
}
if (value_index > end_index)
{
goto test_boundary_collision;
}
return -1;
}
test_boundary_collision:
if (value_index == begin_index or value_index == end_index)
{
return -1;
}
value_index_is_valid:
auto *boundary = pushing_low_boundary ? begin : end;
*boundary = entries->data() + value_index;
return static_cast<int64_t>(value_index);
}
int main()
{
std::vector<Entry> entries;
Entry *begin = nullptr;
Entry *end = nullptr;
entries.resize(10);
auto entry = Entry{.value = 5};
const auto index = find_index(&entries, &begin, &end, entry.value);
assert(index == 0);
entries[0] = entry;
assert(find_index(&entries, &begin, &end, 7) == 2);
assert(find_index(&entries, &begin, &end, 3) == 8);
return 0;
}
Did I made any mistake, like with boundary check, under or overflows?