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 <limits> |
9 #include <set> | 9 #include <set> |
10 #include <utility> | 10 #include <utility> |
(...skipping 440 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
451 // - Doubling the size of the main table | 451 // - Doubling the size of the main table |
452 // - Adding more entries to the extra table | 452 // - Adding more entries to the extra table |
453 // | 453 // |
454 // For example, consider a 64k main table with 8k cells on the extra table (for | 454 // For example, consider a 64k main table with 8k cells on the extra table (for |
455 // a total of 72k cells). Init can be called to add another 8k cells at the end | 455 // a total of 72k cells). Init can be called to add another 8k cells at the end |
456 // (grow to 80k cells). When the size of the extra table approaches 64k, Init | 456 // (grow to 80k cells). When the size of the extra table approaches 64k, Init |
457 // can be called to double the main table (to 128k) and go back to a small extra | 457 // can be called to double the main table (to 128k) and go back to a small extra |
458 // table. | 458 // table. |
459 void IndexTable::Init(IndexTableInitData* params) { | 459 void IndexTable::Init(IndexTableInitData* params) { |
460 bool growing = header_ != NULL; | 460 bool growing = header_ != NULL; |
461 scoped_ptr<IndexBucket[]> old_extra_table; | 461 std::unique_ptr<IndexBucket[]> old_extra_table; |
462 header_ = ¶ms->index_bitmap->header; | 462 header_ = ¶ms->index_bitmap->header; |
463 | 463 |
464 if (params->main_table) { | 464 if (params->main_table) { |
465 if (main_table_) { | 465 if (main_table_) { |
466 // This is doubling the size of main table. | 466 // This is doubling the size of main table. |
467 DCHECK_EQ(base::bits::Log2Floor(header_->table_len), | 467 DCHECK_EQ(base::bits::Log2Floor(header_->table_len), |
468 base::bits::Log2Floor(backup_header_->table_len) + 1); | 468 base::bits::Log2Floor(backup_header_->table_len) + 1); |
469 int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket; | 469 int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket; |
470 DCHECK_GE(extra_size, 0); | 470 DCHECK_GE(extra_size, 0); |
471 | 471 |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
521 DCHECK_GT(old_num_words, old_main_table_bit_words); | 521 DCHECK_GT(old_num_words, old_main_table_bit_words); |
522 memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0, | 522 memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0, |
523 (old_num_words - old_main_table_bit_words) * sizeof(int32_t)); | 523 (old_num_words - old_main_table_bit_words) * sizeof(int32_t)); |
524 } | 524 } |
525 bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len, | 525 bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len, |
526 num_words)); | 526 num_words)); |
527 | 527 |
528 if (growing) { | 528 if (growing) { |
529 int old_num_words = (backup_header_.get()->table_len + 31) / 32; | 529 int old_num_words = (backup_header_.get()->table_len + 31) / 32; |
530 DCHECK_GE(num_words, old_num_words); | 530 DCHECK_GE(num_words, old_num_words); |
531 scoped_ptr<uint32_t[]> storage(new uint32_t[num_words]); | 531 std::unique_ptr<uint32_t[]> storage(new uint32_t[num_words]); |
532 memcpy(storage.get(), backup_bitmap_storage_.get(), | 532 memcpy(storage.get(), backup_bitmap_storage_.get(), |
533 old_num_words * sizeof(int32_t)); | 533 old_num_words * sizeof(int32_t)); |
534 memset(storage.get() + old_num_words, 0, | 534 memset(storage.get() + old_num_words, 0, |
535 (num_words - old_num_words) * sizeof(int32_t)); | 535 (num_words - old_num_words) * sizeof(int32_t)); |
536 | 536 |
537 backup_bitmap_storage_.swap(storage); | 537 backup_bitmap_storage_.swap(storage); |
538 backup_header_->table_len = header_->table_len; | 538 backup_header_->table_len = header_->table_len; |
539 } else { | 539 } else { |
540 backup_bitmap_storage_.reset(params->backup_bitmap.release()); | 540 backup_bitmap_storage_.reset(params->backup_bitmap.release()); |
541 backup_header_.reset(params->backup_header.release()); | 541 backup_header_.reset(params->backup_header.release()); |
(...skipping 413 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
955 int max_bucket = header()->max_bucket; | 955 int max_bucket = header()->max_bucket; |
956 header()->max_bucket = mask_; | 956 header()->max_bucket = mask_; |
957 int used_cells = header()->used_cells; | 957 int used_cells = header()->used_cells; |
958 | 958 |
959 // Consider a large cache: a cell stores the upper 18 bits of the hash | 959 // Consider a large cache: a cell stores the upper 18 bits of the hash |
960 // (h >> 14). If the table is say 8 times the original size (growing from 4x), | 960 // (h >> 14). If the table is say 8 times the original size (growing from 4x), |
961 // the bit that we are interested in would be the 3rd bit of the stored value, | 961 // the bit that we are interested in would be the 3rd bit of the stored value, |
962 // in other words 'multiplier' >> 1. | 962 // in other words 'multiplier' >> 1. |
963 uint32_t new_bit = (1 << extra_bits_) >> 1; | 963 uint32_t new_bit = (1 << extra_bits_) >> 1; |
964 | 964 |
965 scoped_ptr<IndexBucket[]> old_main_table; | 965 std::unique_ptr<IndexBucket[]> old_main_table; |
966 IndexBucket* source_table = main_table_; | 966 IndexBucket* source_table = main_table_; |
967 bool upgrade_format = !extra_bits_; | 967 bool upgrade_format = !extra_bits_; |
968 if (upgrade_format) { | 968 if (upgrade_format) { |
969 // This method should deal with migrating a small table to a big one. Given | 969 // This method should deal with migrating a small table to a big one. Given |
970 // that the first thing to do is read the old table, set small_table_ for | 970 // that the first thing to do is read the old table, set small_table_ for |
971 // the size of the old table. Now, when moving a cell, the result cannot be | 971 // the size of the old table. Now, when moving a cell, the result cannot be |
972 // placed in the old table or we will end up reading it again and attempting | 972 // placed in the old table or we will end up reading it again and attempting |
973 // to move it, so we have to copy the whole table at once. | 973 // to move it, so we have to copy the whole table at once. |
974 DCHECK(!small_table_); | 974 DCHECK(!small_table_); |
975 small_table_ = true; | 975 small_table_ = true; |
(...skipping 167 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1143 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32_t hash) { | 1143 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32_t hash) { |
1144 if (!extra_bits_) | 1144 if (!extra_bits_) |
1145 return false; | 1145 return false; |
1146 | 1146 |
1147 uint32_t mask = (1 << extra_bits_) - 1; | 1147 uint32_t mask = (1 << extra_bits_) - 1; |
1148 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; | 1148 hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; |
1149 return (GetHashValue(cell) & mask) != (hash & mask); | 1149 return (GetHashValue(cell) & mask) != (hash & mask); |
1150 } | 1150 } |
1151 | 1151 |
1152 } // namespace disk_cache | 1152 } // namespace disk_cache |
OLD | NEW |