invariants.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

// Copyright 2006-2008 Daniel James.
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

// This header contains metafunctions/functions to get the equivalent
// associative container for an unordered container, and compare the contents.

#if !defined(BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER)
#define BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER

#include <set>
#include <cmath>
#include "./metafunctions.hpp"
#include "./helpers.hpp"
#include "./allocator.hpp"

#if defined(BOOST_MSVC)
#pragma warning(push)
#pragma warning(disable:4127) // conditional expression is constant
#endif

namespace test
{
    template <class X>
    void check_equivalent_keys(X const& x1)
    {
        BOOST_DEDUCED_TYPENAME X::key_equal eq = x1.key_eq();
        typedef BOOST_DEDUCED_TYPENAME X::key_type key_type;
        // Boost.Test was reporting memory leaks for std::set on g++-3.3.
        // So I work around it by using malloc.
        std::set<key_type, std::less<key_type>, test::malloc_allocator<key_type> > found_;

        BOOST_DEDUCED_TYPENAME X::const_iterator it = x1.begin(), end = x1.end();
        BOOST_DEDUCED_TYPENAME X::size_type size = 0;
        while(it != end) {
            // First test that the current key has not occured before, required
            // to test either that keys are unique or that equivalent keys are
            // adjacent. (6.3.1/6)
            key_type key = get_key<X>(*it);
            if(!found_.insert(key).second)
                BOOST_ERROR("Elements with equivalent keys aren't adjacent.");

            // Iterate over equivalent keys, counting them.
            unsigned int count = 0;
            do {
                ++it;
                ++count;
                ++size;
            } while(it != end && eq(get_key<X>(*it), key));

            // If the container has unique keys, test that there's only one.
            // Since the previous test makes sure that all equivalent keys are
            // adjacent, this is all the equivalent keys - so the test is
            // sufficient. (6.3.1/6 again).
            if(test::has_unique_keys<X>::value && count != 1)
                BOOST_ERROR("Non-unique key.");

            if(x1.count(key) != count) {
                BOOST_ERROR("Incorrect output of count.");
                std::cerr<<x1.count(key)<<","<<count<<"\n";
            }

            // I'm not bothering with the following test for now, as the
            // previous test is probably more enough to catch the kind of
            // errors that this would catch (if an element was in the wrong
            // bucket it not be found by the call to count, if elements are not
            // adjacent then they would be caught when checking against
            // found_.

            // // Check that the keys are in the correct bucket and are
            // // adjacent in the bucket.
            // BOOST_DEDUCED_TYPENAME X::size_type bucket = x1.bucket(key);
            // BOOST_DEDUCED_TYPENAME X::const_local_iterator lit = x1.begin(bucket), lend = x1.end(bucket);
            // for(; lit != lend && !eq(get_key<X>(*lit), key); ++lit) continue;
            // if(lit == lend)
            //     BOOST_ERROR("Unable to find element with a local_iterator");
            // unsigned int count2 = 0;
            // for(; lit != lend && eq(get_key<X>(*lit), key); ++lit) ++count2;
            // if(count != count2)
            //     BOOST_ERROR("Element count doesn't match local_iterator.");
            // for(; lit != lend; ++lit) {
            //     if(eq(get_key<X>(*lit), key)) {
            //         BOOST_ERROR("Non-adjacent element with equivalent key in bucket.");
            //         break;
            //     }
            // }
        };

        // Finally, check that size matches up.
        if(x1.size() != size)
            BOOST_ERROR("x1.size() doesn't match actual size.");
        float load_factor = static_cast<float>(size) / static_cast<float>(x1.bucket_count());
        using namespace std;
        if(fabs(x1.load_factor() - load_factor) > x1.load_factor() / 64)
            BOOST_ERROR("x1.load_factor() doesn't match actual load_factor.");
    }
}

#if defined(BOOST_MSVC)
#pragma warning(pop)
#endif

#endif