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