Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1369)

Side by Side Diff: components/safe_browsing_db/prefix_set.h

Issue 1551433002: Switch to standard integer types in components/, part 3 of 4. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: more Created 4 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « components/rlz/rlz_tracker_unittest.cc ('k') | components/safe_browsing_db/prefix_set.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 31 matching lines...) Expand 10 before | Expand all | Expand 10 after
42 // 4 byte version number 42 // 4 byte version number
43 // 4 byte |index_.size()| 43 // 4 byte |index_.size()|
44 // 4 byte |deltas_.size()| 44 // 4 byte |deltas_.size()|
45 // n * 8 byte |&index_[0]..&index_[n]| 45 // n * 8 byte |&index_[0]..&index_[n]|
46 // m * 2 byte |&deltas_[0]..&deltas_[m]| 46 // m * 2 byte |&deltas_[0]..&deltas_[m]|
47 // 16 byte digest 47 // 16 byte digest
48 48
49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ 49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ 50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
51 51
52 #include <stddef.h>
53 #include <stdint.h>
54
52 #include <utility> 55 #include <utility>
53 #include <vector> 56 #include <vector>
54 57
55 #include "base/gtest_prod_util.h" 58 #include "base/gtest_prod_util.h"
56 #include "base/macros.h" 59 #include "base/macros.h"
57 #include "base/memory/scoped_ptr.h" 60 #include "base/memory/scoped_ptr.h"
58 #include "components/safe_browsing_db/util.h" 61 #include "components/safe_browsing_db/util.h"
59 62
60 namespace base { 63 namespace base {
61 class FilePath; 64 class FilePath;
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after
98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); 101 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout);
99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); 102 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7);
100 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); 103 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8);
101 104
102 // Maximum number of consecutive deltas to encode before generating 105 // Maximum number of consecutive deltas to encode before generating
103 // a new index entry. This helps keep the worst-case performance 106 // a new index entry. This helps keep the worst-case performance
104 // for |Exists()| under control. 107 // for |Exists()| under control.
105 static const size_t kMaxRun = 100; 108 static const size_t kMaxRun = 100;
106 109
107 // Helpers to make |index_| easier to deal with. 110 // Helpers to make |index_| easier to deal with.
108 typedef std::pair<SBPrefix, uint32> IndexPair; 111 typedef std::pair<SBPrefix, uint32_t> IndexPair;
109 typedef std::vector<IndexPair> IndexVector; 112 typedef std::vector<IndexPair> IndexVector;
110 static bool PrefixLess(const IndexPair& a, const IndexPair& b); 113 static bool PrefixLess(const IndexPair& a, const IndexPair& b);
111 114
112 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is 115 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is
113 // added to |index_|, with the other elements added into |deltas_|. 116 // added to |index_|, with the other elements added into |deltas_|.
114 void AddRun(SBPrefix index_prefix, 117 void AddRun(SBPrefix index_prefix,
115 const uint16* run_begin, const uint16* run_end); 118 const uint16_t* run_begin,
119 const uint16_t* run_end);
116 120
117 // |true| if |prefix| is one of the prefixes passed to the set's builder. 121 // |true| if |prefix| is one of the prefixes passed to the set's builder.
118 // Provided for testing purposes. 122 // Provided for testing purposes.
119 bool PrefixExists(SBPrefix prefix) const; 123 bool PrefixExists(SBPrefix prefix) const;
120 124
121 // Regenerate the vector of prefixes passed to the constructor into 125 // Regenerate the vector of prefixes passed to the constructor into
122 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. 126 // |prefixes|. Prefixes will be added in sorted order. Useful for testing.
123 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; 127 void GetPrefixes(std::vector<SBPrefix>* prefixes) const;
124 128
125 // Used by |PrefixSetBuilder|. 129 // Used by |PrefixSetBuilder|.
126 PrefixSet(); 130 PrefixSet();
127 131
128 // Helper for |LoadFile()|. Steals vector contents using |swap()|. 132 // Helper for |LoadFile()|. Steals vector contents using |swap()|.
129 PrefixSet(IndexVector* index, 133 PrefixSet(IndexVector* index,
130 std::vector<uint16>* deltas, 134 std::vector<uint16_t>* deltas,
131 std::vector<SBFullHash>* full_hashes); 135 std::vector<SBFullHash>* full_hashes);
132 136
133 // Top-level index of prefix to offset in |deltas_|. Each pair 137 // Top-level index of prefix to offset in |deltas_|. Each pair
134 // indicates a base prefix and where the deltas from that prefix 138 // indicates a base prefix and where the deltas from that prefix
135 // begin in |deltas_|. The deltas for a pair end at the next pair's 139 // begin in |deltas_|. The deltas for a pair end at the next pair's
136 // index into |deltas_|. 140 // index into |deltas_|.
137 IndexVector index_; 141 IndexVector index_;
138 142
139 // Deltas which are added to the prefix in |index_| to generate 143 // Deltas which are added to the prefix in |index_| to generate
140 // prefixes. Deltas are only valid between consecutive items from 144 // prefixes. Deltas are only valid between consecutive items from
141 // |index_|, or the end of |deltas_| for the last |index_| pair. 145 // |index_|, or the end of |deltas_| for the last |index_| pair.
142 std::vector<uint16> deltas_; 146 std::vector<uint16_t> deltas_;
143 147
144 // Full hashes ordered by SBFullHashLess. 148 // Full hashes ordered by SBFullHashLess.
145 std::vector<SBFullHash> full_hashes_; 149 std::vector<SBFullHash> full_hashes_;
146 150
147 DISALLOW_COPY_AND_ASSIGN(PrefixSet); 151 DISALLOW_COPY_AND_ASSIGN(PrefixSet);
148 }; 152 };
149 153
150 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. 154 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes.
151 class PrefixSetBuilder { 155 class PrefixSetBuilder {
152 public: 156 public:
(...skipping 25 matching lines...) Expand all
178 // Buffers prefixes until enough are avaliable to emit a run. 182 // Buffers prefixes until enough are avaliable to emit a run.
179 std::vector<SBPrefix> buffer_; 183 std::vector<SBPrefix> buffer_;
180 184
181 // The PrefixSet being built. 185 // The PrefixSet being built.
182 scoped_ptr<PrefixSet> prefix_set_; 186 scoped_ptr<PrefixSet> prefix_set_;
183 }; 187 };
184 188
185 } // namespace safe_browsing 189 } // namespace safe_browsing
186 190
187 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ 191 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_
OLDNEW
« no previous file with comments | « components/rlz/rlz_tracker_unittest.cc ('k') | components/safe_browsing_db/prefix_set.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698