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
  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 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 {
  65     return true;
  66   }
  67
  68   template <class... Args>
  69   void construct(T* p, Args&&... args) {
  70     new (p) T(std::forward<Args>(args)...);
  71   }
  72
  73   void destroy(T* p) {
  74     p->~T();
  75   }
  76
  77   T *allocate(size_t n) {
  78     void *p = mmap(nullptr, n * sizeof(T), PROT_READ | PROT_WRITE,
  79         MAP_SHARED | MAP_ANONYMOUS, -1, 0);
  80     if (!p) throw std::bad_alloc();
  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<class KeyT, class ValueT, class Allocator = std::allocator<char>>
  96 void testMap() {
  97   typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
  98                           std::equal_to<KeyT>, Allocator> MyArr;
  99   auto arr = MyArr::create(150);
 100   map<KeyT, ValueT> ref;
 101   for (int i = 0; i < 100; ++i) {
 102     auto e = createEntry<KeyT, ValueT>(i);
 103     auto ret = arr->insert(e);
 104     EXPECT_EQ(!ref.count(e.first), ret.second);  // succeed iff not in ref
 105     ref.insert(e);
 106     EXPECT_EQ(ref.size(), arr->size());
 107     if (ret.first == arr->end()) {
 108       EXPECT_FALSE("AHA should not have run out of space.");
 109       continue;
 110     }
 111     EXPECT_EQ(e.first, ret.first->first);
 112     EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
 113   }
 114
 115   for (int i = 125; i > 0; i -= 10) {
 116     auto e = createEntry<KeyT, ValueT>(i);
 117     auto ret = arr->erase(e.first);
 118     auto refRet = ref.erase(e.first);
 119     EXPECT_EQ(ref.size(), arr->size());
 120     EXPECT_EQ(refRet, ret);
 121   }
 122
 123   for (int i = 155; i > 0; i -= 10) {
 124     auto e = createEntry<KeyT, ValueT>(i);
 125     auto ret = arr->insert(e);
 126     auto refRet = ref.insert(e);
 127     EXPECT_EQ(ref.size(), arr->size());
 128     EXPECT_EQ(*refRet.first, *ret.first);
 129     EXPECT_EQ(refRet.second, ret.second);
 130   }
 131
 132   for (const auto& e : ref) {
 133     auto ret = arr->find(e.first);
 134     if (ret == arr->end()) {
 135       EXPECT_FALSE("Key was not in AHA");
 136       continue;
 137     }
 138     EXPECT_EQ(e.first, ret->first);
 139     EXPECT_EQ(e.second, ret->second);
 140   }
 141 }
 142
 143 template<class KeyT, class ValueT, class Allocator = std::allocator<char>>
 144 void testNoncopyableMap() {
 145   typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
 146                           std::equal_to<KeyT>, Allocator> MyArr;
 147   auto arr = MyArr::create(150);
 148   for (int i = 0; i < 100; i++) {
 149     arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
 150   }
 151   for (int i = 0; i < 100; i++) {
 152     auto ret = arr->find(i);
 153     EXPECT_EQ(*(ret->second), i);
 154   }
 155 }
 156
 157
 158 TEST(Aha, InsertErase_i32_i32) {
 159   testMap<int32_t, int32_t>();
 160   testMap<int32_t, int32_t, MmapAllocator<char>>();
 161   testNoncopyableMap<int32_t, int32_t>();
 162   testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
 163 }
 164 TEST(Aha, InsertErase_i64_i32) {
 165   testMap<int64_t, int32_t>();
 166   testMap<int64_t, int32_t, MmapAllocator<char>>();
 167   testNoncopyableMap<int64_t, int32_t>();
 168   testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
 169 }
 170 TEST(Aha, InsertErase_i64_i64) {
 171   testMap<int64_t, int64_t>();
 172   testMap<int64_t, int64_t, MmapAllocator<char>>();
 173   testNoncopyableMap<int64_t, int64_t>();
 174   testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
 175 }
 176 TEST(Aha, InsertErase_i32_i64) {
 177   testMap<int32_t, int64_t>();
 178   testMap<int32_t, int64_t, MmapAllocator<char>>();
 179   testNoncopyableMap<int32_t, int64_t>();
 180   testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
 181 }
 182 TEST(Aha, InsertErase_i32_str) {
 183   testMap<int32_t, string>();
 184   testMap<int32_t, string, MmapAllocator<char>>();
 185 }
 186 TEST(Aha, InsertErase_i64_str) {
 187   testMap<int64_t, string>();
 188   testMap<int64_t, string, MmapAllocator<char>>();
 189 }