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..d4230360da2b64d14de7138c5e7bbbba7d99aa7b
--- /dev/null
+++ b/base/task_scheduler/scheduler_stack.cc
@@ -0,0 +1,62 @@
+// 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 {
+
+SchedulerStack::SchedulerStack() = default;
+
+SchedulerStack::~SchedulerStack() = default;
+
+void SchedulerStack::Push(int val) {
+  DCHECK_GE(val, 0);
+  DCHECK_LE(val, 63);
+  DCHECK(!Contains(val));
+
+  stack_.push_back(val);
+  bit_field_ |= 1ULL << val;

[gab, 2016/04/18 18:35:40]

Don't think it's guaranteed that ULL will always be a uint64_t, how about a
static_cast<uint64_t>(1U)? Or even "constexpr uint64_t bit = 1U; bit_field |=
bit << val;"

[fdoray, 2016/04/18 20:33:12]

Done.

+}
+
+int SchedulerStack::Pop() {
+  DCHECK(!Empty());
+
+  const int val = stack_.back();
+  stack_.pop_back();
+  bit_field_ &= ~(1ULL << val);
+
+  return val;
+}
+
+void SchedulerStack::Remove(int val) {
+  if (!Contains(val))
+    return;
+
+  auto it = std::find(stack_.begin(), stack_.end(), val);
+  DCHECK(it != stack_.end());
+  stack_.erase(it);

[gab, 2016/04/18 18:35:40]

Lines 41+43 are O(2n) :-(. Can we make Remove() constant by simply invalidating
the |bit_field_| and then Pop() becomes amortized-O(1) instead of pure-O(1) but
that's okay (could also make a purge pass if push is invoked when stack_.size()
== 64).

[fdoray, 2016/04/18 20:33:12]

Done.

+  bit_field_ &= ~(1ULL << val);
+}
+
+size_t SchedulerStack::Size() const {
+  return stack_.size();
+}
+
+bool SchedulerStack::Empty() const {
+  return stack_.empty();
+}
+
+bool SchedulerStack::Contains(int val) const {
+  DCHECK_GE(val, 0);
+  DCHECK_LE(val, 63);
+  return (bit_field_ & (1ULL << val)) != 0;
+}
+
+}  // namespace internal
+}  // namespace base