src/gromacs/domdec/tests/hashedmap.cpp

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2018,2019,2021, by the GROMACS development team, led by
   5  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   6  * and including many others, as listed in the AUTHORS file in the
   7  * top-level source directory and at http://www.gromacs.org.
   8  *
   9  * GROMACS is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public License
  11  * as published by the Free Software Foundation; either version 2.1
  12  * of the License, or (at your option) any later version.
  13  *
  14  * GROMACS is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with GROMACS; if not, see
  21  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  23  *
  24  * If you want to redistribute modifications to GROMACS, please
  25  * consider that scientific software is very special. Version
  26  * control is crucial - bugs must be traceable. We will be happy to
  27  * consider code for inclusion in the official distribution, but
  28  * derived work must not be called official GROMACS. Details are found
  29  * in the README & COPYING files - if they are missing, get the
  30  * official version at http://www.gromacs.org.
  31  *
  32  * To help us fund GROMACS development, we humbly ask that you cite
  33  * the research papers on the package. Check out http://www.gromacs.org.
  34  */
  35 /*! \internal \file
  36  * \brief
  37  * Tests for the HashedMap class.
  38  *
  39  * \author berk Hess <hess@kth.se>
  40  * \ingroup module_domdec
  41  */
  42 #include "gmxpre.h"
  43
  44 #include "gromacs/domdec/hashedmap.h"
  45
  46 #include <gtest/gtest.h>
  47
  48 #include "testutils/testasserts.h"
  49
  50 namespace
  51 {
  52
  53 /*! \brief Checks that the key is found and if so also checks the value */
  54 void checkFinds(const gmx::HashedMap<char>& map, int key, char value)
  55 {
  56     const char* pointer = map.find(key);
  57     EXPECT_FALSE(pointer == nullptr);
  58     if (pointer)
  59     {
  60         EXPECT_EQ(*pointer, value);
  61     }
  62 }
  63
  64 /*! \brief Checks that the key is not found */
  65 void checkDoesNotFind(const gmx::HashedMap<char>& map, int key)
  66 {
  67     const char* pointer = map.find(key);
  68     EXPECT_TRUE(pointer == nullptr);
  69 }
  70
  71 TEST(HashedMap, InsertsFinds)
  72 {
  73     gmx::HashedMap<char> map(2);
  74
  75     map.insert(10, 'a');
  76     map.insert(5, 'b');
  77     map.insert(7, 'c');
  78
  79     checkFinds(map, 10, 'a');
  80     checkFinds(map, 5, 'b');
  81     checkFinds(map, 7, 'c');
  82     checkDoesNotFind(map, 4);
  83 }
  84
  85 TEST(HashedMap, NegativeKeysWork)
  86 {
  87     gmx::HashedMap<char> map(5);
  88
  89     map.insert(-1, 'a');
  90     map.insert(1, 'b');
  91     map.insert(-3, 'c');
  92
  93     checkFinds(map, -1, 'a');
  94     checkFinds(map, 1, 'b');
  95     checkFinds(map, -3, 'c');
  96 }
  97
  98 TEST(HashedMap, InsertsErases)
  99 {
 100     gmx::HashedMap<char> map(3);
 101
 102     map.insert(10, 'a');
 103     map.insert(5, 'b');
 104     map.insert(7, 'c');
 105
 106     checkFinds(map, 10, 'a');
 107     map.erase(10);
 108     checkDoesNotFind(map, 10);
 109 }
 110
 111 TEST(HashedMap, InsertsOrAssigns)
 112 {
 113     gmx::HashedMap<char> map(3);
 114
 115     map.insert(10, 'a');
 116     map.insert(5, 'b');
 117
 118     map.insert_or_assign(7, 'c');
 119     checkFinds(map, 7, 'c');
 120
 121     checkFinds(map, 10, 'a');
 122     map.insert_or_assign(10, 'd');
 123     checkFinds(map, 10, 'd');
 124 }
 125
 126 TEST(HashedMap, Clears)
 127 {
 128     gmx::HashedMap<char> map(3);
 129
 130     map.insert(10, 'a');
 131     map.insert(5, 'b');
 132     map.insert(7, 'c');
 133
 134     map.clear();
 135     checkDoesNotFind(map, 10);
 136     checkDoesNotFind(map, 5);
 137     checkDoesNotFind(map, 7);
 138 }
 139
 140 // Check that entries with the same hash are handled correctly
 141 TEST(HashedMap, LinkedEntries)
 142 {
 143     // HashedMap uses bit masking, so keys that differ by exactly
 144     // a power of 2 larger than the table size will have the same hash
 145
 146     gmx::HashedMap<char> map(20);
 147
 148     const int largePowerOf2 = 2048;
 149
 150     map.insert(3 + 0 * largePowerOf2, 'a');
 151     map.insert(3 + 1 * largePowerOf2, 'b');
 152     map.insert(3 + 2 * largePowerOf2, 'c');
 153
 154     checkFinds(map, 3 + 0 * largePowerOf2, 'a');
 155     checkFinds(map, 3 + 1 * largePowerOf2, 'b');
 156     checkFinds(map, 3 + 2 * largePowerOf2, 'c');
 157
 158     // Erase the middle entry in the linked list
 159     map.erase(3 + 1 * largePowerOf2);
 160
 161     checkFinds(map, 3 + 0 * largePowerOf2, 'a');
 162     checkDoesNotFind(map, 3 + 1 * largePowerOf2);
 163     checkFinds(map, 3 + 2 * largePowerOf2, 'c');
 164 }
 165
 166 // HashedMap only throws in debug mode, so only test in debug mode
 167 #ifndef NDEBUG
 168
 169 TEST(HashedMap, CatchesDuplicateKey)
 170 {
 171     gmx::HashedMap<char> map(15);
 172
 173     map.insert(10, 'a');
 174     map.insert(5, 'b');
 175     EXPECT_THROW_GMX(map.insert(10, 'c'), gmx::InvalidInputError);
 176 }
 177
 178 #endif // NDEBUG
 179
 180 // Check the table is resized after clear()
 181 TEST(HashedMap, ResizesTable)
 182 {
 183     gmx::HashedMap<char> map(1);
 184
 185     // This test assumes the minimum bucket count is 64 or less
 186     EXPECT_LT(map.bucket_count(), 128);
 187
 188     for (int i = 0; i < 60; i++)
 189     {
 190         map.insert(2 * i + 3, 'a');
 191     }
 192     EXPECT_LT(map.bucket_count(), 128);
 193
 194     // Check that the table size is double #elements after clear()
 195     map.clearAndResizeHashTable();
 196     EXPECT_EQ(map.bucket_count(), 128);
 197
 198     // Check that calling clear() a second time does not resize
 199     map.clearAndResizeHashTable();
 200     EXPECT_EQ(map.bucket_count(), 128);
 201
 202     map.insert(2, 'b');
 203     EXPECT_EQ(map.bucket_count(), 128);
 204
 205     // Check that calling clear with 1 elements sizes down
 206     map.clearAndResizeHashTable();
 207     EXPECT_LT(map.bucket_count(), 128);
 208 }
 209
 210 } // namespace