FastArduino  v1.7
C++ library to build fast but small Arduino/AVR projects
queue.h
Go to the documentation of this file.
1 // Copyright 2016-2021 Jean-Francois Poilpret
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
16 
21 #ifndef QUEUE_HH
22 #define QUEUE_HH
23 
24 #include "utilities.h"
25 #include "time.h"
26 
27 namespace containers
28 {
58  template<typename T_, typename TREF_ = const T_&> class Queue
59  {
60  public:
61  Queue(const Queue<T_, TREF_>&) = delete;
62  Queue<T_, TREF_>& operator=(const Queue<T_, TREF_>&) = delete;
63 
65  using T = T_;
66 
68  using TREF = TREF_;
69 
78  template<uint8_t SIZE> explicit Queue(T (&buffer)[SIZE], bool locked = false)
79  : buffer_{buffer}, size_{SIZE}, locked_{locked} {}
80 
86  void lock()
87  {
88  locked_ = true;
89  }
90 
96  void unlock()
97  {
98  locked_ = false;
99  }
100 
106  bool is_locked() const
107  {
108  return locked_;
109  }
110 
126  bool push_(TREF item);
127 
145  bool pull_(T& item);
146 
165  bool peek_(T& item) const;
166 
188  uint8_t peek_(T* buffer, uint8_t size) const;
189 
212  template<uint8_t SIZE> uint8_t peek_(T (&buffer)[SIZE]) const;
213 
219  uint8_t size() const
220  {
221  return size_ - 1;
222  }
223 
233  bool empty_() const
234  {
235  return tail_ == head_;
236  }
237 
246  bool full_() const
247  {
248  return (tail_ + 1) == (head_ ? head_ : size_);
249  }
250 
259  uint8_t items_() const
260  {
261  // - must be 0 when head_ = tail_
262  // - must be size_ - 1 max, when tail_ = head_ - 1
263  return tail_ - head_ + (tail_ >= head_ ? 0 : size_);
264  }
265 
275  uint8_t free_() const
276  {
277  // - must be 0 when tail_ = head_ - 1
278  // - must be size_ - 1, when head_ == tail_
279  // We simply return size_ - 1 - items_() but we optimize it a bit
280  return head_ - tail_ - 1 + (tail_ >= head_ ? size_ : 0);
281  }
282 
291  void clear_()
292  {
293  head_ = tail_ = 0;
294  }
295 
311  bool push(TREF item)
312  {
313  synchronized return push_(item);
314  }
315 
333  bool pull(T& item)
334  {
335  synchronized return pull_(item);
336  }
337 
356  bool peek(T& item) const
357  {
358  synchronized return peek_(item);
359  }
360 
382  uint8_t peek(T* buffer, uint8_t size) const
383  {
384  synchronized return peek_(buffer, size);
385  }
386 
409  template<uint8_t SIZE> uint8_t peek(T (&buffer)[SIZE]) const
410  {
411  synchronized return peek_(buffer);
412  }
413 
420  bool empty() const
421  {
422  synchronized return empty_();
423  }
424 
432  uint8_t items() const
433  {
434  synchronized return items_();
435  }
436 
446  uint8_t free() const
447  {
448  synchronized return free_();
449  }
450 
459  bool full() const
460  {
461  synchronized return full_();
462  }
463 
472  void clear()
473  {
474  synchronized clear_();
475  }
476 
477  private:
478  T* const buffer_;
479  const uint8_t size_;
480  bool locked_;
481  volatile uint8_t head_ = 0;
482  volatile uint8_t tail_ = 0;
483  };
484 
486  template<typename T, typename TREF> bool Queue<T, TREF>::peek_(T& item) const
487  {
488  if (tail_ == head_) return false;
489  item = buffer_[head_];
490  return true;
491  }
492 
493  template<typename T, typename TREF> uint8_t Queue<T, TREF>::peek_(T* buffer, uint8_t size) const
494  {
495  size = (size <= items_()) ? size : items_();
496  if (size)
497  {
498  // Split peek in 2 parts if needed
499  if (head_ < tail_)
500  {
501  const T* source = &buffer_[head_];
502  for (uint8_t i = 0; i < size; ++i) *buffer++ = *source++;
503  }
504  else
505  {
506  uint8_t part_size = size_ - head_;
507  if (part_size > size) part_size = size;
508  const T* source = &buffer_[head_];
509  for (uint8_t i = 0; i < part_size; ++i) *buffer++ = *source++;
510 
511  if (size > part_size)
512  {
513  part_size = size - part_size;
514  source = buffer_;
515  for (uint8_t i = 0; i < part_size; ++i) *buffer++ = *source++;
516  }
517  }
518  }
519  return size;
520  }
521 
522  template<typename T, typename TREF> template<uint8_t SIZE> uint8_t Queue<T, TREF>::peek_(T (&buffer)[SIZE]) const
523  {
524  return peek_(&buffer[0], SIZE);
525  }
526 
527  template<typename T, typename TREF> bool Queue<T, TREF>::push_(TREF item)
528  {
529  if (locked_ || full_()) return false;
530  buffer_[tail_] = item;
531  ++tail_;
532  if (tail_ == size_) tail_ = 0;
533  return true;
534  }
535 
536  template<typename T, typename TREF> bool Queue<T, TREF>::pull_(T& item)
537  {
538  if (empty_()) return false;
539  item = buffer_[head_];
540  ++head_;
541  if (head_ == size_) head_ = 0;
542  return true;
543  }
545 
556  template<typename T, typename TREF> T pull(Queue<T, TREF>& queue)
557  {
558  T item;
559  while (!queue.pull(item)) time::yield();
560  return item;
561  }
562 
573  template<typename T, typename TREF> T peek(Queue<T, TREF>& queue)
574  {
575  T item;
576  while (!queue.peek(item)) time::yield();
577  return item;
578  }
579 }
580 
581 #endif /* QUEUE_HH */
582 
containers::Queue::free_
uint8_t free_() const
Tell the current number of available locations for items to be pushed to this queue.
Definition: queue.h:275
containers::Queue::lock
void lock()
Lock this queue, ie prevent pushing any data to it.
Definition: queue.h:86
containers::Queue::free
uint8_t free() const
Tell the current number of available locations for items to be pushed to this queue.
Definition: queue.h:446
containers::Queue::size
uint8_t size() const
Get the maximum size of this queue.
Definition: queue.h:219
containers::Queue::pull
bool pull(T &item)
Pull an item from the beginning of this queue, if not empty, and copy it into item.
Definition: queue.h:333
containers::Queue::peek
uint8_t peek(T *buffer, uint8_t size) const
Peek up to size items from the beginning of this queue, if not empty, and copy these into buffer arra...
Definition: queue.h:382
containers::Queue
Queue of type T_ items.
Definition: queue.h:59
containers::Queue::pull_
bool pull_(T &item)
Pull an item from the beginning of this queue, if not empty, and copy it into item.
time::yield
void yield()
Utility method used by many FastArduino API in order to "yield" some processor time; concretely it ju...
Definition: time.cpp:22
containers::Queue::clear
void clear()
Completely clear this queue.
Definition: queue.h:472
containers::Queue::full_
bool full_() const
Tell if this queue is currently full.
Definition: queue.h:246
containers::Queue::push
bool push(TREF item)
Push item to the end of this queue, provided there is still available space in its ring buffer.
Definition: queue.h:311
containers
Contains all FastArduino generic containers:
Definition: array.h:23
containers::Queue::items
uint8_t items() const
Tell the current number of items currently present in this queue.
Definition: queue.h:432
time.h
Simple time utilities.
containers::peek
T peek(Queue< T, TREF > &queue)
Peek an item from the beginning of queue.
Definition: queue.h:573
containers::Queue::peek_
uint8_t peek_(T *buffer, uint8_t size) const
Peek up to size items from the beginning of this queue, if not empty, and copy these into buffer arra...
containers::Queue::empty_
bool empty_() const
Tell if this queue is currently empty.
Definition: queue.h:233
containers::Queue::full
bool full() const
Tell if this queue is currently full.
Definition: queue.h:459
containers::pull
T pull(Queue< T, TREF > &queue)
Pull an item from the beginning of queue.
Definition: queue.h:556
containers::Queue::Queue
Queue(T(&buffer)[SIZE], bool locked=false)
Create a new queue, based on the provided buffer array.
Definition: queue.h:78
utilities.h
General utilities API that have broad application in programs.
containers::Queue::push_
bool push_(TREF item)
Push item to the end of this queue, provided there is still available space in its ring buffer.
containers::Queue< uint8_t, uint8_t >::T
uint8_t T
The type of items in this queue.
Definition: queue.h:65
containers::Queue::items_
uint8_t items_() const
Tell the current number of items currently present in this queue.
Definition: queue.h:259
containers::Queue< uint8_t, uint8_t >::TREF
uint8_t TREF
The constant reference type of items in this queue.
Definition: queue.h:68
containers::Queue::peek
uint8_t peek(T(&buffer)[SIZE]) const
Peek up to SIZE items from the beginning of this queue, if not empty, and copy these into buffer arra...
Definition: queue.h:409
containers::Queue::peek_
bool peek_(T &item) const
Peek an item from the beginning of this queue, if not empty, and copy it into item.
containers::Queue::empty
bool empty() const
Tell if this queue is currently empty.
Definition: queue.h:420
containers::Queue::peek
bool peek(T &item) const
Peek an item from the beginning of this queue, if not empty, and copy it into item.
Definition: queue.h:356
containers::Queue::is_locked
bool is_locked() const
Check if this queue is locked, ie if pushing data to it is disabled.
Definition: queue.h:106
containers::Queue::peek_
uint8_t peek_(T(&buffer)[SIZE]) const
Peek up to SIZE items from the beginning of this queue, if not empty, and copy these into buffer arra...
containers::Queue::unlock
void unlock()
Unlock this queue, ie allow pushing data to it.
Definition: queue.h:96
containers::Queue::clear_
void clear_()
Completely clear this queue.
Definition: queue.h:291