TaskScheduler [10] SchedulerWorkerThreadStack

base/task_scheduler/scheduler_stack.h

+// 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.
+
+#ifndef BASE_TASK_SCHEDULER_SCHEDULER_STACK_H_
+#define BASE_TASK_SCHEDULER_SCHEDULER_STACK_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <vector>
+
+#include "base/base_export.h"
+
+namespace base {
+namespace internal {
+
+// A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't
+// allow multiple insertions of the same value.
+//
+// The stack can only contain integers in [0, 63] because it maintains a bit
+// field that indicates whether a value is on the stack.
+//
+// Push() runs in amortized O(1). Remove() runs in O(1). Pop() runs in O(x + 1)
+// where x is the number of values removed from the stack since the previous
+// Pop().
+
+// This class is NOT thread-safe.
+class BASE_EXPORT SchedulerStack {
+ public:
+  SchedulerStack();
+  ~SchedulerStack();
+
+  // Inserts |val| at the top of the stack. |val| must be in [0, 63] and must
+  // not already be on the stack.
+  void Push(int val);
+
+  // Removes the top value from the stack and returns it. Cannot be called on an
+  // empty stack.
+  int Pop();
+
+  // Removes |val| from the stack if it was on it.
+  void Remove(int val);
+
+  // Returns the number of values on the stack.
+  size_t Size() const { return size_; }
+
+  // Returns true if the stack is empty.
+  bool Empty() const { return size_ == 0; }
+
+ private:
+  std::vector<int> stack_;
+
+  // A bit field that indicates whether a value is on |stack_|.
+  uint64_t bit_field_ = 0;
+
+  // Number of elements on the stack.
+  size_t size_ = 0;
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_TASK_SCHEDULER_SCHEDULER_STACK_H_