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
8TEST(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
17TEST(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
25TEST(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
57TEST(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
68TEST(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
89TEST(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
117TEST(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
136TEST(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
178TEST(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
194TEST(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
205TEST(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
220TEST(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
235TEST(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
273TEST(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