TaskScheduler [10] SchedulerWorkerThreadStack

base/task_scheduler/scheduler_stack.cc

Index: base/task_scheduler/scheduler_stack.cc
diff --git a/base/task_scheduler/scheduler_stack.cc b/base/task_scheduler/scheduler_stack.cc
new file mode 100644
index 0000000000000000000000000000000000000000..0cb703bf88349d2446ec2e6e5f5455c4c9658275
--- /dev/null
+++ b/base/task_scheduler/scheduler_stack.cc
@@ -0,0 +1,83 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/task_scheduler/scheduler_stack.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+
+namespace base {
+namespace internal {
+
+namespace {
+
+constexpr uint64_t kBit = 1U;
+
+// Returns true if the |val| bit of |bit_field| is set.
+bool BitIsSet(uint64_t bit_field, int val) {
+  DCHECK_GE(val, 0);
+  DCHECK_LE(val, 63);
+  return (bit_field & (kBit << val)) != 0;
+}
+
+struct BitIsSetPredicate {
+  BitIsSetPredicate(uint64_t bit_field) : bit_field_(bit_field) {}
+
+  bool operator()(int val) const { return BitIsSet(bit_field_, val); }
+
+  const uint64_t bit_field_;
+};
+
+}  // namespace
+
+SchedulerStack::SchedulerStack() = default;
+
+SchedulerStack::~SchedulerStack() = default;
+
+void SchedulerStack::Push(int val) {
+  DCHECK_GE(val, 0);
+  DCHECK_LE(val, 63);
+  DCHECK(!BitIsSet(bit_field_, val));

[robliao, 2016/04/19 00:41:16]

Let's add a message: DCHECK(..) << "Value already on stack".

[fdoray, 2016/04/19 14:05:50]

Done.

+
+  DCHECK_LE(stack_.size(), 64U);
+  if (stack_.size() >= 64U) {
+    // Remove from |stack_| all values whose bit isn't set in |bit_field_|. This
+    // prevents |stack_| from growing indefinitely.
+    stack_.erase(std::remove_if(stack_.begin(), stack_.end(),
+                                BitIsSetPredicate(bit_field_)),

[robliao, 2016/04/19 00:41:16]

Instead of predicate, this may be clearer as a lambda.

[fdoray, 2016/04/19 14:05:50]

Done.

+                 stack_.end());
+  }
+
+  stack_.push_back(val);
+  bit_field_ |= kBit << val;
+  ++size_;
+}
+
+int SchedulerStack::Pop() {
+  DCHECK(!Empty());
+
+  // Pop values from |stack_| until one whose bit is set in |bit_field_| is
+  // found.
+  int val = -1;
+  do {
+    DCHECK(!stack_.empty());
+    val = stack_.back();
+    stack_.pop_back();
+  } while (!BitIsSet(bit_field_, val));
+
+  bit_field_ &= ~(kBit << val);
+  --size_;
+  return val;
+}
+
+void SchedulerStack::Remove(int val) {
+  if (!BitIsSet(bit_field_, val))
+    return;
+  bit_field_ &= ~(kBit << val);
+  --size_;

[robliao, 2016/04/19 00:41:16]

It's worthwhile to note somewhere that an index on the stack doesn't necessarily
mean the bit is set.

[fdoray, 2016/04/19 14:05:50]

Done, in scheduler_stack.h above |stack_|.

+}
+
+}  // namespace internal
+}  // namespace base