1/*
2 * Copyright 2012-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <cstddef>
18#include <map>
19#include <memory>
20#include <stdexcept>
21
22#include <folly/AtomicHashArray.h>
23#include <folly/Conv.h>
24#include <folly/Memory.h>
25#include <folly/hash/Hash.h>
26#include <folly/portability/GTest.h>
27#include <folly/portability/SysMman.h>
28
29using namespace std;
30using namespace folly;
31
32template <class T>
33class MmapAllocator {
34 public:
35 typedef T value_type;
36 typedef T* pointer;
37 typedef const T* const_pointer;
38 typedef T& reference;
39 typedef const T& const_reference;
40
41 typedef ptrdiff_t difference_type;
42 typedef size_t size_type;
43
44 T* address(T& x) const {
45 return std::addressof(x);
46 }
47
48 const T* address(const T& x) const {
49 return std::addressof(x);
50 }
51
52 size_t max_size() const {
53 return std::numeric_limits<size_t>::max();
54 }
55
56 template <class U>
57 struct rebind {
58 typedef MmapAllocator<U> other;
59 };
60
61 bool operator!=(const MmapAllocator<T>& other) const {
62 return !(*this == other);
63 }
64
65 bool operator==(const MmapAllocator<T>& /* other */) const {
66 return true;
67 }
68
69 template <class... Args>
70 void construct(T* p, Args&&... args) {
71 new (p) T(std::forward<Args>(args)...);
72 }
73
74 void destroy(T* p) {
75 p->~T();
76 }
77
78 T* allocate(size_t n) {
79 void* p = mmap(
80 nullptr,
81 n * sizeof(T),
82 PROT_READ | PROT_WRITE,
83 MAP_PRIVATE | MAP_ANONYMOUS,
84 -1,
85 0);
86 if (p == MAP_FAILED) {
87 throw std::bad_alloc();
88 }
89 return (T*)p;
90 }
91
92 void deallocate(T* p, size_t n) {
93 munmap(p, n * sizeof(T));
94 }
95};
96
97template <class KeyT, class ValueT>
98pair<KeyT, ValueT> createEntry(int i) {
99 return pair<KeyT, ValueT>(
100 to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000), to<ValueT>(i + 3));
101}
102
103template <
104 class KeyT,
105 class ValueT,
106 class Allocator = std::allocator<char>,
107 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
108void testMap() {
109 typedef AtomicHashArray<
110 KeyT,
111 ValueT,
112 std::hash<KeyT>,
113 std::equal_to<KeyT>,
114 Allocator,
115 ProbeFcn>
116 MyArr;
117 auto arr = MyArr::create(150);
118 map<KeyT, ValueT> ref;
119 for (int i = 0; i < 100; ++i) {
120 auto e = createEntry<KeyT, ValueT>(i);
121 auto ret = arr->insert(e);
122 EXPECT_EQ(!ref.count(e.first), ret.second); // succeed iff not in ref
123 ref.insert(e);
124 EXPECT_EQ(ref.size(), arr->size());
125 if (ret.first == arr->end()) {
126 EXPECT_FALSE("AHA should not have run out of space.");
127 continue;
128 }
129 EXPECT_EQ(e.first, ret.first->first);
130 EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
131 }
132
133 for (int i = 125; i > 0; i -= 10) {
134 auto e = createEntry<KeyT, ValueT>(i);
135 auto ret = arr->erase(e.first);
136 auto refRet = ref.erase(e.first);
137 EXPECT_EQ(ref.size(), arr->size());
138 EXPECT_EQ(refRet, ret);
139 }
140
141 for (int i = 155; i > 0; i -= 10) {
142 auto e = createEntry<KeyT, ValueT>(i);
143 auto ret = arr->insert(e);
144 auto refRet = ref.insert(e);
145 EXPECT_EQ(ref.size(), arr->size());
146 EXPECT_EQ(*refRet.first, *ret.first);
147 EXPECT_EQ(refRet.second, ret.second);
148 }
149
150 for (const auto& e : ref) {
151 auto ret = arr->find(e.first);
152 if (ret == arr->end()) {
153 EXPECT_FALSE("Key was not in AHA");
154 continue;
155 }
156 EXPECT_EQ(e.first, ret->first);
157 EXPECT_EQ(e.second, ret->second);
158 }
159}
160
161template <
162 class KeyT,
163 class ValueT,
164 class Allocator = std::allocator<char>,
165 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
166void testNoncopyableMap() {
167 typedef AtomicHashArray<
168 KeyT,
169 std::unique_ptr<ValueT>,
170 std::hash<KeyT>,
171 std::equal_to<KeyT>,
172 Allocator,
173 ProbeFcn>
174 MyArr;
175
176 auto arr = MyArr::create(250);
177 for (int i = 0; i < 100; i++) {
178 arr->insert(make_pair(i, std::make_unique<ValueT>(i)));
179 }
180 for (int i = 100; i < 150; i++) {
181 arr->emplace(i, new ValueT(i));
182 }
183 for (int i = 150; i < 200; i++) {
184 arr->emplace(i, new ValueT(i), std::default_delete<ValueT>());
185 }
186 for (int i = 0; i < 200; i++) {
187 auto ret = arr->find(i);
188 EXPECT_EQ(*(ret->second), i);
189 }
190}
191
192TEST(Aha, InsertErase_i32_i32) {
193 testMap<int32_t, int32_t>();
194 testMap<int32_t, int32_t, MmapAllocator<char>>();
195 testMap<
196 int32_t,
197 int32_t,
198 std::allocator<char>,
199 AtomicHashArrayQuadraticProbeFcn>();
200 testMap<
201 int32_t,
202 int32_t,
203 MmapAllocator<char>,
204 AtomicHashArrayQuadraticProbeFcn>();
205 testNoncopyableMap<int32_t, int32_t>();
206 testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
207 testNoncopyableMap<
208 int32_t,
209 int32_t,
210 std::allocator<char>,
211 AtomicHashArrayQuadraticProbeFcn>();
212 testNoncopyableMap<
213 int32_t,
214 int32_t,
215 MmapAllocator<char>,
216 AtomicHashArrayQuadraticProbeFcn>();
217}
218TEST(Aha, InsertErase_i64_i32) {
219 testMap<int64_t, int32_t>();
220 testMap<int64_t, int32_t, MmapAllocator<char>>();
221 testMap<
222 int64_t,
223 int32_t,
224 std::allocator<char>,
225 AtomicHashArrayQuadraticProbeFcn>();
226 testMap<
227 int64_t,
228 int32_t,
229 MmapAllocator<char>,
230 AtomicHashArrayQuadraticProbeFcn>();
231 testNoncopyableMap<int64_t, int32_t>();
232 testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
233 testNoncopyableMap<
234 int64_t,
235 int32_t,
236 std::allocator<char>,
237 AtomicHashArrayQuadraticProbeFcn>();
238 testNoncopyableMap<
239 int64_t,
240 int32_t,
241 MmapAllocator<char>,
242 AtomicHashArrayQuadraticProbeFcn>();
243}
244TEST(Aha, InsertErase_i64_i64) {
245 testMap<int64_t, int64_t>();
246 testMap<int64_t, int64_t, MmapAllocator<char>>();
247 testMap<
248 int64_t,
249 int64_t,
250 std::allocator<char>,
251 AtomicHashArrayQuadraticProbeFcn>();
252 testMap<
253 int64_t,
254 int64_t,
255 MmapAllocator<char>,
256 AtomicHashArrayQuadraticProbeFcn>();
257 testNoncopyableMap<int64_t, int64_t>();
258 testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
259 testNoncopyableMap<
260 int64_t,
261 int64_t,
262 std::allocator<char>,
263 AtomicHashArrayQuadraticProbeFcn>();
264 testNoncopyableMap<
265 int64_t,
266 int64_t,
267 MmapAllocator<char>,
268 AtomicHashArrayQuadraticProbeFcn>();
269}
270TEST(Aha, InsertErase_i32_i64) {
271 testMap<int32_t, int64_t>();
272 testMap<int32_t, int64_t, MmapAllocator<char>>();
273 testMap<
274 int32_t,
275 int64_t,
276 std::allocator<char>,
277 AtomicHashArrayQuadraticProbeFcn>();
278 testMap<
279 int32_t,
280 int64_t,
281 MmapAllocator<char>,
282 AtomicHashArrayQuadraticProbeFcn>();
283 testNoncopyableMap<int32_t, int64_t>();
284 testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
285 testNoncopyableMap<
286 int32_t,
287 int64_t,
288 std::allocator<char>,
289 AtomicHashArrayQuadraticProbeFcn>();
290 testNoncopyableMap<
291 int32_t,
292 int64_t,
293 MmapAllocator<char>,
294 AtomicHashArrayQuadraticProbeFcn>();
295}
296TEST(Aha, InsertErase_i32_str) {
297 testMap<int32_t, string>();
298 testMap<int32_t, string, MmapAllocator<char>>();
299 testMap<
300 int32_t,
301 string,
302 std::allocator<char>,
303 AtomicHashArrayQuadraticProbeFcn>();
304 testMap<
305 int32_t,
306 string,
307 MmapAllocator<char>,
308 AtomicHashArrayQuadraticProbeFcn>();
309}
310TEST(Aha, InsertErase_i64_str) {
311 testMap<int64_t, string>();
312 testMap<int64_t, string, MmapAllocator<char>>();
313 testMap<
314 int64_t,
315 string,
316 std::allocator<char>,
317 AtomicHashArrayQuadraticProbeFcn>();
318 testMap<
319 int64_t,
320 string,
321 MmapAllocator<char>,
322 AtomicHashArrayQuadraticProbeFcn>();
323}
324
325TEST(Aha, Create_cstr_i64) {
326 auto obj = AtomicHashArray<const char*, int64_t>::create(12);
327}
328
329static bool legalKey(char* a);
330
331// Support two additional key lookup types (char and StringPiece) using
332// one set of traits.
333struct EqTraits {
334 bool operator()(char* a, char* b) {
335 return legalKey(a) && (strcmp(a, b) == 0);
336 }
337 bool operator()(char* a, const char& b) {
338 return legalKey(a) && (a[0] != '\0') && (a[0] == b);
339 }
340 bool operator()(char* a, const StringPiece b) {
341 return legalKey(a) && (strlen(a) == b.size()) &&
342 (strncmp(a, b.begin(), b.size()) == 0);
343 }
344};
345
346struct HashTraits {
347 size_t operator()(char* a) {
348 size_t result = 0;
349 while (a[0] != 0) {
350 result += static_cast<size_t>(*(a++));
351 }
352 return result;
353 }
354 size_t operator()(const char& a) {
355 return static_cast<size_t>(a);
356 }
357 size_t operator()(const StringPiece a) {
358 size_t result = 0;
359 for (const auto& ch : a) {
360 result += static_cast<size_t>(ch);
361 }
362 return result;
363 }
364};
365
366// Creates malloc'ed null-terminated strings.
367struct KeyConvertTraits {
368 char* operator()(const char& a) {
369 return strndup(&a, 1);
370 }
371 char* operator()(const StringPiece a) {
372 return strndup(a.begin(), a.size());
373 }
374};
375
376typedef AtomicHashArray<
377 char*,
378 int64_t,
379 HashTraits,
380 EqTraits,
381 MmapAllocator<char>,
382 AtomicHashArrayQuadraticProbeFcn,
383 KeyConvertTraits>
384 AHACstrInt;
385AHACstrInt::Config cstrIntCfg;
386
387static bool legalKey(char* a) {
388 return a != cstrIntCfg.emptyKey && a != cstrIntCfg.lockedKey &&
389 a != cstrIntCfg.erasedKey;
390}
391
392TEST(Aha, LookupAny) {
393 auto arr = AHACstrInt::create(12);
394
395 char* f_char = strdup("f");
396 SCOPE_EXIT {
397 free(f_char);
398 };
399 arr->insert(std::make_pair(f_char, 42));
400
401 EXPECT_EQ(42, arr->find("f")->second);
402 {
403 // Look up a single char, successfully.
404 auto it = arr->find('f');
405 EXPECT_EQ(42, it->second);
406 }
407 {
408 // Look up a single char, unsuccessfully.
409 auto it = arr->find('g');
410 EXPECT_TRUE(it == arr->end());
411 }
412 {
413 // Insert a new char key.
414 auto res = arr->emplace('h', static_cast<int64_t>(123));
415 EXPECT_TRUE(res.second);
416 EXPECT_TRUE(res.first != arr->end());
417 // Look up the string version.
418 EXPECT_EQ(123, arr->find("h")->second);
419 }
420 {
421 // Fail to emplace an existing key.
422 auto res = arr->emplace('f', static_cast<int64_t>(123));
423 EXPECT_FALSE(res.second);
424 EXPECT_TRUE(res.first != arr->end());
425 }
426
427 for (auto it : *arr) {
428 free(it.first);
429 }
430}
431
432using AHAIntCInt = AtomicHashArray<int64_t, const int32_t>;
433
434TEST(Aha, ConstValue) {
435 auto aha = AHAIntCInt::create(10);
436 aha->emplace(1, 2);
437}
438