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
TEST(BitmapTest,OverAllocate)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
TEST(BitmapTest,DefaultConstructor)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
TEST(BitmapTest,Basics)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
TEST(BitmapTest,Toggle)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
TEST(BitmapTest,Resize)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
TEST(BitmapTest,Map)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
TEST(BitmapTest,SetAll)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
TEST(BitmapTest,Range)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
TEST(BitmapTest,FindNextSetBitBeforeLimit)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
TEST(BitmapTest,FindNextSetBitBeforeLimitAligned)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
TEST(BitmapTest,FindNextSetBit)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
TEST(BitmapTest,FindNextBit)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
TEST(BitmapTest,SimpleFindBits)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
TEST(BitmapTest,MultiWordFindBits)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