1/*
2Copyright 2018 Google Inc. All Rights Reserved.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS-IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17#ifndef RESONANCE_AUDIO_UTILS_LOCKLESS_TASK_QUEUE_H_
18#define RESONANCE_AUDIO_UTILS_LOCKLESS_TASK_QUEUE_H_
19
20#include <atomic>
21#include <cstddef>
22#include <cstdint>
23#include <functional>
24#include <vector>
25
26namespace vraudio {
27
28// Lock-less task queue which is thread safe for concurrent task producers and
29// single task consumers.
30class LocklessTaskQueue {
31 public:
32 // Alias for the task closure type.
33 typedef std::function<void()> Task;
34
35 // Constructor. Preallocates nodes on the task queue list.
36 //
37 // @param max_tasks Maximum number of tasks on the task queue.
38 explicit LocklessTaskQueue(size_t max_tasks);
39
40 ~LocklessTaskQueue();
41
42 // Posts a new task to task queue.
43 //
44 // @param task Task to process.
45 void Post(Task&& task);
46
47 // Executes all tasks on the task queue.
48 void Execute();
49
50 // Removes all tasks on the task queue.
51 void Clear();
52
53 private:
54 // To prevent ABA problems during thread synchronization, the most significant
55 // 32 bits of this index type are reserved for a continuously increasing
56 // tag counter. This prevents cases where nodes on the head appears to be
57 // untouched during the preparation of a push operation but instead they have
58 // been popped and pushed back during a context switch.
59 typedef uint64_t TagAndIndex;
60
61 // Node to model a single-linked list.
62 struct Node {
63 Node() = default;
64
65 // Dummy copy constructor to enable vector::resize allocation.
66 Node(const Node& node) : next() {}
67
68 // User task.
69 LocklessTaskQueue::Task task;
70
71 // Index to next node.
72 std::atomic<TagAndIndex> next;
73 };
74
75 // Returned a TagAndIndex with increased tag.
76 TagAndIndex IncreaseTag(TagAndIndex tag_and_index);
77
78 // Extracts the index in the least significant 32 bits from a TagAndIndex.
79 TagAndIndex GetIndex(TagAndIndex tag_and_index);
80
81 // Extracts the flag in the most significant 32 bits from a TagAndIndex.
82 TagAndIndex GetFlag(TagAndIndex tag_and_index);
83
84 // Pushes a node to the front of a list.
85 //
86 // @param list_head Index to list head.
87 // @param node Index of node to be pushed to the front of the list.
88 void PushNodeToList(std::atomic<TagAndIndex>* list_head, TagAndIndex node);
89
90 // Pops a node from the front of a list.
91 //
92 // @param list_head Index to list head.
93 // @return Index of front node, kInvalidIndex if list is empty.
94 TagAndIndex PopNodeFromList(std::atomic<TagAndIndex>* list_head);
95
96 // Iterates over list and moves all tasks to |temp_tasks_| to be executed in
97 // FIFO order. All processed nodes are pushed back to the free list.
98 //
99 // @param list_head Index of head node of list to be processed.
100 // @param execute If true, tasks on task list are executed.
101 void ProcessTaskList(TagAndIndex list_head, bool execute);
102
103 // Initializes task queue structures and preallocates task queue nodes.
104 //
105 // @param num_nodes Number of nodes to be initialized on free list.
106 void Init(size_t num_nodes);
107
108 // Index to head node of free list.
109 std::atomic<TagAndIndex> free_list_head_idx_;
110
111 // Index to head node of task list.
112 std::atomic<TagAndIndex> task_list_head_idx_;
113
114 // Holds preallocated nodes.
115 std::vector<Node> nodes_;
116
117 // Temporary vector to hold |Task|s in order to execute them in reverse order
118 // (FIFO, instead of LIFO).
119 std::vector<Task> temp_tasks_;
120};
121
122} // namespace vraudio
123
124#endif // RESONANCE_AUDIO_UTILS_LOCKLESS_TASK_QUEUE_H_
125

source code of qtmultimedia/src/3rdparty/resonance-audio/resonance_audio/utils/lockless_task_queue.h