OLD | NEW |
---|---|
(Empty) | |
1 /* | |
2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. | |
3 * | |
4 * Use of this source code is governed by a BSD-style license | |
5 * that can be found in the LICENSE file in the root of the source | |
6 * tree. An additional intellectual property rights grant can be found | |
7 * in the file PATENTS. All contributing project authors may | |
8 * be found in the AUTHORS file in the root of the source tree. | |
9 */ | |
10 | |
11 #ifndef WEBRTC_MODULES_SWAPPED_QUEUE_H_ | |
12 #define WEBRTC_MODULES_SWAPPED_QUEUE_H_ | |
kwiberg-webrtc
2015/10/13 13:54:23
Still behind the times!
peah-webrtc
2015/10/14 12:16:47
Ouch, good find!
peah-webrtc
2015/10/14 12:16:47
Done.
| |
13 | |
14 #include <algorithm> | |
15 #include <utility> | |
16 #include <vector> | |
17 | |
18 #include "webrtc/base/checks.h" | |
19 #include "webrtc/base/criticalsection.h" | |
20 | |
21 namespace webrtc { | |
22 | |
23 // This class is a one-way queue where data is written from one end and read | |
24 // from the other end. | |
25 // It is safe to access the class concurrently from multiple threads. | |
26 // The queueable objects must all be swappable as the Insert and Remove methods | |
27 // work by swapping the inputs with the element that is modified in the queue. | |
28 // This is illustrated in the pseudocode example below: | |
29 // | |
30 // Pseudocode example of queue usage: | |
kwiberg-webrtc
2015/10/13 13:54:23
What's pseudo about this code?
peah-webrtc
2015/10/14 12:16:47
:-) Removed pseudo
peah-webrtc
2015/10/14 12:16:47
Done.
| |
31 // SwapQueue<int> q(std::vector<int>(2, 0)); // q contains [0 0]; | |
the sun
2015/10/13 12:34:27
You can't do this with the class as it is defined
peah-webrtc
2015/10/14 12:16:47
Fully correct! I changed it a bit to signify that
| |
32 // int i = 1; | |
33 // q.Insert(&i); // q contains [1 0], i=0 | |
34 // i = 2; | |
35 // q.Insert(&i); // q contains [1 2], i=0 | |
36 // i = -3; | |
37 // q.Remove(&i); // q contains [-3 2], i=1 | |
38 // i = 4; | |
39 // q.Insert(&i); // q contains [4 2], i=-3 | |
40 // i = -5; | |
41 // q.Remove(&i); // q contains [4 -5], i=2 | |
42 // i = -6; | |
43 // q.Remove(&i); // q contains [-6 -5], i=4 | |
44 // | |
45 // It should be noted that if you want the Ts that are returned from the Insert | |
46 // to be of a special size, care must be taken that the queue is initialized | |
the sun
2015/10/13 12:34:27
This has nothing to do with "size". If the caller
kwiberg-webrtc
2015/10/13 14:08:36
Yes, we should definitely do that. (And by "we", w
The Sun (google.com)
2015/10/13 14:19:45
Evidently, given the number of comments we've mana
peah-webrtc
2015/10/14 12:16:47
Revised according to discussion.
| |
47 // with elements of that size, and all Ts that are used as input to Remove | |
48 // must be of that same size. This is important when the sizes of the Ts are | |
49 // dynamic. A pseudocode example of this is shown below where no vector resizing | |
kwiberg-webrtc
2015/10/13 13:54:23
Instead of talking about the size of the Ts, just
peah-webrtc
2015/10/14 12:16:47
I rewrote and rephrased, could you please have a l
| |
50 // is required apart from the one done during the initialization. | |
51 // | |
52 // Pseudocode example of queue usage with vector: | |
kwiberg-webrtc
2015/10/13 13:54:23
Why pseudo?
peah-webrtc
2015/10/14 12:16:47
Done.
| |
53 // // Initialization of vector to only hold vectors of the same size. | |
54 // const size_t kChunkSize = 1000; | |
55 // const size_t kDelay = 10; | |
56 // std::vector<std::vector<int>> v_init(kDelay); | |
57 // for (int k = 0; k < 2; k++) | |
58 // v_init[k].resize(kChunkSize); | |
kwiberg-webrtc
2015/10/13 13:54:23
Use a for (auto& v : v_init) loop. That will initi
peah-webrtc
2015/10/14 12:16:47
Rewrote this.
| |
59 // SwapQueue<int> queue(&v_init); | |
60 // | |
61 // // Initialization of input buffers to be of the same | |
62 // std::vector<int> input; | |
63 // std::vector<int> output; | |
64 // input.resize(kChunkSize); | |
65 // delayed_output.resize(kChunkSize); | |
kwiberg-webrtc
2015/10/13 13:54:23
std::vector<int> input(kChunkSize);
std::vector<in
peah-webrtc
2015/10/14 12:16:48
Done.
| |
66 // | |
67 // // Read int values in chunks and delay them with the length of the queue. | |
68 // int read_samples = 1; | |
69 // while (read_values == kChunkSize) { | |
70 // read_values = function_that_copies_ints_from_file_into_vector(&input); | |
kwiberg-webrtc
2015/10/13 13:54:23
read_samples or read_values?
peah-webrtc
2015/10/14 12:16:47
Done.
| |
71 // queue.Insert(&input); | |
72 // queue.Remove(&output); | |
73 // function_that_does_something(&output); | |
74 // } | |
kwiberg-webrtc
2015/10/13 13:54:24
This example is probably a bit too long to clearly
peah-webrtc
2015/10/14 12:16:47
I have that as well, should I just refer to that i
kwiberg-webrtc
2015/10/14 14:10:16
Yes, provided it's small and clean enough to work
peah-webrtc
2015/10/26 08:56:56
Acknowledged.
| |
75 template <typename T> | |
76 class SwapQueue { | |
77 public: | |
78 // Creates a queue of size size and fills it with the specified number of | |
79 // default constructed Ts. | |
80 explicit SwapQueue(size_t size) : queue_(size) {} | |
81 | |
82 // Create a queue with "empty" Ts from the given | |
the sun
2015/10/13 12:34:27
It does not create a queue with empty Ts. It creat
peah-webrtc
2015/10/14 12:16:47
Done.
| |
83 // vector. (The constructor will steal the contents from | |
84 // the supplied vector, leaving it empty.) | |
85 // TODO(peah): Change to std::vector<T>&& when we have a C++11 | |
86 // standard library. | |
kwiberg-webrtc
2015/10/13 13:54:23
This turned out to not be allowed by the relevant
peah-webrtc
2015/10/14 12:16:47
Done.
| |
87 // | |
88 // If used when T is a vector and the above described pattern that ensures | |
the sun
2015/10/13 12:34:27
Remove this comment, it is confusing
| |
89 // that all elements in the queue are of the same size, this is achieved if | |
90 // the following constructor is used with an input of vectors having the same | |
91 // size. | |
kwiberg-webrtc
2015/10/13 13:54:23
Remove this paragraph. The class documentation alr
peah-webrtc
2015/10/14 12:16:47
Done.
| |
92 explicit SwapQueue(std::vector<T>* empty_slots) { | |
93 RTC_CHECK_GE(empty_slots->size(), 1u); | |
the sun
2015/10/13 12:34:27
That's not actually a requirement. The code works
peah-webrtc
2015/10/14 12:16:47
Done.
| |
94 using std::swap; | |
95 swap(queue_, *empty_slots); | |
96 } | |
97 | |
98 // Resets the queue to have zero content. | |
99 void Clear() { | |
100 rtc::CritScope cs(&crit_queue_); | |
101 next_write_index_ = 0; | |
102 next_read_index_ = 0; | |
103 num_elements_ = 0; | |
104 } | |
105 | |
106 // Inserts a chunk of data into the queue. The input is swapped with the next | |
kwiberg-webrtc
2015/10/13 13:54:23
"chunk of data" -> "T"
peah-webrtc
2015/10/14 12:16:47
Done.
| |
107 // available value of type T present in the queue. | |
kwiberg-webrtc
2015/10/13 13:54:23
This doesn't make it clear that the queue makes a
peah-webrtc
2015/10/14 12:16:47
I agree that the full/empty description simplifies
| |
108 // Returns false if the queue is full (in which case no insert is performed), | |
kwiberg-webrtc
2015/10/13 13:54:24
"is full" -> "was already full"
peah-webrtc
2015/10/14 12:16:47
Done.
| |
109 // and true if not. | |
110 bool Insert(T* input) { | |
111 rtc::CritScope cs(&crit_queue_); | |
112 | |
113 // Early return if the queue is full. | |
kwiberg-webrtc
2015/10/13 13:54:23
This comment is not necessary.
peah-webrtc
2015/10/14 12:16:48
Done.
| |
114 if (num_elements_ == queue_.size()) | |
the sun
2015/10/13 12:34:27
Ohh, braces, please...
kwiberg-webrtc
2015/10/13 14:08:36
But they just make the code harder to read...
The Sun (google.com)
2015/10/13 14:19:45
No, they make sure the reader isn't ever fooled by
peah-webrtc
2015/10/14 12:16:47
Added braces :-)
| |
115 return false; | |
116 | |
117 using std::swap; | |
118 swap(*input, queue_[next_write_index_]); | |
119 | |
120 next_write_index_++; | |
121 if (next_write_index_ == queue_.size()) | |
122 next_write_index_ = 0; | |
123 | |
124 num_elements_++; | |
125 return true; | |
126 } | |
127 | |
128 // Removes a chunk of data from the queue. The queue element is swapped with | |
129 // the previous content of output. | |
130 // Returns false if the queue is empty (om which case no element is removed), | |
131 // and true if not. | |
kwiberg-webrtc
2015/10/13 13:54:23
See the three comments on the Insert doc.
peah-webrtc
2015/10/14 12:16:48
Done.
| |
132 bool Remove(T* output) { | |
133 rtc::CritScope cs(&crit_queue_); | |
134 | |
135 // Early return for empty queue. | |
kwiberg-webrtc
2015/10/13 13:54:23
Remove comment.
peah-webrtc
2015/10/14 12:16:48
Done.
| |
136 if (num_elements_ == 0) | |
137 return false; | |
138 | |
139 using std::swap; | |
140 swap(*output, queue_[next_read_index_]); | |
141 | |
142 next_read_index_++; | |
143 if (next_read_index_ == queue_.size()) | |
144 next_read_index_ = 0; | |
145 | |
146 num_elements_--; | |
147 return true; | |
148 } | |
149 | |
150 private: | |
151 // queue_.size() is constant. | |
152 std::vector<T> queue_ GUARDED_BY(crit_queue_); | |
153 | |
154 // (next_read_index_ + num_elements_) % queue_.size() = | |
155 // next_write_index_ | |
kwiberg-webrtc
2015/10/13 13:54:23
Also, they're both in the range [0,size).
peah-webrtc
2015/10/14 12:16:47
Done.
| |
156 size_t next_write_index_ GUARDED_BY(crit_queue_) = 0; | |
157 size_t next_read_index_ GUARDED_BY(crit_queue_) = 0; | |
158 | |
159 // 0 <= num_elements_ <= queue.size() | |
160 size_t num_elements_ GUARDED_BY(crit_queue_) = 0; | |
161 | |
162 rtc::CriticalSection crit_queue_; | |
163 | |
164 RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue); | |
165 }; | |
166 | |
167 } // namespace webrtc | |
168 | |
169 #endif // WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_ | |
OLD | NEW |