15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/bitmap.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the number of trailing zeros. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int FindLSBSetNonZero(uint32 word) { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the LSB, put it on the exponent of a 32 bit float and remove the 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // mantisa and the bias. This code requires IEEE 32 bit float compliance. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float f = static_cast<float>(word & -static_cast<int>(word)); 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We use a union to go around strict-aliasing complains. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) union { 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float ieee_float; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 as_uint; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } x; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x.ieee_float = f; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (x.as_uint >> 23) - 0x7f; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the index of the first bit set to |value| from |word|. This code 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// assumes that we'll be able to find that bit. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int FindLSBNonEmpty(uint32 word, bool value) { 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we are looking for 0, negate |word| and look for 1. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!value) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) word = ~word; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return FindLSBSetNonZero(word); 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace disk_cache { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Bitmap::Bitmap(int num_bits, bool clear_bits) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : num_bits_(num_bits), 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_size_(RequiredArraySize(num_bits)), 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc_(true) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_ = new uint32[array_size_]; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Initialize all of the bits. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (clear_bits) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Clear(); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Bitmap::Bitmap(uint32* map, int num_bits, int num_words) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : map_(map), 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_bits_(num_bits), 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If size is larger than necessary, trim because array_size_ is used 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // as a bound by various methods. 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_size_(std::min(RequiredArraySize(num_bits), num_words)), 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc_(false) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Bitmap::~Bitmap() { 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (alloc_) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete [] map_; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::Resize(int num_bits, bool clear_bits) { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(alloc_ || !map_); 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int old_maxsize = num_bits_; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int old_array_size = array_size_; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_size_ = RequiredArraySize(num_bits); 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (array_size_ != old_array_size) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32* new_map = new uint32[array_size_]; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Always clear the unused bits in the last word. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_map[array_size_ - 1] = 0; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(new_map, map_, 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sizeof(*map_) * std::min(array_size_, old_array_size)); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (alloc_) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete[] map_; // No need to check for NULL. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_ = new_map; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc_ = true; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_bits_ = num_bits; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old_maxsize < num_bits_ && clear_bits) { 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetRange(old_maxsize, num_bits_, false); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::Set(int index, bool value) { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(index, num_bits_); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(index, 0); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int i = index & (kIntBits - 1); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int j = index / kIntBits; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[j] |= (1 << i); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[j] &= ~(1 << i); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Bitmap::Get(int index) const { 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(index, num_bits_); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(index, 0); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int i = index & (kIntBits-1); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int j = index / kIntBits; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ((map_[j] & (1 << i)) != 0); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::Toggle(int index) { 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(index, num_bits_); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(index, 0); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int i = index & (kIntBits - 1); 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int j = index / kIntBits; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[j] ^= (1 << i); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::SetMapElement(int array_index, uint32 value) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(array_index, array_size_); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(array_index, 0); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[array_index] = value; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uint32 Bitmap::GetMapElement(int array_index) const { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(array_index, array_size_); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(array_index, 0); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return map_[array_index]; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::SetMap(const uint32* map, int size) { 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_)); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::SetRange(int begin, int end, bool value) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(begin, end); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int start_offset = begin & (kIntBits - 1); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (start_offset) { 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set the bits in the first word. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int len = std::min(end - begin, kIntBits - start_offset); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetWordBits(begin, len, value); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) begin += len; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (begin == end) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now set the bits in the last word. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int end_offset = end & (kIntBits - 1); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) end -= end_offset; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetWordBits(end, end_offset, value); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set all the words in the middle. 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00), 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_)); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return true if any bit between begin inclusive and end exclusive 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is set. 0 <= begin <= end <= bits() is required. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Bitmap::TestRange(int begin, int end, bool value) const { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(begin, num_bits_); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(end, num_bits_); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(begin, end); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(begin, 0); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(end, 0); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return false immediately if the range is empty. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (begin >= end || end <= 0) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Calculate the indices of the words containing the first and last bits, 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // along with the positions of the bits within those words. 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int word = begin / kIntBits; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int offset = begin & (kIntBits - 1); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last_word = (end - 1) / kIntBits; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last_offset = (end - 1) & (kIntBits - 1); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we are looking for zeros, negate the data from the map. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 this_word = map_[word]; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!value) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this_word = ~this_word; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the range spans multiple words, discard the extraneous bits of the 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // first word by shifting to the right, and then test the remaining bits. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (word < last_word) { 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (this_word >> offset) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) offset = 0; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) word++; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test each of the "middle" words that lies completely within the range. 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (word < last_word) { 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this_word = map_[word++]; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!value) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this_word = ~this_word; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (this_word) 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test the portion of the last word that lies within the range. (This logic 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // also handles the case where the entire range lies within a single word.) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this_word = map_[last_word]; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!value) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this_word = ~this_word; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (this_word & mask) != 0; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Bitmap::FindNextBit(int* index, int limit, bool value) const { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(*index, num_bits_); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(limit, num_bits_); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(*index, limit); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(*index, 0); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(limit, 0); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int bit_index = *index; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bit_index >= limit || limit <= 0) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // From now on limit != 0, since if it was we would have returned false. 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int word_index = bit_index >> kLogIntBits; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 one_word = map_[word_index]; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Simple optimization where we can immediately return true if the first 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bit is set. This helps for cases where many bits are set, and doesn't 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // hurt too much if not. 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Get(bit_index) == value) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int first_bit_offset = bit_index & (kIntBits - 1); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First word is special - we need to mask off leading bits. 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 mask = 0xFFFFFFFF << first_bit_offset; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value) { 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one_word &= mask; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one_word |= ~mask; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 empty_value = value ? 0 : 0xFFFFFFFF; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop through all but the last word. Note that 'limit' is one 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // past the last bit we want to check, and we don't want to read 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // past the end of "words". E.g. if num_bits_ == 32 only words[0] is 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // valid, so we want to avoid reading words[1] when limit == 32. 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int last_word_index = (limit - 1) >> kLogIntBits; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (word_index < last_word_index) { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (one_word != empty_value) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one_word = map_[++word_index]; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Last word is special - we may need to mask off trailing bits. Note that 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'limit' is one past the last bit we want to check, and if limit is a 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // multiple of 32 we want to check all bits in this word. 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int last_bit_offset = (limit - 1) & (kIntBits - 1); 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mask = 0xFFFFFFFE << last_bit_offset; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value) { 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one_word &= ~mask; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one_word |= mask; 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (one_word != empty_value) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int Bitmap::FindBits(int* index, int limit, bool value) const { 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(*index, num_bits_); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(limit, num_bits_); 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(*index, limit); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(*index, 0); 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(limit, 0); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!FindNextBit(index, limit, value)) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now see how many bits have the same value. 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int end = *index; 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!FindNextBit(&end, limit, !value)) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return limit - *index; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end - *index; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Bitmap::SetWordBits(int start, int len, bool value) { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(len, kIntBits); 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(len, 0); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!len) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int word = start / kIntBits; 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int offset = start % kIntBits; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 to_add = 0xffffffff << len; 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) to_add = (~to_add) << offset; 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value) { 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[word] |= to_add; 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map_[word] &= ~to_add; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace disk_cache 312