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