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);
  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,
  39                            internal::TaskQueueImpl** out_queue) const;
  40
  41  private:
  42   struct AgeComparitor {
  43     // The age numbers are generated in sequence.  These will eventually
  44     // overflow and roll-over to negative numbers.  We must take care to
  45     // preserve the ordering of the map when this happens.
  46     // NOTE we assume that tasks don't get starved for extended periods so that
  47     // the task queue ages in a set have at most one roll-over.
  48     // NOTE signed integer overflow behavior is undefined in C++ so we can't
  49     // use the (a - b) < 0 trick here, because the optimizer won't necessarily
  50     // do what we expect.
  51     // TODO(alexclarke): Consider making age and sequence_num unsigned, because
  52     // unsigned integer overflow behavior is defined.
  53     bool operator()(int a, int b) const {
  54       if (a < 0 && b >= 0)
  55         return false;
  56       if (b < 0 && a >= 0)
  57         return true;
  58       return a < b;
  59     }
  60   };
  61
  62   typedef std::map<int, internal::TaskQueueImpl*, AgeComparitor> AgeToQueueMap;
  63   std::vector<AgeToQueueMap> age_to_queue_maps_;
  64
  65   DISALLOW_COPY_AND_ASSIGN(TaskQueueSets);
  66 };
  67
  68 }  // namespace internal
  69 }  // namespace scheduler
  70
  71 #endif  // COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_