[tint] Support iteration while adding to BlockAllocator
Remove reverse iterators - they weren't used, and looked broken.
Bug: chromium:1487321, oss-fuzz:62750
Change-Id: I05c19ee3ea1233bab07890254d3a9b01c3eb2be0
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/153981
Reviewed-by: James Price <jrprice@google.com>
Auto-Submit: Ben Clayton <bclayton@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
Commit-Queue: James Price <jrprice@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
diff --git a/src/tint/utils/memory/block_allocator.h b/src/tint/utils/memory/block_allocator.h
index 2ee1296..978950a 100644
--- a/src/tint/utils/memory/block_allocator.h
+++ b/src/tint/utils/memory/block_allocator.h
@@ -40,6 +40,7 @@
std::array<T*, kMax> ptrs;
Pointers* next;
Pointers* prev;
+ size_t count;
};
/// Block is linked list of memory blocks.
@@ -48,7 +49,7 @@
/// Note: We're not using std::aligned_storage here as this warns / errors on MSVC.
struct alignas(BLOCK_ALIGNMENT) Block {
uint8_t data[BLOCK_SIZE];
- Block* next;
+ Block* next = nullptr;
};
// Forward declaration
@@ -56,7 +57,7 @@
class TView;
/// An iterator for the objects owned by the BlockAllocator.
- template <bool IS_CONST, bool FORWARD>
+ template <bool IS_CONST>
class TIterator {
using PointerTy = std::conditional_t<IS_CONST, const T*, T*>;
@@ -76,10 +77,12 @@
/// Progress the iterator forward one element
/// @returns this iterator
TIterator& operator++() {
- if (FORWARD) {
- ProgressForward();
- } else {
- ProgressBackwards();
+ if (ptrs != nullptr) {
+ ++idx;
+ if (idx >= ptrs->count) {
+ idx = 0;
+ ptrs = ptrs->next;
+ }
}
return *this;
}
@@ -87,44 +90,27 @@
/// Progress the iterator backwards one element
/// @returns this iterator
TIterator& operator--() {
- if (FORWARD) {
- ProgressBackwards();
- } else {
- ProgressForward();
+ if (ptrs != nullptr) {
+ if (idx == 0) {
+ ptrs = ptrs->prev;
+ idx = ptrs->count - 1;
+ }
+ --idx;
}
return *this;
}
/// @returns the pointer to the object at the current iterator position
- PointerTy operator*() const { return ptrs ? ptrs->ptrs[idx] : nullptr; }
+ PointerTy operator*() const { return ptrs->ptrs[idx]; }
private:
friend TView<IS_CONST>; // Keep internal iterator impl private.
explicit TIterator(const Pointers* p, size_t i) : ptrs(p), idx(i) {}
- /// Progresses the iterator forwards
- void ProgressForward() {
- if (ptrs != nullptr) {
- ++idx;
- if (idx == Pointers::kMax) {
- idx = 0;
- ptrs = ptrs->next;
- }
- }
- }
- /// Progresses the iterator backwards
- void ProgressBackwards() {
- if (ptrs != nullptr) {
- if (idx == 0) {
- idx = Pointers::kMax - 1;
- ptrs = ptrs->prev;
- }
- --idx;
- }
- }
-
- const Pointers* ptrs;
- size_t idx;
+ /// The current Pointers
+ const Pointers* ptrs = nullptr;
+ /// The current index within #ptrs
+ size_t idx = 0;
};
/// View provides begin() and end() methods for looping over the objects owned by the
@@ -133,26 +119,12 @@
class TView {
public:
/// @returns an iterator to the beginning of the view
- TIterator<IS_CONST, true> begin() const {
- return TIterator<IS_CONST, true>{allocator_->data.pointers.root, 0};
+ TIterator<IS_CONST> begin() const {
+ return TIterator<IS_CONST>{allocator_->data.pointers.root, 0};
}
/// @returns an iterator to the end of the view
- TIterator<IS_CONST, true> end() const {
- return allocator_->data.pointers.current_index >= Pointers::kMax
- ? TIterator<IS_CONST, true>{nullptr, 0}
- : TIterator<IS_CONST, true>{allocator_->data.pointers.current,
- allocator_->data.pointers.current_index};
- }
-
- /// @returns an iterator to the beginning of the view
- TIterator<IS_CONST, false> rbegin() const { return TIterator<IS_CONST, false>{nullptr, 0}; }
-
- /// @returns an iterator to the end of the view
- TIterator<IS_CONST, false> rend() const {
- return TIterator<IS_CONST, false>{allocator_->data.pointers.current,
- allocator_->data.pointers.current_index};
- }
+ TIterator<IS_CONST> end() const { return TIterator<IS_CONST>{nullptr, 0}; }
private:
friend BlockAllocator; // For BlockAllocator::operator View()
@@ -162,16 +134,10 @@
public:
/// A forward-iterator type over the objects of the BlockAllocator
- using Iterator = TIterator</* const */ false, /* forward */ true>;
+ using Iterator = TIterator</* const */ false>;
/// An immutable forward-iterator type over the objects of the BlockAllocator
- using ConstIterator = TIterator</* const */ true, /* forward */ true>;
-
- /// A reverse-iterator type over the objects of the BlockAllocator
- using ReverseIterator = TIterator</* const */ false, /* forward */ false>;
-
- /// An immutable reverse-iterator type over the objects of the BlockAllocator
- using ReverseConstIterator = TIterator</* const */ true, /* forward */ false>;
+ using ConstIterator = TIterator</* const */ true>;
/// View provides begin() and end() methods for looping over the objects owned by the
/// BlockAllocator.
@@ -287,7 +253,7 @@
void AddObjectPointer(T* ptr) {
auto& pointers = data.pointers;
- if (pointers.current_index >= Pointers::kMax) {
+ if (!pointers.current || pointers.current->count == Pointers::kMax) {
auto* prev_pointers = pointers.current;
pointers.current = Allocate<Pointers>();
if (!pointers.current) {
@@ -295,7 +261,7 @@
}
pointers.current->next = nullptr;
pointers.current->prev = prev_pointers;
- pointers.current_index = 0;
+ pointers.current->count = 0;
if (prev_pointers) {
prev_pointers->next = pointers.current;
@@ -304,7 +270,7 @@
}
}
- pointers.current->ptrs[pointers.current_index++] = ptr;
+ pointers.current->ptrs[pointers.current->count++] = ptr;
}
struct {
@@ -326,10 +292,6 @@
/// The current (end) Pointers structure of the pointers linked list.
/// AddObjectPointer() adds to this structure.
Pointers* current = nullptr;
- /// The array index in #current for the next append.
- /// Initialized with Pointers::kMax so that the first append triggers a allocation of
- /// the Pointers structure.
- size_t current_index = Pointers::kMax;
} pointers;
size_t count = 0;
diff --git a/src/tint/utils/memory/block_allocator_test.cc b/src/tint/utils/memory/block_allocator_test.cc
index d6da564..821e150 100644
--- a/src/tint/utils/memory/block_allocator_test.cc
+++ b/src/tint/utils/memory/block_allocator_test.cc
@@ -14,6 +14,8 @@
#include "src/tint/utils/memory/block_allocator.h"
+#include <vector>
+
#include "gtest/gtest.h"
namespace tint {
@@ -160,5 +162,30 @@
}
}
+TEST_F(BlockAllocatorTest, AddWhileIterating) {
+ using Allocator = BlockAllocator<size_t>;
+
+ Allocator allocator;
+ for (int i = 0; i < 20; i++) {
+ allocator.Create(allocator.Count());
+
+ std::vector<size_t*> seen;
+ for (auto* j : allocator.Objects()) {
+ if (*j % 3 == 0) {
+ allocator.Create(allocator.Count());
+ }
+ seen.push_back(j);
+ }
+
+ // Check that iteration-while-adding saw the same list of objects as an
+ // iteration-without-adding.
+ size_t n = 0;
+ for (auto* obj : allocator.Objects()) {
+ ASSERT_TRUE(n < seen.size());
+ EXPECT_EQ(seen[n++], obj);
+ }
+ }
+}
+
} // namespace
} // namespace tint
