folly/test/AtomicHashArrayTest.cpp

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