2 * This file is part of the GROMACS molecular simulation package.
4 * Copyright (c) 2018,2019, 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.
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.
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.
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.
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.
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.
37 * Tests for the HashedMap class.
39 * \author berk Hess <hess@kth.se>
40 * \ingroup module_domdec
44 #include "gromacs/domdec/hashedmap.h"
46 #include <gtest/gtest.h>
48 #include "testutils/testasserts.h"
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)
56 const char* pointer = map.find(key);
57 EXPECT_FALSE(pointer == nullptr);
60 EXPECT_EQ(*pointer, value);
64 /*! \brief Checks that the key is not found */
65 void checkDoesNotFind(const gmx::HashedMap<char>& map, int key)
67 const char* pointer = map.find(key);
68 EXPECT_TRUE(pointer == nullptr);
71 TEST(HashedMap, InsertsFinds)
73 gmx::HashedMap<char> map(2);
79 checkFinds(map, 10, 'a');
80 checkFinds(map, 5, 'b');
81 checkFinds(map, 7, 'c');
82 checkDoesNotFind(map, 4);
85 TEST(HashedMap, NegativeKeysWork)
87 gmx::HashedMap<char> map(5);
93 checkFinds(map, -1, 'a');
94 checkFinds(map, 1, 'b');
95 checkFinds(map, -3, 'c');
98 TEST(HashedMap, InsertsErases)
100 gmx::HashedMap<char> map(3);
106 checkFinds(map, 10, 'a');
108 checkDoesNotFind(map, 10);
111 TEST(HashedMap, InsertsOrAssigns)
113 gmx::HashedMap<char> map(3);
118 map.insert_or_assign(7, 'c');
119 checkFinds(map, 7, 'c');
121 checkFinds(map, 10, 'a');
122 map.insert_or_assign(10, 'd');
123 checkFinds(map, 10, 'd');
126 TEST(HashedMap, Clears)
128 gmx::HashedMap<char> map(3);
135 checkDoesNotFind(map, 10);
136 checkDoesNotFind(map, 5);
137 checkDoesNotFind(map, 7);
140 // Check that entries with the same hash are handled correctly
141 TEST(HashedMap, LinkedEntries)
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
146 gmx::HashedMap<char> map(20);
148 const int largePowerOf2 = 2048;
150 map.insert(3 + 0 * largePowerOf2, 'a');
151 map.insert(3 + 1 * largePowerOf2, 'b');
152 map.insert(3 + 2 * largePowerOf2, 'c');
154 checkFinds(map, 3 + 0 * largePowerOf2, 'a');
155 checkFinds(map, 3 + 1 * largePowerOf2, 'b');
156 checkFinds(map, 3 + 2 * largePowerOf2, 'c');
158 // Erase the middle entry in the linked list
159 map.erase(3 + 1 * largePowerOf2);
161 checkFinds(map, 3 + 0 * largePowerOf2, 'a');
162 checkDoesNotFind(map, 3 + 1 * largePowerOf2);
163 checkFinds(map, 3 + 2 * largePowerOf2, 'c');
166 // HashedMap only throws in debug mode, so only test in debug mode
169 TEST(HashedMap, CatchesDuplicateKey)
171 gmx::HashedMap<char> map(15);
175 EXPECT_THROW_GMX(map.insert(10, 'c'), gmx::InvalidInputError);
180 // Check the table is resized after clear()
181 TEST(HashedMap, ResizesTable)
183 gmx::HashedMap<char> map(1);
185 // This test assumes the minimum bucket count is 64 or less
186 EXPECT_LT(map.bucket_count(), 128);
188 for (int i = 0; i < 60; i++)
190 map.insert(2 * i + 3, 'a');
192 EXPECT_LT(map.bucket_count(), 128);
194 // Check that the table size is double #elements after clear()
196 EXPECT_EQ(map.bucket_count(), 128);
198 // Check that calling clear() a second time does not resize
200 EXPECT_EQ(map.bucket_count(), 128);
203 EXPECT_EQ(map.bucket_count(), 128);
205 // Check that calling clear with 1 elements sizes down
207 EXPECT_LT(map.bucket_count(), 128);