diff options
Diffstat (limited to 'third_party/libwebrtc/test/pc/e2e/analyzer/video/multi_reader_queue.h')
-rw-r--r-- | third_party/libwebrtc/test/pc/e2e/analyzer/video/multi_reader_queue.h | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/third_party/libwebrtc/test/pc/e2e/analyzer/video/multi_reader_queue.h b/third_party/libwebrtc/test/pc/e2e/analyzer/video/multi_reader_queue.h new file mode 100644 index 0000000000..39d26b42bc --- /dev/null +++ b/third_party/libwebrtc/test/pc/e2e/analyzer/video/multi_reader_queue.h @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef TEST_PC_E2E_ANALYZER_VIDEO_MULTI_READER_QUEUE_H_ +#define TEST_PC_E2E_ANALYZER_VIDEO_MULTI_READER_QUEUE_H_ + +#include <deque> +#include <memory> +#include <set> +#include <unordered_map> + +#include "absl/types/optional.h" +#include "rtc_base/checks.h" + +namespace webrtc { + +// Represents the queue which can be read by multiple readers. Each reader reads +// from its own queue head. When an element is added it will become visible for +// all readers. When an element will be removed by all the readers, the element +// will be removed from the queue. +template <typename T> +class MultiReaderQueue { + public: + // Creates queue with exactly `readers_count` readers named from 0 to + // `readers_count - 1`. + explicit MultiReaderQueue(size_t readers_count) { + for (size_t i = 0; i < readers_count; ++i) { + heads_[i] = 0; + } + } + // Creates queue with specified readers. + explicit MultiReaderQueue(std::set<size_t> readers) { + for (size_t reader : readers) { + heads_[reader] = 0; + } + } + + // Adds a new `reader`, initializing its reading position (the reader's head) + // equal to the one of `reader_to_copy`. + // Complexity O(MultiReaderQueue::size(reader_to_copy)). + void AddReader(size_t reader, size_t reader_to_copy) { + size_t pos = GetHeadPositionOrDie(reader_to_copy); + + auto it = heads_.find(reader); + RTC_CHECK(it == heads_.end()) + << "Reader " << reader << " is already in the queue"; + heads_[reader] = heads_[reader_to_copy]; + for (size_t i = pos; i < queue_.size(); ++i) { + in_queues_[i]++; + } + } + + // Adds a new `reader`, initializing its reading position equal to first + // element in the queue. + // Complexity O(MultiReaderQueue::size()). + void AddReader(size_t reader) { + auto it = heads_.find(reader); + RTC_CHECK(it == heads_.end()) + << "Reader " << reader << " is already in the queue"; + heads_[reader] = removed_elements_count_; + for (size_t i = 0; i < queue_.size(); ++i) { + in_queues_[i]++; + } + } + + // Removes specified `reader` from the queue. + // Complexity O(MultiReaderQueue::size(reader)). + void RemoveReader(size_t reader) { + size_t pos = GetHeadPositionOrDie(reader); + for (size_t i = pos; i < queue_.size(); ++i) { + in_queues_[i]--; + } + while (!in_queues_.empty() && in_queues_[0] == 0) { + PopFront(); + } + heads_.erase(reader); + } + + // Add value to the end of the queue. Complexity O(1). + void PushBack(T value) { + queue_.push_back(value); + in_queues_.push_back(heads_.size()); + } + + // Extract element from specified head. Complexity O(1). + absl::optional<T> PopFront(size_t reader) { + size_t pos = GetHeadPositionOrDie(reader); + if (pos >= queue_.size()) { + return absl::nullopt; + } + + T out = queue_[pos]; + + in_queues_[pos]--; + heads_[reader]++; + + if (in_queues_[pos] == 0) { + RTC_DCHECK_EQ(pos, 0); + PopFront(); + } + return out; + } + + // Returns element at specified head. Complexity O(1). + absl::optional<T> Front(size_t reader) const { + size_t pos = GetHeadPositionOrDie(reader); + if (pos >= queue_.size()) { + return absl::nullopt; + } + return queue_[pos]; + } + + // Returns true if for specified head there are no more elements in the queue + // or false otherwise. Complexity O(1). + bool IsEmpty(size_t reader) const { + size_t pos = GetHeadPositionOrDie(reader); + return pos >= queue_.size(); + } + + // Returns size of the longest queue between all readers. + // Complexity O(1). + size_t size() const { return queue_.size(); } + + // Returns size of the specified queue. Complexity O(1). + size_t size(size_t reader) const { + size_t pos = GetHeadPositionOrDie(reader); + return queue_.size() - pos; + } + + // Complexity O(1). + size_t readers_count() const { return heads_.size(); } + + private: + size_t GetHeadPositionOrDie(size_t reader) const { + auto it = heads_.find(reader); + RTC_CHECK(it != heads_.end()) << "No queue for reader " << reader; + return it->second - removed_elements_count_; + } + + void PopFront() { + RTC_DCHECK(!queue_.empty()); + RTC_DCHECK_EQ(in_queues_[0], 0); + queue_.pop_front(); + in_queues_.pop_front(); + removed_elements_count_++; + } + + // Number of the elements that were removed from the queue. It is used to + // subtract from each head to compute the right index inside `queue_`; + size_t removed_elements_count_ = 0; + std::deque<T> queue_; + // In how may queues the element at index `i` is. An element can be removed + // from the front if and only if it is in 0 queues. + std::deque<size_t> in_queues_; + // Map from the reader to the head position in the queue. + std::unordered_map<size_t, size_t> heads_; +}; + +} // namespace webrtc + +#endif // TEST_PC_E2E_ANALYZER_VIDEO_MULTI_READER_QUEUE_H_ |