OpenShot Audio Library | OpenShotAudio  0.3.0
juce_HashMap_test.cpp
1 /*
2  ==============================================================================
3 
4  This file is part of the JUCE library.
5  Copyright (c) 2017 - ROLI Ltd.
6 
7  JUCE is an open source library subject to commercial or open-source
8  licensing.
9 
10  The code included in this file is provided under the terms of the ISC license
11  http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12  To use, copy, modify, and/or distribute this software for any purpose with or
13  without fee is hereby granted provided that the above copyright notice and
14  this permission notice appear in all copies.
15 
16  JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17  EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18  DISCLAIMED.
19 
20  ==============================================================================
21 */
22 
23 namespace juce
24 {
25 
26 struct HashMapTest : public UnitTest
27 {
28  HashMapTest()
29  : UnitTest ("HashMap", UnitTestCategories::containers)
30  {}
31 
32  void runTest() override
33  {
34  doTest<AddElementsTest> ("AddElementsTest");
35  doTest<AccessTest> ("AccessTest");
36  doTest<RemoveTest> ("RemoveTest");
37  doTest<PersistantMemoryLocationOfValues> ("PersistantMemoryLocationOfValues");
38  }
39 
40  //==============================================================================
41  struct AddElementsTest
42  {
43  template <typename KeyType>
44  static void run (UnitTest& u)
45  {
46  AssociativeMap<KeyType, int> groundTruth;
47  HashMap<KeyType, int> hashMap;
48 
49  RandomKeys<KeyType> keyOracle (300, 3827829);
50  Random valueOracle (48735);
51 
52  int totalValues = 0;
53  for (int i = 0; i < 10000; ++i)
54  {
55  auto key = keyOracle.next();
56  auto value = valueOracle.nextInt();
57 
58  bool contains = (groundTruth.find (key) != nullptr);
59  u.expectEquals ((int) contains, (int) hashMap.contains (key));
60 
61  groundTruth.add (key, value);
62  hashMap.set (key, value);
63 
64  if (! contains) totalValues++;
65 
66  u.expectEquals (hashMap.size(), totalValues);
67  }
68  }
69  };
70 
71  struct AccessTest
72  {
73  template <typename KeyType>
74  static void run (UnitTest& u)
75  {
76  AssociativeMap<KeyType, int> groundTruth;
77  HashMap<KeyType, int> hashMap;
78 
79  fillWithRandomValues (hashMap, groundTruth);
80 
81  for (auto pair : groundTruth.pairs)
82  u.expectEquals (hashMap[pair.key], pair.value);
83  }
84  };
85 
86  struct RemoveTest
87  {
88  template <typename KeyType>
89  static void run (UnitTest& u)
90  {
91  AssociativeMap<KeyType, int> groundTruth;
92  HashMap<KeyType, int> hashMap;
93 
94  fillWithRandomValues (hashMap, groundTruth);
95  auto n = groundTruth.size();
96 
97  Random r (3827387);
98 
99  for (int i = 0; i < 100; ++i)
100  {
101  auto idx = r.nextInt (n-- - 1);
102  auto key = groundTruth.pairs.getReference (idx).key;
103 
104  groundTruth.pairs.remove (idx);
105  hashMap.remove (key);
106 
107  u.expect (! hashMap.contains (key));
108 
109  for (auto pair : groundTruth.pairs)
110  u.expectEquals (hashMap[pair.key], pair.value);
111  }
112  }
113  };
114 
115  // ensure that the addresses of object references don't change
116  struct PersistantMemoryLocationOfValues
117  {
118  struct AddressAndValue { int value; const int* valueAddress; };
119 
120  template <typename KeyType>
121  static void run (UnitTest& u)
122  {
123  AssociativeMap<KeyType, AddressAndValue> groundTruth;
124  HashMap<KeyType, int> hashMap;
125 
126  RandomKeys<KeyType> keyOracle (300, 3827829);
127  Random valueOracle (48735);
128 
129  for (int i = 0; i < 1000; ++i)
130  {
131  auto key = keyOracle.next();
132  auto value = valueOracle.nextInt();
133 
134  hashMap.set (key, value);
135 
136  if (auto* existing = groundTruth.find (key))
137  {
138  // don't change the address: only the value
139  existing->value = value;
140  }
141  else
142  {
143  groundTruth.add (key, { value, &hashMap.getReference (key) });
144  }
145 
146  for (auto pair : groundTruth.pairs)
147  {
148  const auto& hashMapValue = hashMap.getReference (pair.key);
149 
150  u.expectEquals (hashMapValue, pair.value.value);
151  u.expect (&hashMapValue == pair.value.valueAddress);
152  }
153  }
154 
155  auto n = groundTruth.size();
156  Random r (3827387);
157 
158  for (int i = 0; i < 100; ++i)
159  {
160  auto idx = r.nextInt (n-- - 1);
161  auto key = groundTruth.pairs.getReference (idx).key;
162 
163  groundTruth.pairs.remove (idx);
164  hashMap.remove (key);
165 
166  for (auto pair : groundTruth.pairs)
167  {
168  const auto& hashMapValue = hashMap.getReference (pair.key);
169 
170  u.expectEquals (hashMapValue, pair.value.value);
171  u.expect (&hashMapValue == pair.value.valueAddress);
172  }
173  }
174  }
175  };
176 
177  //==============================================================================
178  template <class Test>
179  void doTest (const String& testName)
180  {
181  beginTest (testName);
182 
183  Test::template run<int> (*this);
184  Test::template run<void*> (*this);
185  Test::template run<String> (*this);
186  }
187 
188  //==============================================================================
189  template <typename KeyType, typename ValueType>
190  struct AssociativeMap
191  {
192  struct KeyValuePair { KeyType key; ValueType value; };
193 
194  ValueType* find (KeyType key)
195  {
196  auto n = pairs.size();
197 
198  for (int i = 0; i < n; ++i)
199  {
200  auto& pair = pairs.getReference (i);
201 
202  if (pair.key == key)
203  return &pair.value;
204  }
205 
206  return nullptr;
207  }
208 
209  void add (KeyType key, ValueType value)
210  {
211  if (ValueType* v = find (key))
212  *v = value;
213  else
214  pairs.add ({key, value});
215  }
216 
217  int size() const { return pairs.size(); }
218 
219  Array<KeyValuePair> pairs;
220  };
221 
222  template <typename KeyType, typename ValueType>
223  static void fillWithRandomValues (HashMap<KeyType, int>& hashMap, AssociativeMap<KeyType, ValueType>& groundTruth)
224  {
225  RandomKeys<KeyType> keyOracle (300, 3827829);
226  Random valueOracle (48735);
227 
228  for (int i = 0; i < 10000; ++i)
229  {
230  auto key = keyOracle.next();
231  auto value = valueOracle.nextInt();
232 
233  groundTruth.add (key, value);
234  hashMap.set (key, value);
235  }
236  }
237 
238  //==============================================================================
239  template <typename KeyType>
240  class RandomKeys
241  {
242  public:
243  RandomKeys (int maxUniqueKeys, int seed) : r (seed)
244  {
245  for (int i = 0; i < maxUniqueKeys; ++i)
246  keys.add (generateRandomKey (r));
247  }
248 
249  const KeyType& next()
250  {
251  int i = r.nextInt (keys.size() - 1);
252  return keys.getReference (i);
253  }
254  private:
255  static KeyType generateRandomKey (Random&);
256 
257  Random r;
258  Array<KeyType> keys;
259  };
260 };
261 
262 template <> int HashMapTest::RandomKeys<int> ::generateRandomKey (Random& rnd) { return rnd.nextInt(); }
263 template <> void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) { return reinterpret_cast<void*> (rnd.nextInt64()); }
264 
265 template <> String HashMapTest::RandomKeys<String>::generateRandomKey (Random& rnd)
266 {
267  String str;
268 
269  int len = rnd.nextInt (8)+1;
270  for (int i = 0; i < len; ++i)
271  str += static_cast<char> (rnd.nextInt (95) + 32);
272 
273  return str;
274 }
275 
276 static HashMapTest hashMapTest;
277 
278 } // namespace juce
UnitTest(const String &name, const String &category=String())
void beginTest(const String &testName)