// @author Vinícius dos Santos Oliveira
// I'm releasing this snippet as public domain.
// Do as you like.
#include <boost/hana/functional/overload_linearly.hpp>
#include <boost/hana/functional/overload.hpp>
#include <boost/hana/functional/always.hpp>
#include <boost/hana/fold_right.hpp>
#include <boost/hana/drop_back.hpp>
#include <boost/hana/not_equal.hpp>
#include <boost/hana/greater.hpp>
#include <boost/hana/minimum.hpp>
#include <boost/hana/reverse.hpp>
#include <boost/hana/string.hpp>
#include <boost/hana/minus.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/fold.hpp>
#include <boost/hana/mult.hpp>
#include <boost/hana/size.hpp>
#include <boost/hana/sort.hpp>
#include <boost/hana/set.hpp>
#include <boost/hana/zip.hpp>
#include <string_view>
#include <iostream>
struct lua_State;
namespace hana = boost::hana;
namespace dispatch_table {
namespace detail {
using hana::literals::operator""_c;
// string_view compares string size before string contents. Therefore, string
// size here already performs work similar to the hash table usage. On the event
// where all string sizes differ, we don't generate another hash function.
struct ConstantHash
{
static constexpr auto value = hana::always(hana::size_c<0>);
static constexpr auto first_pass = hana::always(hana::true_c);
};
template<class Strings>
struct Hash
{
static constexpr std::size_t smallest_pattern_size = hana::minimum(
hana::transform(Strings{}, hana::size));
// We're after a cheap hash for our static search structure, not a perfect
// hash.
static constexpr auto value = []() {
// The algorithm to find the suitable indexes is roughly divided into
// these steps:
//
// * Produce indexes [0, N).
// * Produce reverse indexes [N, 1].
// * Whether and index is reversed is indicated by the boolean constant
// that follows the index. `true` means reversed. Reverse index count
// from the end iterator.
// * We use N=smallest_pattern_size because we don't want to perform
// bounds checking later.
// * Concat the two sequences.
auto initial_idxs = hana::concat(
hana::transform(
hana::to_tuple(
hana::range_c<std::size_t, 0, smallest_pattern_size>),
[](auto&& i) { return hana::make_tuple(i, hana::false_c); }
),
hana::reverse(hana::transform(
hana::to_tuple(
hana::range_c<std::size_t, 1, smallest_pattern_size + 1>),
[](auto&& i) { return hana::make_tuple(i, hana::true_c); }
))
);
// * Apply all strings to each index. The application will compute the
// hash value, store it into a set and append the set's length to the
// end of the index tuple. This length indicates a score.
// * Remove all indexes whose score is 1. They can't be used to
// differentiate between any two strings.
auto idxs_plus_score = initial_idxs |
[](auto&& e) {
auto score = hana::size(hana::to_set(hana::transform(
Strings{},
[idx=e[0_c],rev=e[1_c]](auto&& str) {
return hana::if_(
rev, str[hana::size(str) - idx], str[idx]);
}
)));
return hana::if_(
score == hana::size_c<1>,
hana::make_tuple(),
hana::make_tuple(hana::insert(e, hana::int_c<2>, score)));
};
// * Apply a stable sort by decreasing score.
// * Limit the indexes list to length 4 (i.e. bytes in an int32_t).
// * Discard score.
auto uncompressed_hash = hana::transform(
hana::take_front_c<4>(hana::sort(
idxs_plus_score,
[](auto&& l, auto&& r) { return hana::greater(l[2_c], r[2_c]); }
)),
hana::take_front_c<2>
);
// * Consider the result as a single hash. Generate more hashes by
// discarding tail until new permutations are no longer possible.
auto final_round_choices = hana::while_(
[](auto&& e) { return hana::size(e[0_c]) != hana::size_c<1>; },
hana::make_tuple(uncompressed_hash),
[](auto&& e) {
return hana::insert(e, 0_c, hana::drop_back(e[0_c]));
}
);
// * Compute a score again by applying all the strings to each hash
// candidate. But first we create the function that generate the hash
// function out of the hash spec.
// * Sort by score plus hash complexity (i.e. all else being equal,
// cheaper hashes stay at the front) and get the best one.
auto hash_gen = [](auto&& spec) {
return hana::fold(
hana::zip(
spec,
hana::transform(
hana::to_tuple(
hana::make_range(hana::size_c<0>, hana::size(spec))
),
hana::_ * hana::integral_c<std::uint32_t, 8>)),
hana::always(hana::integral_c<std::uint32_t, 0>),
[](auto&& acc, auto&& subhash) {
return [acc,subhash](const auto& string) {
auto size = hana::overload(
[](std::string_view str) { return str.size(); },
hana::size
);
auto at = hana::overload_linearly(
[](std::string_view str, std::size_t i) {
return std::uint32_t(str[i]);
},
[](auto&& xs, auto&& i) {
return hana::to<
hana::integral_constant_tag<std::uint32_t>
>(hana::at(xs, i));
}
);
auto idx = hana::if_(
/*reverse_index=*/subhash[0_c][1_c],
size(string) - subhash[0_c][0_c],
subhash[0_c][0_c]);
return acc(string) + (at(string, idx) << subhash[1_c]);
};
}
);
};
return hash_gen(/*spec=*/hana::first(hana::front(hana::sort(
hana::transform(
final_round_choices,
[hash_gen](auto&& e) {
auto score = hana::size(hana::to_set(
hana::transform(Strings{}, hash_gen(e))));
return hana::make_pair(e, score);
}),
[](auto&& l, auto&& r) {
return hana::greater(hana::second(l), hana::second(r));
}
))));
}();
static constexpr bool first_pass(std::string_view str)
{
// So later code won't have to perform bounds checking when computing
// hash
if (str.size() < smallest_pattern_size)
return false;
return true;
}
};
template<class Xs>
constexpr bool all_sizes_differ(const Xs& xs)
{
return hana::size(hana::to_set(
hana::transform(hana::transform(xs, hana::first), hana::size)
)) == hana::size(xs);
}
} // namespace detail
// Even if a perfect-hash is generated, a walk through the whole table is
// done. The rationale is to keep the generated code small. Also, for our
// use-case, not-found is an exceptional case, so we purposefully don't optimize
// for it.
template<class Xs, class Fallback, class... Args>
auto dispatch(Xs xs, Fallback fallback, std::string_view key, Args&&... args)
-> decltype(fallback(key, std::forward<Args>(args)...))
{
std::conditional_t<
detail::all_sizes_differ(xs),
detail::ConstantHash,
detail::Hash<decltype(hana::transform(xs, hana::first))>
> hash;
if (!hash.first_pass(key))
return fallback(key, std::forward<Args>(args)...);
return hana::fold_right(
xs,
fallback,
[hash](const auto& arm, const auto& acc) {
return [hash,arm,acc](std::string_view key, auto&&... args) {
auto pattern_ct = hana::first(arm);
std::string_view pattern{
pattern_ct.c_str(), hana::size(pattern_ct)};
if (hash.value(pattern_ct) == hash.value(key) &&
pattern == key) {
return hana::second(arm)(
std::forward<decltype(args)>(args)...);
} else {
return acc(key, std::forward<decltype(args)>(args)...);
}
};
}
)(key, std::forward<Args>(args)...);
}
} // namespace dispatch_table
int foobar(std::string_view key, lua_State* L)
{
return dispatch_table::dispatch(
hana::make_tuple(
hana::make_pair(
BOOST_HANA_STRING("joinable"),
[](lua_State*) -> int { return 1; }
),
hana::make_pair(
BOOST_HANA_STRING("join"),
[](lua_State*) -> int { return 2; }
),
hana::make_pair(
BOOST_HANA_STRING("detach"),
[](lua_State*) -> int { return 3; }
),
hana::make_pair(
BOOST_HANA_STRING("interrupt"),
[](lua_State*) -> int { return 4; }
),
hana::make_pair(
BOOST_HANA_STRING("interruption_caught"),
[](lua_State*) -> int { return 5; }
)
),
[](std::string_view /*key*/, lua_State*) -> int { return -1; },
key,
L
);
}
int main()
{
std::string input;
std::getline(std::cin, input);
std::cout << foobar(input, nullptr) << std::endl;
}
Comments