Skip to content

Latest commit

 

History

History
105 lines (75 loc) · 4.02 KB

README.md

File metadata and controls

105 lines (75 loc) · 4.02 KB
Raw

cqueue

cqueue is a C++20 header-only circular queue container.

Statement Length Reserved Content
cqueue<int> queue; 0 0 -
queue.push(1); 1 8 ➊☉☉☉☉☉☉☉
queue.push(2); 2 8 ➊➁☉☉☉☉☉☉
queue.push(3); 3 8 ➊➁➂☉☉☉☉☉
queue.pop(); 2 8 ☉➋➂☉☉☉☉☉
x = queue[1]; // = 3 2 8 = buffer[(1+1)%8]
for (int i = 4; i <= 8; ++i)
    queue.push(i);		 7 8 ☉➋➂➃➄➅➆➇
queue.push(9); 8 8 ➈➋➂➃➄➅➆➇
queue.push(10); 9 16 ➋➂➃➄➅➆➇➈➉☉☉☉☉☉☉☉
queue.clear(); 0 16 ☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉

cqueue is similar to a std::vector

  • Random access iterators
  • Dynamic memory management
  • Constant time on access, insert and erase operations
  • No external dependences
  • Not thread-safe

... but it behaves like a queue

  • push() add an element at the end
  • pop() remove the first element
  • Cannot insert or remove items in the middle

... where

  • Items are stored 'modulus' n (queue[pos] = buffer[(mFront+pos)%mReserved])
  • Memory new/delete calls are minimized

... having some extras

  • Access index always is checked
  • push_front() support
  • pop_back() support

... and some lacks

  • Comparison operators currently not supported
  • Restricted to C++20 compilers

Motivation

Memory management (alloc/free) done by std::deque is very intense in queue-like operations (push/pop). deque-prof.cpp and cqueue-prof.cpp implements a trivial use case of a queue where we push n items and pop n items repeatedly.

Using std::deque:

> valgrind --leak-check=full --show-leak-kinds=all ./deque-prof
...
==10003== HEAP SUMMARY:
==10003==     in use at exit: 0 bytes in 0 blocks
==10003==   total heap usage: 156,253 allocs, 156,253 frees, 80,073,280 bytes allocated
...

Using gto:cqueue:

> valgrind --leak-check=full --show-leak-kinds=all ./cqueue-prof
...
==10024== HEAP SUMMARY:
==10024==     in use at exit: 0 bytes in 0 blocks
==10024==   total heap usage: 4 allocs, 4 frees, 72,928 bytes allocated
...

Usage

Drop off cqueue.hpp in your project and start using the cqueue.

Read cqueue-example.cpp file to see how to use it.

Testing

# example
make example

# unit tests
make tests

# code coverage
make coverage
firefox coverage/index.html &

Contributors

Name Contribution
Gerard Torrent Initial work
Code maintainer
G. Sliepen Code review (I)
Code review (II)
Toby Speight Code review (II)
372046933 Fix compile
Fix performance issue

License

This project is licensed under the GNU LGPL v3 License - see the LICENSE file for details.