arrow/util/bitset_stack.h

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017
0018 #pragma once
0019
0020 #include <algorithm>
0021 #include <array>
0022 #include <bitset>
0023 #include <cassert>
0024 #include <cstdint>
0025 #include <cstring>
0026 #include <memory>
0027 #include <string>
0028 #include <string_view>
0029 #include <type_traits>
0030 #include <utility>
0031 #include <vector>
0032
0033 #include "arrow/buffer.h"
0034 #include "arrow/memory_pool.h"
0035 #include "arrow/result.h"
0036 #include "arrow/type_fwd.h"
0037 #include "arrow/util/bit_util.h"
0038 #include "arrow/util/compare.h"
0039 #include "arrow/util/functional.h"
0040 #include "arrow/util/macros.h"
0041 #include "arrow/util/string_builder.h"
0042 #include "arrow/util/type_traits.h"
0043 #include "arrow/util/visibility.h"
0044
0045 namespace arrow {
0046 namespace internal {
0047
0048 /// \brief Store a stack of bitsets efficiently. The top bitset may be
0049 /// accessed and its bits may be modified, but it may not be resized.
0050 class BitsetStack {
0051  public:
0052   using reference = typename std::vector<bool>::reference;
0053
0054   /// \brief push a bitset onto the stack
0055   /// \param size number of bits in the next bitset
0056   /// \param value initial value for bits in the pushed bitset
0057   void Push(int size, bool value) {
0058     offsets_.push_back(bit_count());
0059     bits_.resize(bit_count() + size, value);
0060   }
0061
0062   /// \brief number of bits in the bitset at the top of the stack
0063   int TopSize() const {
0064     if (offsets_.size() == 0) return 0;
0065     return bit_count() - offsets_.back();
0066   }
0067
0068   /// \brief pop a bitset off the stack
0069   void Pop() {
0070     bits_.resize(offsets_.back());
0071     offsets_.pop_back();
0072   }
0073
0074   /// \brief get the value of a bit in the top bitset
0075   /// \param i index of the bit to access
0076   bool operator[](int i) const { return bits_[offsets_.back() + i]; }
0077
0078   /// \brief get a mutable reference to a bit in the top bitset
0079   /// \param i index of the bit to access
0080   reference operator[](int i) { return bits_[offsets_.back() + i]; }
0081
0082  private:
0083   int bit_count() const { return static_cast<int>(bits_.size()); }
0084   std::vector<bool> bits_;
0085   std::vector<int> offsets_;
0086 };
0087
0088 }  // namespace internal
0089 }  // namespace arrow