diff options
Diffstat (limited to 'net/disk_cache/blockfile/bitmap_unittest.cc')
-rw-r--r-- | net/disk_cache/blockfile/bitmap_unittest.cc | 293 |
1 files changed, 293 insertions, 0 deletions
diff --git a/net/disk_cache/blockfile/bitmap_unittest.cc b/net/disk_cache/blockfile/bitmap_unittest.cc new file mode 100644 index 0000000..a0748bf --- /dev/null +++ b/net/disk_cache/blockfile/bitmap_unittest.cc @@ -0,0 +1,293 @@ +// Copyright (c) 2009 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 "net/disk_cache/blockfile/bitmap.h" +#include "testing/gtest/include/gtest/gtest.h" + +TEST(BitmapTest, OverAllocate) { + // Test that we don't over allocate on boundaries. + disk_cache::Bitmap map32(32, false); + EXPECT_EQ(1, map32.ArraySize()); + + disk_cache::Bitmap map64(64, false); + EXPECT_EQ(2, map64.ArraySize()); +} + +TEST(BitmapTest, DefaultConstructor) { + // Verify that the default constructor doesn't allocate a bitmap. + disk_cache::Bitmap map; + EXPECT_EQ(0, map.Size()); + EXPECT_EQ(0, map.ArraySize()); + EXPECT_TRUE(NULL == map.GetMap()); +} + +TEST(BitmapTest, Basics) { + disk_cache::Bitmap bitmap(80, true); + const uint32 kValue = 0x74f10060; + + // Test proper allocation size. + EXPECT_EQ(80, bitmap.Size()); + EXPECT_EQ(3, bitmap.ArraySize()); + + // Test Set/GetMapElement. + EXPECT_EQ(0U, bitmap.GetMapElement(1)); + bitmap.SetMapElement(1, kValue); + EXPECT_EQ(kValue, bitmap.GetMapElement(1)); + + // Test Set/Get. + EXPECT_TRUE(bitmap.Get(48)); + EXPECT_FALSE(bitmap.Get(49)); + EXPECT_FALSE(bitmap.Get(50)); + bitmap.Set(49, true); + EXPECT_TRUE(bitmap.Get(48)); + EXPECT_TRUE(bitmap.Get(49)); + EXPECT_FALSE(bitmap.Get(50)); + bitmap.Set(49, false); + EXPECT_TRUE(bitmap.Get(48)); + EXPECT_FALSE(bitmap.Get(49)); + EXPECT_FALSE(bitmap.Get(50)); + + for (int i = 0; i < 80; i++) + bitmap.Set(i, (i % 7) == 0); + for (int i = 0; i < 80; i++) + EXPECT_EQ(bitmap.Get(i), (i % 7) == 0); +} + +TEST(BitmapTest, Toggle) { + static const int kSize = 100; + disk_cache::Bitmap map(kSize, true); + for (int i = 0; i < 100; i += 3) + map.Toggle(i); + for (int i = 0; i < 100; i += 9) + map.Toggle(i); + for (int i = 0; i < 100; ++i) + EXPECT_EQ((i % 3 == 0) && (i % 9 != 0), map.Get(i)); +} + +TEST(BitmapTest, Resize) { + const int kSize1 = 50; + const int kSize2 = 100; + const int kSize3 = 30; + disk_cache::Bitmap map(kSize1, true); + map.Resize(kSize1, true); + EXPECT_EQ(kSize1, map.Size()); + EXPECT_FALSE(map.Get(0)); + EXPECT_FALSE(map.Get(kSize1 - 1)); + + map.Resize(kSize2, true); + EXPECT_FALSE(map.Get(kSize1 - 1)); + EXPECT_FALSE(map.Get(kSize1)); + EXPECT_FALSE(map.Get(kSize2 - 1)); + EXPECT_EQ(kSize2, map.Size()); + + map.Resize(kSize3, true); + EXPECT_FALSE(map.Get(kSize3 - 1)); + EXPECT_EQ(kSize3, map.Size()); +} + +TEST(BitmapTest, Map) { + // Tests Set/GetMap and the constructor that takes an array. + const int kMapSize = 80; + char local_map[kMapSize]; + for (int i = 0; i < kMapSize; i++) + local_map[i] = static_cast<char>(i); + + disk_cache::Bitmap bitmap(kMapSize * 8, false); + bitmap.SetMap(reinterpret_cast<uint32*>(local_map), kMapSize / 4); + for (int i = 0; i < kMapSize; i++) { + if (i % 2) + EXPECT_TRUE(bitmap.Get(i * 8)); + else + EXPECT_FALSE(bitmap.Get(i * 8)); + } + + EXPECT_EQ(0, memcmp(local_map, bitmap.GetMap(), kMapSize)); + + // Now let's create a bitmap that shares local_map as storage. + disk_cache::Bitmap bitmap2(reinterpret_cast<uint32*>(local_map), + kMapSize * 8, kMapSize / 4); + EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize)); + + local_map[kMapSize / 2] = 'a'; + EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize)); + EXPECT_NE(0, memcmp(local_map, bitmap.GetMap(), kMapSize)); +} + +TEST(BitmapTest, SetAll) { + // Tests SetAll and Clear. + const int kMapSize = 80; + char ones[kMapSize]; + char zeros[kMapSize]; + memset(ones, 0xff, kMapSize); + memset(zeros, 0, kMapSize); + + disk_cache::Bitmap map(kMapSize * 8, true); + EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); + map.SetAll(true); + EXPECT_EQ(0, memcmp(ones, map.GetMap(), kMapSize)); + map.SetAll(false); + EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); + map.SetAll(true); + map.Clear(); + EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); +} + +TEST(BitmapTest, Range) { + // Tests SetRange() and TestRange(). + disk_cache::Bitmap map(100, true); + EXPECT_FALSE(map.TestRange(0, 100, true)); + map.Set(50, true); + EXPECT_TRUE(map.TestRange(0, 100, true)); + + map.SetAll(false); + EXPECT_FALSE(map.TestRange(0, 1, true)); + EXPECT_FALSE(map.TestRange(30, 31, true)); + EXPECT_FALSE(map.TestRange(98, 99, true)); + EXPECT_FALSE(map.TestRange(99, 100, true)); + EXPECT_FALSE(map.TestRange(0, 100, true)); + + EXPECT_TRUE(map.TestRange(0, 1, false)); + EXPECT_TRUE(map.TestRange(31, 32, false)); + EXPECT_TRUE(map.TestRange(32, 33, false)); + EXPECT_TRUE(map.TestRange(99, 100, false)); + EXPECT_TRUE(map.TestRange(0, 32, false)); + + map.SetRange(11, 21, true); + for (int i = 0; i < 100; i++) + EXPECT_EQ(map.Get(i), (i >= 11) && (i < 21)); + + EXPECT_TRUE(map.TestRange(0, 32, true)); + EXPECT_TRUE(map.TestRange(0, 100, true)); + EXPECT_TRUE(map.TestRange(11, 21, true)); + EXPECT_TRUE(map.TestRange(15, 16, true)); + EXPECT_TRUE(map.TestRange(5, 12, true)); + EXPECT_TRUE(map.TestRange(5, 11, false)); + EXPECT_TRUE(map.TestRange(20, 60, true)); + EXPECT_TRUE(map.TestRange(21, 60, false)); + + map.SetAll(true); + EXPECT_FALSE(map.TestRange(0, 100, false)); + + map.SetRange(70, 99, false); + EXPECT_TRUE(map.TestRange(69, 99, false)); + EXPECT_TRUE(map.TestRange(70, 100, false)); + EXPECT_FALSE(map.TestRange(70, 99, true)); +} + +TEST(BitmapTest, FindNextSetBitBeforeLimit) { + // Test FindNextSetBitBeforeLimit. Only check bits from 111 to 277 (limit + // bit == 278). Should find all multiples of 27 in that range. + disk_cache::Bitmap map(500, true); + for (int i = 0; i < 500; i++) + map.Set(i, (i % 27) == 0); + + int find_me = 135; // First one expected. + for (int index = 111; map.FindNextSetBitBeforeLimit(&index, 278); + ++index) { + EXPECT_EQ(index, find_me); + find_me += 27; + } + EXPECT_EQ(find_me, 297); // The next find_me after 278. +} + +TEST(BitmapTest, FindNextSetBitBeforeLimitAligned) { + // Test FindNextSetBitBeforeLimit on aligned scans. + disk_cache::Bitmap map(256, true); + for (int i = 0; i < 256; i++) + map.Set(i, (i % 32) == 0); + for (int i = 0; i < 256; i += 32) { + int index = i + 1; + EXPECT_FALSE(map.FindNextSetBitBeforeLimit(&index, i + 32)); + } +} + +TEST(BitmapTest, FindNextSetBit) { + // Test FindNextSetBit. Check all bits in map. Should find multiples + // of 7 from 0 to 98. + disk_cache::Bitmap map(100, true); + for (int i = 0; i < 100; i++) + map.Set(i, (i % 7) == 0); + + int find_me = 0; // First one expected. + for (int index = 0; map.FindNextSetBit(&index); ++index) { + EXPECT_EQ(index, find_me); + find_me += 7; + } + EXPECT_EQ(find_me, 105); // The next find_me after 98. +} + +TEST(BitmapTest, FindNextBit) { + // Almost the same test as FindNextSetBit, but find zeros instead of ones. + disk_cache::Bitmap map(100, false); + map.SetAll(true); + for (int i = 0; i < 100; i++) + map.Set(i, (i % 7) != 0); + + int find_me = 0; // First one expected. + for (int index = 0; map.FindNextBit(&index, 100, false); ++index) { + EXPECT_EQ(index, find_me); + find_me += 7; + } + EXPECT_EQ(find_me, 105); // The next find_me after 98. +} + +TEST(BitmapTest, SimpleFindBits) { + disk_cache::Bitmap bitmap(64, true); + bitmap.SetMapElement(0, 0x7ff10060); + + // Bit at index off. + int index = 0; + EXPECT_EQ(5, bitmap.FindBits(&index, 63, false)); + EXPECT_EQ(0, index); + + EXPECT_EQ(2, bitmap.FindBits(&index, 63, true)); + EXPECT_EQ(5, index); + + index = 0; + EXPECT_EQ(2, bitmap.FindBits(&index, 63, true)); + EXPECT_EQ(5, index); + + index = 6; + EXPECT_EQ(9, bitmap.FindBits(&index, 63, false)); + EXPECT_EQ(7, index); + + // Bit at index on. + index = 16; + EXPECT_EQ(1, bitmap.FindBits(&index, 63, true)); + EXPECT_EQ(16, index); + + index = 17; + EXPECT_EQ(11, bitmap.FindBits(&index, 63, true)); + EXPECT_EQ(20, index); + + index = 31; + EXPECT_EQ(0, bitmap.FindBits(&index, 63, true)); + EXPECT_EQ(31, index); + + // With a limit. + index = 8; + EXPECT_EQ(0, bitmap.FindBits(&index, 16, true)); +} + +TEST(BitmapTest, MultiWordFindBits) { + disk_cache::Bitmap bitmap(500, true); + bitmap.SetMapElement(10, 0xff00); + + int index = 0; + EXPECT_EQ(0, bitmap.FindBits(&index, 300, true)); + + EXPECT_EQ(8, bitmap.FindBits(&index, 500, true)); + EXPECT_EQ(328, index); + + bitmap.SetMapElement(10, 0xff000000); + bitmap.SetMapElement(11, 0xff); + + index = 0; + EXPECT_EQ(16, bitmap.FindBits(&index, 500, true)); + EXPECT_EQ(344, index); + + index = 0; + EXPECT_EQ(4, bitmap.FindBits(&index, 348, true)); + EXPECT_EQ(344, index); +} |