| // Copyright 2020 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_CSS_PROPERTIES_CSS_BITSET_H_ |
| #define THIRD_PARTY_BLINK_RENDERER_CORE_CSS_PROPERTIES_CSS_BITSET_H_ |
| |
| #include <algorithm> |
| #include <cstring> |
| #include <initializer_list> |
| #include "third_party/blink/renderer/core/css/css_property_names.h" |
| |
| namespace blink { |
| |
| // A bitset designed for CSSPropertyIDs. |
| // |
| // It's different from std::bitset, in that it provides optimized traversal |
| // for situations where only a few bits are set (which is the common case for |
| // e.g. CSS declarations which apply to an element). |
| // |
| // The bitset can store a configurable amount of bits for testing purposes, |
| // (though not more than numCSSProperties). |
| template <size_t kBits> |
| class CORE_EXPORT CSSBitsetBase { |
| public: |
| static_assert( |
| kBits <= kNumCSSProperties, |
| "Bit count must not exceed numCSSProperties, as each bit position must " |
| "be representable as a CSSPropertyID"); |
| |
| static const size_t kChunks = (kBits + 63) / 64; |
| |
| CSSBitsetBase() : chunks_() {} |
| CSSBitsetBase(const CSSBitsetBase<kBits>& o) { *this = o; } |
| CSSBitsetBase(std::initializer_list<CSSPropertyID> list) : chunks_() { |
| for (CSSPropertyID id : list) |
| Set(id); |
| } |
| |
| void operator=(const CSSBitsetBase& o) { |
| std::memcpy(chunks_, o.chunks_, sizeof(chunks_)); |
| } |
| |
| bool operator==(const CSSBitsetBase& o) const { |
| return std::memcmp(chunks_, o.chunks_, sizeof(chunks_)) == 0; |
| } |
| bool operator!=(const CSSBitsetBase& o) const { return !(*this == o); } |
| |
| inline void Set(CSSPropertyID id) { |
| size_t bit = static_cast<size_t>(id); |
| DCHECK_LT(bit, kBits); |
| chunks_[bit / 64] |= (1ull << (bit % 64)); |
| } |
| |
| inline void Or(CSSPropertyID id, bool v) { |
| size_t bit = static_cast<size_t>(id); |
| DCHECK_LT(bit, kBits); |
| chunks_[bit / 64] |= (static_cast<uint64_t>(v) << (bit % 64)); |
| } |
| |
| inline bool Has(CSSPropertyID id) const { |
| size_t bit = static_cast<size_t>(id); |
| DCHECK_LT(bit, kBits); |
| return chunks_[bit / 64] & (1ull << (bit % 64)); |
| } |
| |
| inline bool HasAny() const { |
| for (uint64_t chunk : chunks_) { |
| if (chunk) |
| return true; |
| } |
| return false; |
| } |
| |
| inline void Reset() { std::memset(chunks_, 0, sizeof(chunks_)); } |
| |
| // Yields the CSSPropertyIDs which are set. |
| class Iterator { |
| public: |
| Iterator(const uint64_t* chunks, size_t index) |
| : chunks_(chunks), index_(index), chunk_(ChunkAt(index)) {} |
| |
| inline void operator++() { |
| do { |
| ++index_; |
| chunk_ = chunk_ >> 1ull; |
| DCHECK_LE(index_, kBits); |
| |
| if (index_ >= kBits) |
| return; |
| if (!chunk_) { |
| // If the chunk is empty, we can fast-forward to the next chunk. |
| size_t next_chunk_index = (index_ - 1) / 64 + 1; |
| index_ = std::min(next_chunk_index * 64, kBits); |
| chunk_ = ChunkAt(index_); |
| } |
| } while (!(chunk_ & 1)); |
| } |
| |
| inline CSSPropertyID operator*() const { |
| DCHECK_LT(index_, static_cast<size_t>(kNumCSSProperties)); |
| return static_cast<CSSPropertyID>(index_); |
| } |
| |
| inline bool operator==(const Iterator& o) const { |
| return index_ == o.index_; |
| } |
| inline bool operator!=(const Iterator& o) const { |
| return index_ != o.index_; |
| } |
| |
| private: |
| // For a given index, return the corresponding chunk, down-shifted |
| // such that the given index is the LSB of the chunk. |
| // |
| // In other words, (ChunkAt(index) & 1) is a valid way of checking whether |
| // the bit at 'index' is set. |
| // |
| // If the given index is out of bounds, we don't really have a chunk to |
| // return. This function returns 1, solely to automatically fail the |
| // do-while condition in operator++. (It avoids having special handling of |
| // index > kBits there). |
| uint64_t ChunkAt(size_t index) const { |
| return index < kBits ? chunks_[index / 64] >> (index % 64) : 1ull; |
| } |
| |
| const uint64_t* chunks_; |
| // The current bit index this Iterator is pointing to. Note that this is |
| // the "global" index, i.e. it has the range [0, kBits]. (It is not a local |
| // index with range [0, 64]). |
| // |
| // Never exceeds kBits. |
| size_t index_ = 0; |
| // The iterator works by "pre-fetching" the current chunk (corresponding |
| // (to the current index), and down-shifting by one for every iteration. |
| // This allows the iterator to skip the remainder of the chunk when we |
| // shift away the last bit. |
| uint64_t chunk_ = 0; |
| }; |
| |
| Iterator begin() const { return Iterator(chunks_, FirstIndex()); } |
| Iterator end() const { return Iterator(chunks_, kBits); } |
| |
| private: |
| // Find the first index (i.e. first set bit). If no bits are set, returns |
| // kBits. |
| size_t FirstIndex() const { |
| size_t index = 0; |
| // Skip all empty chunks. |
| while (index < kBits && !chunks_[index / 64]) |
| index += 64; |
| // Within the non-empty chunk, iterate until we find the set bit. |
| while (index < kBits && !(chunks_[index / 64] & (1ull << (index % 64)))) |
| ++index; |
| return std::min(index, kBits); |
| } |
| |
| uint64_t chunks_[kChunks]; |
| }; |
| |
| using CSSBitset = CSSBitsetBase<kNumCSSProperties>; |
| |
| } // namespace blink |
| |
| #endif // THIRD_PARTY_BLINK_RENDERER_CORE_CSS_PROPERTIES_CSS_BITSET_H_ |