libcruft-util/test/hash/table.cpp

#include <cruft/util/hash/table.hpp>

#include <cruft/util/tap.hpp>
#include <cruft/util/introspection/name.hpp>


///////////////////////////////////////////////////////////////////////////////
/// Exhaustively test the table hash output for:
///   * uniqueness
///   * equal counts of bit values at each bit offset
template <typename ValueT>
void test_type (cruft::TAP::logger &tap)
{
    // Exhaustively list the hash outputs for u08. The result is sorted
    // because it simplifies upcoming tests and we don't care about mapping it
    // back to the original values.
    std::vector<ValueT> results;
    std::iota (
        std::begin (results),
        std::end   (results),
        0
    );

    std::transform (
        std::begin (results),
        std::end   (results),
        std::begin (results),
        cruft::hash::table<ValueT> {}
    );

    std::sort (std::begin (results), std::end (results));

    // Ensure all values are unique.
    {
        auto const pos = std::adjacent_find (std::begin (results), std::end (results));
        tap.expect (
            pos == std::end (results),
            "no equal elements, {}",
            cruft::introspection::name::bare<ValueT> ()
        );
    }

    // Ensure that at each bit offset we have equal numbers of high and low
    // values across the table results.
    {
        bool success = true;

        std::vector<int> bits;
        for (std::size_t i = 0; i < sizeof (ValueT) * 8; ++i) {
            bits.clear ();

            for (auto const v: results)
                bits.push_back ((v >> i) & 0x1);

            auto const zeros = std::count (std::begin (bits), std::end (bits), 0);
            auto const ones  = std::count (std::begin (bits), std::end (bits), 1);
            if (zeros != ones) {
                success = false;
                break;
            }
        }

        tap.expect (
            success,
            "equal counts at bit positions, {}",
            cruft::introspection::name::bare<ValueT> ()
        );
    }
}


///////////////////////////////////////////////////////////////////////////////
int main ()
{
    cruft::TAP::logger tap;
    test_type<u08> (tap);
    test_type<u16> (tap);
    test_type<u32> (tap);
    test_type<u64> (tap);
    return tap.status ();
}