2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
24 * This is a utility class to view a region of memory as a vector of bits.
26 * It is the user of this class's responsibility to ensure that the memory used
27 * to construct the view is large enough to contain all the bits that get
28 * addressed through operator[]--this class does not perform any allocation or
31 template <bool is_const
>
33 using char_t
= typename
std::conditional
<is_const
,
38 * A reference wrapper for a particular bit in the bitset--note that this is
39 * larger than a typical pointer since it's a pointer to the byte and a mask
40 * to select the particular bit of interest.
42 struct bit_reference
{
43 bit_reference(char_t
* ptr
, char_t mask
)
47 bit_reference(const bit_reference
& o
)
51 bool operator=(bool b
) {
52 *m_ptr
= (*m_ptr
& ~m_mask
) | (b
? m_mask
: 0);
56 operator bool() const {
57 return *m_ptr
& m_mask
;
60 bool operator!() const {
61 return !(static_cast<bool>(*this));
70 * A forward iterator for the bits in a view
72 * As with the view itself, no bounds-checking is performed--it's the callers
73 * responsibility to make sure that every iterator that is dereferenced
74 * points to valid memory
77 iterator(char_t
* ptr
, char_t mask
)
81 using value_type
= bit_reference
;
82 using reference
= bit_reference
;
84 using difference_type
= void;
85 using iterator_category
= std::forward_iterator_tag
;
87 bool operator==(const iterator
& o
) {
88 return m_ptr
== o
.m_ptr
&& m_mask
== o
.m_mask
;
91 bool operator!=(const iterator
& o
) {
95 bit_reference
operator*() const {
96 return bit_reference
{m_ptr
, m_mask
};
99 bit_reference
operator->() const {
103 iterator
& operator++() {
104 const auto carry
= m_mask
>> (sizeof(char_t
) * 8 - 1);
106 m_mask
= (m_mask
<< 1) | carry
;
110 iterator
operator++(int) {
111 auto const ret
= *this;
118 typename
std::remove_const
<char_t
>::type m_mask
;
122 * Construct a BitsetView starting at the given byte
124 explicit BitsetView(char_t
* buf
) : m_buf(buf
) {}
127 * Return the size (in bytes) for a bitset of the given length
129 static size_t sizeFor(size_t len
) {
130 return (len
+ CHAR_BIT
- 1) / CHAR_BIT
;
134 * Access the bit at the given index in the set
136 bit_reference
operator[](size_t idx
) {
137 auto const chunk
= idx
/ CHAR_BIT
;
138 auto const mask
= static_cast<char_t
>(1 << (idx
% CHAR_BIT
));
139 return bit_reference
{m_buf
+ chunk
, mask
};
142 iterator
iteratorAt(size_t off
) {
143 return iterator
{m_buf
+ off
/ CHAR_BIT
,
144 static_cast<char_t
>(1 << (off
% CHAR_BIT
))};
148 * Access the memory being viewed as a bitset
150 char_t
* buffer() { return m_buf
; }
151 const char_t
* buffer() const { return m_buf
; }