15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 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)#ifndef NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ 6a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#define NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/base/net_export.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace disk_cache { 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class provides support for simple maps of bits. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class NET_EXPORT_PRIVATE Bitmap { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitmap() : map_(NULL), num_bits_(0), array_size_(0), alloc_(false) {} 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This constructor will allocate on a uint32 boundary. If |clear_bits| is 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // false, the bitmap bits will not be initialized. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitmap(int num_bits, bool clear_bits); 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Constructs a Bitmap with the actual storage provided by the caller. |map| 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has to be valid until this object destruction. |num_bits| is the number of 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bits in the bitmap, and |num_words| is the size of |map| in 32-bit words. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitmap(uint32* map, int num_bits, int num_words); 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~Bitmap(); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Resizes the bitmap. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If |num_bits| < Size(), the extra bits will be discarded. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If |num_bits| > Size(), the extra bits will be filled with zeros if 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |clear_bits| is true. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This object cannot be using memory provided during construction. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Resize(int num_bits, bool clear_bits); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the number of bits in the bitmap. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int Size() const { return num_bits_; } 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the number of 32-bit words in the bitmap. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ArraySize() const { return array_size_; } 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets all the bits to true or false. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetAll(bool value) { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(map_, (value ? 0xFF : 0x00), array_size_ * sizeof(*map_)); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Clears all bits in the bitmap 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Clear() { SetAll(false); } 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets the value, gets the value or toggles the value of a given bit. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Set(int index, bool value); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Get(int index) const; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Toggle(int index); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Directly sets an element of the internal map. Requires |array_index| < 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ArraySize(); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetMapElement(int array_index, uint32 value); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Gets an entry of the internal map. Requires array_index < 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ArraySize() 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 GetMapElement(int array_index) const; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Directly sets the whole internal map. |size| is the number of 32-bit words 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to set from |map|. If |size| > array_size(), it ignores the end of |map|. 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetMap(const uint32* map, int size); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Gets a pointer to the internal map. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32* GetMap() const { return map_; } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets a range of bits to |value|. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetRange(int begin, int end, bool value); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true if any bit between begin inclusive and end exclusive is set. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0 <= |begin| <= |end| <= Size() is required. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool TestRange(int begin, int end, bool value) const; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Scans bits starting at bit *|index|, looking for a bit set to |value|. If 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it finds that bit before reaching bit index |limit|, sets *|index| to the 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bit index and returns true. Otherwise returns false. 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Requires |limit| <= Size(). 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that to use these methods in a loop you must increment the index 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // after each use, as in: 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for (int index = 0 ; map.FindNextBit(&index, limit, value) ; ++index) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // DoSomethingWith(index); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindNextBit(int* index, int limit, bool value) const; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finds the first offset >= *|index| and < |limit| that has its bit set. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See FindNextBit() for more info. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindNextSetBitBeforeLimit(int* index, int limit) const { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return FindNextBit(index, limit, true); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finds the first offset >= *|index| that has its bit set. 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See FindNextBit() for more info. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindNextSetBit(int *index) const { 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return FindNextSetBitBeforeLimit(index, num_bits_); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Scans bits starting at bit *|index|, looking for a bit set to |value|. If 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it finds that bit before reaching bit index |limit|, sets *|index| to the 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bit index and then counts the number of consecutive bits set to |value| 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (before reaching |limit|), and returns that count. If no bit is found 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // returns 0. Requires |limit| <= Size(). 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int FindBits(int* index, int limit, bool value) const; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns number of allocated words required for a bitmap of size |num_bits|. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int RequiredArraySize(int num_bits) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Force at least one allocated word. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (num_bits <= kIntBits) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (num_bits + kIntBits - 1) >> kLogIntBits; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kIntBits = sizeof(uint32) * 8; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kLogIntBits = 5; // 2^5 == 32 bits per word. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets |len| bits from |start| to |value|. All the bits to be set should be 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // stored in the same word, and len < kIntBits. 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetWordBits(int start, int len, bool value); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32* map_; // The bitmap. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_bits_; // The upper bound of the bitmap. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int array_size_; // The physical size (in uint32s) of the bitmap. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool alloc_; // Whether or not we allocated the memory. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(Bitmap); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace disk_cache 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 136a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#endif // NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ 137