ucx: tests/test_map.cpp@dce9b8450656

     1 /*

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

     3  *

     4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "cx/hash_map.h"

    30 #include "cx/utils.h"

    31 #include "cx/string.h"

    32 #include "util_allocator.h"

    34 #include <gtest/gtest.h>

    35 #include <unordered_map>

    36 #include <unordered_set>

    38 struct map_operation {

    39     enum {

    40         put, rm

    41     } op;

    42     char const *key;

    43     char const *value;

    44 };

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

    47     return {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    65     };

    66 }

    68 static void verify_map_contents(

    69         CxMap *map,

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

    71 ) {

    72     // verify key iterator

    73     {

    74         auto keyiter = cxMapIteratorKeys(map);

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

    76         cx_foreach(CxHashKey*, elem, keyiter) {

    77             keys.insert(std::string(elem->data.cstr, elem->len));

    78         }

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

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

    81         for (auto &&k: keys) {

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

    83         }

    84     }

    86     // verify value iterator

    87     {

    88         auto valiter = cxMapIteratorValues(map);

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

    90         cx_foreach(char const*, elem, valiter) {

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

    92         }

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

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

    95         for (auto &&v: values) {

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

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

    98         }

    99     }

   101     // verify pair iterator

   102     {

   103         auto pairiter = cxMapIterator(map);

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

   105         cx_foreach(CxMapEntry*, entry, pairiter) {

   106             pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value);

   107         }

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

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

   110         for (auto &&p: pairs) {

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

   112         }

   113     }

   114 }

   116 TEST(CxHashMap, Create) {

   117     CxTestingAllocator allocator;

   118     auto map = cxHashMapCreate(&allocator, 1, 0);

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

   120     EXPECT_GT(hmap->bucket_count, 0);

   121     cx_for_n(i, hmap->bucket_count) {

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

   123     }

   124     EXPECT_EQ(map->itemsize, 1);

   125     EXPECT_EQ(map->size, 0);

   126     EXPECT_EQ(map->allocator, &allocator);

   127     EXPECT_FALSE(map->store_pointers);

   128     cxMapStorePointers(map);

   129     EXPECT_TRUE(map->store_pointers);

   130     EXPECT_EQ(map->itemsize, sizeof(void *));

   131     cxMapStoreObjects(map);

   132     EXPECT_FALSE(map->store_pointers);

   134     cxMapDestroy(map);

   135     EXPECT_TRUE(allocator.verify());

   136 }

   138 TEST(CxHashMap, CreateForStoringPointers) {

   139     CxTestingAllocator allocator;

   140     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);

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

   142     EXPECT_GT(hmap->bucket_count, 0);

   143     cx_for_n(i, hmap->bucket_count) {

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

   145     }

   146     EXPECT_EQ(map->size, 0);

   147     EXPECT_EQ(map->allocator, &allocator);

   148     EXPECT_TRUE(map->store_pointers);

   149     EXPECT_EQ(map->itemsize, sizeof(void *));

   151     cxMapDestroy(map);

   152     EXPECT_TRUE(allocator.verify());

   153 }

   155 TEST(CxHashMap, BasicOperations) {

   156     // create the map

   157     CxTestingAllocator allocator;

   158     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);

   160     // create a reference map

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

   163     // generate operations

   164     auto ops = generate_map_operations();

   166     // verify iterators for empty map

   167     verify_map_contents(map, refmap);

   169     // execute operations and verify results

   170     for (auto &&op: ops) {

   171         CxHashKey key = cx_hash_key_str(op.key);

   172         key.hash = 0; // force the hash map to compute the hash

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

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

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

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

   177             EXPECT_EQ(result, 0);

   178             auto added = cxMapGet(map, key);

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

   180         } else {

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

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

   183             auto removed = cxMapRemoveAndGet(map, key);

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

   185                 EXPECT_EQ(removed, nullptr);

   186             } else {

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

   188                 refmap.erase(found);

   189             }

   190         }

   191         // compare the current map state with the reference map

   192         verify_map_contents(map, refmap);

   193     }

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

   196     cxMapDestroy(map);

   197     EXPECT_TRUE(allocator.verify());

   198 }

   200 TEST(CxHashMap, RemoveViaIterator) {

   201     CxTestingAllocator allocator;

   202     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 4);

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

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

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

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

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

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

   211     auto iter = cxMapMutIterator(map);

   212     cx_foreach(CxMapEntry*, entry, iter) {

   213         if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);

   214     }

   215     EXPECT_EQ(map->size, 3);

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

   218     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);

   219     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);

   220     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);

   221     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);

   222     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);

   223     EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);

   225     cxMapDestroy(map);

   226     EXPECT_TRUE(allocator.verify());

   227 }

   229 TEST(CxHashMap, RehashNotRequired) {

   230     CxTestingAllocator allocator;

   231     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);

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

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

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

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

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

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

   240     // 6/8 does not exceed 0.75, therefore the function should not rehash

   241     int result = cxMapRehash(map);

   242     EXPECT_EQ(result, 0);

   243     EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);

   245     cxMapDestroy(map);

   246     EXPECT_TRUE(allocator.verify());

   247 }

   249 TEST(CxHashMap, Rehash) {

   250     CxTestingAllocator allocator;

   251     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);

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

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

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

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

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

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

   259     cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");

   261     int result = cxMapRehash(map);

   262     EXPECT_EQ(result, 0);

   263     EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);

   264     EXPECT_EQ(map->size, 7);

   266     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);

   267     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);

   268     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);

   269     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);

   270     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);

   271     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);

   272     EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);

   274     cxMapDestroy(map);

   275     EXPECT_TRUE(allocator.verify());

   276 }

   278 TEST(CxHashMap, Clear) {

   279     CxTestingAllocator allocator;

   280     auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);

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

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

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

   286     EXPECT_EQ(map->size, 3);

   288     cxMapClear(map);

   290     EXPECT_EQ(map->size, 0);

   291     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);

   292     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);

   293     EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);

   295     cxMapDestroy(map);

   296     EXPECT_TRUE(allocator.verify());

   297 }

   299 TEST(CxHashMap, StoreUcxStrings) {

   300     // create the map

   301     CxTestingAllocator allocator;

   302     auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);

   304     // define some strings

   305     cxstring s1 = CX_STR("this");

   306     cxstring s2 = CX_STR("is");

   307     cxstring s3 = CX_STR("a");

   308     cxstring s4 = CX_STR("test");

   309     cxstring s5 = CX_STR("setup");

   311     // put them into the map

   312     cxMapPut(map, cx_hash_key_str("s1"), &s1);

   313     cxMapPut(map, cx_hash_key_str("s2"), &s2);

   314     cxMapPut(map, cx_hash_key_str("s3"), &s3);

   315     cxMapPut(map, cx_hash_key_str("s4"), &s4);

   317     // overwrite a value

   318     cxMapPut(map, cx_hash_key_str("s1"), &s5);

   320     // look up a string

   321     auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, cx_hash_key_str("s3")));

   322     EXPECT_EQ(s3p->length, s3.length);

   323     EXPECT_EQ(s3p->ptr, s3.ptr);

   324     EXPECT_NE(s3p, &s3);

   326     // remove a string

   327     cxMapRemove(map, cx_hash_key_str("s2"));

   329     // iterate

   330     auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};

   331     auto iter = cxMapIteratorValues(map);

   332     cx_foreach(cxstring*, s, iter) {

   333         auto found = std::find(ref.begin(), ref.end(), s->ptr);

   334         ASSERT_NE(found, ref.end());

   335         ref.erase(found);

   336     }

   337     EXPECT_EQ(ref.size(), 0);

   339     cxMapDestroy(map);

   340     EXPECT_TRUE(allocator.verify());

   341 }

Mercurial > hg > ucx / file revision

tests/test_map.cpp@dce9b8450656

tests/test_map.cpp