Info
-
Did you know that lambdas are const by default but can be mutable and keep state?
Example
auto sum = [sums = 0](auto sum) mutable {
return sums += sum;
};
int main() {
std::cout << sum(1) << sum(2) << sum(3); // prints 1 3 6
}Puzzle
-
Can you implement a mutable lambda
sum_priceswhich parses the input buffer and sums prices (price1,price2,...) for matching messages (dispatch based on header.id)?- Double points for the most generic solution
- Triple points for the most efficient solution (Assembly)
struct [[gnu::packed]] header {
short id;
};
struct [[gnu::packed]] add1 {
header h;
std::array<char, 1> price1;
};
struct [[gnu::packed]] add2 {
header h;
std::array<char, 2> price1;
};
struct [[gnu::packed]] add3 {
header h;
std::array<char, 5> price1;
std::array<char, 6> price2;
};
template<auto Id, class T>
struct msg_traits {
static constexpr auto id = Id;
using type = T;
};
template<class...>
auto sum_prices = [](std::string_view buffer) {
/*TODO*/return 0;
};
int main() {
using namespace boost::ut;
"should return 0 with empty buffer"_test = [] {
expect(0_i == sum_prices<>(std::string_view{}));
};
"should return 0 with empty buffer and traits"_test = [] {
expect(0_i == sum_prices<msg_traits<1, add1>>(std::string_view{}));
};
"should return 0 with not matchind id"_test = [] {
add1 msg{ {.id = {}}, std::array{'9'} };
expect(0_i == (sum_prices<msg_traits<7, add1>>(std::string_view{reinterpret_cast<const char*>(&msg), sizeof(msg)})));
};
"should return the price of matching message"_test = [] {
add1 msg{ {.id = 42}, std::array{'9'} };
expect(9_i == (sum_prices<msg_traits<42, add1>>(std::string_view{reinterpret_cast<const char*>(&msg), sizeof(msg)})));
};
"should return sum of prices for the same id"_test = [] {
add1 msg1{ {.id = 42}, std::array{'2'} };
expect(2_i == (sum_prices<msg_traits<0, add2>, msg_traits<42, add1>>(std::string_view{reinterpret_cast<const char*>(&msg1), sizeof(msg1)})));
add1 msg2{ {.id = 42}, std::array{'3'} };
expect(_i(2 + 3) == (sum_prices<msg_traits<0, add2>, msg_traits<42, add1>>(std::string_view{reinterpret_cast<const char*>(&msg2), sizeof(msg2)})));
};
"should return sum of prices for matching messages by id"_test = [] {
add1 msg1{ {.id = 1}, std::array{'1'} };
expect(1_i == (sum_prices<msg_traits<1, add1>, msg_traits<2, add2>>(std::string_view{reinterpret_cast<const char*>(&msg1), sizeof(msg1)})));
add2 msg2{ {.id = 2}, std::array{'4', '2'} };
expect(_i(1 + 42) == (sum_prices<msg_traits<1, add1>, msg_traits<2, add2>>(std::string_view{reinterpret_cast<const char*>(&msg2), sizeof(msg2)})));
};
"should return sum of prices for matching messages by id in different oder"_test = [] {
add2 msg2{ {.id = 200}, std::array{'1', '1'} };
expect(11_i == (sum_prices<msg_traits<200, add2>, msg_traits<100, add1>>(std::string_view{reinterpret_cast<const char*>(&msg2), sizeof(msg2)})));
add1 msg1{ {.id = 100}, std::array{'7'} };
expect(_i(11 + 7) == (sum_prices<msg_traits<200, add2>, msg_traits<100, add1>>(std::string_view{reinterpret_cast<const char*>(&msg1), sizeof(msg1)})));
};
"should return sum of prices for matching messages with spaces in prices "_test = [] {
add1 msg1{ {.id = 100}, std::array{' '} };
expect(0_i == (sum_prices<msg_traits<100, add1>, msg_traits<200, add2>, msg_traits<300, add3>>(std::string_view{reinterpret_cast<const char*>(&msg1), sizeof(msg1)})));
add2 msg2{ {.id = 200}, std::array{' ', '9'} };
expect(9_i == (sum_prices<msg_traits<100, add1>, msg_traits<200, add2>, msg_traits<300, add3>>(std::string_view{reinterpret_cast<const char*>(&msg2), sizeof(msg2)})));
add3 msg3{ {.id = 300}, std::array{' ', ' ', '1', '2', '3'}, std::array{' ', '0', '8', '7', '0', '0'} };
expect(_i(9 + 123 + 8700) == (sum_prices<msg_traits<100, add1>, msg_traits<200, add2>, msg_traits<300, add3>>(std::string_view{reinterpret_cast<const char*>(&msg3), sizeof(msg3)})));
};
}Solutions
constexpr auto integer_price = [](const auto price) {
auto p = 0;
for (auto i = 0u; i < std::size(price); ++i) {
if (std::isdigit(price[i])) {
p = (p * 10) + (price[i] - '0');
}
}
return p;
};
template<class Traits>
auto sum_prices_impl = [](std::string_view buffer) {
auto sum = 0;
if (const auto* msg = reinterpret_cast<const typename Traits::type*>(std::data(buffer)); std::size(buffer) and Traits::id == msg->h.id) {
if constexpr (requires {msg->price1;}) {
sum += integer_price(msg->price1);
}
if constexpr (requires {msg->price2;}) {
sum += integer_price(msg->price2);
}
}
return sum;
};
template<class... Traits>
auto sum_prices = [total = 0](std::string_view buffer) mutable {
return total += (0 + ... + sum_prices_impl<Traits>(buffer));
};namespace detail {
template <class T, class... TArgs> decltype(void(T{std::declval<TArgs>()...}), std::true_type{}) test_is_braces_constructible(int);
template <class, class...> std::false_type test_is_braces_constructible(...);
template <class T, class... TArgs> using is_braces_constructible = decltype(test_is_braces_constructible<T, TArgs...>(0));
struct any_type { template<class T> constexpr explicit(false) operator T(); };
template<class T>
constexpr auto to_tuple(T&& object) noexcept {
using type = std::decay_t<T>;
if constexpr(is_braces_constructible<type, any_type, any_type, any_type>{}) {
auto&& [p1, p2, p3] = std::forward<T>(object);
return std::tuple(p1, p2, p3);
} else if constexpr(is_braces_constructible<type, any_type, any_type>{}) {
auto&& [p1, p2] = std::forward<T>(object);
return std::tuple(p1, p2);
} else if constexpr(is_braces_constructible<type, any_type>{}) {
auto&& [p1] = std::forward<T>(object);
return std::tuple(p1);
} else {
return std::tuple{};
}
}
template<class R, R N>
static constexpr const R ascii_to_int[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1 * R(std::pow(10, N)), 2* R(std::pow(10, N)), 3* R(std::pow(10, N)), 4* R(std::pow(10, N)), 5* R(std::pow(10, N)), 6* R(std::pow(10, N)), 7* R(std::pow(10, N)), 8* R(std::pow(10, N)), 9* R(std::pow(10, N)) };
template<class R, auto Size>
constexpr auto to_number = [](const auto& buffer) {
return []<auto... Ns>(const auto& buffer, std::integer_sequence<R, Ns...>) {
return ((ascii_to_int<R, sizeof...(Ns) - Ns - 1>[buffer[Ns]]) + ...);
}(buffer, std::make_integer_sequence<R, Size>{});
};
template <class THeader, class... Ts>
auto sum_prices(const std::tuple<THeader, Ts...>& msg) {
return (to_number<std::uint32_t, Ts{}.size()>(std::data(std::get<Ts>(msg))) + ...);
}
template <class... Ts>
constexpr auto sum_prices(const auto& buffer) {
return ([&buffer] {
const auto* msg = reinterpret_cast<const typename Ts::type*>(buffer);
return msg->h.id == Ts::id ? sum_prices(to_tuple(*msg)) : 0;
}() + ... + 0);
}
} // namespace detail
template <class... Ts>
auto sum_prices = [prices = 0](std::string_view buffer) mutable {
return std::size(buffer) ? prices += detail::sum_prices<Ts...>(std::data(buffer)) : prices;
};https://godbolt.org/z/Y3cEn9 | https://godbolt.org/z/qKerKe | https://quick-bench.com/q/Pt3-lzZOU6FodyGLqAPjHHN48Fk
auto parse(const auto& arr) {
auto it = std::find_if(std::cbegin(arr), std::cend(arr),
[](char c) { return c >= '0' && c <= '9'; });
int i{};
std::from_chars(it, std::cend(arr), i);
return i;
};
auto msg_value(const auto& msg) {
return parse(msg.price1);
}
auto msg_value(const add3& msg) {
return parse(msg.price1) + parse(msg.price2);
}
template <class... TMsgTraits>
auto sum_prices = [sum = 0](std::string_view buffer) mutable {
if (std::size(buffer) < sizeof(header)) {
return 0;
}
const auto id = reinterpret_cast<const header*>(std::data(buffer))->id;
([&] <auto Id, class T> (msg_traits<Id, T>) {
if (std::size(buffer) < sizeof(T)) {
return false;
}
if (Id == id) {
sum += msg_value(*reinterpret_cast<const T*>(std::data(buffer)));
return true;
}
return false;
}(TMsgTraits{}) or ...);
return sum;
};namespace detail {
static constexpr auto DEFAULT_RETURN = 0;
constexpr auto from_chars_wrapper(const auto iterable)
{
int output {};
const auto first_num = std::find(std::crbegin(iterable), std::crend(iterable), ' ').base();
(void)std::from_chars(first_num, std::cend(iterable), output);
return output;
}
template <class TMsgTraits>
constexpr auto calculate_price(const char* buffer)
{
using message_t = TMsgTraits::type;
if (const auto id = reinterpret_cast<const header*>(buffer)->id; id != TMsgTraits::id) {
return DEFAULT_RETURN;
}
const message_t* message = reinterpret_cast<const message_t*>(buffer);
int output {};
if constexpr (requires { message_t::price1; }) {
output += from_chars_wrapper(message->price1);
}
if constexpr (requires { message_t::price2; }) {
output += from_chars_wrapper(message->price2);
}
return output;
};
}
template <class... TAllMsgTraits>
auto sum_prices = [sum = 0](std::string_view buffer) mutable {
if (std::size(buffer) < sizeof(header)) {
return detail::DEFAULT_RETURN;
}
sum += (detail::calculate_price<TAllMsgTraits>(std::data(buffer)) + ... + 0);
return sum;
};template <class F>
constexpr decltype(auto) apply_prices(F&& f, const add1& a) { return std::forward<F>(f)(a.price1); }
template <class F>
constexpr decltype(auto) apply_prices(F&& f, const add2& a) { return std::forward<F>(f)(a.price1); }
template <class F>
constexpr decltype(auto) apply_prices(F&& f, const add3& a) { return std::forward<F>(f)(a.price1, a.price2); }
template<class... Ts>
auto sum_prices = [sum = 0](const std::string_view& buffer) mutable {
constexpr auto Ns = sizeof...(Ts);
if constexpr (Ns > 0) {
const auto id = reinterpret_cast<const short*>(buffer.data());
if (sizeof(*id) <= buffer.size()) {
constexpr std::array<std::size_t, Ns> ids{ Ts::id... };
constexpr std::array<int(*)(const void*), Ns> acc{
[](const void* ptr) {
return apply_prices([](const auto&... prices) {
return (... + std::accumulate(
prices.begin(), prices.end(), 0, [](int s, char c) {
if (c == ' ') return s;
return s * 10 + (c - '0');
})
);
}, *reinterpret_cast<const Ts::type*>(ptr));
}...
};
const auto begin = ids.begin();
const auto end = ids.end();
const auto it = std::find(begin, end, *id);
if (it != end) {
sum += acc[it - begin](id);
}
}
}
return sum;
};auto array_to_price(const auto &array){
auto text = std::string{std::data(array), std::size(array)};
auto pos = text.find_first_not_of(' ');
if(std::string::npos == pos){
return 0;
}
return std::stoi(text.substr(pos));
}
template<class Trait>
auto sum_one_price = [](std::string_view buffer) {
using my_type = Trait::type;
if (std::empty(buffer)) { return 0; }
const auto& msg = *reinterpret_cast<const my_type*>(std::data(buffer));
if (msg.h.id == Trait::id) {
const auto price1 = array_to_price(msg.price1);
if constexpr (requires{msg.price2;}){
return price1 + array_to_price(msg.price2);
}
else{
return price1;
}
}
return 0;
};
template<class... Traits>
auto sum_prices =[sum = 0] (std::string_view buffer) mutable {
if constexpr (sizeof...(Traits) ==0 )
return 0;
else {
sum +=(sum_one_price<Traits>(buffer)+...);
return sum;
}
};template<auto N>
int parse_number(const std::array<char, N>& arr) {
int num = 0;
for(uint32_t n=0; n<N; n++)
if(arr[n] != ' ')
num = 10*num + arr[n] - '0';
return num;
};
template<class T> int totalPrices(const T& t) { return parse_number(t.price1); }
template<> int totalPrices<add3>(const add3& t) { return parse_number(t.price1) + parse_number(t.price2); }
template<class> struct process_msg;
template<auto Id, class T>
struct process_msg<msg_traits<Id, T>> {
process_msg(std::string_view buffer) : buffer(buffer) {}
int operator()() {
const T* msg = reinterpret_cast<const T*>(buffer.data());
if( msg->h.id == Id)
return totalPrices(*msg);
else
return 0;
}
std::string_view buffer;
};
template<class...Msgs>
auto sum_prices = [sums = 0](std::string_view buffer) mutable {
if(buffer.size() ==0)
return sums;
if constexpr(sizeof...(Msgs) ==0) {
return sums;
} else {
return sums += (process_msg<Msgs>(buffer)() + ...);
}
};template<class...Ts>
auto sum_prices = [ price = 0](std::string_view buffer) mutable {
if constexpr ( sizeof ...(Ts) == 0 ) return price;
if ( buffer.size() >= sizeof(header) )
{
header hd = *(header*)buffer.data();
([&](){ if( hd.id == Ts::id )
{
std::stringstream ss;
ss << buffer;
ss.seekg(sizeof(header));
int p = 0;
while( ss.good() )
{
ss >> p;
price +=p;
}
}
}(),...);
}
return price;
};template<std::size_t N, typename Seq> struct offset_sequence;
template<std::size_t N, std::size_t... Ints>
struct offset_sequence<N, std::index_sequence<Ints...>> {
using type = std::index_sequence<Ints + N...>;
};
template<std::size_t N, typename Seq>
using offset_sequence_t = typename offset_sequence<N, Seq>::type;
template<auto N>
int constexpr parse_number(const std::array<char, N>& arr) {
int num = 0;
for(uint32_t n=0; n<N; n++)
if(arr[n] != ' ')
num = 10*num + arr[n] - '0';
return num;
};
template<class T> int constexpr totalPrices(const T& t) {
auto tup = to_tuple(t);
return [tup]<std::size_t... Is>(std::index_sequence<Is...>) { return (parse_number(std::get<Is>(tup)) + ...); }
( offset_sequence_t<1, std::make_index_sequence<std::tuple_size_v<decltype(tup)>-1>>{} );
}
template<class> struct process_msg;
template<auto Id, class T>
struct process_msg<msg_traits<Id, T>> {
process_msg(std::string_view buffer) : buffer(buffer) {}
int operator()() {
if(buffer.size() ==0)
return 0;
const T* msg = reinterpret_cast<const T*>(buffer.data());
if( msg->h.id == Id)
return totalPrices(*msg);
else
return 0;
}
std::string_view buffer;
};
template<class...Msgs>
auto sum_prices = [sums = 0](std::string_view buffer) mutable {
if constexpr(sizeof...(Msgs) ==0) {
return sums;
} else {
return sums += (process_msg<Msgs>(buffer)() + ...);
}
};static inline auto skip_spaces(auto & begin) {
while(*begin == ' ')
++begin;
}
template<class TMsg>
auto dispatch(std::string_view buffer)
{
auto id = reinterpret_cast<const short *>(buffer.data());
bool match = TMsg::id == *id;
if (match)
{
using msg_type = typename TMsg::type;
auto msg = reinterpret_cast<const msg_type*>(buffer.data());
auto sum = 0;
if constexpr (requires { msg->price1; }) {
auto begin = msg->price1.begin();
skip_spaces(begin);
if( begin != msg->price1.end())
std::from_chars(begin, msg->price1.end(), sum);
}
if constexpr (requires { msg->price2; }) {
int price2;
auto begin = msg->price2.begin();
skip_spaces(begin);
if( begin != msg->price2.end())
{
std::from_chars(begin, msg->price2.end(), price2);
sum += price2;
}
}
return sum;
}
return 0;
}
template<class...TMsgTrait>
auto sum_prices = [sum = 0](std::string_view buffer) mutable {
if (std::size(buffer) == 0)
return 0;
sum += (dispatch<TMsgTrait>(buffer) + ... + 0);
return sum;
};constexpr auto value_of = [](const auto& data) {
const auto start = std::find_if(std::cbegin(data), std::cend(data),
[](const auto c) { return std::isdigit(static_cast<int>(c)); });
std::size_t value{};
// Assume well-formedness of input prices. In principle, should check
// the error code returned, but handling the error case makes this more expensive
// than it already is...
std::from_chars(start, std::cend(data), value);
return value;
};
template<class TMsg>
concept msg_with_price = requires(TMsg m) { m.price1; };
template<msg_with_price TMsg>
constexpr auto get_price(const TMsg& msg) {
if constexpr (requires{ msg.price2; }) {
return value_of(msg.price1) + value_of(msg.price2);
}
return value_of(msg.price1);
}
template<class... TMsgs>
auto sum_prices = [sum = std::size_t{}](std::string_view buffer) mutable -> std::size_t {
if(std::size(buffer) < sizeof(header)) {
return sum;
}
const auto id = reinterpret_cast<const header*>(std::data(buffer))->id;
([&]<auto Id, class T>(msg_traits<Id, T> msg) {
if (std::size(buffer) < sizeof(T)) {
return false;
}
if (Id == id) {
sum += get_price(*reinterpret_cast<const T*>(std::data(buffer)));
return true;
}
return false;
}(TMsgs{}) or ...);
return sum;
};