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 |