net/disk_cache/blockfile/bitmap_unittest.cc

   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/blockfile/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 }