folly/test/AtomicHashArrayTest.cpp

   1 /*
   2  * Copyright 2015 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 <sys/mman.h>
  18
  19 #include <cstddef>
  20 #include <map>
  21 #include <stdexcept>
  22
  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>
  28
  29 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
  30 #define MAP_ANONYMOUS MAP_ANON
  31 #endif
  32
  33 using namespace std;
  34 using namespace folly;
  35
  36 template <class T>
  37 class MmapAllocator {
  38  public:
  39   typedef T value_type;
  40   typedef T* pointer;
  41   typedef const T* const_pointer;
  42   typedef T& reference;
  43   typedef const T& const_reference;
  44
  45   typedef ptrdiff_t difference_type;
  46   typedef size_t size_type;
  47
  48   T* address(T& x) const {
  49     return std::addressof(x);
  50   }
  51
  52   const T* address(const T& x) const {
  53     return std::addressof(x);
  54   }
  55
  56   size_t max_size() const {
  57     return std::numeric_limits<size_t>::max();
  58   }
  59
  60   template <class U> struct rebind {
  61     typedef MmapAllocator<U> other;
  62   };
  63
  64   bool operator!=(const MmapAllocator<T>& other) const {
  65     return !(*this == other);
  66   }
  67
  68   bool operator==(const MmapAllocator<T>& other) const {
  69     return true;
  70   }
  71
  72   template <class... Args>
  73   void construct(T* p, Args&&... args) {
  74     new (p) T(std::forward<Args>(args)...);
  75   }
  76
  77   void destroy(T* p) {
  78     p->~T();
  79   }
  80
  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();
  85     return (T *)p;
  86   }
  87
  88   void deallocate(T *p, size_t n) {
  89     munmap(p, n * sizeof(T));
  90   }
  91 };
  92
  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),
  96                            to<ValueT>(i + 3));
  97 }
  98
  99 template <class KeyT,
 100           class ValueT,
 101           class Allocator = std::allocator<char>,
 102           class ProbeFcn = AtomicHashArrayLinearProbeFcn>
 103 void testMap() {
 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
 112     ref.insert(e);
 113     EXPECT_EQ(ref.size(), arr->size());
 114     if (ret.first == arr->end()) {
 115       EXPECT_FALSE("AHA should not have run out of space.");
 116       continue;
 117     }
 118     EXPECT_EQ(e.first, ret.first->first);
 119     EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
 120   }
 121
 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);
 128   }
 129
 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);
 137   }
 138
 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");
 143       continue;
 144     }
 145     EXPECT_EQ(e.first, ret->first);
 146     EXPECT_EQ(e.second, ret->second);
 147   }
 148 }
 149
 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;
 156
 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))));
 160   }
 161   for (int i = 100; i < 150; i++) {
 162     arr->emplace(i,new ValueT(i));
 163   }
 164   for (int i = 150; i < 200; i++) {
 165     arr->emplace(i,new ValueT(i),std::default_delete<ValueT>());
 166   }
 167   for (int i = 0; i < 200; i++) {
 168     auto ret = arr->find(i);
 169     EXPECT_EQ(*(ret->second), i);
 170   }
 171 }
 172
 173
 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>();
 187 }
 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>();
 201 }
 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>();
 215 }
 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>();
 229 }
 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>();
 237 }
 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>();
 245 }
 246
 247 TEST(Aha, Create_cstr_i64) {
 248   auto obj = AtomicHashArray<const char*, int64_t>::create(12);
 249 }
 250
 251 static bool legalKey(char* a);
 252
 253 // Support two additional key lookup types (char and StringPiece) using
 254 // one set of traits.
 255 struct EqTraits {
 256   bool operator()(char* a, char* b) {
 257     return legalKey(a) && (strcmp(a, b) == 0);
 258   }
 259   bool operator()(char* a, const char& b) {
 260     return legalKey(a) && (a[0] != '\0') && (a[0] == b);
 261   }
 262   bool operator()(char* a, const StringPiece b) {
 263     return legalKey(a) &&
 264       (strlen(a) == b.size()) && (strncmp(a, b.begin(), b.size()) == 0);
 265   }
 266 };
 267
 268 struct HashTraits {
 269   size_t operator()(char* a) {
 270     size_t result = 0;
 271     while (a[0] != 0) result += static_cast<size_t>(*(a++));
 272     return result;
 273   }
 274   size_t operator()(const char& a) {
 275     return static_cast<size_t>(a);
 276   }
 277   size_t operator()(const StringPiece a) {
 278     size_t result = 0;
 279     for (const auto& ch : a) result += static_cast<size_t>(ch);
 280     return result;
 281   }
 282 };
 283
 284 // Creates malloc'ed null-terminated strings.
 285 struct KeyConvertTraits {
 286   char* operator()(const char& a) {
 287     return strndup(&a, 1);
 288   }
 289   char* operator()(const StringPiece a) {
 290     return strndup(a.begin(), a.size());
 291   }
 292 };
 293
 294 typedef AtomicHashArray<char*, int64_t, HashTraits, EqTraits,
 295                         MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn,
 296                         KeyConvertTraits>
 297   AHACstrInt;
 298 AHACstrInt::Config cstrIntCfg;
 299
 300 static bool legalKey(char* a) {
 301   return a != cstrIntCfg.emptyKey &&
 302     a != cstrIntCfg.lockedKey &&
 303     a != cstrIntCfg.erasedKey;
 304 }
 305
 306 TEST(Aha, LookupAny) {
 307   auto arr = AHACstrInt::create(12);
 308
 309   arr->insert(std::make_pair(strdup("f"), 42));
 310   EXPECT_EQ(42, arr->find("f")->second);
 311   {
 312     // Look up a single char, successfully.
 313     auto it = arr->find('f');
 314     EXPECT_EQ(42, it->second);
 315   }
 316   {
 317     // Look up a single char, unsuccessfully.
 318     auto it = arr->find('g');
 319     EXPECT_TRUE(it == arr->end());
 320   }
 321   {
 322     // Insert a new char key.
 323     auto res = arr->emplace('h', static_cast<int64_t>(123));
 324     EXPECT_TRUE(res.second);
 325     EXPECT_TRUE(res.first != arr->end());
 326     // Look up the string version.
 327     EXPECT_EQ(123, arr->find("h")->second);
 328   }
 329   {
 330     // Fail to emplace an existing key.
 331     auto res = arr->emplace('f', static_cast<int64_t>(123));
 332     EXPECT_FALSE(res.second);
 333     EXPECT_TRUE(res.first != arr->end());
 334   }
 335
 336   for (auto it : *arr) free(it.first);
 337 }