OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ | 5 #ifndef COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ |
6 #define COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ | 6 #define COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ |
7 | 7 |
8 #include <map> | 8 #include <map> |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
(...skipping 21 matching lines...) Expand all Loading... |
32 void OnPushQueue(internal::TaskQueueImpl* queue); | 32 void OnPushQueue(internal::TaskQueueImpl* queue); |
33 | 33 |
34 // If empty it's O(1) amortized, otherwise it's O(log num queues) | 34 // If empty it's O(1) amortized, otherwise it's O(log num queues) |
35 void OnPopQueue(internal::TaskQueueImpl* queue); | 35 void OnPopQueue(internal::TaskQueueImpl* queue); |
36 | 36 |
37 // O(1) | 37 // O(1) |
38 bool GetOldestQueueInSet(size_t set, | 38 bool GetOldestQueueInSet(size_t set, |
39 internal::TaskQueueImpl** out_queue) const; | 39 internal::TaskQueueImpl** out_queue) const; |
40 | 40 |
41 private: | 41 private: |
42 struct EnqueueOrderComparitor { | 42 struct AgeComparitor { |
43 // The enqueueorder numbers are generated in sequence. These will | 43 // The age numbers are generated in sequence. These will eventually |
44 // eventually overflow and roll-over to negative numbers. We must take care | 44 // overflow and roll-over to negative numbers. We must take care to |
45 // to preserve the ordering of the map when this happens. | 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 | 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. | 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 | 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 | 49 // use the (a - b) < 0 trick here, because the optimizer won't necessarily |
50 // do what we expect. | 50 // do what we expect. |
51 // TODO(alexclarke): Consider making age and sequence_num unsigned, because | 51 // TODO(alexclarke): Consider making age and sequence_num unsigned, because |
52 // unsigned integer overflow behavior is defined. | 52 // unsigned integer overflow behavior is defined. |
53 bool operator()(int a, int b) const { | 53 bool operator()(int a, int b) const { |
54 if (a < 0 && b >= 0) | 54 if (a < 0 && b >= 0) |
55 return false; | 55 return false; |
56 if (b < 0 && a >= 0) | 56 if (b < 0 && a >= 0) |
57 return true; | 57 return true; |
58 return a < b; | 58 return a < b; |
59 } | 59 } |
60 }; | 60 }; |
61 | 61 |
62 typedef std::map<int, internal::TaskQueueImpl*, EnqueueOrderComparitor> | 62 typedef std::map<int, internal::TaskQueueImpl*, AgeComparitor> AgeToQueueMap; |
63 EnqueueOrderToQueueMap; | 63 std::vector<AgeToQueueMap> age_to_queue_maps_; |
64 std::vector<EnqueueOrderToQueueMap> enqueue_order_to_queue_maps_; | |
65 | 64 |
66 DISALLOW_COPY_AND_ASSIGN(TaskQueueSets); | 65 DISALLOW_COPY_AND_ASSIGN(TaskQueueSets); |
67 }; | 66 }; |
68 | 67 |
69 } // namespace internal | 68 } // namespace internal |
70 } // namespace scheduler | 69 } // namespace scheduler |
71 | 70 |
72 #endif // COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ | 71 #endif // COMPONENTS_SCHEDULER_CHILD_TASK_QUEUE_SETS_H_ |
OLD | NEW |