Line data Source code
1 : /**
2 : * Copyright (c) 2025 Huawei Technologies Co., Ltd.
3 : * This program is free software, you can redistribute it and/or modify it under the terms and conditions of
4 : * CANN Open Software License Agreement Version 2.0 (the "License").
5 : * Please refer to the License for details. You may not use this file except in compliance with the License.
6 : * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED,
7 : * INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY, OR FITNESS FOR A PARTICULAR PURPOSE.
8 : * See LICENSE in the root of the software repository for the full text of the License.
9 : */
10 : #ifndef CIRCULAR_QUEUE_H
11 : #define CIRCULAR_QUEUE_H
12 :
13 : #include "queue.h"
14 : #include <vector>
15 : namespace Hccl {
16 :
17 : template <typename T>
18 : class CircularQueue : public QueueWithSize<T> {
19 : private:
20 : std::vector<T> elems_;
21 : size_t head_;
22 : size_t tail_;
23 : size_t capacity_;
24 :
25 : public:
26 : class Iterator : public Queue<T>::Iterator {
27 : private:
28 : const CircularQueue* queue_{nullptr};
29 :
30 : protected:
31 4172 : void check() override
32 : {
33 4172 : if (queue_ == nullptr) {
34 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
35 : }
36 4172 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
37 9 : this->it_ = queue_->elems_.end();
38 9 : return;
39 : }
40 :
41 4163 : if (queue_->size_ == 0) {
42 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is empty"));
43 : }
44 4163 : size_t now = this->it_ - queue_->elems_.begin();
45 4163 : if ((queue_->head_ < queue_->tail_) && !(queue_->head_ <= now && now < queue_->tail_)) {
46 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
47 : }
48 4163 : const size_t start_point = 0;
49 4163 : if ((queue_->tail_ <= queue_->head_)
50 4095 : && !(
51 4095 : (start_point <= now && now < queue_->tail_) || (queue_->head_ <= now && now < queue_->capacity_))) {
52 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
53 : }
54 : }
55 :
56 : public:
57 4253 : Iterator(typename std::vector<T>::const_iterator it, const CircularQueue* queue)
58 : : Queue<T>::Iterator(it),
59 4253 : queue_(queue)
60 : {
61 4253 : if (queue_ == nullptr) {
62 0 : THROW<InternalException>(StringFormat("CircularQueue::Iterator queue_ is nullptr"));
63 : }
64 4253 : if ((this->it_) == (queue_->elems_.begin() + queue_->tail_)) {
65 2082 : this->it_ = queue_->elems_.end();
66 : }
67 4253 : }
68 :
69 8351 : ~Iterator() override = default;
70 :
71 6 : typename Queue<T>::Iterator& operator++() override
72 : {
73 6 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
74 6 : check();
75 6 : return *this;
76 : }
77 :
78 2050 : typename Queue<T>::Iterator operator++(int) override
79 : {
80 2050 : Iterator temp = *this;
81 2050 : (this->it_) = ((this->it_) - queue_->elems_.begin() + 1) % queue_->capacity_ + queue_->elems_.begin();
82 2050 : check();
83 4100 : return temp;
84 2050 : }
85 :
86 68 : typename Queue<T>::Iterator& operator--() override
87 : {
88 68 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
89 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
90 : }
91 68 : if (this->it_ == this->queue_->elems_.end()) {
92 0 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
93 : }
94 68 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
95 136 : + queue_->elems_.begin();
96 68 : check();
97 68 : return *this;
98 : }
99 :
100 2048 : typename Queue<T>::Iterator operator--(int) override
101 : {
102 2048 : if (this->it_ == queue_->elems_.begin() + queue_->head_) {
103 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::Iterator out of range"));
104 : }
105 2048 : Iterator temp = *this;
106 2048 : if (this->it_ == this->queue_->elems_.end()) {
107 1 : (this->it_) = queue_->elems_.begin() + queue_->tail_;
108 : }
109 2048 : (this->it_) = ((this->it_) - queue_->elems_.begin() - 1 + queue_->capacity_) % queue_->capacity_
110 4096 : + queue_->elems_.begin();
111 2048 : check();
112 4096 : return temp;
113 2048 : }
114 : };
115 :
116 78 : explicit CircularQueue(size_t capacity) : elems_(capacity + 1), head_(0), tail_(0), capacity_(capacity + 1)
117 : {
118 39 : if (capacity_ == 0) {
119 0 : THROW<InternalException>(StringFormat("CircularQueue capacity cannot be zero"));
120 : }
121 39 : }
122 :
123 187 : ~CircularQueue() override { HCCL_INFO("[CircularQueue]Destroy"); }
124 :
125 38 : void Append(T&& value) override
126 : {
127 38 : if (IsFull()) {
128 0 : head_ = (head_ + 1) % capacity_;
129 0 : this->size_--;
130 : }
131 38 : elems_[tail_] = std::move(value);
132 38 : tail_ = (tail_ + 1) % capacity_;
133 38 : this->size_++;
134 38 : }
135 :
136 10106 : T& GetAndUpdate() override
137 : {
138 10106 : if (IsFull()) {
139 7952 : head_ = (head_ + 1) % capacity_;
140 7952 : this->size_--;
141 : }
142 10106 : auto curTail = tail_;
143 10106 : tail_ = (tail_ + 1) % capacity_;
144 10106 : this->size_++;
145 10106 : return elems_[curTail];
146 : }
147 :
148 1 : void PopFront() override
149 : {
150 1 : if (this->IsEmpty()) {
151 0 : THROW<InternalException>(StringFormat("CircularQueue<T>::PopFront Queue is empty!"));
152 : }
153 1 : head_ = (head_ + 1) % capacity_;
154 1 : this->size_--;
155 1 : }
156 :
157 0 : void Traverse(std::function<void(const T&)> action) override
158 : {
159 0 : size_t i = head_;
160 0 : size_t count = 0;
161 0 : while (count < this->size_) {
162 0 : action(elems_[i]);
163 0 : i = (i + 1) % capacity_;
164 0 : count++;
165 : }
166 0 : }
167 :
168 10144 : bool IsFull() const override { return this->size_ == Capacity(); }
169 :
170 20250 : size_t Capacity() const override { return capacity_ - 1; }
171 :
172 13 : std::shared_ptr<typename Queue<T>::Iterator> Find(std::function<bool(const T&)> cond) override
173 : {
174 13 : size_t i = head_;
175 13 : size_t count = 0;
176 164 : while (count < this->size_) {
177 161 : if (cond(elems_[i])) {
178 10 : return std::make_shared<Iterator>(elems_.begin() + i, this);
179 : }
180 151 : i = (i + 1) % capacity_;
181 151 : count++;
182 : }
183 3 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
184 : }
185 :
186 2151 : std::shared_ptr<typename Queue<T>::Iterator> Begin() const override
187 : {
188 2151 : if (this->IsEmpty()) {
189 6 : HCCL_WARNING("[CircularQueue][Begin] Queue is empty!");
190 2 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
191 : }
192 2149 : return std::make_shared<Iterator>(elems_.begin() + head_, this);
193 : }
194 :
195 13 : std::shared_ptr<typename Queue<T>::Iterator> Tail() const override
196 : {
197 13 : if (this->IsEmpty()) {
198 3 : HCCL_WARNING("[CircularQueue][Tail] Queue is empty!");
199 1 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
200 : }
201 12 : return std::make_shared<Iterator>(elems_.begin() + (tail_ - 1 + capacity_) % capacity_, this);
202 : }
203 :
204 2076 : std::shared_ptr<typename Queue<T>::Iterator> End() const override
205 : {
206 2076 : return std::make_shared<Iterator>(elems_.begin() + tail_, this);
207 : }
208 : };
209 :
210 : } // namespace Hccl
211 : #endif // CIRCULAR_QUEUE_H
|
