SPDX-FileCopyrightText: 2019 Jean-Louis Fuchs <ganwell@fangorn.ch>

SPDX-License-Identifier: AGPL-3.0-or-later
   
=================
Queue / Stack 0.8
=================

Queue and stack with a rbtree-style interface. Both queue and stack use one
next pointer and can be described as linked lists, except that the queue is
actually an ring.

Installation
============

Copy qs.h into your source.

Development
===========

See `README.rst`_

.. _`README.rst`: https://github.com/concretecloud/rbtree

API
===

Queue
-----

qs_queue_bind_decl_m(context, type) alias rb_bind_decl_cx_m
   Bind the qs_queue function declarations for *type* to *context*. Usually
   used in a header.

qs_queue_bind_impl_m(context, type)
   Bind the qs_queue function implementations for *type* to *context*.
   Usually used in a c-file. This variant uses the standard rb_*_m traits.

qs_queue_bind_impl_cx_m(context, type)
   Bind the qs_queue function implementations for *type* to *context*.
   Usually used in a c-file. This variant uses cx##_*_m traits, which means
   you have to define them.

qs_queue_bind_cx_m/qs_queue_bind_m(context, type)
   Shortcut to bind declaration and implementation at once.

Then the following functions will be available.

cx##_enqueue(type** queue, type* item)
   Enqueue an item to the queue.

cx##_dequeue(type** queue, type** item)
   Dequeue an item from the queue. Queue will be set to NULL when empty.

cx##_head(type* queue, type* item)
   *item* will be set to the item in front of the queue, which equals the
   oldest item or the item that is going to be dequeud. Is NULL when the
   queue is empty.

cx##_head(type* queue, type* item)
   *item* will be set to the item in the back of the queue, which equals the
   newest item. Is NULL when the queue is empty.

cx##_iter_init(type* tree, cx##_iter_t* iter, type** elem)
   Initializes *elem* to point to the first element in the queue. Use
   qs_queue_iter_decl_m to declare *iter* and *elem*. If the queue is empty
   *elem* will be a NULL-pointer.

cx##_iter_next(cx##_iter_t* iter, type** elem)
   Move *elem* to the next element in the queue. *elem* will point to
   NULL at the end.

cx##_top(type* stack, type* item)
   *item* will be set to the item on top of the stack.

You can use rb_for_m from rbtree.h with qs.

Stack
-----

qs_stack_bind_decl_m(context, type) alias rb_bind_decl_cx_m
   Bind the qs_stack function declarations for *type* to *context*. Usually
   used in a header.

qs_stack_bind_impl_m(context, type)
   Bind the qs_stack function implementations for *type* to *context*.
   Usually used in a c-file. This variant uses the standard rb_*_m traits.

qs_stack_bind_impl_cx_m(context, type)
   Bind the qs_stack function implementations for *type* to *context*.
   Usually used in a c-file. This variant uses cx##_*_m traits, which means
   you have to define them.

qs_stack_bind_cx_m/qs_stack_bind_m(context, type)
   Shortcut to bind declaration and implementation at once.

Then the following functions will be available.

cx##_push(type** stack, type* item)
   Push an item to the stack.

cx##_pop(type** stack, type** item)
   Pop an item from the stack. Stack will be set to NULL when empty.

cx##_iter_init(type* tree, cx##_iter_t* iter, type** elem)
   Initializes *elem* to point to the first element in the stack. Use
   qs_stack_iter_decl_m to declare *iter* and *elem*. If the stack is empty
   *elem* will be a NULL-pointer.

cx##_iter_next(cx##_iter_t* iter, type** elem)
   Move *elem* to the next element in the stack. *elem* will point to
   NULL at the end.

You can use rb_for_m from rbtree.h with qs.

Implementation
==============

Includes
--------

.. code-block:: cpp

   #ifndef qs_stack_queue_h
   #define qs_stack_queue_h
   #include <assert.h>
   
Traits
------

.. code-block:: cpp

   #define qs_next_m(x) (x)->next
   
Queue
-----

Common arguments

next
   Get the next item of the queue


.. code-block:: text

   .---.        .---.
   | 2 |<-next--| 1 |
   '---'        '---'
     |next        ^
     v        next|
   .---.        .---.
   | 3 |--next->| 4 |<--queue--
   '---'        '---'

qs_enqueue_m
------------

Bound: cx##_enqueue

Enqueues an item to the queue.

queue
   Beginning of the queue

item
   Item to enqueue.

.. code-block:: cpp

   #begindef qs_enqueue_m(
           next,
           queue,
           item
   )
   {
       assert(next(item) == NULL && "Item already in use");
       if(queue == NULL) {
           next(item) = item;
       } else {
           next(item) = next(queue);
           next(queue) = item;
       }
       queue = item;
   }
   #enddef
   
qs_dequeue_m
------------

Bound: cx##_dequeue

Dequeue an item from the queue. Returns the first item in the queue (FIFO).
Does nothing if the queue is empty.

queue
   Beginning of the queue

item
   Item dequeued.

.. code-block:: cpp

   #begindef qs_dequeue_m(
           next,
           queue,
           item
   )
   {
       if(queue != NULL) {
           item = next(queue);
           if(next(queue) == queue) {
               queue = NULL;
           } else {
               next(queue) = next(item);
           }
           next(item) = NULL;
       } else {
           item = NULL;
       }
   }
   #enddef
   
qs_queue_bind_decl_m
--------------------

Alias: qs_queue_bind_decl_cx_m

Bind queue functions to a context. This only generates declarations.

cx
   Name of the new context.

type
   The type of the items of the queue.

.. code-block:: cpp

   #begindef qs_queue_bind_decl_m(cx, type)
       typedef type cx##_iter_t;
       typedef type cx##_type_t;
       void
       cx##_enqueue(
               type** queue,
               type* item
       );
       void
       cx##_dequeue(
               type** queue,
               type** item
       );
       void
       cx##_iter_init(
               type* queue,
               cx##_iter_t** iter,
               type** elem
       );
       void
       cx##_iter_next(
               cx##_iter_t* iter,
               type** elem
       );
       void
       cx##_head(
               type* queue,
               type** item
       );
       void
       cx##_tail(
               type* queue,
               type** item
       );
   #enddef
   
   #begindef qs_queue_bind_decl_cx_m(cx, type)
       qs_queue_bind_decl_m(cx, type)
   #enddef
   
qs_queue_bind_impl_m
---------------------

Bind queue functions to a context. This only generates implementations.

qs_queue_bind_impl_m uses qs_next_m. qs_queue_bind_impl_cx_m uses
cx##_next_m.

cx
   Name of the new context.

type
   The type of the items of the queue.

.. code-block:: cpp

   #begindef _qs_queue_bind_impl_tr_m(cx, type, next)
       void
       cx##_enqueue(
               type** queue,
               type* item
       ) qs_enqueue_m(
               next,
               *queue,
               item
       )
       void
       cx##_dequeue(
               type** queue,
               type** item
       ) qs_dequeue_m(
               next,
               *queue,
               *item
       )
       void
       cx##_iter_init(
               type* queue,
               cx##_iter_t** iter,
               type** elem
       )
       {
           qs_queue_iter_init_m(
               next,
               queue,
               *iter,
               *elem
           );
       }
       void
       cx##_iter_next(
               cx##_iter_t* iter,
               type** elem
       )
       {
           qs_queue_iter_next_m(
               next,
               iter,
               *elem
           )
       }
       void
       cx##_head(
               type* queue,
               type** item
       ) {
           if(queue != NULL) {
               *item = next(queue);
           } else {
               *item = NULL;
           }
       }
       void
       cx##_tail(
               type* queue,
               type** item
       ) {
           *item = queue;
       }
   #enddef
   
   #begindef qs_queue_bind_impl_cx_m(cx, type)
       _qs_queue_bind_impl_tr_m(cx, type, cx##_next_m)
   #enddef
   
   #begindef qs_queue_bind_impl_m(cx, type)
       _qs_queue_bind_impl_tr_m(cx, type, qs_next_m)
   #enddef
   
   #begindef qs_queue_bind_cx_m(cx, type)
       qs_queue_bind_decl_cx_m(cx, type)
       qs_queue_bind_impl_cx_m(cx, type)
   #enddef
   
   #begindef qs_queue_bind_m(cx, type)
       qs_queue_bind_decl_m(cx, type)
       qs_queue_bind_impl_m(cx, type)
   #enddef
   
qs_queue_iter_decl_m
---------------------

Also: qs_queue_iter_decl_cx_m

Declare iterator variables.

iter
   The new iterator variable.

elem
   The pointer to the current element.

.. code-block:: cpp

   #begindef qs_queue_iter_decl_m(type, iter, elem)
       type* iter = NULL;
       type* elem = NULL;
   #enddef
   
   #begindef qs_queue_iter_decl_cx_m(cx, iter, elem)
       cx##_type_t* iter = NULL;
       cx##_type_t* elem = NULL;
   #enddef
   
qs_queue_iter_init_m
---------------------

Bound: cx##_iter_init

Initialize iterator. It will point to the first element or NULL if the queue
is empty.

queue
   The queue.

iter
   The iterator.

elem
   The pointer to the current element.


.. code-block:: cpp

   #begindef qs_queue_iter_init_m(next, queue, iter, elem)
   {
       iter = queue;
       if(queue == NULL) {
           elem = NULL;
       } else {
           elem = next(queue);
       }
   }
   #enddef
   
qs_queue_iter_next_m
--------------------

Bound: cx##_iter_next

Initialize iterator. It will point to the first element. The element will be
NULL, if the iteration is at the end.

queue
   The queue.

elem
   The pointer to the current element.

.. code-block:: cpp

   #begindef qs_queue_iter_next_m(
           next,
           queue,
           elem
   )
   {
       if(elem == queue) {
           elem = NULL;
       } else {
           elem = next(elem);
       }
   }
   #enddef
   
   
Stack
-----

Common arguments

next
   Get the next item of the stack

qs_push_m
---------

Bound: cx##_push

Push an item to the stack.

stack
   Base pointer to the stack.

item
   Item to push.

.. code-block:: cpp

   #begindef qs_push_m(
           next,
           stack,
           item
   )
   {
       assert(next(item) == NULL && "Item already in use");
       next(item) = stack;
       stack = item;
   }
   #enddef
   
qs_pop_m
--------

Bound: cx##_pop

Pop an item from the stack. Returns the last item in the stack (LIFO).
Does nothing if the stack is empty.

stack
   Base pointer to the stack.

item
   Item popped.

.. code-block:: cpp

   #begindef qs_pop_m(
           next,
           stack,
           item
   )
   {
       item = stack;
       if(stack != NULL) {
           stack = next(stack);
           next(item) = NULL;
       }
   }
   #enddef
   
qs_stack_bind_decl_m
--------------------

Alias: qs_stack_bind_decl_cx_m

Bind stack functions to a context. This only generates declarations.

cx
   Name of the new context.

type
   The type of the items of the stack.

.. code-block:: cpp

   #begindef qs_stack_bind_decl_m(cx, type)
       typedef type cx##_iter_t;
       typedef type cx##_type_t;
       void
       cx##_push(
               type** stack,
               type* item
       );
       void
       cx##_pop(
               type** stack,
               type** item
       );
       void
       cx##_iter_init(
               type* stack,
               cx##_iter_t** iter,
               type** elem
       );
       void
       cx##_iter_next(
               cx##_iter_t* iter,
               type** elem
       );
       void
       cx##_top(
               type* stack,
               type** item
       );
   #enddef
   
   #define qs_stack_bind_decl_cx_m(cx, type) qs_stack_bind_decl_m(cx, type)
   
qs_stack_bind_impl_m
---------------------

Bind stack functions to a context. This only generates implementations.

qs_stack_bind_impl_m uses qs_next_m. qs_stack_bind_impl_cx_m uses
cx##_next_m.

cx
   Name of the new context.

type
   The type of the items of the stack.

.. code-block:: cpp

   #begindef _qs_stack_bind_impl_tr_m(cx, type, next)
       void
       cx##_push(
               type** stack,
               type* item
       ) qs_push_m(
               next,
               *stack,
               item
       )
       void
       cx##_pop(
               type** stack,
               type** item
       ) qs_pop_m(
               next,
               *stack,
               *item
       )
       void
       cx##_iter_init(
               type* stack,
               cx##_iter_t** iter,
               type** elem
       )
       {
           (void)(iter);
           qs_stack_iter_init_m(
               next,
               stack,
               *elem
           );
       }
       void
       cx##_iter_next(
               cx##_iter_t* iter,
               type** elem
       )
       {
           (void)(iter);
           qs_stack_iter_next_m(
               next,
               *elem
           )
       }
       void
       cx##_top(
               type* stack,
               type** item
       ) {
           *item = stack;
       }
   #enddef
   
   #begindef qs_stack_bind_impl_cx_m(cx, type)
       _qs_stack_bind_impl_tr_m(cx, type, cx##_next_m)
   #enddef
   
   #begindef qs_stack_bind_impl_m(cx, type)
       _qs_stack_bind_impl_tr_m(cx, type, qs_next_m)
   #enddef
   
   #begindef qs_stack_bind_cx_m(cx, type)
       qs_stack_bind_decl_cx_m(cx, type)
       qs_stack_bind_impl_cx_m(cx, type)
   #enddef
   
   #begindef qs_stack_bind_m(cx, type)
       qs_stack_bind_decl_m(cx, type)
       qs_stack_bind_impl_m(cx, type)
   #enddef
   
qs_stack_iter_decl_m
---------------------

Also: qs_stack_iter_decl_cx_m

Declare iterator variables.

iter
   The new iterator variable.

elem
   The pointer to the current element.

.. code-block:: cpp

   #begindef qs_stack_iter_decl_m(type, iter, elem)
       type* iter = NULL;
       type* elem = NULL;
   #enddef
   
   #begindef qs_stack_iter_decl_cx_m(cx, iter, elem)
       cx##_type_t* iter = NULL;
       cx##_type_t* elem = NULL;
   #enddef
   
qs_stack_iter_init_m
---------------------

Bound: cx##_iter_init

Initialize iterator. It will point to the first element or NULL if the stack
is empty.

stack
   Base pointer to the stack.

elem
   The pointer to the current element.


.. code-block:: cpp

   #begindef qs_stack_iter_init_m(next, stack, elem)
   {
       elem = stack;
   }
   #enddef
   
qs_stack_iter_next_m
--------------------

Bound: cx##_iter_next

Initialize iterator. It will point to the first element. The element will be
NULL, if the iteration is at the end.

elem
   The pointer to the current element.

.. code-block:: cpp

   #begindef qs_stack_iter_next_m(
           next,
           elem
   )
   {
       elem = next(elem);
   }
   #enddef
   #endif //qs_stack_queue_h
