1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright (c) 2009 The Chromium Authors. All rights reserved. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Use of this source code is governed by a BSD-style license that can be 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// found in the LICENSE file. 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/bitmap.h" 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "testing/gtest/include/gtest/gtest.h" 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, OverAllocate) { 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test that we don't over allocate on boundaries. 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map32(32, false); 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(1, map32.ArraySize()); 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map64(64, false); 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(2, map64.ArraySize()); 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, DefaultConstructor) { 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Verify that the default constructor doesn't allocate a bitmap. 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map; 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, map.Size()); 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, map.ArraySize()); 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(NULL == map.GetMap()); 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, Basics) { 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap bitmap(80, true); 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const uint32 kValue = 0x74f10060; 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test proper allocation size. 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(80, bitmap.Size()); 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(3, bitmap.ArraySize()); 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test Set/GetMapElement. 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0U, bitmap.GetMapElement(1)); 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMapElement(1, kValue); 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(kValue, bitmap.GetMapElement(1)); 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test Set/Get. 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(bitmap.Get(48)); 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(49)); 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(50)); 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.Set(49, true); 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(bitmap.Get(48)); 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(bitmap.Get(49)); 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(50)); 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.Set(49, false); 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(bitmap.Get(48)); 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(49)); 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(50)); 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 80; i++) 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.Set(i, (i % 7) == 0); 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 80; i++) 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(bitmap.Get(i), (i % 7) == 0); 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, Toggle) { 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const int kSize = 100; 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(kSize, true); 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; i += 3) 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Toggle(i); 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; i += 9) 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Toggle(i); 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; ++i) 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ((i % 3 == 0) && (i % 9 != 0), map.Get(i)); 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, Resize) { 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kSize1 = 50; 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kSize2 = 100; 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kSize3 = 30; 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(kSize1, true); 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Resize(kSize1, true); 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(kSize1, map.Size()); 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(0)); 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(kSize1 - 1)); 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Resize(kSize2, true); 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(kSize1 - 1)); 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(kSize1)); 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(kSize2 - 1)); 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(kSize2, map.Size()); 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Resize(kSize3, true); 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.Get(kSize3 - 1)); 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(kSize3, map.Size()); 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, Map) { 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Tests Set/GetMap and the constructor that takes an array. 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kMapSize = 80; 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott char local_map[kMapSize]; 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < kMapSize; i++) 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott local_map[i] = static_cast<char>(i); 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap bitmap(kMapSize * 8, false); 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMap(reinterpret_cast<uint32*>(local_map), kMapSize / 4); 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < kMapSize; i++) { 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (i % 2) 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(bitmap.Get(i * 8)); 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott else 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(bitmap.Get(i * 8)); 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(local_map, bitmap.GetMap(), kMapSize)); 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Now let's create a bitmap that shares local_map as storage. 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap bitmap2(reinterpret_cast<uint32*>(local_map), 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott kMapSize * 8, kMapSize / 4); 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize)); 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott local_map[kMapSize / 2] = 'a'; 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize)); 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_NE(0, memcmp(local_map, bitmap.GetMap(), kMapSize)); 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, SetAll) { 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Tests SetAll and Clear. 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kMapSize = 80; 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott char ones[kMapSize]; 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott char zeros[kMapSize]; 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memset(ones, 0xff, kMapSize); 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memset(zeros, 0, kMapSize); 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(kMapSize * 8, true); 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(true); 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(ones, map.GetMap(), kMapSize)); 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(false); 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(true); 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Clear(); 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize)); 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, Range) { 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Tests SetRange() and TestRange(). 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(100, true); 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(0, 100, true)); 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Set(50, true); 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(0, 100, true)); 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(false); 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(0, 1, true)); 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(30, 31, true)); 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(98, 99, true)); 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(99, 100, true)); 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(0, 100, true)); 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(0, 1, false)); 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(31, 32, false)); 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(32, 33, false)); 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(99, 100, false)); 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(0, 32, false)); 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetRange(11, 21, true); 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; i++) 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(map.Get(i), (i >= 11) && (i < 21)); 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(0, 32, true)); 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(0, 100, true)); 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(11, 21, true)); 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(15, 16, true)); 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(5, 12, true)); 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(5, 11, false)); 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(20, 60, true)); 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(21, 60, false)); 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(true); 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(0, 100, false)); 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetRange(70, 99, false); 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(69, 99, false)); 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_TRUE(map.TestRange(70, 100, false)); 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.TestRange(70, 99, true)); 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, FindNextSetBitBeforeLimit) { 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test FindNextSetBitBeforeLimit. Only check bits from 111 to 277 (limit 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // bit == 278). Should find all multiples of 27 in that range. 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(500, true); 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 500; i++) 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Set(i, (i % 27) == 0); 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int find_me = 135; // First one expected. 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int index = 111; map.FindNextSetBitBeforeLimit(&index, 278); 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++index) { 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(index, find_me); 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott find_me += 27; 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 191c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(find_me, 297); // The next find_me after 278. 192c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, FindNextSetBitBeforeLimitAligned) { 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test FindNextSetBitBeforeLimit on aligned scans. 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(256, true); 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 256; i++) 198c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Set(i, (i % 32) == 0); 199c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 256; i += 32) { 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int index = i + 1; 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_FALSE(map.FindNextSetBitBeforeLimit(&index, i + 32)); 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, FindNextSetBit) { 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test FindNextSetBit. Check all bits in map. Should find multiples 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // of 7 from 0 to 98. 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(100, true); 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; i++) 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Set(i, (i % 7) == 0); 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int find_me = 0; // First one expected. 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int index = 0; map.FindNextSetBit(&index); ++index) { 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(index, find_me); 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott find_me += 7; 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(find_me, 105); // The next find_me after 98. 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, FindNextBit) { 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Almost the same test as FindNextSetBit, but find zeros instead of ones. 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap map(100, false); 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.SetAll(true); 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < 100; i++) 225c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map.Set(i, (i % 7) != 0); 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int find_me = 0; // First one expected. 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int index = 0; map.FindNextBit(&index, 100, false); ++index) { 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(index, find_me); 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott find_me += 7; 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(find_me, 105); // The next find_me after 98. 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, SimpleFindBits) { 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap bitmap(64, true); 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMapElement(0, 0x7ff10060); 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Bit at index off. 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int index = 0; 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(5, bitmap.FindBits(&index, 63, false)); 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, index); 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(2, bitmap.FindBits(&index, 63, true)); 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(5, index); 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 0; 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(2, bitmap.FindBits(&index, 63, true)); 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(5, index); 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 6; 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(9, bitmap.FindBits(&index, 63, false)); 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(7, index); 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Bit at index on. 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 16; 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(1, bitmap.FindBits(&index, 63, true)); 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(16, index); 259c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 260c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 17; 261c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(11, bitmap.FindBits(&index, 63, true)); 262c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(20, index); 263c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 264c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 31; 265c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, bitmap.FindBits(&index, 63, true)); 266c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(31, index); 267c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 268c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // With a limit. 269c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 8; 270c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, bitmap.FindBits(&index, 16, true)); 271c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 272c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 273c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTEST(BitmapTest, MultiWordFindBits) { 274c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Bitmap bitmap(500, true); 275c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMapElement(10, 0xff00); 276c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 277c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int index = 0; 278c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(0, bitmap.FindBits(&index, 300, true)); 279c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 280c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(8, bitmap.FindBits(&index, 500, true)); 281c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(328, index); 282c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 283c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMapElement(10, 0xff000000); 284c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bitmap.SetMapElement(11, 0xff); 285c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 286c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 0; 287c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(16, bitmap.FindBits(&index, 500, true)); 288c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(344, index); 289c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 290c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott index = 0; 291c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(4, bitmap.FindBits(&index, 348, true)); 292c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EXPECT_EQ(344, index); 293c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 294