folly/test/AtomicHashArrayTest.cpp

   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> struct rebind {
  57     typedef MmapAllocator<U> other;
  58   };
  59
  60   bool operator!=(const MmapAllocator<T>& other) const {
  61     return !(*this == other);
  62   }
  63
  64   bool operator==(const MmapAllocator<T>& /* other */) const { return true; }
  65
  66   template <class... Args>
  67   void construct(T* p, Args&&... args) {
  68     new (p) T(std::forward<Args>(args)...);
  69   }
  70
  71   void destroy(T* p) {
  72     p->~T();
  73   }
  74
  75   T *allocate(size_t n) {
  76     void *p = mmap(nullptr, n * sizeof(T), PROT_READ | PROT_WRITE,
  77         MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  78     if (p == MAP_FAILED) {
  79       throw std::bad_alloc();
  80     }
  81     return (T *)p;
  82   }
  83
  84   void deallocate(T *p, size_t n) {
  85     munmap(p, n * sizeof(T));
  86   }
  87 };
  88
  89 template <class KeyT, class ValueT>
  90 pair<KeyT,ValueT> createEntry(int i) {
  91   return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
  92                            to<ValueT>(i + 3));
  93 }
  94
  95 template <
  96     class KeyT,
  97     class ValueT,
  98     class Allocator = std::allocator<char>,
  99     class ProbeFcn = AtomicHashArrayLinearProbeFcn>
 100 void testMap() {
 101   typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
 102                           std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
 103   auto arr = MyArr::create(150);
 104   map<KeyT, ValueT> ref;
 105   for (int i = 0; i < 100; ++i) {
 106     auto e = createEntry<KeyT, ValueT>(i);
 107     auto ret = arr->insert(e);
 108     EXPECT_EQ(!ref.count(e.first), ret.second);  // succeed iff not in ref
 109     ref.insert(e);
 110     EXPECT_EQ(ref.size(), arr->size());
 111     if (ret.first == arr->end()) {
 112       EXPECT_FALSE("AHA should not have run out of space.");
 113       continue;
 114     }
 115     EXPECT_EQ(e.first, ret.first->first);
 116     EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
 117   }
 118
 119   for (int i = 125; i > 0; i -= 10) {
 120     auto e = createEntry<KeyT, ValueT>(i);
 121     auto ret = arr->erase(e.first);
 122     auto refRet = ref.erase(e.first);
 123     EXPECT_EQ(ref.size(), arr->size());
 124     EXPECT_EQ(refRet, ret);
 125   }
 126
 127   for (int i = 155; i > 0; i -= 10) {
 128     auto e = createEntry<KeyT, ValueT>(i);
 129     auto ret = arr->insert(e);
 130     auto refRet = ref.insert(e);
 131     EXPECT_EQ(ref.size(), arr->size());
 132     EXPECT_EQ(*refRet.first, *ret.first);
 133     EXPECT_EQ(refRet.second, ret.second);
 134   }
 135
 136   for (const auto& e : ref) {
 137     auto ret = arr->find(e.first);
 138     if (ret == arr->end()) {
 139       EXPECT_FALSE("Key was not in AHA");
 140       continue;
 141     }
 142     EXPECT_EQ(e.first, ret->first);
 143     EXPECT_EQ(e.second, ret->second);
 144   }
 145 }
 146
 147 template <
 148     class KeyT,
 149     class ValueT,
 150     class Allocator = std::allocator<char>,
 151     class ProbeFcn = AtomicHashArrayLinearProbeFcn>
 152 void testNoncopyableMap() {
 153   typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
 154                           std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
 155
 156   auto arr = MyArr::create(250);
 157   for (int i = 0; i < 100; i++) {
 158     arr->insert(make_pair(i, std::make_unique<ValueT>(i)));
 159   }
 160   for (int i = 100; i < 150; i++) {
 161     arr->emplace(i,new ValueT(i));
 162   }
 163   for (int i = 150; i < 200; i++) {
 164     arr->emplace(i,new ValueT(i),std::default_delete<ValueT>());
 165   }
 166   for (int i = 0; i < 200; i++) {
 167     auto ret = arr->find(i);
 168     EXPECT_EQ(*(ret->second), i);
 169   }
 170 }
 171
 172
 173 TEST(Aha, InsertErase_i32_i32) {
 174   testMap<int32_t, int32_t>();
 175   testMap<int32_t, int32_t, MmapAllocator<char>>();
 176   testMap<int32_t, int32_t,
 177       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 178   testMap<int32_t, int32_t,
 179       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 180   testNoncopyableMap<int32_t, int32_t>();
 181   testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
 182   testNoncopyableMap<int32_t, int32_t,
 183       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 184   testNoncopyableMap<int32_t, int32_t,
 185       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 186 }
 187 TEST(Aha, InsertErase_i64_i32) {
 188   testMap<int64_t, int32_t>();
 189   testMap<int64_t, int32_t, MmapAllocator<char>>();
 190   testMap<int64_t, int32_t,
 191       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 192   testMap<int64_t, int32_t,
 193       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 194   testNoncopyableMap<int64_t, int32_t>();
 195   testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
 196   testNoncopyableMap<int64_t, int32_t,
 197       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 198   testNoncopyableMap<int64_t, int32_t,
 199       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 200 }
 201 TEST(Aha, InsertErase_i64_i64) {
 202   testMap<int64_t, int64_t>();
 203   testMap<int64_t, int64_t, MmapAllocator<char>>();
 204   testMap<int64_t, int64_t,
 205       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 206   testMap<int64_t, int64_t,
 207       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 208   testNoncopyableMap<int64_t, int64_t>();
 209   testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
 210   testNoncopyableMap<int64_t, int64_t,
 211       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 212   testNoncopyableMap<int64_t, int64_t,
 213       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 214 }
 215 TEST(Aha, InsertErase_i32_i64) {
 216   testMap<int32_t, int64_t>();
 217   testMap<int32_t, int64_t, MmapAllocator<char>>();
 218   testMap<int32_t, int64_t,
 219       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 220   testMap<int32_t, int64_t,
 221       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 222   testNoncopyableMap<int32_t, int64_t>();
 223   testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
 224   testNoncopyableMap<int32_t, int64_t,
 225       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 226   testNoncopyableMap<int32_t, int64_t,
 227       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 228 }
 229 TEST(Aha, InsertErase_i32_str) {
 230   testMap<int32_t, string>();
 231   testMap<int32_t, string, MmapAllocator<char>>();
 232   testMap<int32_t, string,
 233       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 234   testMap<int32_t, string,
 235       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 236 }
 237 TEST(Aha, InsertErase_i64_str) {
 238   testMap<int64_t, string>();
 239   testMap<int64_t, string, MmapAllocator<char>>();
 240   testMap<int64_t, string,
 241       std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 242   testMap<int64_t, string,
 243       MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
 244 }
 245
 246 TEST(Aha, Create_cstr_i64) {
 247   auto obj = AtomicHashArray<const char*, int64_t>::create(12);
 248 }
 249
 250 static bool legalKey(char* a);
 251
 252 // Support two additional key lookup types (char and StringPiece) using
 253 // one set of traits.
 254 struct EqTraits {
 255   bool operator()(char* a, char* b) {
 256     return legalKey(a) && (strcmp(a, b) == 0);
 257   }
 258   bool operator()(char* a, const char& b) {
 259     return legalKey(a) && (a[0] != '\0') && (a[0] == b);
 260   }
 261   bool operator()(char* a, const StringPiece b) {
 262     return legalKey(a) &&
 263       (strlen(a) == b.size()) && (strncmp(a, b.begin(), b.size()) == 0);
 264   }
 265 };
 266
 267 struct HashTraits {
 268   size_t operator()(char* a) {
 269     size_t result = 0;
 270     while (a[0] != 0) {
 271       result += static_cast<size_t>(*(a++));
 272     }
 273     return result;
 274   }
 275   size_t operator()(const char& a) {
 276     return static_cast<size_t>(a);
 277   }
 278   size_t operator()(const StringPiece a) {
 279     size_t result = 0;
 280     for (const auto& ch : a) {
 281       result += static_cast<size_t>(ch);
 282     }
 283     return result;
 284   }
 285 };
 286
 287 // Creates malloc'ed null-terminated strings.
 288 struct KeyConvertTraits {
 289   char* operator()(const char& a) {
 290     return strndup(&a, 1);
 291   }
 292   char* operator()(const StringPiece a) {
 293     return strndup(a.begin(), a.size());
 294   }
 295 };
 296
 297 typedef AtomicHashArray<char*, int64_t, HashTraits, EqTraits,
 298                         MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn,
 299                         KeyConvertTraits>
 300   AHACstrInt;
 301 AHACstrInt::Config cstrIntCfg;
 302
 303 static bool legalKey(char* a) {
 304   return a != cstrIntCfg.emptyKey &&
 305     a != cstrIntCfg.lockedKey &&
 306     a != cstrIntCfg.erasedKey;
 307 }
 308
 309 TEST(Aha, LookupAny) {
 310   auto arr = AHACstrInt::create(12);
 311
 312   char* f_char = strdup("f");
 313   SCOPE_EXIT { free(f_char); };
 314   arr->insert(std::make_pair(f_char, 42));
 315
 316   EXPECT_EQ(42, arr->find("f")->second);
 317   {
 318     // Look up a single char, successfully.
 319     auto it = arr->find('f');
 320     EXPECT_EQ(42, it->second);
 321   }
 322   {
 323     // Look up a single char, unsuccessfully.
 324     auto it = arr->find('g');
 325     EXPECT_TRUE(it == arr->end());
 326   }
 327   {
 328     // Insert a new char key.
 329     auto res = arr->emplace('h', static_cast<int64_t>(123));
 330     EXPECT_TRUE(res.second);
 331     EXPECT_TRUE(res.first != arr->end());
 332     // Look up the string version.
 333     EXPECT_EQ(123, arr->find("h")->second);
 334   }
 335   {
 336     // Fail to emplace an existing key.
 337     auto res = arr->emplace('f', static_cast<int64_t>(123));
 338     EXPECT_FALSE(res.second);
 339     EXPECT_TRUE(res.first != arr->end());
 340   }
 341
 342   for (auto it : *arr) {
 343     free(it.first);
 344   }
 345 }
 346
 347 using AHAIntCInt = AtomicHashArray<int64_t, const int32_t>;
 348
 349 TEST(Aha, ConstValue) {
 350   auto aha = AHAIntCInt::create(10);
 351   aha->emplace(1, 2);
 352 }