1 // Copyright 2019 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 #ifndef UTIL_YET_ANOTHER_BIT_VECTOR_H_ 6 #define UTIL_YET_ANOTHER_BIT_VECTOR_H_ 7 8 #include <stdint.h> 9 10 #include <limits> 11 12 namespace openscreen { 13 14 // This is yet another bit vector implementation. Unlike the ones found in the 15 // standard library, this one provides useful functionality (find first bit set, 16 // count number of bits set, shift right) as well as efficiency. 17 // 18 // Storage details: The vector must be explicitly sized (when constructed or 19 // Resize()'ed). There is no dynamic resizing via a push_back()-like operation. 20 // Storage is determined based on the size specified by the user: either one 21 // 64-bit integer stored within the class structure (for all sizes <= 64), or a 22 // heap-allocated array of multiple 64-bit integers. 23 class YetAnotherBitVector { 24 public: 25 enum Fill : bool { SET = true, CLEARED = false }; 26 27 // Constructs an empty bit vector. 28 YetAnotherBitVector(); 29 30 // Constructs a bit vector having the given |size| and all bits set/cleared. 31 YetAnotherBitVector(int size, Fill fill); 32 33 ~YetAnotherBitVector(); 34 35 YetAnotherBitVector(YetAnotherBitVector&& other); 36 YetAnotherBitVector& operator=(YetAnotherBitVector&& other); 37 38 // Not Implemented: Conceptually, there's no reason to prohibit copying these 39 // objects. Implement it if you need it. :) 40 YetAnotherBitVector(const YetAnotherBitVector& other) = delete; 41 YetAnotherBitVector& operator=(const YetAnotherBitVector& other) = delete; 42 size()43 int size() const { return size_; } 44 45 // Query/Set/Clear a single bit at the given |pos|. 46 bool IsSet(int pos) const; 47 void Set(int pos); 48 void Clear(int pos); 49 50 // Resize the bit vector and set/clear all the bits according to |fill|. 51 void Resize(int new_size, Fill fill); 52 53 // Sets/Clears all bits. 54 void SetAll(); 55 void ClearAll(); 56 57 // Shift all bits right by some number of |steps|, zero-padding the leftmost 58 // bits. |steps| must be between zero and |size()|. 59 void ShiftRight(int steps); 60 61 // Returns the position of the first bit set, or |size()| if no bits are set. 62 int FindFirstSet() const; 63 64 // Returns how many of the bits are set in the range [begin, end). 65 int CountBitsSet(int begin, int end) const; 66 67 private: using_array_storage()68 bool using_array_storage() const { return size_ > kBitsPerInteger; } 69 70 // Returns the number of integers required to store |size_| bits. array_size()71 int array_size() const { 72 // The math here is: CEIL(size_ ÷ kBitsPerInteger). 73 return (size_ + kBitsPerInteger - 1) / kBitsPerInteger; 74 } 75 76 // Helper to create array storage (only if necessary) and initialize all the 77 // bits based on the given |fill|. Precondition: Any prior heap-allocated 78 // array storage has already been deallocated. 79 void InitializeForNewSize(int new_size, Fill fill); 80 81 // Helper to find the integer that contains the bit at the given position, and 82 // updates |pos| to the offset of the bit within the integer. 83 const uint64_t* Select(int* pos) const; 84 85 // Total number of bits. 86 int size_; 87 88 // Either store one integer's worth of bits inline, or all are stored in a 89 // separate heap-allocated array. The using_array_storage() method is used to 90 // determine which. 91 union { 92 uint64_t as_integer; 93 uint64_t* as_array; 94 } bits_; 95 96 static constexpr int kBitsPerInteger = std::numeric_limits<uint64_t>::digits; 97 static constexpr uint64_t kAllBitsSet = std::numeric_limits<uint64_t>::max(); 98 static constexpr uint64_t kNoBitsSet = 0; 99 }; 100 101 } // namespace openscreen 102 103 #endif // UTIL_YET_ANOTHER_BIT_VECTOR_H_ 104