universe@556: /*
universe@556:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@556:  *
universe@556:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@556:  *
universe@556:  * Redistribution and use in source and binary forms, with or without
universe@556:  * modification, are permitted provided that the following conditions are met:
universe@556:  *
universe@556:  *   1. Redistributions of source code must retain the above copyright
universe@556:  *      notice, this list of conditions and the following disclaimer.
universe@556:  *
universe@556:  *   2. Redistributions in binary form must reproduce the above copyright
universe@556:  *      notice, this list of conditions and the following disclaimer in the
universe@556:  *      documentation and/or other materials provided with the distribution.
universe@556:  *
universe@556:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@556:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@556:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@556:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@556:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@556:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@556:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@556:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@556:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@556:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@556:  * POSSIBILITY OF SUCH DAMAGE.
universe@556:  */
universe@556: 
universe@556: #include "cx/hash_map.h"
universe@556: #include "cx/utils.h"
universe@556: #include "util_allocator.h"
universe@556: 
universe@556: #include <gtest/gtest.h>
universe@556: #include <unordered_map>
universe@556: #include <unordered_set>
universe@556: 
universe@556: struct map_operation {
universe@556:     enum {
universe@556:         put, rm
universe@556:     } op;
universe@556:     char const *key;
universe@556:     char const *value;
universe@556: };
universe@556: 
universe@556: auto generate_map_operations() -> std::vector<map_operation> {
universe@556:     return {
universe@556:             {map_operation::put, "key 1",          "test"},
universe@556:             {map_operation::put, "key 2",          "blub"},
universe@556:             {map_operation::put, "key 3",          "hallo"},
universe@556:             {map_operation::put, "key 2",          "foobar"},
universe@556:             {map_operation::put, "key 4",          "value 4"},
universe@556:             {map_operation::put, "key 5",          "value 5"},
universe@556:             {map_operation::put, "key 6",          "value 6"},
universe@556:             {map_operation::rm,  "key 4",          nullptr},
universe@556:             {map_operation::put, "key 7",          "value 7"},
universe@556:             {map_operation::put, "key 8",          "value 8"},
universe@556:             {map_operation::rm,  "does not exist", nullptr},
universe@556:             {map_operation::put, "key 9",          "value 9"},
universe@556:             {map_operation::put, "key 6",          "other value"},
universe@556:             {map_operation::put, "key 7",          "something else"},
universe@556:             {map_operation::rm,  "key 8",          nullptr},
universe@556:             {map_operation::rm,  "key 2",          nullptr},
universe@556:             {map_operation::put, "key 8",          "new value"},
universe@556:     };
universe@556: }
universe@556: 
universe@556: static void verify_map_contents(
universe@556:         CxMap *map,
universe@556:         std::unordered_map<std::string, std::string> const &refmap
universe@556: ) {
universe@556:     // verify key iterator
universe@556:     {
universe@556:         auto keyiter = cxMapIteratorKeys(map);
universe@556:         std::unordered_set<std::string> keys;
universe@563:         cx_foreach(CxHashKey*, elem, keyiter) {
universe@604:             keys.insert(std::string(elem->data.cstr, elem->len));
universe@556:         }
universe@561:         EXPECT_EQ(keyiter.index, map->size);
universe@556:         ASSERT_EQ(keys.size(), map->size);
universe@556:         for (auto &&k: keys) {
universe@556:             EXPECT_NE(refmap.find(k), refmap.end());
universe@556:         }
universe@556:     }
universe@556: 
universe@556:     // verify value iterator
universe@556:     {
universe@556:         auto valiter = cxMapIteratorValues(map);
universe@556:         std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
universe@556:         cx_foreach(char const*, elem, valiter) {
universe@556:             values.insert(std::string(elem));
universe@556:         }
universe@561:         EXPECT_EQ(valiter.index, map->size);
universe@556:         ASSERT_EQ(values.size(), map->size);
universe@556:         for (auto &&v: values) {
universe@556:             EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
universe@556:                                    [v](auto const &e) { return e.second == v; }), refmap.end());
universe@556:         }
universe@556:     }
universe@556: 
universe@556:     // verify pair iterator
universe@556:     {
universe@556:         auto pairiter = cxMapIterator(map);
universe@556:         std::unordered_map<std::string, std::string> pairs;
universe@556:         cx_foreach(CxMapEntry*, entry, pairiter) {
universe@604:             pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value);
universe@556:         }
universe@561:         EXPECT_EQ(pairiter.index, map->size);
universe@556:         ASSERT_EQ(pairs.size(), refmap.size());
universe@556:         for (auto &&p: pairs) {
universe@556:             ASSERT_EQ(p.second, refmap.at(p.first));
universe@556:         }
universe@556:     }
universe@556: }
universe@556: 
universe@556: TEST(CxHashMap, Create) {
universe@556:     CxTestingAllocator allocator;
universe@556:     auto map = cxHashMapCreate(&allocator, 0);
universe@556:     auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
universe@556:     EXPECT_GT(hmap->bucket_count, 0);
universe@556:     cx_for_n(i, hmap->bucket_count) {
universe@556:         EXPECT_EQ(hmap->buckets[i], nullptr);
universe@556:     }
universe@556:     EXPECT_EQ(map->size, 0);
universe@556:     EXPECT_EQ(map->allocator, &allocator);
universe@556: 
universe@556:     cxMapDestroy(map);
universe@556:     EXPECT_TRUE(allocator.verify());
universe@556: }
universe@556: 
universe@556: TEST(CxHashMap, BasicOperations) {
universe@556:     // create the map
universe@556:     CxTestingAllocator allocator;
universe@556:     auto map = cxHashMapCreate(&allocator, 8);
universe@556: 
universe@556:     // create a reference map
universe@556:     std::unordered_map<std::string, std::string> refmap;
universe@556: 
universe@556:     // generate operations
universe@556:     auto ops = generate_map_operations();
universe@556: 
universe@556:     // verify iterators for empty map
universe@556:     verify_map_contents(map, refmap);
universe@556: 
universe@556:     // execute operations and verify results
universe@556:     for (auto &&op: ops) {
universe@563:         CxHashKey key = cx_hash_key_str(op.key);
universe@563:         key.hash = 0; // force the hash map to compute the hash
universe@556:         if (op.op == map_operation::put) {
universe@556:             // execute a put operation and verify that the exact value can be read back
universe@556:             refmap[std::string(op.key)] = std::string(op.value);
universe@556:             int result = cxMapPut(map, key, (void *) op.value);
universe@556:             EXPECT_EQ(result, 0);
universe@556:             auto added = cxMapGet(map, key);
universe@556:             EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
universe@556:         } else {
universe@556:             // execute a remove and verify that the removed element was returned (or nullptr)
universe@556:             auto found = refmap.find(op.key);
universe@556:             auto removed = cxMapRemove(map, key);
universe@556:             if (found == refmap.end()) {
universe@556:                 EXPECT_EQ(removed, nullptr);
universe@556:             } else {
universe@556:                 EXPECT_EQ(std::string((char *) removed), found->second);
universe@556:                 refmap.erase(found);
universe@556:             }
universe@556:         }
universe@556:         // compare the current map state with the reference map
universe@556:         verify_map_contents(map, refmap);
universe@556:     }
universe@556: 
universe@556:     // destroy the map and verify the memory (de)allocations
universe@556:     cxMapDestroy(map);
universe@556:     EXPECT_TRUE(allocator.verify());
universe@556: }
universe@561: 
universe@561: TEST(CxHashMap, RemoveViaIterator) {
universe@561:     CxTestingAllocator allocator;
universe@561:     auto map = cxHashMapCreate(&allocator, 4);
universe@561: 
universe@563:     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
universe@563:     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
universe@563:     cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
universe@563:     cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
universe@563:     cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
universe@563:     cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
universe@561: 
universe@630:     auto iter = cxMapMutIterator(map);
universe@561:     cx_foreach(CxMapEntry*, entry, iter) {
universe@630:         if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
universe@561:     }
universe@561:     EXPECT_EQ(map->size, 3);
universe@561:     EXPECT_EQ(iter.index, map->size);
universe@561: 
universe@563:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
universe@563:     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
universe@563:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
universe@563:     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
universe@563:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
universe@563:     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
universe@561: 
universe@561:     cxMapDestroy(map);
universe@561:     EXPECT_TRUE(allocator.verify());
universe@561: }
universe@562: 
universe@562: TEST(CxHashMap, RehashNotRequired) {
universe@562:     CxTestingAllocator allocator;
universe@562:     auto map = cxHashMapCreate(&allocator, 8);
universe@562: 
universe@563:     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
universe@563:     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
universe@563:     cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
universe@563:     cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
universe@563:     cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
universe@563:     cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
universe@562: 
universe@562:     // 6/8 does not exceed 0.75, therefore the function should not rehash
universe@562:     int result = cxMapRehash(map);
universe@562:     EXPECT_EQ(result, 0);
universe@562:     EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
universe@562: 
universe@562:     cxMapDestroy(map);
universe@562:     EXPECT_TRUE(allocator.verify());
universe@562: }
universe@562: 
universe@562: TEST(CxHashMap, Rehash) {
universe@562:     CxTestingAllocator allocator;
universe@562:     auto map = cxHashMapCreate(&allocator, 8);
universe@562: 
universe@563:     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
universe@563:     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
universe@563:     cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
universe@563:     cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
universe@563:     cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
universe@563:     cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
universe@563:     cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");
universe@562: 
universe@562:     int result = cxMapRehash(map);
universe@562:     EXPECT_EQ(result, 0);
universe@562:     EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
universe@562:     EXPECT_EQ(map->size, 7);
universe@562: 
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
universe@563:     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);
universe@562: 
universe@562:     cxMapDestroy(map);
universe@562:     EXPECT_TRUE(allocator.verify());
universe@594: }
universe@594: 
universe@594: TEST(CxHashMap, Clear) {
universe@594:     CxTestingAllocator allocator;
universe@594:     auto map = cxHashMapCreate(&allocator, 0);
universe@595:     
universe@594:     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
universe@594:     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
universe@594:     cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
universe@594: 
universe@594:     EXPECT_EQ(map->size, 3);
universe@594: 
universe@594:     cxMapClear(map);
universe@594: 
universe@594:     EXPECT_EQ(map->size, 0);
universe@594:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
universe@594:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
universe@594:     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
universe@594: 
universe@594:     cxMapDestroy(map);
universe@594:     EXPECT_TRUE(allocator.verify());
universe@562: }