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