1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * This is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License version 2.1, as published by the Free Software
9 * Foundation. See file COPYING.
10 * Copyright 2013 Inktank
13 #include "gtest/gtest.h"
14 #include "osd/HitSet.h"
17 class HitSetTestStrap {
21 explicit HitSetTestStrap(HitSet *h) : hitset(h) {}
23 void fill(unsigned count) {
25 for (unsigned i = 0; i < count; ++i) {
26 sprintf(buf, "hitsettest_%u", i);
27 hobject_t obj(object_t(buf), "", 0, i, 0, "");
30 EXPECT_EQ(count, hitset->insert_count());
32 void verify_fill(unsigned count) {
34 for (unsigned i = 0; i < count; ++i) {
35 sprintf(buf, "hitsettest_%u", i);
36 hobject_t obj(object_t(buf), "", 0, i, 0, "");
37 EXPECT_TRUE(hitset->contains(obj));
43 class BloomHitSetTest : public testing::Test, public HitSetTestStrap {
46 BloomHitSetTest() : HitSetTestStrap(new HitSet(new BloomHitSet)) {}
48 void rebuild(double fp, uint64_t target, uint64_t seed) {
49 BloomHitSet::Params *bparams = new BloomHitSet::Params(fp, target, seed);
50 HitSet::Params param(bparams);
51 HitSet new_set(param);
55 BloomHitSet *get_hitset() { return static_cast<BloomHitSet*>(hitset->impl.get()); }
58 TEST_F(BloomHitSetTest, Params) {
59 BloomHitSet::Params params(0.01, 100, 5);
60 EXPECT_EQ(.01, params.get_fpp());
61 EXPECT_EQ((unsigned)100, params.target_size);
62 EXPECT_EQ((unsigned)5, params.seed);
64 EXPECT_EQ(0.1, params.get_fpp());
68 BloomHitSet::Params p2;
69 bufferlist::iterator iter = bl.begin();
71 EXPECT_EQ(0.1, p2.get_fpp());
72 EXPECT_EQ((unsigned)100, p2.target_size);
73 EXPECT_EQ((unsigned)5, p2.seed);
76 TEST_F(BloomHitSetTest, Construct) {
77 ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
81 TEST_F(BloomHitSetTest, Rebuild) {
83 ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
86 TEST_F(BloomHitSetTest, InsertsMatch) {
90 * the approx unique count is atrocious on bloom filters. Empirical
91 * evidence suggests the current test will produce a value of 62
92 * regardless of hitset size
94 EXPECT_TRUE(hitset->approx_unique_insert_count() >= 50 &&
95 hitset->approx_unique_insert_count() <= 62);
97 EXPECT_FALSE(hitset->is_full());
100 TEST_F(BloomHitSetTest, FillsUp) {
104 EXPECT_TRUE(hitset->is_full());
107 TEST_F(BloomHitSetTest, RejectsNoMatch) {
108 rebuild(0.001, 100, 1);
111 EXPECT_TRUE(hitset->is_full());
115 for (int i = 100; i < 200; ++i) {
116 sprintf(buf, "hitsettest_%d", i);
117 hobject_t obj(object_t(buf), "", 0, i, 0, "");
118 if (hitset->contains(obj))
121 // we set a 1 in 1000 false positive; allow one in our 100
122 EXPECT_LT(matches, 2);
125 class ExplicitHashHitSetTest : public testing::Test, public HitSetTestStrap {
128 ExplicitHashHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitHashHitSet)) {}
130 ExplicitHashHitSet *get_hitset() { return static_cast<ExplicitHashHitSet*>(hitset->impl.get()); }
133 TEST_F(ExplicitHashHitSetTest, Construct) {
134 ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_HASH);
138 TEST_F(ExplicitHashHitSetTest, InsertsMatch) {
141 EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
142 EXPECT_FALSE(hitset->is_full());
145 TEST_F(ExplicitHashHitSetTest, RejectsNoMatch) {
148 EXPECT_FALSE(hitset->is_full());
152 for (int i = 100; i < 200; ++i) {
153 sprintf(buf, "hitsettest_%d", i);
154 hobject_t obj(object_t(buf), "", 0, i, 0, "");
155 if (hitset->contains(obj)) {
159 EXPECT_EQ(matches, 0);
162 class ExplicitObjectHitSetTest : public testing::Test, public HitSetTestStrap {
165 ExplicitObjectHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitObjectHitSet)) {}
167 ExplicitObjectHitSet *get_hitset() { return static_cast<ExplicitObjectHitSet*>(hitset->impl.get()); }
170 TEST_F(ExplicitObjectHitSetTest, Construct) {
171 ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_OBJECT);
175 TEST_F(ExplicitObjectHitSetTest, InsertsMatch) {
178 EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
179 EXPECT_FALSE(hitset->is_full());
182 TEST_F(ExplicitObjectHitSetTest, RejectsNoMatch) {
185 EXPECT_FALSE(hitset->is_full());
189 for (int i = 100; i < 200; ++i) {
190 sprintf(buf, "hitsettest_%d", i);
191 hobject_t obj(object_t(buf), "", 0, i, 0, "");
192 if (hitset->contains(obj)) {
196 EXPECT_EQ(matches, 0);