| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 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 // A read-only set implementation for |SBPrefix| items. Prefixes are | 5 // A read-only set implementation for |SBPrefix| items. Prefixes are |
| 6 // sorted and stored as 16-bit deltas from the previous prefix. An | 6 // sorted and stored as 16-bit deltas from the previous prefix. An |
| 7 // index structure provides quick random access, and also handles | 7 // index structure provides quick random access, and also handles |
| 8 // cases where 16 bits cannot encode a delta. | 8 // cases where 16 bits cannot encode a delta. |
| 9 // | 9 // |
| 10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would | 10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would |
| (...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 66 bool Exists(SBPrefix prefix) const; | 66 bool Exists(SBPrefix prefix) const; |
| 67 | 67 |
| 68 // Persist the set on disk. | 68 // Persist the set on disk. |
| 69 static PrefixSet* LoadFile(const FilePath& filter_name); | 69 static PrefixSet* LoadFile(const FilePath& filter_name); |
| 70 bool WriteFile(const FilePath& filter_name) const; | 70 bool WriteFile(const FilePath& filter_name) const; |
| 71 | 71 |
| 72 // Regenerate the vector of prefixes passed to the constructor into | 72 // Regenerate the vector of prefixes passed to the constructor into |
| 73 // |prefixes|. Prefixes will be added in sorted order. | 73 // |prefixes|. Prefixes will be added in sorted order. |
| 74 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 74 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
| 75 | 75 |
| 76 // TODO(shess): The following are debugging accessors. Delete once | |
| 77 // the encoding problem is figured out. | |
| 78 | |
| 79 size_t IndexBinFor(size_t target_index) const; | |
| 80 | |
| 81 // The number of prefixes represented. | |
| 82 size_t GetSize() const; | |
| 83 | |
| 84 // Returns |true| if the element at |target_index| is between items in the | |
| 85 // |index_| array. | |
| 86 bool IsDeltaAt(size_t target_index) const; | |
| 87 | |
| 88 // Returns the delta used to calculate the element at | |
| 89 // |target_index|. Only call if |IsDeltaAt()| returned |true|. | |
| 90 uint16 DeltaAt(size_t target_index) const; | |
| 91 | |
| 92 // Check whether |index_| and |deltas_| still match the checksum | |
| 93 // generated during construction. | |
| 94 bool CheckChecksum() const; | |
| 95 | |
| 96 // Accumulates xor checksum over what GetPrefixes() would return, | |
| 97 // without requiring a large temporary structure. | |
| 98 SBPrefix GetPrefixesChecksum() const; | |
| 99 | |
| 100 private: | 76 private: |
| 101 // Maximum number of consecutive deltas to encode before generating | 77 // Maximum number of consecutive deltas to encode before generating |
| 102 // a new index entry. This helps keep the worst-case performance | 78 // a new index entry. This helps keep the worst-case performance |
| 103 // for |Exists()| under control. | 79 // for |Exists()| under control. |
| 104 static const size_t kMaxRun = 100; | 80 static const size_t kMaxRun = 100; |
| 105 | 81 |
| 106 // Helper for |LoadFile()|. Steals the contents of |index| and | 82 // Helper for |LoadFile()|. Steals the contents of |index| and |
| 107 // |deltas| using |swap()|. | 83 // |deltas| using |swap()|. |
| 108 PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, | 84 PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, |
| 109 std::vector<uint16> *deltas); | 85 std::vector<uint16> *deltas); |
| 110 | 86 |
| 111 // Top-level index of prefix to offset in |deltas_|. Each pair | 87 // Top-level index of prefix to offset in |deltas_|. Each pair |
| 112 // indicates a base prefix and where the deltas from that prefix | 88 // indicates a base prefix and where the deltas from that prefix |
| 113 // begin in |deltas_|. The deltas for a pair end at the next pair's | 89 // begin in |deltas_|. The deltas for a pair end at the next pair's |
| 114 // index into |deltas_|. | 90 // index into |deltas_|. |
| 115 std::vector<std::pair<SBPrefix,size_t> > index_; | 91 std::vector<std::pair<SBPrefix,size_t> > index_; |
| 116 | 92 |
| 117 // Deltas which are added to the prefix in |index_| to generate | 93 // Deltas which are added to the prefix in |index_| to generate |
| 118 // prefixes. Deltas are only valid between consecutive items from | 94 // prefixes. Deltas are only valid between consecutive items from |
| 119 // |index_|, or the end of |deltas_| for the last |index_| pair. | 95 // |index_|, or the end of |deltas_| for the last |index_| pair. |
| 120 std::vector<uint16> deltas_; | 96 std::vector<uint16> deltas_; |
| 121 | 97 |
| 122 // For debugging, used to verify that |index_| and |deltas| were not | |
| 123 // changed after generation during construction. |checksum_| is | |
| 124 // calculated from the data used to construct those vectors. | |
| 125 uint32 checksum_; | |
| 126 | |
| 127 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 98 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
| 128 }; | 99 }; |
| 129 | 100 |
| 130 } // namespace safe_browsing | 101 } // namespace safe_browsing |
| 131 | 102 |
| 132 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 103 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
| OLD | NEW |