blob: 1bd280a344ebdc9710f642ed00f8bd9b3e646eb7 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#pragma clang system_header
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements. See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership. The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the License for the
// specific language governing permissions and limitations
// under the License.
#pragma once
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <memory>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/buffer.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/memory_pool.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/result.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/type_fwd.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/bit_util.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/compare.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/functional.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/macros.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/string_builder.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/type_traits.h"
#include "contrib/libs/apache/arrow_next/cpp/src/arrow/util/visibility.h"
namespace arrow20 {
namespace internal {
/// \brief Store a stack of bitsets efficiently. The top bitset may be
/// accessed and its bits may be modified, but it may not be resized.
class BitsetStack {
public:
using reference = typename std::vector<bool>::reference;
/// \brief push a bitset onto the stack
/// \param size number of bits in the next bitset
/// \param value initial value for bits in the pushed bitset
void Push(int size, bool value) {
offsets_.push_back(bit_count());
bits_.resize(bit_count() + size, value);
}
/// \brief number of bits in the bitset at the top of the stack
int TopSize() const {
if (offsets_.size() == 0) return 0;
return bit_count() - offsets_.back();
}
/// \brief pop a bitset off the stack
void Pop() {
bits_.resize(offsets_.back());
offsets_.pop_back();
}
/// \brief get the value of a bit in the top bitset
/// \param i index of the bit to access
bool operator[](int i) const { return bits_[offsets_.back() + i]; }
/// \brief get a mutable reference to a bit in the top bitset
/// \param i index of the bit to access
reference operator[](int i) { return bits_[offsets_.back() + i]; }
private:
int bit_count() const { return static_cast<int>(bits_.size()); }
std::vector<bool> bits_;
std::vector<int> offsets_;
};
} // namespace internal
} // namespace arrow20
|
