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 BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 6 #define BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 7 8 #include <map> 9 #include <vector> 10 11 #include "base/base_export.h" 12 #include "base/logging.h" 13 #include "base/macros.h" 14 #include "base/task/sequence_manager/intrusive_heap.h" 15 #include "base/task/sequence_manager/task_queue_impl.h" 16 #include "base/task/sequence_manager/work_queue.h" 17 #include "base/trace_event/trace_event_argument.h" 18 19 namespace base { 20 namespace sequence_manager { 21 namespace internal { 22 23 // There is a WorkQueueSet for each scheduler priority and each WorkQueueSet 24 // uses a EnqueueOrderToWorkQueueMap to keep track of which queue in the set has 25 // the oldest task (i.e. the one that should be run next if the 26 // TaskQueueSelector chooses to run a task a given priority). The reason this 27 // works is because std::map is a tree based associative container and all the 28 // values are kept in sorted order. 29 class BASE_EXPORT WorkQueueSets { 30 public: 31 WorkQueueSets(size_t num_sets, const char* name); 32 ~WorkQueueSets(); 33 34 // O(log num queues) 35 void AddQueue(WorkQueue* queue, size_t set_index); 36 37 // O(log num queues) 38 void RemoveQueue(WorkQueue* work_queue); 39 40 // O(log num queues) 41 void ChangeSetIndex(WorkQueue* queue, size_t set_index); 42 43 // O(log num queues) 44 void OnFrontTaskChanged(WorkQueue* queue); 45 46 // O(log num queues) 47 void OnTaskPushedToEmptyQueue(WorkQueue* work_queue); 48 49 // If empty it's O(1) amortized, otherwise it's O(log num queues) 50 // Assumes |work_queue| contains the lowest enqueue order in the set. 51 void OnPopQueue(WorkQueue* work_queue); 52 53 // O(log num queues) 54 void OnQueueBlocked(WorkQueue* work_queue); 55 56 // O(1) 57 bool GetOldestQueueInSet(size_t set_index, WorkQueue** out_work_queue) const; 58 59 // O(1) 60 bool GetOldestQueueAndEnqueueOrderInSet( 61 size_t set_index, 62 WorkQueue** out_work_queue, 63 EnqueueOrder* out_enqueue_order) const; 64 65 // O(1) 66 bool IsSetEmpty(size_t set_index) const; 67 68 #if DCHECK_IS_ON() || !defined(NDEBUG) 69 // Note this iterates over everything in |work_queue_heaps_|. 70 // It's intended for use with DCHECKS and for testing 71 bool ContainsWorkQueueForTest(const WorkQueue* queue) const; 72 #endif 73 GetName()74 const char* GetName() const { return name_; } 75 76 private: 77 struct OldestTaskEnqueueOrder { 78 EnqueueOrder key; 79 WorkQueue* value; 80 81 bool operator<=(const OldestTaskEnqueueOrder& other) const { 82 return key <= other.key; 83 } 84 SetHeapHandleOldestTaskEnqueueOrder85 void SetHeapHandle(HeapHandle handle) { value->set_heap_handle(handle); } 86 ClearHeapHandleOldestTaskEnqueueOrder87 void ClearHeapHandle() { value->set_heap_handle(HeapHandle()); } 88 }; 89 90 // For each set |work_queue_heaps_| has a queue of WorkQueue ordered by the 91 // oldest task in each WorkQueue. 92 std::vector<IntrusiveHeap<OldestTaskEnqueueOrder>> work_queue_heaps_; 93 const char* const name_; 94 95 DISALLOW_COPY_AND_ASSIGN(WorkQueueSets); 96 }; 97 98 } // namespace internal 99 } // namespace sequence_manager 100 } // namespace base 101 102 #endif // BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 103