chunk_range.cc revision 731df977c0511bca2206b5f333555b1205ff1f43
1// Copyright (c) 2010 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// Implementation of ChunkRange class. 6 7#include "chrome/browser/safe_browsing/chunk_range.h" 8 9#include "base/logging.h" 10#include "base/string_number_conversions.h" 11#include "base/string_split.h" 12#include "base/string_util.h" 13 14ChunkRange::ChunkRange(int start) : start_(start), stop_(start) { 15} 16 17ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) { 18} 19 20ChunkRange::ChunkRange(const ChunkRange& rhs) 21 : start_(rhs.start()), stop_(rhs.stop()) { 22} 23 24// Helper functions ----------------------------------------------------------- 25 26// Traverse the chunks vector looking for contiguous integers. 27void ChunksToRanges(const std::vector<int>& chunks, 28 std::vector<ChunkRange>* ranges) { 29 DCHECK(ranges); 30 for (size_t i = 0; i < chunks.size(); ++i) { 31 int start = static_cast<int>(i); 32 int next = start + 1; 33 while (next < static_cast<int>(chunks.size()) && 34 (chunks[start] == chunks[next] - 1 || 35 chunks[start] == chunks[next])) { 36 ++start; 37 ++next; 38 } 39 ranges->push_back(ChunkRange(chunks[i], chunks[start])); 40 if (next >= static_cast<int>(chunks.size())) 41 break; 42 i = start; 43 } 44} 45 46void RangesToChunks(const std::vector<ChunkRange>& ranges, 47 std::vector<int>* chunks) { 48 DCHECK(chunks); 49 for (size_t i = 0; i < ranges.size(); ++i) { 50 const ChunkRange& range = ranges[i]; 51 for (int chunk = range.start(); chunk <= range.stop(); ++chunk) { 52 chunks->push_back(chunk); 53 } 54 } 55} 56 57void RangesToString(const std::vector<ChunkRange>& ranges, 58 std::string* result) { 59 DCHECK(result); 60 result->clear(); 61 std::vector<ChunkRange>::const_iterator it = ranges.begin(); 62 for (; it != ranges.end(); ++it) { 63 if (!result->empty()) 64 result->append(","); 65 if (it->start() == it->stop()) { 66 std::string num_buf = base::IntToString(it->start()); 67 result->append(num_buf); 68 } else { 69 result->append(StringPrintf("%d-%d", it->start(), it->stop())); 70 } 71 } 72} 73 74bool StringToRanges(const std::string& input, 75 std::vector<ChunkRange>* ranges) { 76 DCHECK(ranges); 77 78 // Crack the string into chunk parts, then crack each part looking for a 79 // range. 80 std::vector<std::string> chunk_parts; 81 base::SplitString(input, ',', &chunk_parts); 82 83 for (size_t i = 0; i < chunk_parts.size(); ++i) { 84 std::vector<std::string> chunk_ranges; 85 base::SplitString(chunk_parts[i], '-', &chunk_ranges); 86 int start = atoi(chunk_ranges[0].c_str()); 87 int stop = start; 88 if (chunk_ranges.size() == 2) 89 stop = atoi(chunk_ranges[1].c_str()); 90 if (start == 0 || stop == 0) { 91 // atoi error, since chunk numbers are guaranteed to never be 0. 92 ranges->clear(); 93 return false; 94 } 95 ranges->push_back(ChunkRange(start, stop)); 96 } 97 98 return true; 99} 100 101// Binary search over a series of ChunkRanges. 102bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) { 103 if (ranges.empty()) 104 return false; 105 106 int low = 0; 107 int high = ranges.size() - 1; 108 109 while (low <= high) { 110 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html 111 int mid = ((unsigned int)low + (unsigned int)high) >> 1; 112 const ChunkRange& chunk = ranges[mid]; 113 if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number)) 114 return true; // chunk_number is in range. 115 116 // Adjust our mid point. 117 if (chunk.stop() < chunk_number) 118 low = mid + 1; 119 else 120 high = mid - 1; 121 } 122 123 return false; 124} 125