components/scheduler/child/task_queue_sets.h

   1 // Copyright 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_
   6 #define COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_
   7
   8 #include <map>
   9 #include <vector>
  10
  11 #include "base/macros.h"
  12 #include "base/trace_event/trace_event_argument.h"
  13 #include "components/scheduler/child/task_queue.h"
  14 #include "components/scheduler/scheduler_export.h"
  15
  16 namespace scheduler {
  17 namespace internal {
  18 class TaskQueueImpl;
  19
  20 class SCHEDULER_EXPORT TaskQueueSets {
  21  public:
  22   explicit TaskQueueSets(size_t num_sets);
  23   ~TaskQueueSets();
  24
  25   // O(log num queues)
  26   void RemoveQueue(internal::TaskQueueImpl* queue);
  27
  28   // O(log num queues)
  29   void AssignQueueToSet(internal::TaskQueueImpl* queue, size_t set_index);
  30
  31   // O(log num queues)
  32   void OnPushQueue(internal::TaskQueueImpl* queue);
  33
  34   // If empty it's O(1) amortized, otherwise it's O(log num queues)
  35   void OnPopQueue(internal::TaskQueueImpl* queue);
  36
  37   // O(1)
  38   bool GetOldestQueueInSet(size_t set_index,
  39                            internal::TaskQueueImpl** out_queue) const;
  40
  41   // O(1)
  42   bool IsSetEmpty(size_t set_index) const;
  43
  44  private:
  45   struct EnqueueOrderComparitor {
  46     // The enqueueorder numbers are generated in sequence.  These will
  47     // eventually overflow and roll-over to negative numbers.  We must take care
  48     // to preserve the ordering of the map when this happens.
  49     // NOTE we assume that tasks don't get starved for extended periods so that
  50     // the task queue ages in a set have at most one roll-over.
  51     // NOTE signed integer overflow behavior is undefined in C++ so we can't
  52     // use the (a - b) < 0 trick here, because the optimizer won't necessarily
  53     // do what we expect.
  54     // TODO(alexclarke): Consider making age and sequence_num unsigned, because
  55     // unsigned integer overflow behavior is defined.
  56     bool operator()(int a, int b) const {
  57       if (a < 0 && b >= 0)
  58         return false;
  59       if (b < 0 && a >= 0)
  60         return true;
  61       return a < b;
  62     }
  63   };
  64
  65   typedef std::map<int, internal::TaskQueueImpl*, EnqueueOrderComparitor>
  66       EnqueueOrderToQueueMap;
  67   std::vector<EnqueueOrderToQueueMap> enqueue_order_to_queue_maps_;
  68
  69   DISALLOW_COPY_AND_ASSIGN(TaskQueueSets);
  70 };
  71
  72 }  // namespace internal
  73 }  // namespace scheduler
  74
  75 #endif  // COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_