2 * Copyright 2015 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 {
72 template <class... Args>
73 void construct(T* p, Args&&... args) {
74 new (p) T(std::forward<Args>(args)...);
81 T *allocate(size_t n) {
82 void *p = mmap(nullptr, n * sizeof(T), PROT_READ | PROT_WRITE,
83 MAP_SHARED | MAP_ANONYMOUS, -1, 0);
84 if (p == MAP_FAILED) throw std::bad_alloc();
88 void deallocate(T *p, size_t n) {
89 munmap(p, n * sizeof(T));
93 template<class KeyT, class ValueT>
94 pair<KeyT,ValueT> createEntry(int i) {
95 return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
101 class Allocator = std::allocator<char>,
102 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
104 typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
105 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
106 auto arr = MyArr::create(150);
107 map<KeyT, ValueT> ref;
108 for (int i = 0; i < 100; ++i) {
109 auto e = createEntry<KeyT, ValueT>(i);
110 auto ret = arr->insert(e);
111 EXPECT_EQ(!ref.count(e.first), ret.second); // succeed iff not in ref
113 EXPECT_EQ(ref.size(), arr->size());
114 if (ret.first == arr->end()) {
115 EXPECT_FALSE("AHA should not have run out of space.");
118 EXPECT_EQ(e.first, ret.first->first);
119 EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
122 for (int i = 125; i > 0; i -= 10) {
123 auto e = createEntry<KeyT, ValueT>(i);
124 auto ret = arr->erase(e.first);
125 auto refRet = ref.erase(e.first);
126 EXPECT_EQ(ref.size(), arr->size());
127 EXPECT_EQ(refRet, ret);
130 for (int i = 155; i > 0; i -= 10) {
131 auto e = createEntry<KeyT, ValueT>(i);
132 auto ret = arr->insert(e);
133 auto refRet = ref.insert(e);
134 EXPECT_EQ(ref.size(), arr->size());
135 EXPECT_EQ(*refRet.first, *ret.first);
136 EXPECT_EQ(refRet.second, ret.second);
139 for (const auto& e : ref) {
140 auto ret = arr->find(e.first);
141 if (ret == arr->end()) {
142 EXPECT_FALSE("Key was not in AHA");
145 EXPECT_EQ(e.first, ret->first);
146 EXPECT_EQ(e.second, ret->second);
150 template<class KeyT, class ValueT,
151 class Allocator = std::allocator<char>,
152 class ProbeFcn = AtomicHashArrayLinearProbeFcn>
153 void testNoncopyableMap() {
154 typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
155 std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
157 auto arr = MyArr::create(250);
158 for (int i = 0; i < 100; i++) {
159 arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
161 for (int i = 100; i < 150; i++) {
162 arr->emplace(i,new ValueT(i));
164 for (int i = 150; i < 200; i++) {
165 arr->emplace(i,new ValueT(i),std::default_delete<ValueT>());
167 for (int i = 0; i < 200; i++) {
168 auto ret = arr->find(i);
169 EXPECT_EQ(*(ret->second), i);
174 TEST(Aha, InsertErase_i32_i32) {
175 testMap<int32_t, int32_t>();
176 testMap<int32_t, int32_t, MmapAllocator<char>>();
177 testMap<int32_t, int32_t,
178 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
179 testMap<int32_t, int32_t,
180 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
181 testNoncopyableMap<int32_t, int32_t>();
182 testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
183 testNoncopyableMap<int32_t, int32_t,
184 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
185 testNoncopyableMap<int32_t, int32_t,
186 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
188 TEST(Aha, InsertErase_i64_i32) {
189 testMap<int64_t, int32_t>();
190 testMap<int64_t, int32_t, MmapAllocator<char>>();
191 testMap<int64_t, int32_t,
192 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
193 testMap<int64_t, int32_t,
194 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
195 testNoncopyableMap<int64_t, int32_t>();
196 testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
197 testNoncopyableMap<int64_t, int32_t,
198 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
199 testNoncopyableMap<int64_t, int32_t,
200 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
202 TEST(Aha, InsertErase_i64_i64) {
203 testMap<int64_t, int64_t>();
204 testMap<int64_t, int64_t, MmapAllocator<char>>();
205 testMap<int64_t, int64_t,
206 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
207 testMap<int64_t, int64_t,
208 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
209 testNoncopyableMap<int64_t, int64_t>();
210 testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
211 testNoncopyableMap<int64_t, int64_t,
212 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
213 testNoncopyableMap<int64_t, int64_t,
214 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
216 TEST(Aha, InsertErase_i32_i64) {
217 testMap<int32_t, int64_t>();
218 testMap<int32_t, int64_t, MmapAllocator<char>>();
219 testMap<int32_t, int64_t,
220 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
221 testMap<int32_t, int64_t,
222 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
223 testNoncopyableMap<int32_t, int64_t>();
224 testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
225 testNoncopyableMap<int32_t, int64_t,
226 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
227 testNoncopyableMap<int32_t, int64_t,
228 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
230 TEST(Aha, InsertErase_i32_str) {
231 testMap<int32_t, string>();
232 testMap<int32_t, string, MmapAllocator<char>>();
233 testMap<int32_t, string,
234 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
235 testMap<int32_t, string,
236 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
238 TEST(Aha, InsertErase_i64_str) {
239 testMap<int64_t, string>();
240 testMap<int64_t, string, MmapAllocator<char>>();
241 testMap<int64_t, string,
242 std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
243 testMap<int64_t, string,
244 MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
247 TEST(Aha, Create_cstr_i64) {
248 auto obj = AtomicHashArray<const char*, int64_t>::create(12);