/*
 * Copyright (c) 2018-2021 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "TestHarness.h"
#include <functional>
#include "pas_hashtable.h"
#include <vector>

using namespace std;

namespace {

template<typename EntryType>
bool hashtableForEachEntryCallback(EntryType* entry, void* arg)
{
    function<bool(EntryType*)>* callback = reinterpret_cast<function<bool(EntryType*)>*>(arg);
    return (*callback)(entry);
}

template<typename EntryType, typename HashtableType, typename ForEachEntryFunc, typename Func>
bool hashtableForEachEntry(HashtableType* hashtable, const ForEachEntryFunc& forEachEntryFunc,
                           const Func& func)
{
    function<bool(EntryType*)> callback = func;
    return forEachEntryFunc(hashtable, hashtableForEachEntryCallback<EntryType>, &callback);
}

struct Key {
    Key() = default;
    
    Key(unsigned key)
        : key(key)
    {
    }
    
    unsigned key { 0 };
};

typedef Key CollidingKey;
typedef Key CollidingEntry;

inline CollidingEntry CollidingEntry_create_empty()
{
    return { };
}

inline CollidingEntry CollidingEntry_create_deleted()
{
    return UINT_MAX;
}

inline bool CollidingEntry_is_empty_or_deleted(CollidingEntry entry)
{
    return entry.key == 0 || entry.key == UINT_MAX;
}

inline bool CollidingEntry_is_empty(CollidingEntry entry)
{
    return entry.key == 0;
}

inline bool CollidingEntry_is_deleted(CollidingEntry entry)
{
    return entry.key == UINT_MAX;
}

inline CollidingKey CollidingEntry_get_key(CollidingEntry entry)
{
    return entry;
}

inline unsigned CollidingKey_get_hash(CollidingKey key)
{
    return 0;
}

inline bool CollidingKey_is_equal(CollidingKey a, CollidingKey b)
{
    return a.key == b.key;
}

PAS_CREATE_HASHTABLE(CollidingHashtable,
                     CollidingEntry,
                     CollidingKey);

void testEmptyCollidingHashtable()
{
    CollidingHashtable hashtable;
    CollidingHashtable_construct(&hashtable);
    CollidingHashtable_destruct(&hashtable, &allocationConfig);
}

void testCollidingHashtableAddFindTakeImpl(const vector<CollidingEntry>& entries)
{
    CollidingHashtable hashtable;
    CollidingHashtable_construct(&hashtable);
    
    for (CollidingEntry entry : entries) {
        CHECK(!CollidingEntry_is_empty_or_deleted(entry));
        CollidingHashtable_add_new(&hashtable, entry, nullptr, &allocationConfig);
    }

    CHECK_EQUAL(hashtable.key_count, entries.size());
    CHECK_EQUAL(hashtable.deleted_count, 0);
    
    for (CollidingEntry entry : entries) {
        CollidingEntry* foundEntry = CollidingHashtable_find(&hashtable, entry);
        CHECK(foundEntry);
        CHECK_EQUAL(foundEntry->key, entry.key);
    }
    for (CollidingEntry entry : entries) {
        CollidingEntry takenEntry = CollidingHashtable_take(&hashtable, entry, nullptr, &allocationConfig);
        CHECK(!CollidingEntry_is_empty(takenEntry));
        CHECK_EQUAL(takenEntry.key, entry.key);
    }
    
    CHECK_EQUAL(hashtable.key_count, 0);
    CHECK_LESS_EQUAL(hashtable.deleted_count, entries.size());
    
    CollidingHashtable_destruct(&hashtable, &allocationConfig);
}

template<typename... Arguments>
void testCollidingHashtableAddFindTake(Arguments... arguments)
{
    vector<CollidingEntry> entries = { arguments... };
    testCollidingHashtableAddFindTakeImpl(entries);
}

void testCollidingHashtableAddAddTakeSet()
{
    CollidingHashtable hashtable;
    
    CollidingHashtable_construct(&hashtable);
    CollidingHashtable_add_new(&hashtable, 1, nullptr, &allocationConfig);
    CollidingHashtable_add_new(&hashtable, 2, nullptr, &allocationConfig);
    CHECK_EQUAL(CollidingHashtable_take(&hashtable, 1, nullptr, &allocationConfig).key, 1);
    CHECK(!CollidingHashtable_set(&hashtable, 2, nullptr, &allocationConfig));
    
    bool foundTwo = false;
    hashtableForEachEntry<CollidingEntry>(
        &hashtable, CollidingHashtable_for_each_entry,
        [&] (CollidingEntry* entry) -> bool {
            if (foundTwo)
                CHECK(!"Should not have found any other entries");
            CHECK_EQUAL(entry->key, 2);
            foundTwo = true;
            return true;
        });
    
    CHECK_EQUAL(hashtable.key_count, 1);
    CHECK_EQUAL(hashtable.deleted_count, 1);
    
    CollidingHashtable_destruct(&hashtable, &allocationConfig);
}

void testCollidingHashtableAddAddAddTakeTakeSet()
{
    CollidingHashtable hashtable;
    
    CollidingHashtable_construct(&hashtable);
    CollidingHashtable_add_new(&hashtable, 1, nullptr, &allocationConfig);
    CollidingHashtable_add_new(&hashtable, 2, nullptr, &allocationConfig);
    CollidingHashtable_add_new(&hashtable, 3, nullptr, &allocationConfig);
    CHECK_EQUAL(CollidingHashtable_take(&hashtable, 1, nullptr, &allocationConfig).key, 1);
    CHECK_EQUAL(CollidingHashtable_take(&hashtable, 2, nullptr, &allocationConfig).key, 2);
    CHECK(!CollidingHashtable_set(&hashtable, 3, nullptr, &allocationConfig));
    
    bool foundThree = false;
    hashtableForEachEntry<CollidingEntry>(
        &hashtable, CollidingHashtable_for_each_entry,
        [&] (CollidingEntry* entry) -> bool {
            if (foundThree)
                CHECK(!"Should not have found any other entries");
            CHECK_EQUAL(entry->key, 3);
            foundThree = true;
            return true;
        });
    
    CHECK_EQUAL(hashtable.key_count, 1);
    CHECK_EQUAL(hashtable.deleted_count, 2);
    
    CollidingHashtable_destruct(&hashtable, &allocationConfig);
}

void testCollidingHashtableAddAddAddTakeTakeAddSet()
{
    CollidingHashtable hashtable;
    
    CollidingHashtable_construct(&hashtable);
    CollidingHashtable_add_new(&hashtable, 1, nullptr, &allocationConfig);
    CollidingHashtable_add_new(&hashtable, 2, nullptr, &allocationConfig);
    CollidingHashtable_add_new(&hashtable, 3, nullptr, &allocationConfig);
    CHECK_EQUAL(CollidingHashtable_take(&hashtable, 1, nullptr, &allocationConfig).key, 1);
    CHECK_EQUAL(CollidingHashtable_take(&hashtable, 2, nullptr, &allocationConfig).key, 2);
    CollidingHashtable_add_new(&hashtable, 4, nullptr, &allocationConfig);
    CHECK(!CollidingHashtable_set(&hashtable, 3, nullptr, &allocationConfig));
    
    bool foundThree = false;
    bool foundFour = false;
    hashtableForEachEntry<CollidingEntry>(
        &hashtable, CollidingHashtable_for_each_entry,
        [&] (CollidingEntry* entry) -> bool {
            if (foundThree && foundFour)
                CHECK(!"Should not have found any other entries");
            if (foundThree) {
                CHECK_EQUAL(entry->key, 4);
                foundFour = true;
                return true;
            }
            if (foundFour) {
                CHECK_EQUAL(entry->key, 3);
                foundThree = true;
                return true;
            }
            if (entry->key == 3)
                foundThree = true;
            else if (entry->key == 4)
                foundFour = true;
            else
                CHECK(!"Found wrong key");
            return true;
        });
    
    CHECK_EQUAL(hashtable.key_count, 2);
    CHECK_EQUAL(hashtable.deleted_count, 1);
    
    CollidingHashtable_destruct(&hashtable, &allocationConfig);
}

typedef Key OutOfLineKey;
typedef Key* OutOfLineEntry;

inline OutOfLineEntry OutOfLineEntry_create_empty()
{
    return nullptr;
}

inline OutOfLineEntry OutOfLineEntry_create_deleted()
{
    return reinterpret_cast<OutOfLineEntry>(static_cast<uintptr_t>(1));
}

inline bool OutOfLineEntry_is_empty_or_deleted(OutOfLineEntry entry)
{
    return reinterpret_cast<uintptr_t>(entry) <= static_cast<uintptr_t>(1);
}

inline bool OutOfLineEntry_is_empty(OutOfLineEntry entry)
{
    return !entry;
}

inline bool OutOfLineEntry_is_deleted(OutOfLineEntry entry)
{
    return entry == reinterpret_cast<OutOfLineEntry>(static_cast<uintptr_t>(1));
}

inline OutOfLineKey OutOfLineEntry_get_key(OutOfLineEntry entry)
{
    return *entry;
}

inline unsigned OutOfLineKey_get_hash(OutOfLineKey key)
{
    return key.key;
}

inline bool OutOfLineKey_is_equal(OutOfLineKey a, OutOfLineKey b)
{
    return a.key == b.key;
}

PAS_CREATE_HASHTABLE(OutOfLineHashtable,
                     OutOfLineEntry,
                     OutOfLineKey);

// Need to test:
// - Rehashing with empty/deleted entries.
// - Iterating with empty/deleted entries.
// - Finding with empty/deleted entries.
// - Adding with empty/deleted entries.
// - Taking with empty/deleted entries.

void testOutOfLineHashtable(unsigned numElements)
{
    OutOfLineHashtable hashtable;
    
    OutOfLineHashtable_construct(&hashtable);

    for (unsigned i = numElements; i--;)
        CHECK(!OutOfLineHashtable_find(&hashtable, i));
    
    hashtableForEachEntry<OutOfLineEntry>(
        &hashtable, OutOfLineHashtable_for_each_entry,
        [&] (OutOfLineEntry* entry) -> bool {
            CHECK(!"Should not have found anything.");
            return true;
        });
    
    for (unsigned i = numElements; i--;)
        OutOfLineHashtable_add_new(&hashtable, new Key(i), nullptr, &allocationConfig);
    
    for (unsigned i = numElements; i--;) {
        OutOfLineEntry* entry = OutOfLineHashtable_find(&hashtable, i);
        CHECK(entry);
        CHECK(*entry);
        CHECK_EQUAL((*entry)->key, i);
    }
    
    for (unsigned i = numElements; i--;) {
        OutOfLineEntry entry = OutOfLineHashtable_take(&hashtable, i, nullptr, &allocationConfig);
        CHECK(entry);
        CHECK_EQUAL(entry->key, i);
    }
    
    hashtableForEachEntry<OutOfLineEntry>(
        &hashtable, OutOfLineHashtable_for_each_entry,
        [&] (OutOfLineEntry* entry) -> bool {
            CHECK(!"Should not have found anything.");
            return true;
        });
    
    for (unsigned i = numElements; i--;)
        CHECK(!OutOfLineHashtable_find(&hashtable, i));
    
    for (unsigned i = numElements; i--;)
        OutOfLineHashtable_add_new(&hashtable, new Key(i), nullptr, &allocationConfig);
    
    CHECK_EQUAL(hashtable.key_count, numElements);
    
    OutOfLineHashtable_destruct(&hashtable, &allocationConfig);
}

} // anonymous namespace

void addHashtableTests()
{
    ADD_TEST(testEmptyCollidingHashtable());
    ADD_TEST(testCollidingHashtableAddFindTake(1));
    ADD_TEST(testCollidingHashtableAddFindTake(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
    ADD_TEST(testCollidingHashtableAddAddTakeSet());
    ADD_TEST(testCollidingHashtableAddAddAddTakeTakeSet());
    ADD_TEST(testCollidingHashtableAddAddAddTakeTakeAddSet());
    ADD_TEST(testOutOfLineHashtable(0));
    ADD_TEST(testOutOfLineHashtable(1));
    ADD_TEST(testOutOfLineHashtable(10));
    ADD_TEST(testOutOfLineHashtable(100));
    ADD_TEST(testOutOfLineHashtable(1000));
    ADD_TEST(testOutOfLineHashtable(10000));
    ADD_TEST(testOutOfLineHashtable(100000));
}