RAPPOR implementation

components/rappor/bloom_filter_unittest.cc

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/rappor/bloom_filter.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace rappor {
+
+namespace {
+
+int CountBits(const ByteVector& v) {

[Alexei Svitkine (slow), 2014/01/21 18:14:04]

Is it me or is this duplicate in like 3 test files?

I suggest moving this to byte_vector_utils.h

[Steven Holte, 2014/01/21 20:25:14]

Done.

+  int bit_count = 0;
+  for(size_t i = 0; i < v.size(); i++) {
+    uint8_t byte = v[i];
+    for (int j = 0; j < 8 ; j++) {
+      if(byte & 1 << j) {
+        bit_count++;
+      }
+    }
+  }
+  return bit_count;
+}
+
+}  // namespace
+
+TEST(BloomFilterTest, TestTinyFilter) {
+  BloomFilter filter(1u, 4u);
+
+  // Size is 1 and it's initially empty
+  EXPECT_EQ(1u, filter.bytes().size());
+  EXPECT_EQ(0x00, filter.bytes()[0]);
+
+  // "Bar" has a self-collision, and only sets 3 bits.
+  filter.AddString("Bar");
+  EXPECT_EQ(0x13, filter.bytes()[0]);
+
+  // Adding the same value shouldn't change anything.
+  filter.AddString("Bar");
+  EXPECT_EQ(0x13, filter.bytes()[0]);
+
+  BloomFilter filter2(1, 4);
+  EXPECT_EQ(0x00, filter2.bytes()[0]);
+  filter2.AddString("Foo");
+  EXPECT_EQ(0x2B, filter2.bytes()[0]);
+
+  // Adding a colliding string should just set new bits.
+  filter.AddString("Foo");
+  EXPECT_EQ(0x3B, filter.bytes()[0]);
+}
+
+TEST(BloomFilterTest, TestHugeFilter) {
+  BloomFilter filter(500u, 1u);
+
+  // Size is 500 and it's initially empty
+  EXPECT_EQ(500u, filter.bytes().size());
+  EXPECT_EQ(0, CountBits(filter.bytes()));
+
+  filter.AddString("Bar");
+  EXPECT_EQ(1, CountBits(filter.bytes()));
+
+  // Adding the same value shouldn't change anything.
+  filter.AddString("Bar");
+  EXPECT_EQ(1, CountBits(filter.bytes()));
+}
+
+TEST(BloomFilterTest, TestAddStrings) {
+  BloomFilter filter(1u, 4u);
+  std::vector<std::string> strs;
+  strs.push_back("Bar");
+  strs.push_back("Foo");
+  filter.AddStrings(strs);
+
+  EXPECT_EQ(1u, filter.bytes().size());
+  EXPECT_EQ(0x3B, filter.bytes()[0]);
+}
+
+}  // namespace rappor