2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <folly/AtomicHashArray.h>
22 #include <folly/Conv.h>
23 #include <folly/Hash.h>
24 #include <folly/Memory.h>
25 #include <folly/portability/SysMman.h>
26 #include <gtest/gtest.h>
29 using namespace folly;
36 typedef const T* const_pointer;
38 typedef const T& const_reference;
40 typedef ptrdiff_t difference_type;
41 typedef size_t size_type;
43 T* address(T& x) const {
44 return std::addressof(x);
47 const T* address(const T& x) const {
48 return std::addressof(x);
51 size_t max_size() const {
52 return std::numeric_limits<size_t>::max();
55 template <class U> struct rebind {
56 typedef MmapAllocator<U> other;
59 bool operator!=(const MmapAllocator<T>& other) const {
60 return !(*this == other);
63 bool operator==(const MmapAllocator<T>& /* other */) const { return true; }
65 template <class... Args>
66 void construct(T* p, Args&&... args) {
67 new (p) T(std::forward<Args>(args)...);
74 T *allocate(size_t n) {
75 void *p = mmap(nullptr, n * sizeof(T), PROT_READ | PROT_WRITE,
76 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
77 if (p == MAP_FAILED) throw std::bad_alloc();
81 void deallocate(T *p, size_t n) {
82 munmap(p, n * sizeof(T));
86 template<class KeyT, class ValueT>
87 pair<KeyT,ValueT> createEntry(int i) {
88 return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
94 class Allocator = std::allocator<char>,
95 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
97 typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
98 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
99 auto arr = MyArr::create(150);
100 map<KeyT, ValueT> ref;
101 for (int i = 0; i < 100; ++i) {
102 auto e = createEntry<KeyT, ValueT>(i);
103 auto ret = arr->insert(e);
104 EXPECT_EQ(!ref.count(e.first), ret.second); // succeed iff not in ref
106 EXPECT_EQ(ref.size(), arr->size());
107 if (ret.first == arr->end()) {
108 EXPECT_FALSE("AHA should not have run out of space.");
111 EXPECT_EQ(e.first, ret.first->first);
112 EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
115 for (int i = 125; i > 0; i -= 10) {
116 auto e = createEntry<KeyT, ValueT>(i);
117 auto ret = arr->erase(e.first);
118 auto refRet = ref.erase(e.first);
119 EXPECT_EQ(ref.size(), arr->size());
120 EXPECT_EQ(refRet, ret);
123 for (int i = 155; i > 0; i -= 10) {
124 auto e = createEntry<KeyT, ValueT>(i);
125 auto ret = arr->insert(e);
126 auto refRet = ref.insert(e);
127 EXPECT_EQ(ref.size(), arr->size());
128 EXPECT_EQ(*refRet.first, *ret.first);
129 EXPECT_EQ(refRet.second, ret.second);
132 for (const auto& e : ref) {
133 auto ret = arr->find(e.first);
134 if (ret == arr->end()) {
135 EXPECT_FALSE("Key was not in AHA");
138 EXPECT_EQ(e.first, ret->first);
139 EXPECT_EQ(e.second, ret->second);
143 template<class KeyT, class ValueT,
144 class Allocator = std::allocator<char>,
145 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
146 void testNoncopyableMap() {
147 typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
148 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
150 auto arr = MyArr::create(250);
151 for (int i = 0; i < 100; i++) {
152 arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
154 for (int i = 100; i < 150; i++) {
155 arr->emplace(i,new ValueT(i));
157 for (int i = 150; i < 200; i++) {
158 arr->emplace(i,new ValueT(i),std::default_delete<ValueT>());
160 for (int i = 0; i < 200; i++) {
161 auto ret = arr->find(i);
162 EXPECT_EQ(*(ret->second), i);
167 TEST(Aha, InsertErase_i32_i32) {
168 testMap<int32_t, int32_t>();
169 testMap<int32_t, int32_t, MmapAllocator<char>>();
170 testMap<int32_t, int32_t,
171 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
172 testMap<int32_t, int32_t,
173 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
174 testNoncopyableMap<int32_t, int32_t>();
175 testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
176 testNoncopyableMap<int32_t, int32_t,
177 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
178 testNoncopyableMap<int32_t, int32_t,
179 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
181 TEST(Aha, InsertErase_i64_i32) {
182 testMap<int64_t, int32_t>();
183 testMap<int64_t, int32_t, MmapAllocator<char>>();
184 testMap<int64_t, int32_t,
185 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
186 testMap<int64_t, int32_t,
187 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
188 testNoncopyableMap<int64_t, int32_t>();
189 testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
190 testNoncopyableMap<int64_t, int32_t,
191 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
192 testNoncopyableMap<int64_t, int32_t,
193 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
195 TEST(Aha, InsertErase_i64_i64) {
196 testMap<int64_t, int64_t>();
197 testMap<int64_t, int64_t, MmapAllocator<char>>();
198 testMap<int64_t, int64_t,
199 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
200 testMap<int64_t, int64_t,
201 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
202 testNoncopyableMap<int64_t, int64_t>();
203 testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
204 testNoncopyableMap<int64_t, int64_t,
205 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
206 testNoncopyableMap<int64_t, int64_t,
207 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
209 TEST(Aha, InsertErase_i32_i64) {
210 testMap<int32_t, int64_t>();
211 testMap<int32_t, int64_t, MmapAllocator<char>>();
212 testMap<int32_t, int64_t,
213 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
214 testMap<int32_t, int64_t,
215 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
216 testNoncopyableMap<int32_t, int64_t>();
217 testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
218 testNoncopyableMap<int32_t, int64_t,
219 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
220 testNoncopyableMap<int32_t, int64_t,
221 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
223 TEST(Aha, InsertErase_i32_str) {
224 testMap<int32_t, string>();
225 testMap<int32_t, string, MmapAllocator<char>>();
226 testMap<int32_t, string,
227 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
228 testMap<int32_t, string,
229 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
231 TEST(Aha, InsertErase_i64_str) {
232 testMap<int64_t, string>();
233 testMap<int64_t, string, MmapAllocator<char>>();
234 testMap<int64_t, string,
235 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
236 testMap<int64_t, string,
237 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
240 TEST(Aha, Create_cstr_i64) {
241 auto obj = AtomicHashArray<const char*, int64_t>::create(12);
244 static bool legalKey(char* a);
246 // Support two additional key lookup types (char and StringPiece) using
247 // one set of traits.
249 bool operator()(char* a, char* b) {
250 return legalKey(a) && (strcmp(a, b) == 0);
252 bool operator()(char* a, const char& b) {
253 return legalKey(a) && (a[0] != '\0') && (a[0] == b);
255 bool operator()(char* a, const StringPiece b) {
256 return legalKey(a) &&
257 (strlen(a) == b.size()) && (strncmp(a, b.begin(), b.size()) == 0);
262 size_t operator()(char* a) {
264 while (a[0] != 0) result += static_cast<size_t>(*(a++));
267 size_t operator()(const char& a) {
268 return static_cast<size_t>(a);
270 size_t operator()(const StringPiece a) {
272 for (const auto& ch : a) result += static_cast<size_t>(ch);
277 // Creates malloc'ed null-terminated strings.
278 struct KeyConvertTraits {
279 char* operator()(const char& a) {
280 return strndup(&a, 1);
282 char* operator()(const StringPiece a) {
283 return strndup(a.begin(), a.size());
287 typedef AtomicHashArray<char*, int64_t, HashTraits, EqTraits,
288 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn,
291 AHACstrInt::Config cstrIntCfg;
293 static bool legalKey(char* a) {
294 return a != cstrIntCfg.emptyKey &&
295 a != cstrIntCfg.lockedKey &&
296 a != cstrIntCfg.erasedKey;
299 TEST(Aha, LookupAny) {
300 auto arr = AHACstrInt::create(12);
302 char* f_char = strdup("f");
303 SCOPE_EXIT { free(f_char); };
304 arr->insert(std::make_pair(f_char, 42));
306 EXPECT_EQ(42, arr->find("f")->second);
308 // Look up a single char, successfully.
309 auto it = arr->find('f');
310 EXPECT_EQ(42, it->second);
313 // Look up a single char, unsuccessfully.
314 auto it = arr->find('g');
315 EXPECT_TRUE(it == arr->end());
318 // Insert a new char key.
319 auto res = arr->emplace('h', static_cast<int64_t>(123));
320 EXPECT_TRUE(res.second);
321 EXPECT_TRUE(res.first != arr->end());
322 // Look up the string version.
323 EXPECT_EQ(123, arr->find("h")->second);
326 // Fail to emplace an existing key.
327 auto res = arr->emplace('f', static_cast<int64_t>(123));
328 EXPECT_FALSE(res.second);
329 EXPECT_TRUE(res.first != arr->end());
332 for (auto it : *arr) {
337 using AHAIntCInt = AtomicHashArray<int64_t, const int32_t>;
339 TEST(Aha, ConstValue) {
340 auto aha = AHAIntCInt::create(10);