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 "folly/AtomicHashArray.h"
  18 #include "folly/Hash.h"
  19 #include "folly/Conv.h"
  20 #include <gtest/gtest.h>
  21
  22 using namespace std;
  23 using namespace folly;
  24
  25 template<class KeyT, class ValueT>
  26 pair<KeyT,ValueT> createEntry(int i) {
  27   return pair<KeyT,ValueT>(to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000),
  28                            to<ValueT>(i + 3));
  29 }
  30
  31 template<class KeyT, class ValueT>
  32 void testMap() {
  33   typedef AtomicHashArray<KeyT, ValueT>  MyArr;
  34   auto arr = MyArr::create(150);
  35   map<KeyT, ValueT> ref;
  36   for (int i = 0; i < 100; ++i) {
  37     auto e = createEntry<KeyT, ValueT>(i);
  38     auto ret = arr->insert(e);
  39     EXPECT_EQ(!ref.count(e.first), ret.second);  // succeed iff not in ref
  40     ref.insert(e);
  41     EXPECT_EQ(ref.size(), arr->size());
  42     if (ret.first == arr->end()) {
  43       EXPECT_FALSE("AHA should not have run out of space.");
  44       continue;
  45     }
  46     EXPECT_EQ(e.first, ret.first->first);
  47     EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
  48   }
  49
  50   for (int i = 125; i > 0; i -= 10) {
  51     auto e = createEntry<KeyT, ValueT>(i);
  52     auto ret = arr->erase(e.first);
  53     auto refRet = ref.erase(e.first);
  54     EXPECT_EQ(ref.size(), arr->size());
  55     EXPECT_EQ(refRet, ret);
  56   }
  57
  58   for (int i = 155; i > 0; i -= 10) {
  59     auto e = createEntry<KeyT, ValueT>(i);
  60     auto ret = arr->insert(e);
  61     auto refRet = ref.insert(e);
  62     EXPECT_EQ(ref.size(), arr->size());
  63     EXPECT_EQ(*refRet.first, *ret.first);
  64     EXPECT_EQ(refRet.second, ret.second);
  65   }
  66
  67   for (const auto& e : ref) {
  68     auto ret = arr->find(e.first);
  69     if (ret == arr->end()) {
  70       EXPECT_FALSE("Key was not in AHA");
  71       continue;
  72     }
  73     EXPECT_EQ(e.first, ret->first);
  74     EXPECT_EQ(e.second, ret->second);
  75   }
  76 }
  77
  78 template<class KeyT, class ValueT>
  79 void testNoncopyableMap() {
  80   typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>>  MyArr;
  81   auto arr = MyArr::create(150);
  82   for (int i = 0; i < 100; i++) {
  83     arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
  84   }
  85   for (int i = 0; i < 100; i++) {
  86     auto ret = arr->find(i);
  87     EXPECT_EQ(*(ret->second), i);
  88   }
  89 }
  90
  91
  92 TEST(Aha, InsertErase_i32_i32) {
  93   testMap<int32_t,int32_t>();
  94   testNoncopyableMap<int32_t,int32_t>();
  95 }
  96 TEST(Aha, InsertErase_i64_i32) {
  97   testMap<int64_t,int32_t>();
  98   testNoncopyableMap<int64_t,int32_t>();
  99 }
 100 TEST(Aha, InsertErase_i64_i64) {
 101   testMap<int64_t,int64_t>();
 102   testNoncopyableMap<int64_t,int64_t>();
 103 }
 104 TEST(Aha, InsertErase_i32_i64) {
 105   testMap<int32_t,int64_t>();
 106   testNoncopyableMap<int32_t,int64_t>();
 107 }
 108 TEST(Aha, InsertErase_i32_str) {
 109   testMap<int32_t,string>();
 110 }
 111 TEST(Aha, InsertErase_i64_str) {
 112   testMap<int64_t,string>();
 113 }