src/gromacs/domdec/tests/hashedmap.cpp

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2018, 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,
  55                 int                         key,
  56                 char                        value)
  57 {
  58     const char *pointer = map.find(key);
  59     EXPECT_FALSE(pointer == nullptr);
  60     if (pointer)
  61     {
  62         EXPECT_EQ(*pointer, value);
  63     }
  64 }
  65
  66 /*! \brief Checks that the key is not found */
  67 void checkDoesNotFind(const gmx::HashedMap<char> &map,
  68                       int                         key)
  69 {
  70     const char *pointer = map.find(key);
  71     EXPECT_TRUE(pointer == nullptr);
  72 }
  73
  74 TEST(HashedMap, InsertsFinds)
  75 {
  76     gmx::HashedMap<char> map(2);
  77
  78     map.insert(10, 'a');
  79     map.insert(5,  'b');
  80     map.insert(7,  'c');
  81
  82     checkFinds(map, 10, 'a');
  83     checkFinds(map, 5,  'b');
  84     checkFinds(map, 7,  'c');
  85     checkDoesNotFind(map, 4);
  86 }
  87
  88 TEST(HashedMap, NegativeKeysWork)
  89 {
  90     gmx::HashedMap<char> map(5);
  91
  92     map.insert(-1, 'a');
  93     map.insert(1,  'b');
  94     map.insert(-3, 'c');
  95
  96     checkFinds(map, -1, 'a');
  97     checkFinds(map, 1,  'b');
  98     checkFinds(map, -3, 'c');
  99 }
 100
 101 TEST(HashedMap, InsertsErases)
 102 {
 103     gmx::HashedMap<char> map(3);
 104
 105     map.insert(10, 'a');
 106     map.insert(5,  'b');
 107     map.insert(7,  'c');
 108
 109     checkFinds(map, 10, 'a');
 110     map.erase(10);
 111     checkDoesNotFind(map, 10);
 112 }
 113
 114 TEST(HashedMap, InsertsOrAssigns)
 115 {
 116     gmx::HashedMap<char> map(3);
 117
 118     map.insert(10, 'a');
 119     map.insert(5,  'b');
 120
 121     map.insert_or_assign(7, 'c');
 122     checkFinds(map, 7, 'c');
 123
 124     checkFinds(map, 10, 'a');
 125     map.insert_or_assign(10, 'd');
 126     checkFinds(map, 10, 'd');
 127 }
 128
 129 TEST(HashedMap, Clears)
 130 {
 131     gmx::HashedMap<char> map(3);
 132
 133     map.insert(10, 'a');
 134     map.insert(5,  'b');
 135     map.insert(7,  'c');
 136
 137     map.clear();
 138     checkDoesNotFind(map, 10);
 139     checkDoesNotFind(map, 5);
 140     checkDoesNotFind(map, 7);
 141 }
 142
 143 // Check that entries with the same hash are handled correctly
 144 TEST(HashedMap, LinkedEntries)
 145 {
 146     // HashedMap uses bit masking, so keys that differ by exactly
 147     // a power of 2 larger than the table size will have the same hash
 148
 149     gmx::HashedMap<char> map(20);
 150
 151     const int            largePowerOf2 = 2048;
 152
 153     map.insert(3 + 0*largePowerOf2, 'a');
 154     map.insert(3 + 1*largePowerOf2, 'b');
 155     map.insert(3 + 2*largePowerOf2, 'c');
 156
 157     checkFinds(map, 3 + 0*largePowerOf2, 'a');
 158     checkFinds(map, 3 + 1*largePowerOf2, 'b');
 159     checkFinds(map, 3 + 2*largePowerOf2, 'c');
 160
 161     // Erase the middle entry in the linked list
 162     map.erase(3 + 1*largePowerOf2);
 163
 164     checkFinds(map, 3 + 0*largePowerOf2, 'a');
 165     checkDoesNotFind(map, 3 + 1*largePowerOf2);
 166     checkFinds(map, 3 + 2*largePowerOf2, 'c');
 167 }
 168
 169 // HashedMap only throws in debug mode, so only test in debug mode
 170 #ifndef NDEBUG
 171
 172 TEST(HashedMap, CatchesDuplicateKey)
 173 {
 174     gmx::HashedMap<char> map(15);
 175
 176     map.insert(10, 'a');
 177     map.insert(5,  'b');
 178     EXPECT_THROW_GMX(map.insert(10, 'c'), gmx::InvalidInputError);
 179 }
 180
 181 #endif // NDEBUG
 182
 183 // Check the table is resized after clear()
 184 TEST(HashedMap, ResizesTable)
 185 {
 186     gmx::HashedMap<char> map(1);
 187
 188     // This test assumes the minimum bucket count is 64 or less
 189     EXPECT_LT(map.bucket_count(), 128);
 190
 191     for (int i = 0; i < 60; i++)
 192     {
 193         map.insert(2*i + 3, 'a');
 194     }
 195     EXPECT_LT(map.bucket_count(), 128);
 196
 197     // Check that the table size is double #elements after clear()
 198     map.clear();
 199     EXPECT_EQ(map.bucket_count(), 128);
 200
 201     // Check that calling clear() a second time does not resize
 202     map.clear();
 203     EXPECT_EQ(map.bucket_count(), 128);
 204
 205     map.insert(2, 'b');
 206     EXPECT_EQ(map.bucket_count(), 128);
 207
 208     // Check that calling clear with 1 elements sizes down
 209     map.clear();
 210     EXPECT_LT(map.bucket_count(), 128);
 211 }
 212
 213 }      // namespace