folly/test/AtomicHashArrayTest.cpp

   1 /*
   2  * Copyright 2013 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 #include <cstddef>
  19 #include <stdexcept>
  20
  21 #include "folly/AtomicHashArray.h"
  22 #include "folly/Hash.h"
  23 #include "folly/Conv.h"
  24 #include "folly/Memory.h"
  25 #include <gtest/gtest.h>
  26
  27 using namespace std;
  28 using namespace folly;
  29
  30 template <class T>
  31 class MmapAllocator {
  32  public:
  33   typedef T value_type;
  34   typedef T* pointer;
  35   typedef const T* const_pointer;
  36   typedef T& reference;
  37   typedef const T& const_reference;
  38
  39   typedef ptrdiff_t difference_type;
  40   typedef size_t size_type;
  41
  42   T* address(T& x) const {
  43     return std::addressof(x);
  44   }
  45
  46   const T* address(const T& x) const {
  47     return std::addressof(x);
  48   }
  49
  50   size_t max_size() const {
  51     return std::numeric_limits<size_t>::max();
  52   }
  53
  54   template <class U> struct rebind {
  55     typedef MmapAllocator<U> other;
  56   };
  57
  58   bool operator!=(const MmapAllocator<T>& other) const {
  59     return !(*this == other);
  60   }
  61
  62   bool operator==(const MmapAllocator<T>& other) const {
  63     return true;
  64   }
  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_SHARED | MAP_ANONYMOUS, -1, 0);
  78     if (!p) throw std::bad_alloc();
  79     return (T *)p;
  80   }
  81
  82   void deallocate(T *p, size_t n) {
  83     munmap(p, n * sizeof(T));
  84   }
  85 };
  86
  87 template<class KeyT, class ValueT>
  88 pair<KeyT,ValueT> createEntry(int i) {
  89   return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
  90                            to<ValueT>(i + 3));
  91 }
  92
  93 template<class KeyT, class ValueT, class Allocator = std::allocator<char>>
  94 void testMap() {
  95   typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
  96                           std::equal_to<KeyT>, Allocator> MyArr;
  97   auto arr = MyArr::create(150);
  98   map<KeyT, ValueT> ref;
  99   for (int i = 0; i < 100; ++i) {
 100     auto e = createEntry<KeyT, ValueT>(i);
 101     auto ret = arr->insert(e);
 102     EXPECT_EQ(!ref.count(e.first), ret.second);  // succeed iff not in ref
 103     ref.insert(e);
 104     EXPECT_EQ(ref.size(), arr->size());
 105     if (ret.first == arr->end()) {
 106       EXPECT_FALSE("AHA should not have run out of space.");
 107       continue;
 108     }
 109     EXPECT_EQ(e.first, ret.first->first);
 110     EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
 111   }
 112
 113   for (int i = 125; i > 0; i -= 10) {
 114     auto e = createEntry<KeyT, ValueT>(i);
 115     auto ret = arr->erase(e.first);
 116     auto refRet = ref.erase(e.first);
 117     EXPECT_EQ(ref.size(), arr->size());
 118     EXPECT_EQ(refRet, ret);
 119   }
 120
 121   for (int i = 155; i > 0; i -= 10) {
 122     auto e = createEntry<KeyT, ValueT>(i);
 123     auto ret = arr->insert(e);
 124     auto refRet = ref.insert(e);
 125     EXPECT_EQ(ref.size(), arr->size());
 126     EXPECT_EQ(*refRet.first, *ret.first);
 127     EXPECT_EQ(refRet.second, ret.second);
 128   }
 129
 130   for (const auto& e : ref) {
 131     auto ret = arr->find(e.first);
 132     if (ret == arr->end()) {
 133       EXPECT_FALSE("Key was not in AHA");
 134       continue;
 135     }
 136     EXPECT_EQ(e.first, ret->first);
 137     EXPECT_EQ(e.second, ret->second);
 138   }
 139 }
 140
 141 template<class KeyT, class ValueT, class Allocator = std::allocator<char>>
 142 void testNoncopyableMap() {
 143   typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
 144                           std::equal_to<KeyT>, Allocator> MyArr;
 145   auto arr = MyArr::create(150);
 146   for (int i = 0; i < 100; i++) {
 147     arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
 148   }
 149   for (int i = 0; i < 100; i++) {
 150     auto ret = arr->find(i);
 151     EXPECT_EQ(*(ret->second), i);
 152   }
 153 }
 154
 155
 156 TEST(Aha, InsertErase_i32_i32) {
 157   testMap<int32_t, int32_t>();
 158   testMap<int32_t, int32_t, MmapAllocator<char>>();
 159   testNoncopyableMap<int32_t, int32_t>();
 160   testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
 161 }
 162 TEST(Aha, InsertErase_i64_i32) {
 163   testMap<int64_t, int32_t>();
 164   testMap<int64_t, int32_t, MmapAllocator<char>>();
 165   testNoncopyableMap<int64_t, int32_t>();
 166   testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
 167 }
 168 TEST(Aha, InsertErase_i64_i64) {
 169   testMap<int64_t, int64_t>();
 170   testMap<int64_t, int64_t, MmapAllocator<char>>();
 171   testNoncopyableMap<int64_t, int64_t>();
 172   testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
 173 }
 174 TEST(Aha, InsertErase_i32_i64) {
 175   testMap<int32_t, int64_t>();
 176   testMap<int32_t, int64_t, MmapAllocator<char>>();
 177   testNoncopyableMap<int32_t, int64_t>();
 178   testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
 179 }
 180 TEST(Aha, InsertErase_i32_str) {
 181   testMap<int32_t, string>();
 182   testMap<int32_t, string, MmapAllocator<char>>();
 183 }
 184 TEST(Aha, InsertErase_i64_str) {
 185   testMap<int64_t, string>();
 186   testMap<int64_t, string, MmapAllocator<char>>();
 187 }