OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/disk_cache/blockfile/index_table_v3.h" | 5 #include "net/disk_cache/blockfile/index_table_v3.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <limits> |
8 #include <set> | 9 #include <set> |
9 #include <utility> | 10 #include <utility> |
10 | 11 |
11 #include "base/bits.h" | 12 #include "base/bits.h" |
12 #include "net/base/io_buffer.h" | 13 #include "net/base/io_buffer.h" |
13 #include "net/base/net_errors.h" | 14 #include "net/base/net_errors.h" |
14 #include "net/disk_cache/disk_cache.h" | 15 #include "net/disk_cache/disk_cache.h" |
15 | 16 |
16 using base::Time; | 17 using base::Time; |
17 using base::TimeDelta; | 18 using base::TimeDelta; |
18 using disk_cache::CellInfo; | 19 using disk_cache::CellInfo; |
19 using disk_cache::CellList; | 20 using disk_cache::CellList; |
20 using disk_cache::IndexCell; | 21 using disk_cache::IndexCell; |
21 using disk_cache::IndexIterator; | 22 using disk_cache::IndexIterator; |
22 | 23 |
23 namespace { | 24 namespace { |
24 | 25 |
25 // The following constants describe the bitfields of an IndexCell so they are | 26 // The following constants describe the bitfields of an IndexCell so they are |
26 // implicitly synchronized with the descrption of IndexCell on file_format_v3.h. | 27 // implicitly synchronized with the descrption of IndexCell on file_format_v3.h. |
27 const uint64 kCellLocationMask = (1 << 22) - 1; | 28 const uint64_t kCellLocationMask = (1 << 22) - 1; |
28 const uint64 kCellIdMask = (1 << 18) - 1; | 29 const uint64_t kCellIdMask = (1 << 18) - 1; |
29 const uint64 kCellTimestampMask = (1 << 20) - 1; | 30 const uint64_t kCellTimestampMask = (1 << 20) - 1; |
30 const uint64 kCellReuseMask = (1 << 4) - 1; | 31 const uint64_t kCellReuseMask = (1 << 4) - 1; |
31 const uint8 kCellStateMask = (1 << 3) - 1; | 32 const uint8_t kCellStateMask = (1 << 3) - 1; |
32 const uint8 kCellGroupMask = (1 << 3) - 1; | 33 const uint8_t kCellGroupMask = (1 << 3) - 1; |
33 const uint8 kCellSumMask = (1 << 2) - 1; | 34 const uint8_t kCellSumMask = (1 << 2) - 1; |
34 | 35 |
35 const uint64 kCellSmallTableLocationMask = (1 << 16) - 1; | 36 const uint64_t kCellSmallTableLocationMask = (1 << 16) - 1; |
36 const uint64 kCellSmallTableIdMask = (1 << 24) - 1; | 37 const uint64_t kCellSmallTableIdMask = (1 << 24) - 1; |
37 | 38 |
38 const int kCellIdOffset = 22; | 39 const int kCellIdOffset = 22; |
39 const int kCellTimestampOffset = 40; | 40 const int kCellTimestampOffset = 40; |
40 const int kCellReuseOffset = 60; | 41 const int kCellReuseOffset = 60; |
41 const int kCellGroupOffset = 3; | 42 const int kCellGroupOffset = 3; |
42 const int kCellSumOffset = 6; | 43 const int kCellSumOffset = 6; |
43 | 44 |
44 const int kCellSmallTableIdOffset = 16; | 45 const int kCellSmallTableIdOffset = 16; |
45 | 46 |
46 // The number of bits that a hash has to be shifted to grab the part that | 47 // The number of bits that a hash has to be shifted to grab the part that |
47 // defines the cell id. | 48 // defines the cell id. |
48 const int kHashShift = 14; | 49 const int kHashShift = 14; |
49 const int kSmallTableHashShift = 8; | 50 const int kSmallTableHashShift = 8; |
50 | 51 |
51 // Unfortunately we have to break the abstaction a little here: the file number | 52 // Unfortunately we have to break the abstaction a little here: the file number |
52 // where entries are stored is outside of the control of this code, and it is | 53 // where entries are stored is outside of the control of this code, and it is |
53 // usually part of the stored address. However, for small tables we only store | 54 // usually part of the stored address. However, for small tables we only store |
54 // 16 bits of the address so the file number is never stored on a cell. We have | 55 // 16 bits of the address so the file number is never stored on a cell. We have |
55 // to infere the file number from the type of entry (normal vs evicted), and | 56 // to infere the file number from the type of entry (normal vs evicted), and |
56 // the knowledge that given that the table will not keep more than 64k entries, | 57 // the knowledge that given that the table will not keep more than 64k entries, |
57 // a single file of each type is enough. | 58 // a single file of each type is enough. |
58 const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1; | 59 const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1; |
59 const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1; | 60 const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1; |
60 const int kMaxLocation = 1 << 22; | 61 const int kMaxLocation = 1 << 22; |
61 const int kMinFileNumber = 1 << 16; | 62 const int kMinFileNumber = 1 << 16; |
62 | 63 |
63 uint32 GetCellLocation(const IndexCell& cell) { | 64 uint32_t GetCellLocation(const IndexCell& cell) { |
64 return cell.first_part & kCellLocationMask; | 65 return cell.first_part & kCellLocationMask; |
65 } | 66 } |
66 | 67 |
67 uint32 GetCellSmallTableLocation(const IndexCell& cell) { | 68 uint32_t GetCellSmallTableLocation(const IndexCell& cell) { |
68 return cell.first_part & kCellSmallTableLocationMask; | 69 return cell.first_part & kCellSmallTableLocationMask; |
69 } | 70 } |
70 | 71 |
71 uint32 GetCellId(const IndexCell& cell) { | 72 uint32_t GetCellId(const IndexCell& cell) { |
72 return (cell.first_part >> kCellIdOffset) & kCellIdMask; | 73 return (cell.first_part >> kCellIdOffset) & kCellIdMask; |
73 } | 74 } |
74 | 75 |
75 uint32 GetCellSmallTableId(const IndexCell& cell) { | 76 uint32_t GetCellSmallTableId(const IndexCell& cell) { |
76 return (cell.first_part >> kCellSmallTableIdOffset) & | 77 return (cell.first_part >> kCellSmallTableIdOffset) & |
77 kCellSmallTableIdMask; | 78 kCellSmallTableIdMask; |
78 } | 79 } |
79 | 80 |
80 int GetCellTimestamp(const IndexCell& cell) { | 81 int GetCellTimestamp(const IndexCell& cell) { |
81 return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask; | 82 return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask; |
82 } | 83 } |
83 | 84 |
84 int GetCellReuse(const IndexCell& cell) { | 85 int GetCellReuse(const IndexCell& cell) { |
85 return (cell.first_part >> kCellReuseOffset) & kCellReuseMask; | 86 return (cell.first_part >> kCellReuseOffset) & kCellReuseMask; |
86 } | 87 } |
87 | 88 |
88 int GetCellState(const IndexCell& cell) { | 89 int GetCellState(const IndexCell& cell) { |
89 return cell.last_part & kCellStateMask; | 90 return cell.last_part & kCellStateMask; |
90 } | 91 } |
91 | 92 |
92 int GetCellGroup(const IndexCell& cell) { | 93 int GetCellGroup(const IndexCell& cell) { |
93 return (cell.last_part >> kCellGroupOffset) & kCellGroupMask; | 94 return (cell.last_part >> kCellGroupOffset) & kCellGroupMask; |
94 } | 95 } |
95 | 96 |
96 int GetCellSum(const IndexCell& cell) { | 97 int GetCellSum(const IndexCell& cell) { |
97 return (cell.last_part >> kCellSumOffset) & kCellSumMask; | 98 return (cell.last_part >> kCellSumOffset) & kCellSumMask; |
98 } | 99 } |
99 | 100 |
100 void SetCellLocation(IndexCell* cell, uint32 address) { | 101 void SetCellLocation(IndexCell* cell, uint32_t address) { |
101 DCHECK_LE(address, static_cast<uint32>(kCellLocationMask)); | 102 DCHECK_LE(address, static_cast<uint32_t>(kCellLocationMask)); |
102 cell->first_part &= ~kCellLocationMask; | 103 cell->first_part &= ~kCellLocationMask; |
103 cell->first_part |= address; | 104 cell->first_part |= address; |
104 } | 105 } |
105 | 106 |
106 void SetCellSmallTableLocation(IndexCell* cell, uint32 address) { | 107 void SetCellSmallTableLocation(IndexCell* cell, uint32_t address) { |
107 DCHECK_LE(address, static_cast<uint32>(kCellSmallTableLocationMask)); | 108 DCHECK_LE(address, static_cast<uint32_t>(kCellSmallTableLocationMask)); |
108 cell->first_part &= ~kCellSmallTableLocationMask; | 109 cell->first_part &= ~kCellSmallTableLocationMask; |
109 cell->first_part |= address; | 110 cell->first_part |= address; |
110 } | 111 } |
111 | 112 |
112 void SetCellId(IndexCell* cell, uint32 hash) { | 113 void SetCellId(IndexCell* cell, uint32_t hash) { |
113 DCHECK_LE(hash, static_cast<uint32>(kCellIdMask)); | 114 DCHECK_LE(hash, static_cast<uint32_t>(kCellIdMask)); |
114 cell->first_part &= ~(kCellIdMask << kCellIdOffset); | 115 cell->first_part &= ~(kCellIdMask << kCellIdOffset); |
115 cell->first_part |= static_cast<int64>(hash) << kCellIdOffset; | 116 cell->first_part |= static_cast<int64_t>(hash) << kCellIdOffset; |
116 } | 117 } |
117 | 118 |
118 void SetCellSmallTableId(IndexCell* cell, uint32 hash) { | 119 void SetCellSmallTableId(IndexCell* cell, uint32_t hash) { |
119 DCHECK_LE(hash, static_cast<uint32>(kCellSmallTableIdMask)); | 120 DCHECK_LE(hash, static_cast<uint32_t>(kCellSmallTableIdMask)); |
120 cell->first_part &= ~(kCellSmallTableIdMask << kCellSmallTableIdOffset); | 121 cell->first_part &= ~(kCellSmallTableIdMask << kCellSmallTableIdOffset); |
121 cell->first_part |= static_cast<int64>(hash) << kCellSmallTableIdOffset; | 122 cell->first_part |= static_cast<int64_t>(hash) << kCellSmallTableIdOffset; |
122 } | 123 } |
123 | 124 |
124 void SetCellTimestamp(IndexCell* cell, int timestamp) { | 125 void SetCellTimestamp(IndexCell* cell, int timestamp) { |
125 DCHECK_LT(timestamp, 1 << 20); | 126 DCHECK_LT(timestamp, 1 << 20); |
126 DCHECK_GE(timestamp, 0); | 127 DCHECK_GE(timestamp, 0); |
127 cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset); | 128 cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset); |
128 cell->first_part |= static_cast<int64>(timestamp) << kCellTimestampOffset; | 129 cell->first_part |= static_cast<int64_t>(timestamp) << kCellTimestampOffset; |
129 } | 130 } |
130 | 131 |
131 void SetCellReuse(IndexCell* cell, int count) { | 132 void SetCellReuse(IndexCell* cell, int count) { |
132 DCHECK_LT(count, 16); | 133 DCHECK_LT(count, 16); |
133 DCHECK_GE(count, 0); | 134 DCHECK_GE(count, 0); |
134 cell->first_part &= ~(kCellReuseMask << kCellReuseOffset); | 135 cell->first_part &= ~(kCellReuseMask << kCellReuseOffset); |
135 cell->first_part |= static_cast<int64>(count) << kCellReuseOffset; | 136 cell->first_part |= static_cast<int64_t>(count) << kCellReuseOffset; |
136 } | 137 } |
137 | 138 |
138 void SetCellState(IndexCell* cell, disk_cache::EntryState state) { | 139 void SetCellState(IndexCell* cell, disk_cache::EntryState state) { |
139 cell->last_part &= ~kCellStateMask; | 140 cell->last_part &= ~kCellStateMask; |
140 cell->last_part |= state; | 141 cell->last_part |= state; |
141 } | 142 } |
142 | 143 |
143 void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) { | 144 void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) { |
144 cell->last_part &= ~(kCellGroupMask << kCellGroupOffset); | 145 cell->last_part &= ~(kCellGroupMask << kCellGroupOffset); |
145 cell->last_part |= group << kCellGroupOffset; | 146 cell->last_part |= group << kCellGroupOffset; |
146 } | 147 } |
147 | 148 |
148 void SetCellSum(IndexCell* cell, int sum) { | 149 void SetCellSum(IndexCell* cell, int sum) { |
149 DCHECK_LT(sum, 4); | 150 DCHECK_LT(sum, 4); |
150 DCHECK_GE(sum, 0); | 151 DCHECK_GE(sum, 0); |
151 cell->last_part &= ~(kCellSumMask << kCellSumOffset); | 152 cell->last_part &= ~(kCellSumMask << kCellSumOffset); |
152 cell->last_part |= sum << kCellSumOffset; | 153 cell->last_part |= sum << kCellSumOffset; |
153 } | 154 } |
154 | 155 |
155 // This is a very particular way to calculate the sum, so it will not match if | 156 // This is a very particular way to calculate the sum, so it will not match if |
156 // compared a gainst a pure 2 bit, modulo 2 sum. | 157 // compared a gainst a pure 2 bit, modulo 2 sum. |
157 int CalculateCellSum(const IndexCell& cell) { | 158 int CalculateCellSum(const IndexCell& cell) { |
158 uint32* words = bit_cast<uint32*>(&cell); | 159 uint32_t* words = bit_cast<uint32_t*>(&cell); |
159 uint8* bytes = bit_cast<uint8*>(&cell); | 160 uint8_t* bytes = bit_cast<uint8_t*>(&cell); |
160 uint32 result = words[0] + words[1]; | 161 uint32_t result = words[0] + words[1]; |
161 result += result >> 16; | 162 result += result >> 16; |
162 result += (result >> 8) + (bytes[8] & 0x3f); | 163 result += (result >> 8) + (bytes[8] & 0x3f); |
163 result += result >> 4; | 164 result += result >> 4; |
164 result += result >> 2; | 165 result += result >> 2; |
165 return result & 3; | 166 return result & 3; |
166 } | 167 } |
167 | 168 |
168 bool SanityCheck(const IndexCell& cell) { | 169 bool SanityCheck(const IndexCell& cell) { |
169 if (GetCellSum(cell) != CalculateCellSum(cell)) | 170 if (GetCellSum(cell) != CalculateCellSum(cell)) |
170 return false; | 171 return false; |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
245 iterator->cells.clear(); | 246 iterator->cells.clear(); |
246 } | 247 } |
247 if (time == iterator->timestamp) { | 248 if (time == iterator->timestamp) { |
248 CellInfo cell_info = { cell.hash(), cell.GetAddress() }; | 249 CellInfo cell_info = { cell.hash(), cell.GetAddress() }; |
249 iterator->cells.push_back(cell_info); | 250 iterator->cells.push_back(cell_info); |
250 } | 251 } |
251 } | 252 } |
252 | 253 |
253 void InitIterator(IndexIterator* iterator) { | 254 void InitIterator(IndexIterator* iterator) { |
254 iterator->cells.clear(); | 255 iterator->cells.clear(); |
255 iterator->timestamp = iterator->forward ? kint32max : 0; | 256 iterator->timestamp = |
| 257 iterator->forward ? std::numeric_limits<int32_t>::max() : 0; |
256 } | 258 } |
257 | 259 |
258 } // namespace | 260 } // namespace |
259 | 261 |
260 namespace disk_cache { | 262 namespace disk_cache { |
261 | 263 |
262 EntryCell::~EntryCell() { | 264 EntryCell::~EntryCell() { |
263 } | 265 } |
264 | 266 |
265 bool EntryCell::IsValid() const { | 267 bool EntryCell::IsValid() const { |
266 return GetCellLocation(cell_) != 0; | 268 return GetCellLocation(cell_) != 0; |
267 } | 269 } |
268 | 270 |
269 // This code has to map the cell address (up to 22 bits) to a general cache Addr | 271 // This code has to map the cell address (up to 22 bits) to a general cache Addr |
270 // (up to 24 bits of general addressing). It also set the implied file_number | 272 // (up to 24 bits of general addressing). It also set the implied file_number |
271 // in the case of small tables. See also the comment by the definition of | 273 // in the case of small tables. See also the comment by the definition of |
272 // kEntriesFile. | 274 // kEntriesFile. |
273 Addr EntryCell::GetAddress() const { | 275 Addr EntryCell::GetAddress() const { |
274 uint32 location = GetLocation(); | 276 uint32_t location = GetLocation(); |
275 int file_number = FileNumberFromLocation(location); | 277 int file_number = FileNumberFromLocation(location); |
276 if (small_table_) { | 278 if (small_table_) { |
277 DCHECK_EQ(0, file_number); | 279 DCHECK_EQ(0, file_number); |
278 file_number = (GetGroup() == ENTRY_EVICTED) ? kEvictedEntriesFile : | 280 file_number = (GetGroup() == ENTRY_EVICTED) ? kEvictedEntriesFile : |
279 kEntriesFile; | 281 kEntriesFile; |
280 } | 282 } |
281 DCHECK_NE(0, file_number); | 283 DCHECK_NE(0, file_number); |
282 FileType file_type = (GetGroup() == ENTRY_EVICTED) ? BLOCK_EVICTED : | 284 FileType file_type = (GetGroup() == ENTRY_EVICTED) ? BLOCK_EVICTED : |
283 BLOCK_ENTRIES; | 285 BLOCK_ENTRIES; |
284 return Addr(file_type, 1, file_number, StartBlockFromLocation(location)); | 286 return Addr(file_type, 1, file_number, StartBlockFromLocation(location)); |
(...skipping 25 matching lines...) Expand all Loading... |
310 | 312 |
311 void EntryCell::SetReuse(int count) { | 313 void EntryCell::SetReuse(int count) { |
312 SetCellReuse(&cell_, count); | 314 SetCellReuse(&cell_, count); |
313 } | 315 } |
314 | 316 |
315 void EntryCell::SetTimestamp(int timestamp) { | 317 void EntryCell::SetTimestamp(int timestamp) { |
316 SetCellTimestamp(&cell_, timestamp); | 318 SetCellTimestamp(&cell_, timestamp); |
317 } | 319 } |
318 | 320 |
319 // Static. | 321 // Static. |
320 EntryCell EntryCell::GetEntryCellForTest(int32 cell_num, | 322 EntryCell EntryCell::GetEntryCellForTest(int32_t cell_num, |
321 uint32 hash, | 323 uint32_t hash, |
322 Addr address, | 324 Addr address, |
323 IndexCell* cell, | 325 IndexCell* cell, |
324 bool small_table) { | 326 bool small_table) { |
325 if (cell) { | 327 if (cell) { |
326 EntryCell entry_cell(cell_num, hash, *cell, small_table); | 328 EntryCell entry_cell(cell_num, hash, *cell, small_table); |
327 return entry_cell; | 329 return entry_cell; |
328 } | 330 } |
329 | 331 |
330 return EntryCell(cell_num, hash, address, small_table); | 332 return EntryCell(cell_num, hash, address, small_table); |
331 } | 333 } |
332 | 334 |
333 void EntryCell::SerializaForTest(IndexCell* destination) { | 335 void EntryCell::SerializaForTest(IndexCell* destination) { |
334 FixSum(); | 336 FixSum(); |
335 Serialize(destination); | 337 Serialize(destination); |
336 } | 338 } |
337 | 339 |
338 EntryCell::EntryCell() : cell_num_(0), hash_(0), small_table_(false) { | 340 EntryCell::EntryCell() : cell_num_(0), hash_(0), small_table_(false) { |
339 cell_.Clear(); | 341 cell_.Clear(); |
340 } | 342 } |
341 | 343 |
342 EntryCell::EntryCell(int32 cell_num, | 344 EntryCell::EntryCell(int32_t cell_num, |
343 uint32 hash, | 345 uint32_t hash, |
344 Addr address, | 346 Addr address, |
345 bool small_table) | 347 bool small_table) |
346 : cell_num_(cell_num), | 348 : cell_num_(cell_num), hash_(hash), small_table_(small_table) { |
347 hash_(hash), | |
348 small_table_(small_table) { | |
349 DCHECK(IsValidAddress(address) || !address.value()); | 349 DCHECK(IsValidAddress(address) || !address.value()); |
350 | 350 |
351 cell_.Clear(); | 351 cell_.Clear(); |
352 SetCellState(&cell_, ENTRY_NEW); | 352 SetCellState(&cell_, ENTRY_NEW); |
353 SetCellGroup(&cell_, ENTRY_NO_USE); | 353 SetCellGroup(&cell_, ENTRY_NO_USE); |
354 if (small_table) { | 354 if (small_table) { |
355 DCHECK(address.FileNumber() == kEntriesFile || | 355 DCHECK(address.FileNumber() == kEntriesFile || |
356 address.FileNumber() == kEvictedEntriesFile); | 356 address.FileNumber() == kEvictedEntriesFile); |
357 SetCellSmallTableLocation(&cell_, address.start_block()); | 357 SetCellSmallTableLocation(&cell_, address.start_block()); |
358 SetCellSmallTableId(&cell_, hash >> kSmallTableHashShift); | 358 SetCellSmallTableId(&cell_, hash >> kSmallTableHashShift); |
359 } else { | 359 } else { |
360 uint32 location = address.FileNumber() << 16 | address.start_block(); | 360 uint32_t location = address.FileNumber() << 16 | address.start_block(); |
361 SetCellLocation(&cell_, location); | 361 SetCellLocation(&cell_, location); |
362 SetCellId(&cell_, hash >> kHashShift); | 362 SetCellId(&cell_, hash >> kHashShift); |
363 } | 363 } |
364 } | 364 } |
365 | 365 |
366 EntryCell::EntryCell(int32 cell_num, | 366 EntryCell::EntryCell(int32_t cell_num, |
367 uint32 hash, | 367 uint32_t hash, |
368 const IndexCell& cell, | 368 const IndexCell& cell, |
369 bool small_table) | 369 bool small_table) |
370 : cell_num_(cell_num), | 370 : cell_num_(cell_num), |
371 hash_(hash), | 371 hash_(hash), |
372 cell_(cell), | 372 cell_(cell), |
373 small_table_(small_table) { | 373 small_table_(small_table) {} |
374 } | |
375 | 374 |
376 void EntryCell::FixSum() { | 375 void EntryCell::FixSum() { |
377 SetCellSum(&cell_, CalculateCellSum(cell_)); | 376 SetCellSum(&cell_, CalculateCellSum(cell_)); |
378 } | 377 } |
379 | 378 |
380 uint32 EntryCell::GetLocation() const { | 379 uint32_t EntryCell::GetLocation() const { |
381 if (small_table_) | 380 if (small_table_) |
382 return GetCellSmallTableLocation(cell_); | 381 return GetCellSmallTableLocation(cell_); |
383 | 382 |
384 return GetCellLocation(cell_); | 383 return GetCellLocation(cell_); |
385 } | 384 } |
386 | 385 |
387 uint32 EntryCell::RecomputeHash() { | 386 uint32_t EntryCell::RecomputeHash() { |
388 if (small_table_) { | 387 if (small_table_) { |
389 hash_ &= (1 << kSmallTableHashShift) - 1; | 388 hash_ &= (1 << kSmallTableHashShift) - 1; |
390 hash_ |= GetCellSmallTableId(cell_) << kSmallTableHashShift; | 389 hash_ |= GetCellSmallTableId(cell_) << kSmallTableHashShift; |
391 return hash_; | 390 return hash_; |
392 } | 391 } |
393 | 392 |
394 hash_ &= (1 << kHashShift) - 1; | 393 hash_ &= (1 << kHashShift) - 1; |
395 hash_ |= GetCellId(cell_) << kHashShift; | 394 hash_ |= GetCellId(cell_) << kHashShift; |
396 return hash_; | 395 return hash_; |
397 } | 396 } |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
505 // bitmap with 1 bit per cell, and that bitmap has num_words 32-bit words. | 504 // bitmap with 1 bit per cell, and that bitmap has num_words 32-bit words. |
506 int num_words = (header_->table_len + 31) / 32; | 505 int num_words = (header_->table_len + 31) / 32; |
507 | 506 |
508 if (old_extra_table) { | 507 if (old_extra_table) { |
509 // All the cells from the extra table are moving to the new tables so before | 508 // All the cells from the extra table are moving to the new tables so before |
510 // creating the bitmaps, clear the part of the bitmap referring to the extra | 509 // creating the bitmaps, clear the part of the bitmap referring to the extra |
511 // table. | 510 // table. |
512 int old_main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32; | 511 int old_main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32; |
513 DCHECK_GT(num_words, old_main_table_bit_words); | 512 DCHECK_GT(num_words, old_main_table_bit_words); |
514 memset(params->index_bitmap->bitmap + old_main_table_bit_words, 0, | 513 memset(params->index_bitmap->bitmap + old_main_table_bit_words, 0, |
515 (num_words - old_main_table_bit_words) * sizeof(int32)); | 514 (num_words - old_main_table_bit_words) * sizeof(int32_t)); |
516 | 515 |
517 DCHECK(growing); | 516 DCHECK(growing); |
518 int old_num_words = (backup_header_.get()->table_len + 31) / 32; | 517 int old_num_words = (backup_header_.get()->table_len + 31) / 32; |
519 DCHECK_GT(old_num_words, old_main_table_bit_words); | 518 DCHECK_GT(old_num_words, old_main_table_bit_words); |
520 memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0, | 519 memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0, |
521 (old_num_words - old_main_table_bit_words) * sizeof(int32)); | 520 (old_num_words - old_main_table_bit_words) * sizeof(int32_t)); |
522 } | 521 } |
523 bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len, | 522 bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len, |
524 num_words)); | 523 num_words)); |
525 | 524 |
526 if (growing) { | 525 if (growing) { |
527 int old_num_words = (backup_header_.get()->table_len + 31) / 32; | 526 int old_num_words = (backup_header_.get()->table_len + 31) / 32; |
528 DCHECK_GE(num_words, old_num_words); | 527 DCHECK_GE(num_words, old_num_words); |
529 scoped_ptr<uint32[]> storage(new uint32[num_words]); | 528 scoped_ptr<uint32_t[]> storage(new uint32_t[num_words]); |
530 memcpy(storage.get(), backup_bitmap_storage_.get(), | 529 memcpy(storage.get(), backup_bitmap_storage_.get(), |
531 old_num_words * sizeof(int32)); | 530 old_num_words * sizeof(int32_t)); |
532 memset(storage.get() + old_num_words, 0, | 531 memset(storage.get() + old_num_words, 0, |
533 (num_words - old_num_words) * sizeof(int32)); | 532 (num_words - old_num_words) * sizeof(int32_t)); |
534 | 533 |
535 backup_bitmap_storage_.swap(storage); | 534 backup_bitmap_storage_.swap(storage); |
536 backup_header_->table_len = header_->table_len; | 535 backup_header_->table_len = header_->table_len; |
537 } else { | 536 } else { |
538 backup_bitmap_storage_.reset(params->backup_bitmap.release()); | 537 backup_bitmap_storage_.reset(params->backup_bitmap.release()); |
539 backup_header_.reset(params->backup_header.release()); | 538 backup_header_.reset(params->backup_header.release()); |
540 } | 539 } |
541 | 540 |
542 num_words = (backup_header_->table_len + 31) / 32; | 541 num_words = (backup_header_->table_len + 31) / 32; |
543 backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(), | 542 backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(), |
(...skipping 23 matching lines...) Expand all Loading... |
567 | 566 |
568 // The general method for locating cells is to: | 567 // The general method for locating cells is to: |
569 // 1. Get the first bucket. This usually means directly indexing the table (as | 568 // 1. Get the first bucket. This usually means directly indexing the table (as |
570 // this method does), or iterating through all possible buckets. | 569 // this method does), or iterating through all possible buckets. |
571 // 2. Iterate through all the cells in that first bucket. | 570 // 2. Iterate through all the cells in that first bucket. |
572 // 3. If there is a linked bucket, locate it directly in the extra table. | 571 // 3. If there is a linked bucket, locate it directly in the extra table. |
573 // 4. Go back to 2, as needed. | 572 // 4. Go back to 2, as needed. |
574 // | 573 // |
575 // One consequence of this pattern is that we never start looking at buckets in | 574 // One consequence of this pattern is that we never start looking at buckets in |
576 // the extra table, unless we are following a link from the main table. | 575 // the extra table, unless we are following a link from the main table. |
577 EntrySet IndexTable::LookupEntries(uint32 hash) { | 576 EntrySet IndexTable::LookupEntries(uint32_t hash) { |
578 EntrySet entries; | 577 EntrySet entries; |
579 int bucket_num = static_cast<int>(hash & mask_); | 578 int bucket_num = static_cast<int>(hash & mask_); |
580 IndexBucket* bucket = &main_table_[bucket_num]; | 579 IndexBucket* bucket = &main_table_[bucket_num]; |
581 do { | 580 do { |
582 for (int i = 0; i < kCellsPerBucket; i++) { | 581 for (int i = 0; i < kCellsPerBucket; i++) { |
583 IndexCell* current_cell = &bucket->cells[i]; | 582 IndexCell* current_cell = &bucket->cells[i]; |
584 if (!GetLocation(*current_cell)) | 583 if (!GetLocation(*current_cell)) |
585 continue; | 584 continue; |
586 if (!SanityCheck(*current_cell)) { | 585 if (!SanityCheck(*current_cell)) { |
587 NOTREACHED(); | 586 NOTREACHED(); |
(...skipping 16 matching lines...) Expand all Loading... |
604 entries.evicted_count++; | 603 entries.evicted_count++; |
605 } | 604 } |
606 } | 605 } |
607 } | 606 } |
608 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, | 607 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, |
609 &bucket); | 608 &bucket); |
610 } while (bucket_num); | 609 } while (bucket_num); |
611 return entries; | 610 return entries; |
612 } | 611 } |
613 | 612 |
614 EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) { | 613 EntryCell IndexTable::CreateEntryCell(uint32_t hash, Addr address) { |
615 DCHECK(IsValidAddress(address)); | 614 DCHECK(IsValidAddress(address)); |
616 DCHECK(address.FileNumber() || address.start_block()); | 615 DCHECK(address.FileNumber() || address.start_block()); |
617 | 616 |
618 int bucket_num = static_cast<int>(hash & mask_); | 617 int bucket_num = static_cast<int>(hash & mask_); |
619 int cell_num = 0; | 618 int cell_num = 0; |
620 IndexBucket* bucket = &main_table_[bucket_num]; | 619 IndexBucket* bucket = &main_table_[bucket_num]; |
621 IndexCell* current_cell = NULL; | 620 IndexCell* current_cell = NULL; |
622 bool found = false; | 621 bool found = false; |
623 do { | 622 do { |
624 for (int i = 0; i < kCellsPerBucket && !found; i++) { | 623 for (int i = 0; i < kCellsPerBucket && !found; i++) { |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
658 if (found) { | 657 if (found) { |
659 bitmap_->Set(cell_num, true); | 658 bitmap_->Set(cell_num, true); |
660 backup_bitmap_->Set(cell_num, true); | 659 backup_bitmap_->Set(cell_num, true); |
661 header()->used_cells++; | 660 header()->used_cells++; |
662 modified_ = true; | 661 modified_ = true; |
663 } | 662 } |
664 | 663 |
665 return entry_cell; | 664 return entry_cell; |
666 } | 665 } |
667 | 666 |
668 EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) { | 667 EntryCell IndexTable::FindEntryCell(uint32_t hash, Addr address) { |
669 return FindEntryCellImpl(hash, address, false); | 668 return FindEntryCellImpl(hash, address, false); |
670 } | 669 } |
671 | 670 |
672 int IndexTable::CalculateTimestamp(Time time) { | 671 int IndexTable::CalculateTimestamp(Time time) { |
673 TimeDelta delta = time - Time::FromInternalValue(header_->base_time); | 672 TimeDelta delta = time - Time::FromInternalValue(header_->base_time); |
674 return std::max(delta.InMinutes(), 0); | 673 return std::max(delta.InMinutes(), 0); |
675 } | 674 } |
676 | 675 |
677 base::Time IndexTable::TimeFromTimestamp(int timestamp) { | 676 base::Time IndexTable::TimeFromTimestamp(int timestamp) { |
678 return Time::FromInternalValue(header_->base_time) + | 677 return Time::FromInternalValue(header_->base_time) + |
679 TimeDelta::FromMinutes(timestamp); | 678 TimeDelta::FromMinutes(timestamp); |
680 } | 679 } |
681 | 680 |
682 void IndexTable::SetSate(uint32 hash, Addr address, EntryState state) { | 681 void IndexTable::SetSate(uint32_t hash, Addr address, EntryState state) { |
683 EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE); | 682 EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE); |
684 if (!cell.IsValid()) { | 683 if (!cell.IsValid()) { |
685 NOTREACHED(); | 684 NOTREACHED(); |
686 return; | 685 return; |
687 } | 686 } |
688 | 687 |
689 EntryState old_state = cell.GetState(); | 688 EntryState old_state = cell.GetState(); |
690 switch (state) { | 689 switch (state) { |
691 case ENTRY_FREE: | 690 case ENTRY_FREE: |
692 DCHECK_EQ(old_state, ENTRY_DELETED); | 691 DCHECK_EQ(old_state, ENTRY_DELETED); |
(...skipping 27 matching lines...) Expand all Loading... |
720 cell.Clear(); | 719 cell.Clear(); |
721 Write(cell); | 720 Write(cell); |
722 header()->used_cells--; | 721 header()->used_cells--; |
723 return; | 722 return; |
724 } | 723 } |
725 cell.SetState(state); | 724 cell.SetState(state); |
726 | 725 |
727 Save(&cell); | 726 Save(&cell); |
728 } | 727 } |
729 | 728 |
730 void IndexTable::UpdateTime(uint32 hash, Addr address, base::Time current) { | 729 void IndexTable::UpdateTime(uint32_t hash, Addr address, base::Time current) { |
731 EntryCell cell = FindEntryCell(hash, address); | 730 EntryCell cell = FindEntryCell(hash, address); |
732 if (!cell.IsValid()) | 731 if (!cell.IsValid()) |
733 return; | 732 return; |
734 | 733 |
735 int minutes = CalculateTimestamp(current); | 734 int minutes = CalculateTimestamp(current); |
736 | 735 |
737 // Keep about 3 months of headroom. | 736 // Keep about 3 months of headroom. |
738 const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90; | 737 const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90; |
739 if (minutes > kMaxTimestamp) { | 738 if (minutes > kMaxTimestamp) { |
740 // TODO(rvargas): | 739 // TODO(rvargas): |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
785 scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes)); | 784 scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes)); |
786 memcpy(buffer->data(), header_, sizeof(*header_)); | 785 memcpy(buffer->data(), header_, sizeof(*header_)); |
787 memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(), | 786 memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(), |
788 num_words * 4); | 787 num_words * 4); |
789 backend_->SaveIndex(buffer.get(), num_bytes); | 788 backend_->SaveIndex(buffer.get(), num_bytes); |
790 modified_ = false; | 789 modified_ = false; |
791 } | 790 } |
792 | 791 |
793 // ----------------------------------------------------------------------- | 792 // ----------------------------------------------------------------------- |
794 | 793 |
795 EntryCell IndexTable::FindEntryCellImpl(uint32 hash, Addr address, | 794 EntryCell IndexTable::FindEntryCellImpl(uint32_t hash, |
| 795 Addr address, |
796 bool allow_deleted) { | 796 bool allow_deleted) { |
797 int bucket_num = static_cast<int>(hash & mask_); | 797 int bucket_num = static_cast<int>(hash & mask_); |
798 IndexBucket* bucket = &main_table_[bucket_num]; | 798 IndexBucket* bucket = &main_table_[bucket_num]; |
799 do { | 799 do { |
800 for (int i = 0; i < kCellsPerBucket; i++) { | 800 for (int i = 0; i < kCellsPerBucket; i++) { |
801 IndexCell* current_cell = &bucket->cells[i]; | 801 IndexCell* current_cell = &bucket->cells[i]; |
802 if (!GetLocation(*current_cell)) | 802 if (!GetLocation(*current_cell)) |
803 continue; | 803 continue; |
804 DCHECK(SanityCheck(*current_cell)); | 804 DCHECK(SanityCheck(*current_cell)); |
805 if (IsHashMatch(*current_cell, hash)) { | 805 if (IsHashMatch(*current_cell, hash)) { |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
840 } | 840 } |
841 } | 841 } |
842 | 842 |
843 if (current_state == ENTRY_FIXING) | 843 if (current_state == ENTRY_FIXING) |
844 backend_->FixCell(cell); | 844 backend_->FixCell(cell); |
845 } | 845 } |
846 | 846 |
847 void IndexTable::Write(const EntryCell& cell) { | 847 void IndexTable::Write(const EntryCell& cell) { |
848 IndexBucket* bucket = NULL; | 848 IndexBucket* bucket = NULL; |
849 int bucket_num = cell.cell_num() / kCellsPerBucket; | 849 int bucket_num = cell.cell_num() / kCellsPerBucket; |
850 if (bucket_num < static_cast<int32>(mask_ + 1)) { | 850 if (bucket_num < static_cast<int32_t>(mask_ + 1)) { |
851 bucket = &main_table_[bucket_num]; | 851 bucket = &main_table_[bucket_num]; |
852 } else { | 852 } else { |
853 DCHECK_LE(bucket_num, header()->max_bucket); | 853 DCHECK_LE(bucket_num, header()->max_bucket); |
854 bucket = &extra_table_[bucket_num - (mask_ + 1)]; | 854 bucket = &extra_table_[bucket_num - (mask_ + 1)]; |
855 } | 855 } |
856 | 856 |
857 int cell_number = cell.cell_num() % kCellsPerBucket; | 857 int cell_number = cell.cell_num() % kCellsPerBucket; |
858 if (GetLocation(bucket->cells[cell_number]) && cell.GetLocation()) { | 858 if (GetLocation(bucket->cells[cell_number]) && cell.GetLocation()) { |
859 DCHECK_EQ(cell.GetLocation(), | 859 DCHECK_EQ(cell.GetLocation(), |
860 GetLocation(bucket->cells[cell_number])); | 860 GetLocation(bucket->cells[cell_number])); |
(...skipping 20 matching lines...) Expand all Loading... |
881 | 881 |
882 void IndexTable::WalkTables(int limit_time, | 882 void IndexTable::WalkTables(int limit_time, |
883 IndexIterator* no_use, | 883 IndexIterator* no_use, |
884 IndexIterator* low_use, | 884 IndexIterator* low_use, |
885 IndexIterator* high_use) { | 885 IndexIterator* high_use) { |
886 header_->num_no_use_entries = 0; | 886 header_->num_no_use_entries = 0; |
887 header_->num_low_use_entries = 0; | 887 header_->num_low_use_entries = 0; |
888 header_->num_high_use_entries = 0; | 888 header_->num_high_use_entries = 0; |
889 header_->num_evicted_entries = 0; | 889 header_->num_evicted_entries = 0; |
890 | 890 |
891 for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) { | 891 for (int i = 0; i < static_cast<int32_t>(mask_ + 1); i++) { |
892 int bucket_num = i; | 892 int bucket_num = i; |
893 IndexBucket* bucket = &main_table_[i]; | 893 IndexBucket* bucket = &main_table_[i]; |
894 do { | 894 do { |
895 UpdateFromBucket(bucket, i, limit_time, no_use, low_use, high_use); | 895 UpdateFromBucket(bucket, i, limit_time, no_use, low_use, high_use); |
896 | 896 |
897 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, | 897 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, |
898 &bucket); | 898 &bucket); |
899 } while (bucket_num); | 899 } while (bucket_num); |
900 } | 900 } |
901 header_->num_entries = header_->num_no_use_entries + | 901 header_->num_entries = header_->num_no_use_entries + |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
950 void IndexTable::MoveCells(IndexBucket* old_extra_table) { | 950 void IndexTable::MoveCells(IndexBucket* old_extra_table) { |
951 int max_hash = (mask_ + 1) / 2; | 951 int max_hash = (mask_ + 1) / 2; |
952 int max_bucket = header()->max_bucket; | 952 int max_bucket = header()->max_bucket; |
953 header()->max_bucket = mask_; | 953 header()->max_bucket = mask_; |
954 int used_cells = header()->used_cells; | 954 int used_cells = header()->used_cells; |
955 | 955 |
956 // Consider a large cache: a cell stores the upper 18 bits of the hash | 956 // Consider a large cache: a cell stores the upper 18 bits of the hash |
957 // (h >> 14). If the table is say 8 times the original size (growing from 4x), | 957 // (h >> 14). If the table is say 8 times the original size (growing from 4x), |
958 // the bit that we are interested in would be the 3rd bit of the stored value, | 958 // the bit that we are interested in would be the 3rd bit of the stored value, |
959 // in other words 'multiplier' >> 1. | 959 // in other words 'multiplier' >> 1. |
960 uint32 new_bit = (1 << extra_bits_) >> 1; | 960 uint32_t new_bit = (1 << extra_bits_) >> 1; |
961 | 961 |
962 scoped_ptr<IndexBucket[]> old_main_table; | 962 scoped_ptr<IndexBucket[]> old_main_table; |
963 IndexBucket* source_table = main_table_; | 963 IndexBucket* source_table = main_table_; |
964 bool upgrade_format = !extra_bits_; | 964 bool upgrade_format = !extra_bits_; |
965 if (upgrade_format) { | 965 if (upgrade_format) { |
966 // This method should deal with migrating a small table to a big one. Given | 966 // This method should deal with migrating a small table to a big one. Given |
967 // that the first thing to do is read the old table, set small_table_ for | 967 // that the first thing to do is read the old table, set small_table_ for |
968 // the size of the old table. Now, when moving a cell, the result cannot be | 968 // the size of the old table. Now, when moving a cell, the result cannot be |
969 // placed in the old table or we will end up reading it again and attempting | 969 // placed in the old table or we will end up reading it again and attempting |
970 // to move it, so we have to copy the whole table at once. | 970 // to move it, so we have to copy the whole table at once. |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1009 DCHECK_EQ(header()->used_cells, used_cells); | 1009 DCHECK_EQ(header()->used_cells, used_cells); |
1010 | 1010 |
1011 if (upgrade_format) { | 1011 if (upgrade_format) { |
1012 small_table_ = false; | 1012 small_table_ = false; |
1013 header()->flags &= ~SMALL_CACHE; | 1013 header()->flags &= ~SMALL_CACHE; |
1014 } | 1014 } |
1015 } | 1015 } |
1016 | 1016 |
1017 void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_num, | 1017 void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_num, |
1018 int main_table_index, bool growing) { | 1018 int main_table_index, bool growing) { |
1019 uint32 hash = GetFullHash(*current_cell, main_table_index); | 1019 uint32_t hash = GetFullHash(*current_cell, main_table_index); |
1020 EntryCell old_cell(cell_num, hash, *current_cell, small_table_); | 1020 EntryCell old_cell(cell_num, hash, *current_cell, small_table_); |
1021 | 1021 |
1022 // This method may be called when moving entries from a small table to a | 1022 // This method may be called when moving entries from a small table to a |
1023 // normal table. In that case, the caller (MoveCells) has to read the old | 1023 // normal table. In that case, the caller (MoveCells) has to read the old |
1024 // table, so it needs small_table_ set to true, but this method needs to | 1024 // table, so it needs small_table_ set to true, but this method needs to |
1025 // write to the new table so small_table_ has to be set to false, and the | 1025 // write to the new table so small_table_ has to be set to false, and the |
1026 // value restored to true before returning. | 1026 // value restored to true before returning. |
1027 bool upgrade_format = !extra_bits_ && growing; | 1027 bool upgrade_format = !extra_bits_ && growing; |
1028 if (upgrade_format) | 1028 if (upgrade_format) |
1029 small_table_ = false; | 1029 small_table_ = false; |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1063 } | 1063 } |
1064 } | 1064 } |
1065 header()->used_cells--; | 1065 header()->used_cells--; |
1066 } | 1066 } |
1067 | 1067 |
1068 void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_num, | 1068 void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_num, |
1069 int main_table_index) { | 1069 int main_table_index) { |
1070 NOTREACHED(); // No unit tests yet. | 1070 NOTREACHED(); // No unit tests yet. |
1071 | 1071 |
1072 // The cell may be misplaced, or a duplicate cell exists with this data. | 1072 // The cell may be misplaced, or a duplicate cell exists with this data. |
1073 uint32 hash = GetFullHash(*current_cell, main_table_index); | 1073 uint32_t hash = GetFullHash(*current_cell, main_table_index); |
1074 MoveSingleCell(current_cell, cell_num, main_table_index, false); | 1074 MoveSingleCell(current_cell, cell_num, main_table_index, false); |
1075 | 1075 |
1076 // Now look for a duplicate cell. | 1076 // Now look for a duplicate cell. |
1077 CheckBucketList(hash & mask_); | 1077 CheckBucketList(hash & mask_); |
1078 } | 1078 } |
1079 | 1079 |
1080 void IndexTable::CheckBucketList(int bucket_num) { | 1080 void IndexTable::CheckBucketList(int bucket_num) { |
1081 typedef std::pair<int, EntryGroup> AddressAndGroup; | 1081 typedef std::pair<int, EntryGroup> AddressAndGroup; |
1082 std::set<AddressAndGroup> entries; | 1082 std::set<AddressAndGroup> entries; |
1083 IndexBucket* bucket = &main_table_[bucket_num]; | 1083 IndexBucket* bucket = &main_table_[bucket_num]; |
(...skipping 17 matching lines...) Expand all Loading... |
1101 continue; | 1101 continue; |
1102 } | 1102 } |
1103 CheckState(cell); | 1103 CheckState(cell); |
1104 } | 1104 } |
1105 | 1105 |
1106 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, | 1106 bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, |
1107 &bucket); | 1107 &bucket); |
1108 } while (bucket_num); | 1108 } while (bucket_num); |
1109 } | 1109 } |
1110 | 1110 |
1111 uint32 IndexTable::GetLocation(const IndexCell& cell) { | 1111 uint32_t IndexTable::GetLocation(const IndexCell& cell) { |
1112 if (small_table_) | 1112 if (small_table_) |
1113 return GetCellSmallTableLocation(cell); | 1113 return GetCellSmallTableLocation(cell); |
1114 | 1114 |
1115 return GetCellLocation(cell); | 1115 return GetCellLocation(cell); |
1116 } | 1116 } |
1117 | 1117 |
1118 uint32 IndexTable::GetHashValue(const IndexCell& cell) { | 1118 uint32_t IndexTable::GetHashValue(const IndexCell& cell) { |
1119 if (small_table_) | 1119 if (small_table_) |
1120 return GetCellSmallTableId(cell); | 1120 return GetCellSmallTableId(cell); |
1121 | 1121 |
1122 return GetCellId(cell); | 1122 return GetCellId(cell); |
1123 } | 1123 } |
1124 | 1124 |
1125 uint32 IndexTable::GetFullHash(const IndexCell& cell, uint32 lower_part) { | 1125 uint32_t IndexTable::GetFullHash(const IndexCell& cell, uint32_t lower_part) { |
1126 // It is OK for the high order bits of lower_part to overlap with the stored | 1126 // It is OK for the high order bits of lower_part to overlap with the stored |
1127 // part of the hash. | 1127 // part of the hash. |
1128 if (small_table_) | 1128 if (small_table_) |
1129 return (GetCellSmallTableId(cell) << kSmallTableHashShift) | lower_part; | 1129 return (GetCellSmallTableId(cell) << kSmallTableHashShift) | lower_part; |
1130 | 1130 |
1131 return (GetCellId(cell) << kHashShift) | lower_part; | 1131 return (GetCellId(cell) << kHashShift) | lower_part; |
1132 } | 1132 } |
1133 | 1133 |
1134 // All the bits stored in the cell should match the provided hash. | 1134 // All the bits stored in the cell should match the provided hash. |
1135 bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) { | 1135 bool IndexTable::IsHashMatch(const IndexCell& cell, uint32_t hash) { |
1136 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; | 1136 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; |
1137 return GetHashValue(cell) == hash; | 1137 return GetHashValue(cell) == hash; |
1138 } | 1138 } |
1139 | 1139 |
1140 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32 hash) { | 1140 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32_t hash) { |
1141 if (!extra_bits_) | 1141 if (!extra_bits_) |
1142 return false; | 1142 return false; |
1143 | 1143 |
1144 uint32 mask = (1 << extra_bits_) - 1; | 1144 uint32_t mask = (1 << extra_bits_) - 1; |
1145 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; | 1145 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; |
1146 return (GetHashValue(cell) & mask) != (hash & mask); | 1146 return (GetHashValue(cell) & mask) != (hash & mask); |
1147 } | 1147 } |
1148 | 1148 |
1149 } // namespace disk_cache | 1149 } // namespace disk_cache |
OLD | NEW |