2 * Copyright 2013 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "folly/AtomicHashArray.h"
18 #include "folly/Hash.h"
19 #include "folly/Conv.h"
20 #include <gtest/gtest.h>
23 using namespace folly;
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),
31 template<class KeyT, class ValueT>
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
41 EXPECT_EQ(ref.size(), arr->size());
42 if (ret.first == arr->end()) {
43 EXPECT_FALSE("AHA should not have run out of space.");
46 EXPECT_EQ(e.first, ret.first->first);
47 EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
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);
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);
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");
73 EXPECT_EQ(e.first, ret->first);
74 EXPECT_EQ(e.second, ret->second);
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))));
85 for (int i = 0; i < 100; i++) {
86 auto ret = arr->find(i);
87 EXPECT_EQ(*(ret->second), i);
92 TEST(Aha, InsertErase_i32_i32) {
93 testMap<int32_t,int32_t>();
94 testNoncopyableMap<int32_t,int32_t>();
96 TEST(Aha, InsertErase_i64_i32) {
97 testMap<int64_t,int32_t>();
98 testNoncopyableMap<int64_t,int32_t>();
100 TEST(Aha, InsertErase_i64_i64) {
101 testMap<int64_t,int64_t>();
102 testNoncopyableMap<int64_t,int64_t>();
104 TEST(Aha, InsertErase_i32_i64) {
105 testMap<int32_t,int64_t>();
106 testNoncopyableMap<int32_t,int64_t>();
108 TEST(Aha, InsertErase_i32_str) {
109 testMap<int32_t,string>();
111 TEST(Aha, InsertErase_i64_str) {
112 testMap<int64_t,string>();