Mercurial > hg > ucx / file revision

 /*

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

  *

  * Copyright 2021 Mike Becker, Olaf Wintermann 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 THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT HOLDER 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 "cx/hash_map.h"

 #include "cx/utils.h"

 #include "util_allocator.h"

 #include <gtest/gtest.h>

 #include <unordered_map>

 #include <unordered_set>

 struct map_operation {

     enum {

         put, rm

     } op;

     char const *key;

     char const *value;

 };

 auto generate_map_operations() -> std::vector<map_operation> {

     return {

             {map_operation::put, "key 1",          "test"},

             {map_operation::put, "key 2",          "blub"},

             {map_operation::put, "key 3",          "hallo"},

             {map_operation::put, "key 2",          "foobar"},

             {map_operation::put, "key 4",          "value 4"},

             {map_operation::put, "key 5",          "value 5"},

             {map_operation::put, "key 6",          "value 6"},

             {map_operation::rm,  "key 4",          nullptr},

             {map_operation::put, "key 7",          "value 7"},

             {map_operation::put, "key 8",          "value 8"},

             {map_operation::rm,  "does not exist", nullptr},

             {map_operation::put, "key 9",          "value 9"},

             {map_operation::put, "key 6",          "other value"},

             {map_operation::put, "key 7",          "something else"},

             {map_operation::rm,  "key 8",          nullptr},

             {map_operation::rm,  "key 2",          nullptr},

             {map_operation::put, "key 8",          "new value"},

     };

 }

 static void verify_map_contents(

         CxMap *map,

         std::unordered_map<std::string, std::string> const &refmap

 ) {

     // verify key iterator

     {

         auto keyiter = cxMapIteratorKeys(map);

         std::unordered_set<std::string> keys;

         cx_foreach(CxDataPtr*, elem, keyiter) {

             // we use that our test keys contain NULL-terminated strings

             keys.insert(std::string(reinterpret_cast<const char *>(elem->data)));

         }

         EXPECT_EQ(keyiter.index, map->size);

         ASSERT_EQ(keys.size(), map->size);

         for (auto &&k: keys) {

             EXPECT_NE(refmap.find(k), refmap.end());

         }

     }

     // verify value iterator

     {

         auto valiter = cxMapIteratorValues(map);

         std::unordered_set<std::string> values; // we use that the values in our test data are unique strings

         cx_foreach(char const*, elem, valiter) {

             values.insert(std::string(elem));

         }

         EXPECT_EQ(valiter.index, map->size);

         ASSERT_EQ(values.size(), map->size);

         for (auto &&v: values) {

             EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),

                                    [v](auto const &e) { return e.second == v; }), refmap.end());

         }

     }

     // verify pair iterator

     {

         auto pairiter = cxMapIterator(map);

         std::unordered_map<std::string, std::string> pairs;

         cx_foreach(CxMapEntry*, entry, pairiter) {

             pairs[std::string((char const *) entry->key->data)] = std::string((char *) entry->value);

         }

         EXPECT_EQ(pairiter.index, map->size);

         ASSERT_EQ(pairs.size(), refmap.size());

         for (auto &&p: pairs) {

             ASSERT_EQ(p.second, refmap.at(p.first));

         }

     }

 }

 TEST(CxHashMap, Create) {

     CxTestingAllocator allocator;

     auto map = cxHashMapCreate(&allocator, 0);

     auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);

     EXPECT_GT(hmap->bucket_count, 0);

     cx_for_n(i, hmap->bucket_count) {

         EXPECT_EQ(hmap->buckets[i], nullptr);

     }

     EXPECT_EQ(map->size, 0);

     EXPECT_EQ(map->allocator, &allocator);

     cxMapDestroy(map);

     EXPECT_TRUE(allocator.verify());

 }

 TEST(CxHashMap, BasicOperations) {

     // create the map

     CxTestingAllocator allocator;

     auto map = cxHashMapCreate(&allocator, 8);

     // create a reference map

     std::unordered_map<std::string, std::string> refmap;

     // generate operations

     auto ops = generate_map_operations();

     // verify iterators for empty map

     verify_map_contents(map, refmap);

     // execute operations and verify results

     for (auto &&op: ops) {

         CxDataPtr key = cxMapKeyStr(op.key);

         if (op.op == map_operation::put) {

             // execute a put operation and verify that the exact value can be read back

             refmap[std::string(op.key)] = std::string(op.value);

             int result = cxMapPut(map, key, (void *) op.value);

             EXPECT_EQ(result, 0);

             auto added = cxMapGet(map, key);

             EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);

         } else {

             // execute a remove and verify that the removed element was returned (or nullptr)

             auto found = refmap.find(op.key);

             auto removed = cxMapRemove(map, key);

             if (found == refmap.end()) {

                 EXPECT_EQ(removed, nullptr);

             } else {

                 EXPECT_EQ(std::string((char *) removed), found->second);

                 refmap.erase(found);

             }

         }

         // compare the current map state with the reference map

         verify_map_contents(map, refmap);

     }

     // destroy the map and verify the memory (de)allocations

     cxMapDestroy(map);

     EXPECT_TRUE(allocator.verify());

 }

 TEST(CxHashMap, RemoveViaIterator) {

     CxTestingAllocator allocator;

     auto map = cxHashMapCreate(&allocator, 4);

     cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");

     cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");

     cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");

     cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");

     cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");

     cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");

     auto iter = cxMapIterator(map);

     cx_foreach(CxMapEntry*, entry, iter) {

         if (entry->key->data[4] % 2 == 1) iter.remove = true;

     }

     EXPECT_EQ(map->size, 3);

     EXPECT_EQ(iter.index, map->size);

     EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 1")), nullptr);

     EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 2")), nullptr);

     EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 3")), nullptr);

     EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 4")), nullptr);

     EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 5")), nullptr);

     EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 6")), nullptr);

     cxMapDestroy(map);

     EXPECT_TRUE(allocator.verify());

 }