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

3 files changed, 47 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;
+}
+
diff --git a/chrome/browser/safe_browsing/chunk_range.h b/chrome/browser/safe_browsing/chunk_range.h
index d547dea..a9969b1 100644
--- a/chrome/browser/safe_browsing/chunk_range.h
+++ b/chrome/browser/safe_browsing/chunk_range.h
@@ -60,5 +60,7 @@ void RangesToString(const std::vector<ChunkRange>& ranges,
 bool StringToRanges(const std::string& input,
                     std::vector<ChunkRange>* ranges);
 
+// Tests if a chunk number is contained a sorted vector of ChunkRanges.
+bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges);
 
 #endif  // CHROME_BROWSER_SAFE_BROWSING_CHUNK_RANGE_H_
diff --git a/chrome/browser/safe_browsing/chunk_range_unittest.cc b/chrome/browser/safe_browsing/chunk_range_unittest.cc
index e467dfd..91e44db 100644
--- a/chrome/browser/safe_browsing/chunk_range_unittest.cc
+++ b/chrome/browser/safe_browsing/chunk_range_unittest.cc
@@ -175,3 +175,22 @@ TEST(SafeBrowsingChunkRangeTest, TestRangesToChunks) {
   EXPECT_EQ(chunks[3], 4);
   EXPECT_EQ(chunks[4], 17);
 }
+
+
+TEST(SafeBrowsingChunkRangeTest, TestSearchChunkRanges) {
+  std::string range_str("1-10,15-17,21-410,555,991-1000");
+  std::vector<ChunkRange> ranges;
+  StringToRanges(range_str, &ranges);
+
+  EXPECT_TRUE(IsChunkInRange(7, ranges));
+  EXPECT_TRUE(IsChunkInRange(300, ranges));
+  EXPECT_TRUE(IsChunkInRange(555, ranges));
+  EXPECT_TRUE(IsChunkInRange(1, ranges));
+  EXPECT_TRUE(IsChunkInRange(1000, ranges));
+
+  EXPECT_FALSE(IsChunkInRange(11, ranges));
+  EXPECT_FALSE(IsChunkInRange(990, ranges));
+  EXPECT_FALSE(IsChunkInRange(2000, ranges));
+}
+
+