// Copyright 2014 The Android Open Source Project
//
// This software is licensed under the terms of the GNU General Public
// License version 2, as published by the Free Software Foundation, and
// may be copied, distributed, and modified under those terms.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#include "android/base/containers/HashUtils.h"

#include <gtest/gtest.h>

#include <math.h>

#define ARRAYLEN(x)  (sizeof(x)/sizeof(x[0]))

namespace android {
namespace base {

namespace {

// Return true iff |x| is a prime integer.
bool isPrime(int x) {
    if (x == 1 || x == 2)
        return true;

    int max_n = (int)ceil(sqrt(x));
    for (int n = 2; n <= max_n; ++n) {
        if ((x % n) == 0) {
            return false;
        }
    }
    return true;
}

}  // namespace

TEST(HashUtils, kPrimes) {
    for (size_t n = 0; n < 32U; ++n) {
        int prime = internal::kPrimes[n];
        if (n > 0) {
            EXPECT_LT(internal::kPrimes[n - 1], prime)
                    << "Prime #" << n << " (" << prime << ")";
        }
        EXPECT_TRUE(isPrime(prime))
                << "Prime #" << n << " (" << prime << ")";
    }
}

TEST(HashUtils, hashShiftAdjust) {
    static const struct {
        size_t size;
        size_t shift;
        size_t expected;
    } kData[] = {
        { 0, 3, 3 },
        { 1, 3, 3 },
        { 2, 3, 3 },
        { 3, 3, 3 },
        { 4, 3, 3 },
        { 4, 3, 3 },
        { 6, 3, 3 },
        { 7, 3, 4 },
        { 8, 3, 4 },
        { 8, 4, 4 },
        { 3, 4, 3 },
        { 15, 4, 5 },
        { 15000, 16, 15 },
        { 32768, 16, 16 },
        { 55000, 16, 17 },
    };
    for (size_t n = 0; n < ARRAYLEN(kData); ++n) {
        EXPECT_EQ(kData[n].expected,
                  internal::hashShiftAdjust(kData[n].size,
                                            kData[n].shift))
                << "For size="
                << kData[n].size
                << " and shift="
                << kData[n].shift;
    }
}


}  // namespace base
}  // namespace android