1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright (c) 2009 The Chromium Authors. All rights reserved. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Use of this source code is governed by a BSD-style license that can be 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// found in the LICENSE file. 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/bitmap.h" 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen#include <algorithm> 872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/logging.h" 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace { 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Returns the number of trailing zeros. 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint FindLSBSetNonZero(uint32 word) { 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Get the LSB, put it on the exponent of a 32 bit float and remove the 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // mantisa and the bias. This code requires IEEE 32 bit float compliance. 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott float f = static_cast<float>(word & -static_cast<int>(word)); 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We use a union to go around strict-aliasing complains. 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott union { 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott float ieee_float; 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 as_uint; 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } x; 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott x.ieee_float = f; 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return (x.as_uint >> 23) - 0x7f; 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Returns the index of the first bit set to |value| from |word|. This code 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// assumes that we'll be able to find that bit. 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint FindLSBNonEmpty(uint32 word, bool value) { 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If we are looking for 0, negate |word| and look for 1. 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!value) 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott word = ~word; 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return FindLSBSetNonZero(word); 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace disk_cache { 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 4372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian MonsenBitmap::Bitmap(int num_bits, bool clear_bits) 4472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen : num_bits_(num_bits), 4572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen array_size_(RequiredArraySize(num_bits)), 4672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen alloc_(true) { 4772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen map_ = new uint32[array_size_]; 4872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 4972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // Initialize all of the bits. 5072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (clear_bits) 5172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Clear(); 5272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 5372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 5472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian MonsenBitmap::Bitmap(uint32* map, int num_bits, int num_words) 5572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen : map_(map), 5672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen num_bits_(num_bits), 5772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // If size is larger than necessary, trim because array_size_ is used 5872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // as a bound by various methods. 5972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen array_size_(std::min(RequiredArraySize(num_bits), num_words)), 6072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen alloc_(false) { 6172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 6272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 6372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian MonsenBitmap::~Bitmap() { 6472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (alloc_) 6572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen delete [] map_; 6672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 6772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::Resize(int num_bits, bool clear_bits) { 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(alloc_ || !map_); 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int old_maxsize = num_bits_; 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int old_array_size = array_size_; 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott array_size_ = RequiredArraySize(num_bits); 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (array_size_ != old_array_size) { 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32* new_map = new uint32[array_size_]; 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Always clear the unused bits in the last word. 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott new_map[array_size_ - 1] = 0; 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memcpy(new_map, map_, 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sizeof(*map_) * std::min(array_size_, old_array_size)); 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (alloc_) 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] map_; // No need to check for NULL. 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map_ = new_map; 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott alloc_ = true; 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott num_bits_ = num_bits; 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (old_maxsize < num_bits_ && clear_bits) { 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott SetRange(old_maxsize, num_bits_, false); 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::Set(int index, bool value) { 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(index, num_bits_); 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(index, 0); 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int i = index & (kIntBits - 1); 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int j = index / kIntBits; 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (value) 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map_[j] |= (1 << i); 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott else 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map_[j] &= ~(1 << i); 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Bitmap::Get(int index) const { 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(index, num_bits_); 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(index, 0); 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int i = index & (kIntBits-1); 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int j = index / kIntBits; 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return map_[j] & (1 << i) ? true : false; 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::Toggle(int index) { 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(index, num_bits_); 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(index, 0); 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int i = index & (kIntBits - 1); 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int j = index / kIntBits; 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map_[j] ^= (1 << i); 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::SetMapElement(int array_index, uint32 value) { 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(array_index, array_size_); 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(array_index, 0); 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott map_[array_index] = value; 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottuint32 Bitmap::GetMapElement(int array_index) const { 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(array_index, array_size_); 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(array_index, 0); 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return map_[array_index]; 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::SetMap(const uint32* map, int size) { 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_)); 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Bitmap::SetRange(int begin, int end, bool value) { 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(begin, end); 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int start_offset = begin & (kIntBits - 1); 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (start_offset) { 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Set the bits in the first word. 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int len = std::min(end - begin, kIntBits - start_offset); 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott SetWordBits(begin, len, value); 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott begin += len; 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (begin == end) 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Now set the bits in the last word. 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int end_offset = end & (kIntBits - 1); 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott end -= end_offset; 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott SetWordBits(end, end_offset, value); 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Set all the words in the middle. 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00), 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_)); 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Return true if any bit between begin inclusive and end exclusive 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// is set. 0 <= begin <= end <= bits() is required. 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Bitmap::TestRange(int begin, int end, bool value) const { 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(begin, num_bits_); 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(end, num_bits_); 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(begin, end); 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(begin, 0); 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(end, 0); 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Return false immediately if the range is empty. 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (begin >= end || end <= 0) 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Calculate the indices of the words containing the first and last bits, 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // along with the positions of the bits within those words. 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int word = begin / kIntBits; 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int offset = begin & (kIntBits - 1); 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int last_word = (end - 1) / kIntBits; 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int last_offset = (end - 1) & (kIntBits - 1); 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If we are looking for zeros, negate the data from the map. 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 this_word = map_[word]; 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!value) 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott this_word = ~this_word; 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If the range spans multiple words, discard the extraneous bits of the 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // first word by shifting to the right, and then test the remaining bits. 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (word < last_word) { 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (this_word >> offset) 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott offset = 0; 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott word++; 191c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test each of the "middle" words that lies completely within the range. 192c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (word < last_word) { 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott this_word = map_[word++]; 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!value) 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott this_word = ~this_word; 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (this_word) 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 198c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 199c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Test the portion of the last word that lies within the range. (This logic 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // also handles the case where the entire range lies within a single word.) 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset; 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott this_word = map_[last_word]; 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!value) 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott this_word = ~this_word; 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return (this_word & mask) != 0; 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Bitmap::FindNextBit(int* index, int limit, bool value) const { 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(*index, num_bits_); 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(limit, num_bits_); 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(*index, limit); 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(*index, 0); 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(limit, 0); 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int bit_index = *index; 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (bit_index >= limit || limit <= 0) 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // From now on limit != 0, since if it was we would have returned false. 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int word_index = bit_index >> kLogIntBits; 225c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 one_word = map_[word_index]; 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Simple optimization where we can immediately return true if the first 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // bit is set. This helps for cases where many bits are set, and doesn't 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // hurt too much if not. 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (Get(bit_index) == value) 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int first_bit_offset = bit_index & (kIntBits - 1); 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // First word is special - we need to mask off leading bits. 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 mask = 0xFFFFFFFF << first_bit_offset; 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (value) { 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott one_word &= mask; 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott one_word |= ~mask; 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 empty_value = value ? 0 : 0xFFFFFFFF; 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Loop through all but the last word. Note that 'limit' is one 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // past the last bit we want to check, and we don't want to read 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // past the end of "words". E.g. if num_bits_ == 32 only words[0] is 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // valid, so we want to avoid reading words[1] when limit == 32. 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int last_word_index = (limit - 1) >> kLogIntBits; 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (word_index < last_word_index) { 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (one_word != empty_value) { 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value); 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott one_word = map_[++word_index]; 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Last word is special - we may need to mask off trailing bits. Note that 259c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // 'limit' is one past the last bit we want to check, and if limit is a 260c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // multiple of 32 we want to check all bits in this word. 261c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int last_bit_offset = (limit - 1) & (kIntBits - 1); 262c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott mask = 0xFFFFFFFE << last_bit_offset; 263c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (value) { 264c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott one_word &= ~mask; 265c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 266c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott one_word |= mask; 267c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 268c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (one_word != empty_value) { 269c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value); 270c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 271c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 272c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 273c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 274c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 275c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint Bitmap::FindBits(int* index, int limit, bool value) const { 276c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LT(*index, num_bits_); 277c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(limit, num_bits_); 278c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_LE(*index, limit); 279c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(*index, 0); 280c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK_GE(limit, 0); 281c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 282c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!FindNextBit(index, limit, value)) 283c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 284c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 285c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Now see how many bits have the same value. 286c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int end = *index; 287c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!FindNextBit(&end, limit, !value)) 288c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return limit - *index; 289c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 290c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return end - *index; 291c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 292c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 29372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Bitmap::SetWordBits(int start, int len, bool value) { 29472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen DCHECK_LT(len, kIntBits); 29572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen DCHECK_GE(len, 0); 29672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!len) 29772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 29872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 29972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen int word = start / kIntBits; 30072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen int offset = start % kIntBits; 30172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 30272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen uint32 to_add = 0xffffffff << len; 30372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen to_add = (~to_add) << offset; 30472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (value) { 30572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen map_[word] |= to_add; 30672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else { 30772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen map_[word] &= ~to_add; 30872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 30972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 31072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 311c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace disk_cache 312