Use PODArray<> in SparseArray<>.
Change-Id: If73915f36fef697985f75ed8530a99ae081c4db9
Reviewed-on: https://code-review.googlesource.com/c/37396
Reviewed-by: Paul Wankadia <[email protected]>
diff --git a/util/sparse_array.h b/util/sparse_array.h
index 73d262a..0c085d5 100644
--- a/util/sparse_array.h
+++ b/util/sparse_array.h
@@ -55,7 +55,7 @@
// IMPLEMENTATION
//
-// SparseArray is an array dense_ and an array sparse_, both of size max_size_.
+// SparseArray is an array dense_ and an array sparse_ of identical size.
// At any point, the number of elements in the sparse array is size_.
//
// The array dense_ contains the size_ elements in the sparse array (with
@@ -95,15 +95,15 @@
#include <assert.h>
#include <stdint.h>
-#include <string.h>
#if __has_feature(memory_sanitizer)
#include <sanitizer/msan_interface.h>
#endif
#include <algorithm>
#include <memory>
-#include <type_traits>
#include <utility>
+#include "util/pod_array.h"
+
namespace re2 {
template<typename Value>
@@ -115,8 +115,6 @@
// IndexValue pairs: exposed in SparseArray::iterator.
class IndexValue;
- static_assert(std::is_trivially_destructible<IndexValue>::value,
- "IndexValue must be trivially destructible");
typedef IndexValue* iterator;
typedef const IndexValue* const_iterator;
@@ -139,17 +137,17 @@
// Iterate over the array.
iterator begin() {
- return dense_.get();
+ return dense_.data();
}
iterator end() {
- return dense_.get() + size_;
+ return dense_.data() + size_;
}
const_iterator begin() const {
- return dense_.get();
+ return dense_.data();
}
const_iterator end() const {
- return dense_.get() + size_;
+ return dense_.data() + size_;
}
// Change the maximum size of the array.
@@ -159,7 +157,7 @@
// Return the maximum size of the array.
// Indices can be in the range [0, max_size).
int max_size() const {
- return max_size_;
+ return dense_.size();
}
// Clear the array.
@@ -208,7 +206,7 @@
private:
iterator SetInternal(bool allow_existing, int i, const Value& v) {
DebugCheckInvariants();
- if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size_)) {
+ if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(dense_.size())) {
assert(false && "illegal index");
// Semantically, end() would be better here, but we already know
// the user did something stupid, so begin() insulates them from
@@ -230,7 +228,7 @@
assert(has_index(i));
dense_[sparse_[i]].value_ = v;
DebugCheckInvariants();
- return dense_.get() + sparse_[i];
+ return dense_.data() + sparse_[i];
}
// Add the index i to the array.
@@ -248,7 +246,7 @@
// Initializes memory for elements [min, max).
void MaybeInitializeMemory(int min, int max) {
#if __has_feature(memory_sanitizer)
- __msan_unpoison(sparse_.get() + min, (max - min) * sizeof sparse_[0]);
+ __msan_unpoison(sparse_.data() + min, (max - min) * sizeof sparse_[0]);
#elif defined(RE2_ON_VALGRIND)
for (int i = min; i < max; i++) {
sparse_[i] = 0xababababU;
@@ -257,9 +255,8 @@
}
int size_ = 0;
- int max_size_ = 0;
- std::unique_ptr<int[]> sparse_;
- std::unique_ptr<IndexValue[]> dense_;
+ PODArray<int> sparse_;
+ PODArray<IndexValue> dense_;
};
template<typename Value>
@@ -268,45 +265,40 @@
template<typename Value>
SparseArray<Value>::SparseArray(const SparseArray& src)
: size_(src.size_),
- max_size_(src.max_size_),
- sparse_(new int[max_size_]),
- dense_(new IndexValue[max_size_]) {
- std::copy_n(src.sparse_.get(), max_size_, sparse_.get());
- std::copy_n(src.dense_.get(), max_size_, dense_.get());
+ sparse_(src.sparse_.size()),
+ dense_(src.dense_.size()) {
+ std::copy_n(src.sparse_.data(), src.sparse_.size(), sparse_.data());
+ std::copy_n(src.dense_.data(), src.dense_.size(), dense_.data());
}
template<typename Value>
SparseArray<Value>::SparseArray(SparseArray&& src)
: size_(src.size_),
- max_size_(src.max_size_),
sparse_(std::move(src.sparse_)),
dense_(std::move(src.dense_)) {
src.size_ = 0;
- src.max_size_ = 0;
}
template<typename Value>
SparseArray<Value>& SparseArray<Value>::operator=(const SparseArray& src) {
+ // Construct these first for exception safety.
+ PODArray<int> a(src.sparse_.size());
+ PODArray<IndexValue> b(src.dense_.size());
+
size_ = src.size_;
- max_size_ = src.max_size_;
- std::unique_ptr<int[]> a(new int[max_size_]);
- std::copy_n(src.sparse_.get(), src.max_size_, a.get());
sparse_ = std::move(a);
- std::unique_ptr<IndexValue[]> b(new IndexValue[max_size_]);
- std::copy_n(src.dense_.get(), src.max_size_, b.get());
dense_ = std::move(b);
+ std::copy_n(src.sparse_.data(), src.sparse_.size(), sparse_.data());
+ std::copy_n(src.dense_.data(), src.dense_.size(), dense_.data());
return *this;
}
template<typename Value>
SparseArray<Value>& SparseArray<Value>::operator=(SparseArray&& src) {
size_ = src.size_;
- max_size_ = src.max_size_;
sparse_ = std::move(src.sparse_);
dense_ = std::move(src.dense_);
- // clear out the source
src.size_ = 0;
- src.max_size_ = 0;
return *this;
}
@@ -329,25 +321,26 @@
template<typename Value>
void SparseArray<Value>::resize(int max_size) {
DebugCheckInvariants();
- if (max_size > max_size_) {
- std::unique_ptr<int[]> a(new int[max_size]);
- if (sparse_) {
- std::copy_n(sparse_.get(), max_size_, a.get());
+ if (max_size > dense_.size()) {
+ const int old_max_size = dense_.size();
+
+ PODArray<int> a(max_size);
+ if (sparse_.data() != NULL) {
+ std::copy_n(sparse_.data(), old_max_size, a.data());
}
- std::unique_ptr<IndexValue[]> b(new IndexValue[max_size]);
- if (dense_) {
- std::copy_n(dense_.get(), max_size_, b.get());
+ PODArray<IndexValue> b(max_size);
+ if (dense_.data() != NULL) {
+ std::copy_n(dense_.data(), old_max_size, b.data());
}
sparse_ = std::move(a);
dense_ = std::move(b);
- MaybeInitializeMemory(max_size_, max_size);
+ MaybeInitializeMemory(old_max_size, max_size);
}
- max_size_ = max_size;
- if (size_ > max_size_)
- size_ = max_size_;
+ if (size_ > max_size)
+ size_ = max_size;
DebugCheckInvariants();
}
@@ -355,8 +348,8 @@
template<typename Value>
bool SparseArray<Value>::has_index(int i) const {
assert(i >= 0);
- assert(i < max_size_);
- if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size_)) {
+ assert(i < dense_.size());
+ if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(dense_.size())) {
return false;
}
// Unsigned comparison avoids checking sparse_[i] < 0.
@@ -367,18 +360,15 @@
template<typename Value>
void SparseArray<Value>::create_index(int i) {
assert(!has_index(i));
- assert(size_ < max_size_);
+ assert(size_ < dense_.size());
sparse_[i] = size_;
dense_[size_].index_ = i;
size_++;
}
-template<typename Value> SparseArray<Value>::SparseArray(int max_size) {
- sparse_.reset(new int[max_size]);
- dense_.reset(new IndexValue[max_size]);
- size_ = 0;
+template<typename Value> SparseArray<Value>::SparseArray(int max_size) :
+ sparse_(max_size), dense_(max_size) {
MaybeInitializeMemory(size_, max_size);
- max_size_ = max_size;
DebugCheckInvariants();
}
@@ -388,8 +378,9 @@
template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const {
assert(0 <= size_);
- assert(size_ <= max_size_);
- assert(size_ == 0 || sparse_ != NULL);
+ assert(size_ <= dense_.size());
+ assert(sparse_.size() == dense_.size());
+ assert(size_ == 0 || dense_.data() != NULL);
}
// Comparison function for sorting.
diff --git a/util/sparse_set.h b/util/sparse_set.h
index 18f616a..6b1a8e5 100644
--- a/util/sparse_set.h
+++ b/util/sparse_set.h
@@ -54,7 +54,6 @@
#include <assert.h>
#include <stdint.h>
-#include <string.h>
#if __has_feature(memory_sanitizer)
#include <sanitizer/msan_interface.h>
#endif
