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 | |
29 | using namespace std; |
30 | using namespace folly; |
31 | |
32 | template <class T> |
33 | class 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 | |
97 | template <class KeyT, class ValueT> |
98 | pair<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 | |
103 | template < |
104 | class KeyT, |
105 | class ValueT, |
106 | class Allocator = std::allocator<char>, |
107 | class ProbeFcn = AtomicHashArrayLinearProbeFcn> |
108 | void 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 | |
161 | template < |
162 | class KeyT, |
163 | class ValueT, |
164 | class Allocator = std::allocator<char>, |
165 | class ProbeFcn = AtomicHashArrayLinearProbeFcn> |
166 | void 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 | |
192 | TEST(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 | } |
218 | TEST(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 | } |
244 | TEST(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 | } |
270 | TEST(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 | } |
296 | TEST(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 | } |
310 | TEST(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 | |
325 | TEST(Aha, Create_cstr_i64) { |
326 | auto obj = AtomicHashArray<const char*, int64_t>::create(12); |
327 | } |
328 | |
329 | static bool legalKey(char* a); |
330 | |
331 | // Support two additional key lookup types (char and StringPiece) using |
332 | // one set of traits. |
333 | struct 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 | |
346 | struct 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. |
367 | struct 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 | |
376 | typedef AtomicHashArray< |
377 | char*, |
378 | int64_t, |
379 | HashTraits, |
380 | EqTraits, |
381 | MmapAllocator<char>, |
382 | AtomicHashArrayQuadraticProbeFcn, |
383 | KeyConvertTraits> |
384 | AHACstrInt; |
385 | AHACstrInt::Config cstrIntCfg; |
386 | |
387 | static bool legalKey(char* a) { |
388 | return a != cstrIntCfg.emptyKey && a != cstrIntCfg.lockedKey && |
389 | a != cstrIntCfg.erasedKey; |
390 | } |
391 | |
392 | TEST(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 | |
432 | using AHAIntCInt = AtomicHashArray<int64_t, const int32_t>; |
433 | |
434 | TEST(Aha, ConstValue) { |
435 | auto aha = AHAIntCInt::create(10); |
436 | aha->emplace(1, 2); |
437 | } |
438 | |