Page MenuHomePhabricator
Files F13115748

D8837.diff
No OneTemporary
Actions

D8837.diff
View Options

diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -110,19 +110,56 @@
* expose whether the stack is empty and whether or not any false values are
* present at all. To implement OP_ELSE, a toggle_top modifier is added, which
* flips the last value without returning it.
+ *
+ * This uses an optimized implementation that does not materialize the
+ * actual stack. Instead, it just stores the size of the would-be stack,
+ * and the position of the first false value in it.
*/
class ConditionStack {
private:
- std::vector<bool> m_flags;
+ //! A constant for m_first_false_pos to indicate there are no falses.
+ static constexpr uint32_t NO_FALSE = std::numeric_limits<uint32_t>::max();
+
+ //! The size of the implied stack.
+ uint32_t m_stack_size = 0;
+ //! The position of the first false value on the implied stack, or NO_FALSE
+ //! if all true.
+ uint32_t m_first_false_pos = NO_FALSE;
public:
- bool empty() { return m_flags.empty(); }
- bool all_true() {
- return !std::count(m_flags.begin(), m_flags.end(), false);
+ bool empty() { return m_stack_size == 0; }
+ bool all_true() { return m_first_false_pos == NO_FALSE; }
+ void push_back(bool f) {
+ if (m_first_false_pos == NO_FALSE && !f) {
+ // The stack consists of all true values, and a false is added.
+ // The first false value will appear at the current size.
+ m_first_false_pos = m_stack_size;
+ }
+ ++m_stack_size;
+ }
+ void pop_back() {
+ assert(m_stack_size > 0);
+ --m_stack_size;
+ if (m_first_false_pos == m_stack_size) {
+ // When popping off the first false value, everything becomes true.
+ m_first_false_pos = NO_FALSE;
+ }
+ }
+ void toggle_top() {
+ assert(m_stack_size > 0);
+ if (m_first_false_pos == NO_FALSE) {
+ // The current stack is all true values; the first false will be the
+ // top.
+ m_first_false_pos = m_stack_size - 1;
+ } else if (m_first_false_pos == m_stack_size - 1) {
+ // The top is the first false value; toggling it will make
+ // everything true.
+ m_first_false_pos = NO_FALSE;
+ } else {
+ // There is a false value, but not on top. No action is needed as
+ // toggling anything but the first false value is unobservable.
+ }
}
- void push_back(bool f) { m_flags.push_back(f); }
- void pop_back() { m_flags.pop_back(); }
- void toggle_top() { m_flags.back() = !m_flags.back(); }
};
} // namespace

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 1, 11:56 (34 m, 11 s)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5187736
Default Alt Text
D8837.diff (2 KB)

Event Timeline