| 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 |