OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 // | |
5 // A read-only set implementation for |SBPrefix| items. Prefixes are | |
6 // sorted and stored as 16-bit deltas from the previous prefix. An | |
7 // index structure provides quick random access, and also handles | |
8 // cases where 16 bits cannot encode a delta. | |
9 // | |
10 // This structure is intended for storage of sparse uniform sets of | |
11 // prefixes of a certain size. As of this writing, my safe-browsing | |
12 // database contains: | |
13 // 653132 add prefixes | |
14 // 6446 are duplicates (from different chunks) | |
15 // 24301 w/in 2^8 of the prior prefix | |
16 // 622337 w/in 2^16 of the prior prefix | |
17 // 47 further than 2^16 from the prior prefix | |
18 // For this input, the memory usage is approximately 2 bytes per | |
19 // prefix, a bit over 1.2M. The bloom filter used 25 bits per prefix, | |
20 // a bit over 1.9M on this data. | |
21 // | |
22 // Experimenting with random selections of the above data, storage | |
23 // size drops almost linearly as prefix count drops, until the index | |
24 // overhead starts to become a problem a bit under 200k prefixes. The | |
25 // memory footprint gets worse than storing the raw prefix data around | |
26 // 75k prefixes. Fortunately, the actual memory footprint also falls | |
27 // continuously. If the prefix count increases the memory footprint | |
28 // should increase approximately linearly. | |
29 // | |
30 // TODO(shess): Write serialization code. Something like this should | |
31 // work: | |
32 // 4 byte magic number | |
33 // 4 byte version number | |
34 // 4 byte |index_.size()| | |
35 // 4 byte |deltas_.size()| | |
36 // n * 8 byte |&index_[0]..&index_[n]| | |
37 // m * 2 byte |&deltas_[0]..&deltas_[m]| | |
38 // 16 byte digest | |
39 | |
40 #ifndef CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | |
41 #define CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | |
42 #pragma once | |
43 | |
44 #include <vector> | |
45 | |
46 #include "chrome/browser/safe_browsing/safe_browsing_util.h" | |
47 | |
48 namespace safe_browsing { | |
49 | |
50 class PrefixSet { | |
51 public: | |
52 explicit PrefixSet(const std::vector<SBPrefix>& prefixes); | |
53 | |
54 // |true| if |prefix| was in |prefixes| passed to the constructor. | |
55 bool Exists(SBPrefix prefix) const; | |
56 | |
57 private: | |
58 // Maximum delta that can be encoded in a 16-bit unsigned. | |
59 static const unsigned kMaxDelta = 256 * 256; | |
60 | |
61 // Maximum number of consecutive deltas to encode before generating | |
62 // a new index entry. This helps keep the worst-case performance | |
63 // for |Exists()| under control. | |
64 static const size_t kMaxRun = 100; | |
65 | |
66 // Top-level index of prefix to offset in |deltas_|. Each pair | |
lzheng
2011/02/05 01:03:42
You might want to give an example. It is a little
Scott Hess - ex-Googler
2011/02/07 19:20:23
Adding a comment in the file header.
| |
67 // indicates a base prefix and where the deltas from that prefix | |
68 // begin in |deltas_|. The deltas for a pair end at the next pair's | |
69 // index into |deltas_|. | |
70 std::vector<std::pair<SBPrefix,size_t> > index_; | |
71 | |
72 // Deltas which are added to the prefix in |index_| to generate | |
73 // prefixes. Deltas are only valid between consecutive items from | |
74 // |index_|, or the end of |deltas_| for the last |index_| pair. | |
75 std::vector<uint16> deltas_; | |
76 | |
77 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | |
78 }; | |
79 | |
80 } // namespace safe_browsing | |
81 | |
82 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | |
OLD | NEW |