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.
23 #include <folly/AtomicHashArray.h>
24 #include <folly/Hash.h>
25 #include <folly/Conv.h>
26 #include <folly/Memory.h>
27 #include <gtest/gtest.h>
29 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
30 #define MAP_ANONYMOUS MAP_ANON
34 using namespace folly;
41 typedef const T* const_pointer;
43 typedef const T& const_reference;
45 typedef ptrdiff_t difference_type;
46 typedef size_t size_type;
48 T* address(T& x) const {
49 return std::addressof(x);
52 const T* address(const T& x) const {
53 return std::addressof(x);
56 size_t max_size() const {
57 return std::numeric_limits<size_t>::max();
60 template <class U> struct rebind {
61 typedef MmapAllocator<U> other;
64 bool operator!=(const MmapAllocator<T>& other) const {
65 return !(*this == other);
68 bool operator==(const MmapAllocator<T>& /* other */) const { return true; }
70 template <class... Args>
71 void construct(T* p, Args&&... args) {
72 new (p) T(std::forward<Args>(args)...);
79 T *allocate(size_t n) {
80 void *p = mmap(nullptr, n * sizeof(T), PROT_READ | PROT_WRITE,
81 MAP_SHARED | MAP_ANONYMOUS, -1, 0);
82 if (p == MAP_FAILED) throw std::bad_alloc();
86 void deallocate(T *p, size_t n) {
87 munmap(p, n * sizeof(T));
91 template<class KeyT, class ValueT>
92 pair<KeyT,ValueT> createEntry(int i) {
93 return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
99 class Allocator = std::allocator<char>,
100 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
102 typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
103 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
104 auto arr = MyArr::create(150);
105 map<KeyT, ValueT> ref;
106 for (int i = 0; i < 100; ++i) {
107 auto e = createEntry<KeyT, ValueT>(i);
108 auto ret = arr->insert(e);
109 EXPECT_EQ(!ref.count(e.first), ret.second); // succeed iff not in ref
111 EXPECT_EQ(ref.size(), arr->size());
112 if (ret.first == arr->end()) {
113 EXPECT_FALSE("AHA should not have run out of space.");
116 EXPECT_EQ(e.first, ret.first->first);
117 EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
120 for (int i = 125; i > 0; i -= 10) {
121 auto e = createEntry<KeyT, ValueT>(i);
122 auto ret = arr->erase(e.first);
123 auto refRet = ref.erase(e.first);
124 EXPECT_EQ(ref.size(), arr->size());
125 EXPECT_EQ(refRet, ret);
128 for (int i = 155; i > 0; i -= 10) {
129 auto e = createEntry<KeyT, ValueT>(i);
130 auto ret = arr->insert(e);
131 auto refRet = ref.insert(e);
132 EXPECT_EQ(ref.size(), arr->size());
133 EXPECT_EQ(*refRet.first, *ret.first);
134 EXPECT_EQ(refRet.second, ret.second);
137 for (const auto& e : ref) {
138 auto ret = arr->find(e.first);
139 if (ret == arr->end()) {
140 EXPECT_FALSE("Key was not in AHA");
143 EXPECT_EQ(e.first, ret->first);
144 EXPECT_EQ(e.second, ret->second);
148 template<class KeyT, class ValueT,
149 class Allocator = std::allocator<char>,
150 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
151 void testNoncopyableMap() {
152 typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
153 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
155 auto arr = MyArr::create(250);
156 for (int i = 0; i < 100; i++) {
157 arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
159 for (int i = 100; i < 150; i++) {
160 arr->emplace(i,new ValueT(i));
162 for (int i = 150; i < 200; i++) {
163 arr->emplace(i,new ValueT(i),std::default_delete<ValueT>());
165 for (int i = 0; i < 200; i++) {
166 auto ret = arr->find(i);
167 EXPECT_EQ(*(ret->second), i);
172 TEST(Aha, InsertErase_i32_i32) {
173 testMap<int32_t, int32_t>();
174 testMap<int32_t, int32_t, MmapAllocator<char>>();
175 testMap<int32_t, int32_t,
176 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
177 testMap<int32_t, int32_t,
178 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
179 testNoncopyableMap<int32_t, int32_t>();
180 testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
181 testNoncopyableMap<int32_t, int32_t,
182 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
183 testNoncopyableMap<int32_t, int32_t,
184 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
186 TEST(Aha, InsertErase_i64_i32) {
187 testMap<int64_t, int32_t>();
188 testMap<int64_t, int32_t, MmapAllocator<char>>();
189 testMap<int64_t, int32_t,
190 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
191 testMap<int64_t, int32_t,
192 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
193 testNoncopyableMap<int64_t, int32_t>();
194 testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
195 testNoncopyableMap<int64_t, int32_t,
196 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
197 testNoncopyableMap<int64_t, int32_t,
198 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
200 TEST(Aha, InsertErase_i64_i64) {
201 testMap<int64_t, int64_t>();
202 testMap<int64_t, int64_t, MmapAllocator<char>>();
203 testMap<int64_t, int64_t,
204 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
205 testMap<int64_t, int64_t,
206 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
207 testNoncopyableMap<int64_t, int64_t>();
208 testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
209 testNoncopyableMap<int64_t, int64_t,
210 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
211 testNoncopyableMap<int64_t, int64_t,
212 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
214 TEST(Aha, InsertErase_i32_i64) {
215 testMap<int32_t, int64_t>();
216 testMap<int32_t, int64_t, MmapAllocator<char>>();
217 testMap<int32_t, int64_t,
218 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
219 testMap<int32_t, int64_t,
220 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
221 testNoncopyableMap<int32_t, int64_t>();
222 testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
223 testNoncopyableMap<int32_t, int64_t,
224 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
225 testNoncopyableMap<int32_t, int64_t,
226 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
228 TEST(Aha, InsertErase_i32_str) {
229 testMap<int32_t, string>();
230 testMap<int32_t, string, MmapAllocator<char>>();
231 testMap<int32_t, string,
232 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
233 testMap<int32_t, string,
234 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
236 TEST(Aha, InsertErase_i64_str) {
237 testMap<int64_t, string>();
238 testMap<int64_t, string, MmapAllocator<char>>();
239 testMap<int64_t, string,
240 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
241 testMap<int64_t, string,
242 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
245 TEST(Aha, Create_cstr_i64) {
246 auto obj = AtomicHashArray<const char*, int64_t>::create(12);
249 static bool legalKey(char* a);
251 // Support two additional key lookup types (char and StringPiece) using
252 // one set of traits.
254 bool operator()(char* a, char* b) {
255 return legalKey(a) && (strcmp(a, b) == 0);
257 bool operator()(char* a, const char& b) {
258 return legalKey(a) && (a[0] != '\0') && (a[0] == b);
260 bool operator()(char* a, const StringPiece b) {
261 return legalKey(a) &&
262 (strlen(a) == b.size()) && (strncmp(a, b.begin(), b.size()) == 0);
267 size_t operator()(char* a) {
269 while (a[0] != 0) result += static_cast<size_t>(*(a++));
272 size_t operator()(const char& a) {
273 return static_cast<size_t>(a);
275 size_t operator()(const StringPiece a) {
277 for (const auto& ch : a) result += static_cast<size_t>(ch);
282 // Creates malloc'ed null-terminated strings.
283 struct KeyConvertTraits {
284 char* operator()(const char& a) {
285 return strndup(&a, 1);
287 char* operator()(const StringPiece a) {
288 return strndup(a.begin(), a.size());
292 typedef AtomicHashArray<char*, int64_t, HashTraits, EqTraits,
293 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn,
296 AHACstrInt::Config cstrIntCfg;
298 static bool legalKey(char* a) {
299 return a != cstrIntCfg.emptyKey &&
300 a != cstrIntCfg.lockedKey &&
301 a != cstrIntCfg.erasedKey;
304 TEST(Aha, LookupAny) {
305 auto arr = AHACstrInt::create(12);
307 arr->insert(std::make_pair(strdup("f"), 42));
308 EXPECT_EQ(42, arr->find("f")->second);
310 // Look up a single char, successfully.
311 auto it = arr->find('f');
312 EXPECT_EQ(42, it->second);
315 // Look up a single char, unsuccessfully.
316 auto it = arr->find('g');
317 EXPECT_TRUE(it == arr->end());
320 // Insert a new char key.
321 auto res = arr->emplace('h', static_cast<int64_t>(123));
322 EXPECT_TRUE(res.second);
323 EXPECT_TRUE(res.first != arr->end());
324 // Look up the string version.
325 EXPECT_EQ(123, arr->find("h")->second);
328 // Fail to emplace an existing key.
329 auto res = arr->emplace('f', static_cast<int64_t>(123));
330 EXPECT_FALSE(res.second);
331 EXPECT_TRUE(res.first != arr->end());
334 for (auto it : *arr) free(it.first);