| 1 |
ron |
1 |
/**
|
|
|
2 |
* Marlin 3D Printer Firmware
|
|
|
3 |
* Copyright (C) 2016 MarlinFirmware [https://github.com/MarlinFirmware/Marlin]
|
|
|
4 |
*
|
|
|
5 |
* Based on Sprinter and grbl.
|
|
|
6 |
* Copyright (C) 2011 Camiel Gubbels / Erik van der Zalm
|
|
|
7 |
*
|
|
|
8 |
* This program is free software: you can redistribute it and/or modify
|
|
|
9 |
* it under the terms of the GNU General Public License as published by
|
|
|
10 |
* the Free Software Foundation, either version 3 of the License, or
|
|
|
11 |
* (at your option) any later version.
|
|
|
12 |
*
|
|
|
13 |
* This program is distributed in the hope that it will be useful,
|
|
|
14 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
15 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
16 |
* GNU General Public License for more details.
|
|
|
17 |
*
|
|
|
18 |
* You should have received a copy of the GNU General Public License
|
|
|
19 |
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
|
20 |
*
|
|
|
21 |
*/
|
|
|
22 |
|
|
|
23 |
#ifndef __CIRCULARQUEUE_H__
|
|
|
24 |
#define __CIRCULARQUEUE_H__
|
|
|
25 |
|
|
|
26 |
#include <Arduino.h>
|
|
|
27 |
|
|
|
28 |
/**
|
|
|
29 |
* @brief Circular Queue class
|
|
|
30 |
* @details Implementation of the classic ring buffer data structure
|
|
|
31 |
*/
|
|
|
32 |
template<typename T, uint8_t N>
|
|
|
33 |
class CircularQueue {
|
|
|
34 |
private:
|
|
|
35 |
|
|
|
36 |
/**
|
|
|
37 |
* @brief Buffer structure
|
|
|
38 |
* @details This structure consolidates all the overhead required to handle
|
|
|
39 |
* a circular queue such as the pointers and the buffer vector.
|
|
|
40 |
*/
|
|
|
41 |
struct buffer_t {
|
|
|
42 |
uint8_t head;
|
|
|
43 |
uint8_t tail;
|
|
|
44 |
uint8_t count;
|
|
|
45 |
uint8_t size;
|
|
|
46 |
T queue[N];
|
|
|
47 |
} buffer;
|
|
|
48 |
|
|
|
49 |
public:
|
|
|
50 |
/**
|
|
|
51 |
* @brief Class constructor
|
|
|
52 |
* @details This class requires two template parameters, T defines the type
|
|
|
53 |
* of item this queue will handle and N defines the maximum number of
|
|
|
54 |
* items that can be stored on the queue.
|
|
|
55 |
*/
|
|
|
56 |
CircularQueue<T, N>() {
|
|
|
57 |
this->buffer.size = N;
|
|
|
58 |
this->buffer.count = this->buffer.head = this->buffer.tail = 0;
|
|
|
59 |
}
|
|
|
60 |
|
|
|
61 |
/**
|
|
|
62 |
* @brief Removes and returns a item from the queue
|
|
|
63 |
* @details Removes the oldest item on the queue, pointed to by the
|
|
|
64 |
* buffer_t head field. The item is returned to the caller.
|
|
|
65 |
* @return type T item
|
|
|
66 |
*/
|
|
|
67 |
T dequeue() {
|
|
|
68 |
if (this->isEmpty()) return T();
|
|
|
69 |
|
|
|
70 |
uint8_t index = this->buffer.head;
|
|
|
71 |
|
|
|
72 |
--this->buffer.count;
|
|
|
73 |
if (++this->buffer.head == this->buffer.size)
|
|
|
74 |
this->buffer.head = 0;
|
|
|
75 |
|
|
|
76 |
return this->buffer.queue[index];
|
|
|
77 |
}
|
|
|
78 |
|
|
|
79 |
/**
|
|
|
80 |
* @brief Adds an item to the queue
|
|
|
81 |
* @details Adds an item to the queue on the location pointed by the buffer_t
|
|
|
82 |
* tail variable. Returns false if no queue space is available.
|
|
|
83 |
* @param item Item to be added to the queue
|
|
|
84 |
* @return true if the operation was successful
|
|
|
85 |
*/
|
|
|
86 |
bool enqueue(T const &item) {
|
|
|
87 |
if (this->isFull()) return false;
|
|
|
88 |
|
|
|
89 |
this->buffer.queue[this->buffer.tail] = item;
|
|
|
90 |
|
|
|
91 |
++this->buffer.count;
|
|
|
92 |
if (++this->buffer.tail == this->buffer.size)
|
|
|
93 |
this->buffer.tail = 0;
|
|
|
94 |
|
|
|
95 |
return true;
|
|
|
96 |
}
|
|
|
97 |
|
|
|
98 |
/**
|
|
|
99 |
* @brief Checks if the queue has no items
|
|
|
100 |
* @details Returns true if there are no items on the queue, false otherwise.
|
|
|
101 |
* @return true if queue is empty
|
|
|
102 |
*/
|
|
|
103 |
bool isEmpty() {
|
|
|
104 |
return this->buffer.count == 0;
|
|
|
105 |
}
|
|
|
106 |
|
|
|
107 |
/**
|
|
|
108 |
* @brief Checks if the queue is full
|
|
|
109 |
* @details Returns true if the queue is full, false otherwise.
|
|
|
110 |
* @return true if queue is full
|
|
|
111 |
*/
|
|
|
112 |
bool isFull() {
|
|
|
113 |
return this->buffer.count == this->buffer.size;
|
|
|
114 |
}
|
|
|
115 |
|
|
|
116 |
/**
|
|
|
117 |
* @brief Gets the queue size
|
|
|
118 |
* @details Returns the maximum number of items a queue can have.
|
|
|
119 |
* @return the queue size
|
|
|
120 |
*/
|
|
|
121 |
uint8_t size() {
|
|
|
122 |
return this->buffer.size;
|
|
|
123 |
}
|
|
|
124 |
|
|
|
125 |
/**
|
|
|
126 |
* @brief Gets the next item from the queue without removing it
|
|
|
127 |
* @details Returns the next item in the queue without removing it
|
|
|
128 |
* or updating the pointers.
|
|
|
129 |
* @return first item in the queue
|
|
|
130 |
*/
|
|
|
131 |
T peek() {
|
|
|
132 |
return this->buffer.queue[this->buffer.head];
|
|
|
133 |
}
|
|
|
134 |
|
|
|
135 |
/**
|
|
|
136 |
* @brief Gets the number of items on the queue
|
|
|
137 |
* @details Returns the current number of items stored on the queue.
|
|
|
138 |
* @return number of items in the queue
|
|
|
139 |
*/
|
|
|
140 |
uint8_t count() {
|
|
|
141 |
return this->buffer.count;
|
|
|
142 |
}
|
|
|
143 |
};
|
|
|
144 |
|
|
|
145 |
#endif
|