diff options
| author | paulg@google.com <paulg@google.com@0039d316-1c4b-4281-b951-d872f2087c98> | 2008-10-08 02:14:08 +0000 |
|---|---|---|
| committer | paulg@google.com <paulg@google.com@0039d316-1c4b-4281-b951-d872f2087c98> | 2008-10-08 02:14:08 +0000 |
| commit | 4f24e87d4c051571744bab377cc356bdef093701 (patch) | |
| tree | 7da8e990e10f95aabf6cf73670971bc654e3c214 /chrome/browser/safe_browsing/chunk_range.cc | |
| parent | 6bf766924e2e8dc08ccd248bc128bd6fe29297cd (diff) | |
| download | chromium_src-4f24e87d4c051571744bab377cc356bdef093701.zip chromium_src-4f24e87d4c051571744bab377cc356bdef093701.tar.gz chromium_src-4f24e87d4c051571744bab377cc356bdef093701.tar.bz2 | |
Make chunk ranges searchable.
Review URL: http://codereview.chromium.org/5645
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@2990 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'chrome/browser/safe_browsing/chunk_range.cc')
| -rw-r--r-- | chrome/browser/safe_browsing/chunk_range.cc | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/chrome/browser/safe_browsing/chunk_range.cc b/chrome/browser/safe_browsing/chunk_range.cc index e40ee72..0781e45 100644 --- a/chrome/browser/safe_browsing/chunk_range.cc +++ b/chrome/browser/safe_browsing/chunk_range.cc @@ -94,3 +94,29 @@ bool StringToRanges(const std::string& input, return true; } + +// Binary search over a series of ChunkRanges. +bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) { + if (ranges.empty()) + return false; + + int low = 0; + int high = ranges.size() - 1; + + while (low <= high) { + // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html + int mid = ((unsigned int)low + (unsigned int)high) >> 1; + const ChunkRange& chunk = ranges[mid]; + if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number)) + return true; // chunk_number is in range. + + // Adjust our mid point. + if (chunk.stop() < chunk_number) + low = mid + 1; + else + high = mid - 1; + } + + return false; +} + |