Mercurial > hg > ucx / changeset

     1.1 --- a/test/CMakeLists.txt	Fri May 27 12:28:49 2022 +0200
     1.2 +++ b/test/CMakeLists.txt	Fri May 27 12:59:32 2022 +0200
     1.3 @@ -18,6 +18,7 @@
     1.4          test_buffer.cpp
     1.5          test_list.cpp
     1.6          test_tree.cpp
     1.7 +        test_map.cpp
     1.8          selftest.cpp
     1.9          util_allocator.cpp
    1.10          )

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/test/test_map.cpp	Fri May 27 12:59:32 2022 +0200
     2.3 @@ -0,0 +1,170 @@
     2.4 +/*
     2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     2.6 + *
     2.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     2.8 + *
     2.9 + * Redistribution and use in source and binary forms, with or without
    2.10 + * modification, are permitted provided that the following conditions are met:
    2.11 + *
    2.12 + *   1. Redistributions of source code must retain the above copyright
    2.13 + *      notice, this list of conditions and the following disclaimer.
    2.14 + *
    2.15 + *   2. Redistributions in binary form must reproduce the above copyright
    2.16 + *      notice, this list of conditions and the following disclaimer in the
    2.17 + *      documentation and/or other materials provided with the distribution.
    2.18 + *
    2.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    2.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    2.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    2.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    2.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    2.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    2.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    2.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    2.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    2.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    2.29 + * POSSIBILITY OF SUCH DAMAGE.
    2.30 + */
    2.31 +
    2.32 +#include "cx/hash_map.h"
    2.33 +#include "cx/utils.h"
    2.34 +#include "util_allocator.h"
    2.35 +
    2.36 +#include <gtest/gtest.h>
    2.37 +#include <unordered_map>
    2.38 +#include <unordered_set>
    2.39 +
    2.40 +struct map_operation {
    2.41 +    enum {
    2.42 +        put, rm
    2.43 +    } op;
    2.44 +    char const *key;
    2.45 +    char const *value;
    2.46 +};
    2.47 +
    2.48 +auto generate_map_operations() -> std::vector<map_operation> {
    2.49 +    return {
    2.50 +            {map_operation::put, "key 1",          "test"},
    2.51 +            {map_operation::put, "key 2",          "blub"},
    2.52 +            {map_operation::put, "key 3",          "hallo"},
    2.53 +            {map_operation::put, "key 2",          "foobar"},
    2.54 +            {map_operation::put, "key 4",          "value 4"},
    2.55 +            {map_operation::put, "key 5",          "value 5"},
    2.56 +            {map_operation::put, "key 6",          "value 6"},
    2.57 +            {map_operation::rm,  "key 4",          nullptr},
    2.58 +            {map_operation::put, "key 7",          "value 7"},
    2.59 +            {map_operation::put, "key 8",          "value 8"},
    2.60 +            {map_operation::rm,  "does not exist", nullptr},
    2.61 +            {map_operation::put, "key 9",          "value 9"},
    2.62 +            {map_operation::put, "key 6",          "other value"},
    2.63 +            {map_operation::put, "key 7",          "something else"},
    2.64 +            {map_operation::rm,  "key 8",          nullptr},
    2.65 +            {map_operation::rm,  "key 2",          nullptr},
    2.66 +            {map_operation::put, "key 8",          "new value"},
    2.67 +    };
    2.68 +}
    2.69 +
    2.70 +static void verify_map_contents(
    2.71 +        CxMap *map,
    2.72 +        std::unordered_map<std::string, std::string> const &refmap
    2.73 +) {
    2.74 +    // verify key iterator
    2.75 +    {
    2.76 +        auto keyiter = cxMapIteratorKeys(map);
    2.77 +        std::unordered_set<std::string> keys;
    2.78 +        cx_foreach(CxDataPtr*, elem, keyiter) {
    2.79 +            // we use that our test keys contain NULL-terminated strings
    2.80 +            keys.insert(std::string(reinterpret_cast<const char *>(elem->data)));
    2.81 +        }
    2.82 +        ASSERT_EQ(keys.size(), map->size);
    2.83 +        for (auto &&k: keys) {
    2.84 +            EXPECT_NE(refmap.find(k), refmap.end());
    2.85 +        }
    2.86 +    }
    2.87 +
    2.88 +    // verify value iterator
    2.89 +    {
    2.90 +        auto valiter = cxMapIteratorValues(map);
    2.91 +        std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
    2.92 +        cx_foreach(char const*, elem, valiter) {
    2.93 +            values.insert(std::string(elem));
    2.94 +        }
    2.95 +        ASSERT_EQ(values.size(), map->size);
    2.96 +        for (auto &&v: values) {
    2.97 +            EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
    2.98 +                                   [v](auto const &e) { return e.second == v; }), refmap.end());
    2.99 +        }
   2.100 +    }
   2.101 +
   2.102 +    // verify pair iterator
   2.103 +    {
   2.104 +        auto pairiter = cxMapIterator(map);
   2.105 +        std::unordered_map<std::string, std::string> pairs;
   2.106 +        cx_foreach(CxMapEntry*, entry, pairiter) {
   2.107 +            pairs[std::string((char const *) entry->key->data)] = std::string((char *) entry->value);
   2.108 +        }
   2.109 +        ASSERT_EQ(pairs.size(), refmap.size());
   2.110 +        for (auto &&p: pairs) {
   2.111 +            ASSERT_EQ(p.second, refmap.at(p.first));
   2.112 +        }
   2.113 +    }
   2.114 +}
   2.115 +
   2.116 +TEST(CxHashMap, Create) {
   2.117 +    CxTestingAllocator allocator;
   2.118 +    auto map = cxHashMapCreate(&allocator, 0);
   2.119 +    auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
   2.120 +    EXPECT_GT(hmap->bucket_count, 0);
   2.121 +    cx_for_n(i, hmap->bucket_count) {
   2.122 +        EXPECT_EQ(hmap->buckets[i], nullptr);
   2.123 +    }
   2.124 +    EXPECT_EQ(map->size, 0);
   2.125 +    EXPECT_EQ(map->allocator, &allocator);
   2.126 +
   2.127 +    cxMapDestroy(map);
   2.128 +    EXPECT_TRUE(allocator.verify());
   2.129 +}
   2.130 +
   2.131 +TEST(CxHashMap, BasicOperations) {
   2.132 +    // create the map
   2.133 +    CxTestingAllocator allocator;
   2.134 +    auto map = cxHashMapCreate(&allocator, 8);
   2.135 +
   2.136 +    // create a reference map
   2.137 +    std::unordered_map<std::string, std::string> refmap;
   2.138 +
   2.139 +    // generate operations
   2.140 +    auto ops = generate_map_operations();
   2.141 +
   2.142 +    // verify iterators for empty map
   2.143 +    verify_map_contents(map, refmap);
   2.144 +
   2.145 +    // execute operations and verify results
   2.146 +    for (auto &&op: ops) {
   2.147 +        CxDataPtr key = {reinterpret_cast<const unsigned char *>(op.key), 1 + strlen(op.key)};
   2.148 +        if (op.op == map_operation::put) {
   2.149 +            // execute a put operation and verify that the exact value can be read back
   2.150 +            refmap[std::string(op.key)] = std::string(op.value);
   2.151 +            int result = cxMapPut(map, key, (void *) op.value);
   2.152 +            EXPECT_EQ(result, 0);
   2.153 +            auto added = cxMapGet(map, key);
   2.154 +            EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
   2.155 +        } else {
   2.156 +            // execute a remove and verify that the removed element was returned (or nullptr)
   2.157 +            auto found = refmap.find(op.key);
   2.158 +            auto removed = cxMapRemove(map, key);
   2.159 +            if (found == refmap.end()) {
   2.160 +                EXPECT_EQ(removed, nullptr);
   2.161 +            } else {
   2.162 +                EXPECT_EQ(std::string((char *) removed), found->second);
   2.163 +                refmap.erase(found);
   2.164 +            }
   2.165 +        }
   2.166 +        // compare the current map state with the reference map
   2.167 +        verify_map_contents(map, refmap);
   2.168 +    }
   2.169 +
   2.170 +    // destroy the map and verify the memory (de)allocations
   2.171 +    cxMapDestroy(map);
   2.172 +    EXPECT_TRUE(allocator.verify());
   2.173 +}