AtomicHashArrayTest.cpp File Reference

#include <cstddef>
#include <map>
#include <memory>
#include <stdexcept>
#include <folly/AtomicHashArray.h>
#include <folly/Conv.h>
#include <folly/Memory.h>
#include <folly/hash/Hash.h>
#include <folly/portability/GTest.h>
#include <folly/portability/SysMman.h>

Go to the source code of this file.

Classes
class	MmapAllocator< T >
struct	MmapAllocator< T >::rebind< U >
struct	EqTraits
struct	HashTraits
struct	KeyConvertTraits

Typedefs
typedef AtomicHashArray< char *, int64_t, HashTraits, EqTraits, MmapAllocator< char >, AtomicHashArrayQuadraticProbeFcn, KeyConvertTraits >	AHACstrInt
using	AHAIntCInt = AtomicHashArray< int64_t, const int32_t >

Functions
template<class KeyT , class ValueT >
pair< KeyT, ValueT >	createEntry (int i)
template<class KeyT , class ValueT , class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn>
void	testMap ()
template<class KeyT , class ValueT , class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn>
void	testNoncopyableMap ()
	TEST (Aha, InsertErase_i32_i32)
	TEST (Aha, InsertErase_i64_i32)
	TEST (Aha, InsertErase_i64_i64)
	TEST (Aha, InsertErase_i32_i64)
	TEST (Aha, InsertErase_i32_str)
	TEST (Aha, InsertErase_i64_str)
	TEST (Aha, Create_cstr_i64)
static bool	legalKey (char *a)
	TEST (Aha, LookupAny)
	TEST (Aha, ConstValue)

Variables
AHACstrInt::Config	cstrIntCfg

Typedef Documentation

typedef AtomicHashArray< char*, int64_t, HashTraits, EqTraits, MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn, KeyConvertTraits> AHACstrInt

Definition at line 384 of file AtomicHashArrayTest.cpp.

using AHAIntCInt = AtomicHashArray<int64_t, const int32_t>

Definition at line 432 of file AtomicHashArrayTest.cpp.

Function Documentation

template<class KeyT , class ValueT >

pair<KeyT, ValueT> createEntry

(

int

i

)

Definition at line 98 of file AtomicHashArrayTest.cpp.

References folly::hash::jenkins_rev_mix32().

                                      {
  return pair<KeyT, ValueT>(
      to<KeyT>(folly::hash::jenkins_rev_mix32(i) % 1000), to<ValueT>(i + 3));
}

static bool legalKey ( char *  a )

static

Definition at line 387 of file AtomicHashArrayTest.cpp.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::emptyKey, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::erasedKey, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::lockedKey.

Referenced by EqTraits::operator()(), and TEST().

                              {
  return a != cstrIntCfg.emptyKey && a != cstrIntCfg.lockedKey &&
      a != cstrIntCfg.erasedKey;
}

TEST	(	Aha	,
		InsertErase_i32_i32
	)

Definition at line 192 of file AtomicHashArrayTest.cpp.

References int32_t, testMap(), and testNoncopyableMap().

                               {
  testMap<int32_t, int32_t>();
  testMap<int32_t, int32_t, MmapAllocator<char>>();
  testMap<
      int32_t,
      int32_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int32_t,
      int32_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<int32_t, int32_t>();
  testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
  testNoncopyableMap<
      int32_t,
      int32_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<
      int32_t,
      int32_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		InsertErase_i64_i32
	)

Definition at line 218 of file AtomicHashArrayTest.cpp.

References int32_t, int64_t, testMap(), and testNoncopyableMap().

                               {
  testMap<int64_t, int32_t>();
  testMap<int64_t, int32_t, MmapAllocator<char>>();
  testMap<
      int64_t,
      int32_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int64_t,
      int32_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<int64_t, int32_t>();
  testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
  testNoncopyableMap<
      int64_t,
      int32_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<
      int64_t,
      int32_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		InsertErase_i64_i64
	)

Definition at line 244 of file AtomicHashArrayTest.cpp.

References int64_t, testMap(), and testNoncopyableMap().

                               {
  testMap<int64_t, int64_t>();
  testMap<int64_t, int64_t, MmapAllocator<char>>();
  testMap<
      int64_t,
      int64_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int64_t,
      int64_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<int64_t, int64_t>();
  testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
  testNoncopyableMap<
      int64_t,
      int64_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<
      int64_t,
      int64_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		InsertErase_i32_i64
	)

Definition at line 270 of file AtomicHashArrayTest.cpp.

References int32_t, int64_t, testMap(), and testNoncopyableMap().

                               {
  testMap<int32_t, int64_t>();
  testMap<int32_t, int64_t, MmapAllocator<char>>();
  testMap<
      int32_t,
      int64_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int32_t,
      int64_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<int32_t, int64_t>();
  testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
  testNoncopyableMap<
      int32_t,
      int64_t,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testNoncopyableMap<
      int32_t,
      int64_t,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		InsertErase_i32_str
	)

Definition at line 296 of file AtomicHashArrayTest.cpp.

References int32_t, string, and testMap().

                               {
  testMap<int32_t, string>();
  testMap<int32_t, string, MmapAllocator<char>>();
  testMap<
      int32_t,
      string,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int32_t,
      string,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		InsertErase_i64_str
	)

Definition at line 310 of file AtomicHashArrayTest.cpp.

References int64_t, string, and testMap().

                               {
  testMap<int64_t, string>();
  testMap<int64_t, string, MmapAllocator<char>>();
  testMap<
      int64_t,
      string,
      std::allocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
  testMap<
      int64_t,
      string,
      MmapAllocator<char>,
      AtomicHashArrayQuadraticProbeFcn>();
}

TEST	(	Aha	,
		Create_cstr_i64
	)

Definition at line 325 of file AtomicHashArrayTest.cpp.

References a, and legalKey().

                           {
  auto obj = AtomicHashArray<const char*, int64_t>::create(12);
}

TEST	(	Aha	,
		LookupAny
	)

Definition at line 392 of file AtomicHashArrayTest.cpp.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, bm::free(), and SCOPE_EXIT.

                     {
  auto arr = AHACstrInt::create(12);

  char* f_char = strdup("f");
  SCOPE_EXIT {
    free(f_char);
  };
  arr->insert(std::make_pair(f_char, 42));

  EXPECT_EQ(42, arr->find("f")->second);
  {
    // Look up a single char, successfully.
    auto it = arr->find('f');
    EXPECT_EQ(42, it->second);
  }
  {
    // Look up a single char, unsuccessfully.
    auto it = arr->find('g');
    EXPECT_TRUE(it == arr->end());
  }
  {
    // Insert a new char key.
    auto res = arr->emplace('h', static_cast<int64_t>(123));
    EXPECT_TRUE(res.second);
    EXPECT_TRUE(res.first != arr->end());
    // Look up the string version.
    EXPECT_EQ(123, arr->find("h")->second);
  }
  {
    // Fail to emplace an existing key.
    auto res = arr->emplace('f', static_cast<int64_t>(123));
    EXPECT_FALSE(res.second);
    EXPECT_TRUE(res.first != arr->end());
  }

  for (auto it : *arr) {
    free(it.first);
  }
}

TEST	(	Aha	,
		ConstValue
	)

Definition at line 434 of file AtomicHashArrayTest.cpp.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create().

                      {
  auto aha = AHAIntCInt::create(10);
  aha->emplace(1, 2);
}

template<class KeyT , class ValueT , class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn>

void testMap

(

)

Definition at line 108 of file AtomicHashArrayTest.cpp.

References EXPECT_EQ, EXPECT_FALSE, and i.

Referenced by getBenchPerfectIndexMapUniqueGetsCodeTestMap(), getBenchPerfectIndexMapUniqueGetsOtherStringTestMap(), getBenchUnorderedMapUniqueGetsTestMap(), and TEST().

               {
  typedef AtomicHashArray<
      KeyT,
      ValueT,
      std::hash<KeyT>,
      std::equal_to<KeyT>,
      Allocator,
      ProbeFcn>
      MyArr;
  auto arr = MyArr::create(150);
  map<KeyT, ValueT> ref;
  for (int i = 0; i < 100; ++i) {
    auto e = createEntry<KeyT, ValueT>(i);
    auto ret = arr->insert(e);
    EXPECT_EQ(!ref.count(e.first), ret.second); // succeed iff not in ref
    ref.insert(e);
    EXPECT_EQ(ref.size(), arr->size());
    if (ret.first == arr->end()) {
      EXPECT_FALSE("AHA should not have run out of space.");
      continue;
    }
    EXPECT_EQ(e.first, ret.first->first);
    EXPECT_EQ(ref.find(e.first)->second, ret.first->second);
  }

  for (int i = 125; i > 0; i -= 10) {
    auto e = createEntry<KeyT, ValueT>(i);
    auto ret = arr->erase(e.first);
    auto refRet = ref.erase(e.first);
    EXPECT_EQ(ref.size(), arr->size());
    EXPECT_EQ(refRet, ret);
  }

  for (int i = 155; i > 0; i -= 10) {
    auto e = createEntry<KeyT, ValueT>(i);
    auto ret = arr->insert(e);
    auto refRet = ref.insert(e);
    EXPECT_EQ(ref.size(), arr->size());
    EXPECT_EQ(*refRet.first, *ret.first);
    EXPECT_EQ(refRet.second, ret.second);
  }

  for (const auto& e : ref) {
    auto ret = arr->find(e.first);
    if (ret == arr->end()) {
      EXPECT_FALSE("Key was not in AHA");
      continue;
    }
    EXPECT_EQ(e.first, ret->first);
    EXPECT_EQ(e.second, ret->second);
  }
}

template<class KeyT , class ValueT , class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn>

void testNoncopyableMap

(

)

Definition at line 166 of file AtomicHashArrayTest.cpp.

References EXPECT_EQ, and i.

Referenced by TEST().

                          {
  typedef AtomicHashArray<
      KeyT,
      std::unique_ptr<ValueT>,
      std::hash<KeyT>,
      std::equal_to<KeyT>,
      Allocator,
      ProbeFcn>
      MyArr;

  auto arr = MyArr::create(250);
  for (int i = 0; i < 100; i++) {
    arr->insert(make_pair(i, std::make_unique<ValueT>(i)));
  }
  for (int i = 100; i < 150; i++) {
    arr->emplace(i, new ValueT(i));
  }
  for (int i = 150; i < 200; i++) {
    arr->emplace(i, new ValueT(i), std::default_delete<ValueT>());
  }
  for (int i = 0; i < 200; i++) {
    auto ret = arr->find(i);
    EXPECT_EQ(*(ret->second), i);
  }
}

Variable Documentation

AHACstrInt::Config cstrIntCfg

Definition at line 385 of file AtomicHashArrayTest.cpp.