blob: 218203f9e0f1cdbbb0304ca9613e6994812683ef [file] [log] [blame]
David Srbecky052f8ca2018-04-26 15:42:54 +01001/*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_LIBARTBASE_BASE_BIT_TABLE_H_
18#define ART_LIBARTBASE_BASE_BIT_TABLE_H_
19
David Srbeckydd966bc2018-05-24 13:55:52 +010020#include <array>
David Srbeckyf325e282018-06-13 15:02:32 +010021#include <initializer_list>
David Srbeckydd966bc2018-05-24 13:55:52 +010022#include <numeric>
23#include <string.h>
24#include <type_traits>
25#include <unordered_map>
David Srbecky052f8ca2018-04-26 15:42:54 +010026
27#include "base/bit_memory_region.h"
David Srbeckydd966bc2018-05-24 13:55:52 +010028#include "base/casts.h"
David Srbecky93bd3612018-07-02 19:30:18 +010029#include "base/iteration_range.h"
David Srbecky052f8ca2018-04-26 15:42:54 +010030#include "base/memory_region.h"
David Srbeckydd966bc2018-05-24 13:55:52 +010031#include "base/scoped_arena_containers.h"
32#include "base/stl_util.h"
David Srbecky052f8ca2018-04-26 15:42:54 +010033
34namespace art {
35
36constexpr uint32_t kVarintHeaderBits = 4;
37constexpr uint32_t kVarintSmallValue = 11; // Maximum value which is stored as-is.
38
39// Load variable-length bit-packed integer from `data` starting at `bit_offset`.
40// The first four bits determine the variable length of the encoded integer:
41// Values 0..11 represent the result as-is, with no further following bits.
42// Values 12..15 mean the result is in the next 8/16/24/32-bits respectively.
David Srbecky078d7ba2018-06-21 15:36:48 +010043ALWAYS_INLINE static inline uint32_t DecodeVarintBits(BitMemoryReader& reader) {
44 uint32_t x = reader.ReadBits(kVarintHeaderBits);
David Srbecky052f8ca2018-04-26 15:42:54 +010045 if (x > kVarintSmallValue) {
David Srbecky078d7ba2018-06-21 15:36:48 +010046 x = reader.ReadBits((x - kVarintSmallValue) * kBitsPerByte);
David Srbecky052f8ca2018-04-26 15:42:54 +010047 }
48 return x;
49}
50
51// Store variable-length bit-packed integer from `data` starting at `bit_offset`.
52template<typename Vector>
David Srbecky078d7ba2018-06-21 15:36:48 +010053ALWAYS_INLINE static inline void EncodeVarintBits(BitMemoryWriter<Vector>& out, uint32_t value) {
David Srbecky052f8ca2018-04-26 15:42:54 +010054 if (value <= kVarintSmallValue) {
David Srbecky078d7ba2018-06-21 15:36:48 +010055 out.WriteBits(value, kVarintHeaderBits);
David Srbecky052f8ca2018-04-26 15:42:54 +010056 } else {
57 uint32_t num_bits = RoundUp(MinimumBitsToStore(value), kBitsPerByte);
David Srbecky052f8ca2018-04-26 15:42:54 +010058 uint32_t header = kVarintSmallValue + num_bits / kBitsPerByte;
David Srbecky078d7ba2018-06-21 15:36:48 +010059 out.WriteBits(header, kVarintHeaderBits);
60 out.WriteBits(value, num_bits);
David Srbecky052f8ca2018-04-26 15:42:54 +010061 }
62}
63
David Srbeckycf7833e2018-06-14 16:45:22 +010064// Generic purpose table of uint32_t values, which are tightly packed at bit level.
65// It has its own header with the number of rows and the bit-widths of all columns.
66// The values are accessible by (row, column). The value -1 is stored efficiently.
David Srbecky052f8ca2018-04-26 15:42:54 +010067template<uint32_t kNumColumns>
David Srbeckycf7833e2018-06-14 16:45:22 +010068class BitTableBase {
David Srbecky052f8ca2018-04-26 15:42:54 +010069 public:
David Srbeckycf7833e2018-06-14 16:45:22 +010070 static constexpr uint32_t kNoValue = std::numeric_limits<uint32_t>::max(); // == -1.
71 static constexpr uint32_t kValueBias = kNoValue; // Bias so that -1 is encoded as 0.
David Srbecky052f8ca2018-04-26 15:42:54 +010072
David Srbeckycf7833e2018-06-14 16:45:22 +010073 BitTableBase() {}
David Srbecky078d7ba2018-06-21 15:36:48 +010074 explicit BitTableBase(BitMemoryReader& reader) {
75 Decode(reader);
David Srbecky052f8ca2018-04-26 15:42:54 +010076 }
77
David Srbecky078d7ba2018-06-21 15:36:48 +010078 ALWAYS_INLINE void Decode(BitMemoryReader& reader) {
David Srbecky052f8ca2018-04-26 15:42:54 +010079 // Decode row count and column sizes from the table header.
David Srbecky078d7ba2018-06-21 15:36:48 +010080 size_t initial_bit_offset = reader.GetBitOffset();
81 num_rows_ = DecodeVarintBits(reader);
David Srbecky052f8ca2018-04-26 15:42:54 +010082 if (num_rows_ != 0) {
83 column_offset_[0] = 0;
84 for (uint32_t i = 0; i < kNumColumns; i++) {
David Srbecky078d7ba2018-06-21 15:36:48 +010085 size_t column_end = column_offset_[i] + DecodeVarintBits(reader);
David Srbeckydd966bc2018-05-24 13:55:52 +010086 column_offset_[i + 1] = dchecked_integral_cast<uint16_t>(column_end);
David Srbecky052f8ca2018-04-26 15:42:54 +010087 }
88 }
David Srbecky078d7ba2018-06-21 15:36:48 +010089 header_bit_size_ = reader.GetBitOffset() - initial_bit_offset;
David Srbecky052f8ca2018-04-26 15:42:54 +010090
91 // Record the region which contains the table data and skip past it.
David Srbecky078d7ba2018-06-21 15:36:48 +010092 table_data_ = reader.Skip(num_rows_ * NumRowBits());
David Srbecky052f8ca2018-04-26 15:42:54 +010093 }
94
95 ALWAYS_INLINE uint32_t Get(uint32_t row, uint32_t column = 0) const {
96 DCHECK_LT(row, num_rows_);
97 DCHECK_LT(column, kNumColumns);
98 size_t offset = row * NumRowBits() + column_offset_[column];
99 return table_data_.LoadBits(offset, NumColumnBits(column)) + kValueBias;
100 }
101
David Srbecky5513c2b2018-05-24 15:03:20 +0100102 ALWAYS_INLINE BitMemoryRegion GetBitMemoryRegion(uint32_t row, uint32_t column = 0) const {
103 DCHECK_LT(row, num_rows_);
104 DCHECK_LT(column, kNumColumns);
105 size_t offset = row * NumRowBits() + column_offset_[column];
106 return table_data_.Subregion(offset, NumColumnBits(column));
107 }
108
David Srbecky052f8ca2018-04-26 15:42:54 +0100109 size_t NumRows() const { return num_rows_; }
110
111 uint32_t NumRowBits() const { return column_offset_[kNumColumns]; }
112
113 constexpr size_t NumColumns() const { return kNumColumns; }
114
115 uint32_t NumColumnBits(uint32_t column) const {
116 return column_offset_[column + 1] - column_offset_[column];
117 }
118
David Srbecky86decb62018-06-05 06:41:10 +0100119 size_t HeaderBitSize() const { return header_bit_size_; }
David Srbeckycf7833e2018-06-14 16:45:22 +0100120
David Srbecky86decb62018-06-05 06:41:10 +0100121 size_t BitSize() const { return header_bit_size_ + table_data_.size_in_bits(); }
David Srbecky052f8ca2018-04-26 15:42:54 +0100122
123 protected:
124 BitMemoryRegion table_data_;
125 size_t num_rows_ = 0;
126
127 uint16_t column_offset_[kNumColumns + 1] = {};
David Srbecky86decb62018-06-05 06:41:10 +0100128 uint16_t header_bit_size_ = 0;
David Srbecky052f8ca2018-04-26 15:42:54 +0100129};
130
David Srbeckycf7833e2018-06-14 16:45:22 +0100131// Helper class which can be used to create BitTable accessors with named getters.
132template<uint32_t NumColumns>
133class BitTableAccessor {
134 public:
135 static constexpr uint32_t kNumColumns = NumColumns;
136 static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue;
137
David Srbeckycf7833e2018-06-14 16:45:22 +0100138 BitTableAccessor(const BitTableBase<kNumColumns>* table, uint32_t row)
139 : table_(table), row_(row) {
David Srbeckya45a85c2018-06-21 16:03:12 +0100140 DCHECK(table_ != nullptr);
David Srbeckycf7833e2018-06-14 16:45:22 +0100141 }
142
143 ALWAYS_INLINE uint32_t Row() const { return row_; }
144
David Srbeckya45a85c2018-06-21 16:03:12 +0100145 ALWAYS_INLINE bool IsValid() const { return row_ < table_->NumRows(); }
David Srbeckycf7833e2018-06-14 16:45:22 +0100146
147 ALWAYS_INLINE bool Equals(const BitTableAccessor& other) {
148 return this->table_ == other.table_ && this->row_ == other.row_;
149 }
150
151// Helper macro to create constructors and per-table utilities in derived class.
152#define BIT_TABLE_HEADER() \
153 using BitTableAccessor<kNumColumns>::BitTableAccessor; /* inherit constructors */ \
154 template<int COLUMN, int UNUSED /*needed to compile*/> struct ColumnName; \
155
156// Helper macro to create named column accessors in derived class.
157#define BIT_TABLE_COLUMN(COLUMN, NAME) \
158 static constexpr uint32_t k##NAME = COLUMN; \
159 ALWAYS_INLINE uint32_t Get##NAME() const { return table_->Get(row_, COLUMN); } \
160 ALWAYS_INLINE bool Has##NAME() const { return Get##NAME() != kNoValue; } \
161 template<int UNUSED> struct ColumnName<COLUMN, UNUSED> { \
162 static constexpr const char* Value = #NAME; \
163 }; \
164
165 protected:
166 const BitTableBase<kNumColumns>* table_ = nullptr;
167 uint32_t row_ = -1;
168};
169
David Srbeckyd97e0822018-06-03 12:00:24 +0100170// Template meta-programming helper.
171template<typename Accessor, size_t... Columns>
David Srbecky86decb62018-06-05 06:41:10 +0100172static const char* const* GetBitTableColumnNamesImpl(std::index_sequence<Columns...>) {
David Srbeckyd97e0822018-06-03 12:00:24 +0100173 static const char* names[] = { Accessor::template ColumnName<Columns, 0>::Value... };
174 return names;
175}
David Srbecky052f8ca2018-04-26 15:42:54 +0100176
David Srbeckycf7833e2018-06-14 16:45:22 +0100177// Returns the names of all columns in the given accessor.
David Srbeckyd97e0822018-06-03 12:00:24 +0100178template<typename Accessor>
David Srbecky86decb62018-06-05 06:41:10 +0100179static const char* const* GetBitTableColumnNames() {
David Srbeckycf7833e2018-06-14 16:45:22 +0100180 return GetBitTableColumnNamesImpl<Accessor>(std::make_index_sequence<Accessor::kNumColumns>());
David Srbeckyd97e0822018-06-03 12:00:24 +0100181}
David Srbecky052f8ca2018-04-26 15:42:54 +0100182
David Srbeckycf7833e2018-06-14 16:45:22 +0100183// Wrapper which makes it easier to use named accessors for the individual rows.
184template<typename Accessor>
185class BitTable : public BitTableBase<Accessor::kNumColumns> {
186 public:
David Srbecky0b4e5a32018-06-11 16:25:29 +0100187 class const_iterator : public std::iterator<std::random_access_iterator_tag,
188 /* value_type */ Accessor,
189 /* difference_type */ int32_t,
190 /* pointer */ void,
191 /* reference */ void> {
192 public:
193 using difference_type = int32_t;
194 const_iterator() {}
195 const_iterator(const BitTable* table, uint32_t row) : table_(table), row_(row) {}
196 const_iterator operator+(difference_type n) { return const_iterator(table_, row_ + n); }
197 const_iterator operator-(difference_type n) { return const_iterator(table_, row_ - n); }
198 difference_type operator-(const const_iterator& other) { return row_ - other.row_; }
199 void operator+=(difference_type rows) { row_ += rows; }
200 void operator-=(difference_type rows) { row_ -= rows; }
201 const_iterator operator++() { return const_iterator(table_, ++row_); }
202 const_iterator operator--() { return const_iterator(table_, --row_); }
203 const_iterator operator++(int) { return const_iterator(table_, row_++); }
204 const_iterator operator--(int) { return const_iterator(table_, row_--); }
205 bool operator==(const_iterator i) const { DCHECK(table_ == i.table_); return row_ == i.row_; }
206 bool operator!=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ != i.row_; }
207 bool operator<=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ <= i.row_; }
208 bool operator>=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ >= i.row_; }
209 bool operator<(const_iterator i) const { DCHECK(table_ == i.table_); return row_ < i.row_; }
210 bool operator>(const_iterator i) const { DCHECK(table_ == i.table_); return row_ > i.row_; }
David Srbecky93bd3612018-07-02 19:30:18 +0100211 Accessor operator*() {
212 DCHECK_LT(row_, table_->NumRows());
213 return Accessor(table_, row_);
214 }
215 Accessor operator->() {
216 DCHECK_LT(row_, table_->NumRows());
217 return Accessor(table_, row_);
218 }
219 Accessor operator[](size_t index) {
220 DCHECK_LT(row_ + index, table_->NumRows());
221 return Accessor(table_, row_ + index);
222 }
David Srbecky0b4e5a32018-06-11 16:25:29 +0100223 private:
224 const BitTable* table_ = nullptr;
225 uint32_t row_ = 0;
226 };
227
David Srbeckycf7833e2018-06-14 16:45:22 +0100228 using BitTableBase<Accessor::kNumColumns>::BitTableBase; // Constructors.
229
David Srbecky0b4e5a32018-06-11 16:25:29 +0100230 ALWAYS_INLINE const_iterator begin() const { return const_iterator(this, 0); }
231 ALWAYS_INLINE const_iterator end() const { return const_iterator(this, this->NumRows()); }
232
David Srbeckycf7833e2018-06-14 16:45:22 +0100233 ALWAYS_INLINE Accessor GetRow(uint32_t row) const {
234 return Accessor(this, row);
235 }
David Srbeckya45a85c2018-06-21 16:03:12 +0100236
237 ALWAYS_INLINE Accessor GetInvalidRow() const {
238 return Accessor(this, static_cast<uint32_t>(-1));
239 }
David Srbeckycf7833e2018-06-14 16:45:22 +0100240};
241
David Srbecky0b4e5a32018-06-11 16:25:29 +0100242template<typename Accessor>
243typename BitTable<Accessor>::const_iterator operator+(
244 typename BitTable<Accessor>::const_iterator::difference_type n,
245 typename BitTable<Accessor>::const_iterator a) {
246 return a + n;
247}
248
David Srbecky93bd3612018-07-02 19:30:18 +0100249template<typename Accessor>
250class BitTableRange : public IterationRange<typename BitTable<Accessor>::const_iterator> {
251 public:
252 typedef typename BitTable<Accessor>::const_iterator const_iterator;
253
254 using IterationRange<const_iterator>::IterationRange;
255 BitTableRange() : IterationRange<const_iterator>(const_iterator(), const_iterator()) { }
256
257 bool empty() const { return this->begin() == this->end(); }
258 size_t size() const { return this->end() - this->begin(); }
259
260 Accessor operator[](size_t index) const {
261 const_iterator it = this->begin() + index;
262 DCHECK(it < this->end());
263 return *it;
264 }
265
266 Accessor back() const {
267 DCHECK(!empty());
268 return *(this->end() - 1);
269 }
270
271 void pop_back() {
272 DCHECK(!empty());
273 --this->last_;
274 }
275};
276
David Srbeckydd966bc2018-05-24 13:55:52 +0100277// Helper class for encoding BitTable. It can optionally de-duplicate the inputs.
David Srbeckyf325e282018-06-13 15:02:32 +0100278template<uint32_t kNumColumns>
David Srbeckycf7833e2018-06-14 16:45:22 +0100279class BitTableBuilderBase {
David Srbecky052f8ca2018-04-26 15:42:54 +0100280 public:
David Srbeckycf7833e2018-06-14 16:45:22 +0100281 static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue;
282 static constexpr uint32_t kValueBias = BitTableBase<kNumColumns>::kValueBias;
283
David Srbeckyf325e282018-06-13 15:02:32 +0100284 class Entry {
285 public:
286 Entry() {
David Srbeckycf7833e2018-06-14 16:45:22 +0100287 std::fill_n(data_, kNumColumns, kNoValue);
David Srbeckyf325e282018-06-13 15:02:32 +0100288 }
289
290 Entry(std::initializer_list<uint32_t> values) {
291 DCHECK_EQ(values.size(), kNumColumns);
292 std::copy(values.begin(), values.end(), data_);
293 }
294
295 uint32_t& operator[](size_t column) {
296 DCHECK_LT(column, kNumColumns);
297 return data_[column];
298 }
299
300 uint32_t operator[](size_t column) const {
301 DCHECK_LT(column, kNumColumns);
302 return data_[column];
303 }
304
305 private:
306 uint32_t data_[kNumColumns];
307 };
David Srbecky052f8ca2018-04-26 15:42:54 +0100308
David Srbeckycf7833e2018-06-14 16:45:22 +0100309 explicit BitTableBuilderBase(ScopedArenaAllocator* allocator)
David Srbecky159c9dd2018-05-24 14:56:51 +0100310 : rows_(allocator->Adapter(kArenaAllocBitTableBuilder)),
311 dedup_(8, allocator->Adapter(kArenaAllocBitTableBuilder)) {
David Srbeckydd966bc2018-05-24 13:55:52 +0100312 }
313
David Srbeckyf325e282018-06-13 15:02:32 +0100314 Entry& operator[](size_t row) { return rows_[row]; }
315 const Entry& operator[](size_t row) const { return rows_[row]; }
David Srbecky0b4e5a32018-06-11 16:25:29 +0100316 const Entry& back() const { return rows_.back(); }
David Srbeckydd966bc2018-05-24 13:55:52 +0100317 size_t size() const { return rows_.size(); }
318
David Srbecky159c9dd2018-05-24 14:56:51 +0100319 // Append given value to the vector without de-duplication.
320 // This will not add the element to the dedup map to avoid its associated costs.
David Srbeckyf325e282018-06-13 15:02:32 +0100321 void Add(Entry value) {
David Srbeckydd966bc2018-05-24 13:55:52 +0100322 rows_.push_back(value);
David Srbecky052f8ca2018-04-26 15:42:54 +0100323 }
324
David Srbecky159c9dd2018-05-24 14:56:51 +0100325 // Append given list of values and return the index of the first value.
326 // If the exact same set of values was already added, return the old index.
David Srbeckyf325e282018-06-13 15:02:32 +0100327 uint32_t Dedup(Entry* values, size_t count = 1) {
David Srbecky159c9dd2018-05-24 14:56:51 +0100328 FNVHash<MemoryRegion> hasher;
David Srbeckyf325e282018-06-13 15:02:32 +0100329 uint32_t hash = hasher(MemoryRegion(values, sizeof(Entry) * count));
David Srbecky159c9dd2018-05-24 14:56:51 +0100330
331 // Check if we have already added identical set of values.
332 auto range = dedup_.equal_range(hash);
333 for (auto it = range.first; it != range.second; ++it) {
334 uint32_t index = it->second;
335 if (count <= size() - index &&
336 std::equal(values,
337 values + count,
David Srbecky5f937102018-06-02 10:24:25 +0100338 rows_.begin() + index,
David Srbeckyf325e282018-06-13 15:02:32 +0100339 [](const Entry& lhs, const Entry& rhs) {
340 return memcmp(&lhs, &rhs, sizeof(Entry)) == 0;
David Srbecky159c9dd2018-05-24 14:56:51 +0100341 })) {
342 return index;
343 }
344 }
345
346 // Add the set of values and add the index to the dedup map.
347 uint32_t index = size();
348 rows_.insert(rows_.end(), values, values + count);
349 dedup_.emplace(hash, index);
350 return index;
351 }
352
David Srbeckyf325e282018-06-13 15:02:32 +0100353 uint32_t Dedup(Entry value) {
354 return Dedup(&value, /* count */ 1);
David Srbecky052f8ca2018-04-26 15:42:54 +0100355 }
356
David Srbeckydd966bc2018-05-24 13:55:52 +0100357 // Calculate the column bit widths based on the current data.
358 void Measure(/*out*/ std::array<uint32_t, kNumColumns>* column_bits) const {
359 uint32_t max_column_value[kNumColumns];
360 std::fill_n(max_column_value, kNumColumns, 0);
361 for (uint32_t r = 0; r < size(); r++) {
362 for (uint32_t c = 0; c < kNumColumns; c++) {
David Srbeckycf7833e2018-06-14 16:45:22 +0100363 max_column_value[c] |= rows_[r][c] - kValueBias;
David Srbeckydd966bc2018-05-24 13:55:52 +0100364 }
365 }
366 for (uint32_t c = 0; c < kNumColumns; c++) {
367 (*column_bits)[c] = MinimumBitsToStore(max_column_value[c]);
368 }
369 }
370
371 // Encode the stored data into a BitTable.
David Srbecky052f8ca2018-04-26 15:42:54 +0100372 template<typename Vector>
David Srbecky078d7ba2018-06-21 15:36:48 +0100373 void Encode(BitMemoryWriter<Vector>& out) const {
374 size_t initial_bit_offset = out.GetBitOffset();
David Srbeckydd966bc2018-05-24 13:55:52 +0100375
376 std::array<uint32_t, kNumColumns> column_bits;
377 Measure(&column_bits);
David Srbecky078d7ba2018-06-21 15:36:48 +0100378 EncodeVarintBits(out, size());
David Srbeckydd966bc2018-05-24 13:55:52 +0100379 if (size() != 0) {
380 // Write table header.
David Srbecky052f8ca2018-04-26 15:42:54 +0100381 for (uint32_t c = 0; c < kNumColumns; c++) {
David Srbecky078d7ba2018-06-21 15:36:48 +0100382 EncodeVarintBits(out, column_bits[c]);
David Srbeckydd966bc2018-05-24 13:55:52 +0100383 }
384
385 // Write table data.
David Srbeckydd966bc2018-05-24 13:55:52 +0100386 for (uint32_t r = 0; r < size(); r++) {
387 for (uint32_t c = 0; c < kNumColumns; c++) {
David Srbecky078d7ba2018-06-21 15:36:48 +0100388 out.WriteBits(rows_[r][c] - kValueBias, column_bits[c]);
David Srbeckydd966bc2018-05-24 13:55:52 +0100389 }
David Srbecky052f8ca2018-04-26 15:42:54 +0100390 }
391 }
David Srbeckydd966bc2018-05-24 13:55:52 +0100392
David Srbecky052f8ca2018-04-26 15:42:54 +0100393 // Verify the written data.
394 if (kIsDebugBuild) {
David Srbeckycf7833e2018-06-14 16:45:22 +0100395 BitTableBase<kNumColumns> table;
David Srbeckya38e6cf2018-06-26 18:13:49 +0100396 BitMemoryReader reader(out.data(), initial_bit_offset);
David Srbecky078d7ba2018-06-21 15:36:48 +0100397 table.Decode(reader);
David Srbeckydd966bc2018-05-24 13:55:52 +0100398 DCHECK_EQ(size(), table.NumRows());
David Srbecky052f8ca2018-04-26 15:42:54 +0100399 for (uint32_t c = 0; c < kNumColumns; c++) {
400 DCHECK_EQ(column_bits[c], table.NumColumnBits(c));
401 }
David Srbeckydd966bc2018-05-24 13:55:52 +0100402 for (uint32_t r = 0; r < size(); r++) {
David Srbecky052f8ca2018-04-26 15:42:54 +0100403 for (uint32_t c = 0; c < kNumColumns; c++) {
David Srbeckyf325e282018-06-13 15:02:32 +0100404 DCHECK_EQ(rows_[r][c], table.Get(r, c)) << " (" << r << ", " << c << ")";
David Srbecky052f8ca2018-04-26 15:42:54 +0100405 }
406 }
407 }
408 }
409
410 protected:
David Srbeckyf325e282018-06-13 15:02:32 +0100411 ScopedArenaDeque<Entry> rows_;
David Srbecky159c9dd2018-05-24 14:56:51 +0100412 ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index.
David Srbecky052f8ca2018-04-26 15:42:54 +0100413};
414
David Srbeckycf7833e2018-06-14 16:45:22 +0100415template<typename Accessor>
416class BitTableBuilder : public BitTableBuilderBase<Accessor::kNumColumns> {
417 public:
418 using BitTableBuilderBase<Accessor::kNumColumns>::BitTableBuilderBase; // Constructors.
419};
420
David Srbecky5513c2b2018-05-24 15:03:20 +0100421// Helper class for encoding single-column BitTable of bitmaps (allows more than 32 bits).
422class BitmapTableBuilder {
423 public:
424 explicit BitmapTableBuilder(ScopedArenaAllocator* const allocator)
425 : allocator_(allocator),
426 rows_(allocator->Adapter(kArenaAllocBitTableBuilder)),
427 dedup_(8, allocator_->Adapter(kArenaAllocBitTableBuilder)) {
428 }
429
430 MemoryRegion operator[](size_t row) { return rows_[row]; }
431 const MemoryRegion operator[](size_t row) const { return rows_[row]; }
432 size_t size() const { return rows_.size(); }
433
434 // Add the given bitmap to the table and return its index.
435 // If the bitmap was already added it will be deduplicated.
436 // The last bit must be set and any padding bits in the last byte must be zero.
437 uint32_t Dedup(const void* bitmap, size_t num_bits) {
438 MemoryRegion region(const_cast<void*>(bitmap), BitsToBytesRoundUp(num_bits));
439 DCHECK(num_bits == 0 || BitMemoryRegion(region).LoadBit(num_bits - 1) == 1);
440 DCHECK_EQ(BitMemoryRegion(region).LoadBits(num_bits, region.size_in_bits() - num_bits), 0u);
441 FNVHash<MemoryRegion> hasher;
442 uint32_t hash = hasher(region);
443
444 // Check if we have already added identical bitmap.
445 auto range = dedup_.equal_range(hash);
446 for (auto it = range.first; it != range.second; ++it) {
447 if (MemoryRegion::ContentEquals()(region, rows_[it->second])) {
448 return it->second;
449 }
450 }
451
452 // Add the bitmap and add the index to the dedup map.
453 uint32_t index = size();
454 void* copy = allocator_->Alloc(region.size(), kArenaAllocBitTableBuilder);
455 memcpy(copy, region.pointer(), region.size());
456 rows_.push_back(MemoryRegion(copy, region.size()));
457 dedup_.emplace(hash, index);
458 max_num_bits_ = std::max(max_num_bits_, num_bits);
459 return index;
460 }
461
462 // Encode the stored data into a BitTable.
463 template<typename Vector>
David Srbecky078d7ba2018-06-21 15:36:48 +0100464 void Encode(BitMemoryWriter<Vector>& out) const {
465 size_t initial_bit_offset = out.GetBitOffset();
David Srbecky5513c2b2018-05-24 15:03:20 +0100466
David Srbecky078d7ba2018-06-21 15:36:48 +0100467 EncodeVarintBits(out, size());
David Srbecky5513c2b2018-05-24 15:03:20 +0100468 if (size() != 0) {
David Srbecky078d7ba2018-06-21 15:36:48 +0100469 EncodeVarintBits(out, max_num_bits_);
David Srbecky5513c2b2018-05-24 15:03:20 +0100470
471 // Write table data.
David Srbecky5513c2b2018-05-24 15:03:20 +0100472 for (MemoryRegion row : rows_) {
473 BitMemoryRegion src(row);
David Srbecky078d7ba2018-06-21 15:36:48 +0100474 BitMemoryRegion dst = out.Allocate(max_num_bits_);
475 dst.StoreBits(/* bit_offset */ 0, src, std::min(max_num_bits_, src.size_in_bits()));
David Srbecky5513c2b2018-05-24 15:03:20 +0100476 }
477 }
478
479 // Verify the written data.
480 if (kIsDebugBuild) {
David Srbeckycf7833e2018-06-14 16:45:22 +0100481 BitTableBase<1> table;
David Srbeckya38e6cf2018-06-26 18:13:49 +0100482 BitMemoryReader reader(out.data(), initial_bit_offset);
David Srbecky078d7ba2018-06-21 15:36:48 +0100483 table.Decode(reader);
David Srbecky5513c2b2018-05-24 15:03:20 +0100484 DCHECK_EQ(size(), table.NumRows());
485 DCHECK_EQ(max_num_bits_, table.NumColumnBits(0));
486 for (uint32_t r = 0; r < size(); r++) {
487 BitMemoryRegion expected(rows_[r]);
488 BitMemoryRegion seen = table.GetBitMemoryRegion(r);
489 size_t num_bits = std::max(expected.size_in_bits(), seen.size_in_bits());
490 for (size_t b = 0; b < num_bits; b++) {
491 bool e = b < expected.size_in_bits() && expected.LoadBit(b);
492 bool s = b < seen.size_in_bits() && seen.LoadBit(b);
493 DCHECK_EQ(e, s) << " (" << r << ")[" << b << "]";
494 }
495 }
496 }
497 }
498
499 private:
500 ScopedArenaAllocator* const allocator_;
501 ScopedArenaDeque<MemoryRegion> rows_;
502 ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index.
503 size_t max_num_bits_ = 0u;
504};
505
David Srbecky052f8ca2018-04-26 15:42:54 +0100506} // namespace art
507
508#endif // ART_LIBARTBASE_BASE_BIT_TABLE_H_