generic_queue.h

/*  License: MIT. See end of file.

    Overview:
        This implementation is heavily based on macros (it's nothing but
        macros). In order to get actual functions and structs they need to be
        instantiated. Two helpers are provided for this: DECLARATIONS_Queue(T)
        and DEFINITIONS_Queue(T). Place DECLARATIONS_Queue(T) in one (1) header
        file. Place DEFINITIONS_Queue(T) in one (1) source file which includes
        that header file. Define GENERIC_QUEUE_IMPL before including. Replace T
        with your desired type. See example below

        Optionally define GENERIC_QUEUE_MULTITHREADED before including
        `generic_queue.h` in the header to enable automatic locking of the queue
        when enqueueing, dequeueing and getting the size of the queue.


    API:
        Types:
            Queue(T);                             // opaque Queue type.
        Functions:
            Queue(T) *newQueue(T)();              // allocate a new queue
            void deleteQueue(T)(Queue(T) *);      // Deallocate a queue
            void enqueue(T)(Queue(T) *, T);       // Push an item onto the queue
            T dequeue(T)(Queue(T) *);             // Pop an item from the queue (returns the popped item)
                                                  // Note: if the queue is empty, the behaviour is undefined
            int tryDequeue(T)(Queue(T)*, T *item) // If the queue is not empty, pop an item from the queue,
                                                  // assign it to `item` and return 1.
                                                  // If the queue is empty, do not change `item` and return 0.
            size_t getSize(T)(Queue(T) *)         // Get number of elements in the queue (O(n) operation)
            int getSize(T)(Queue(T) *)            // 0 if queue is not empty (O(1) operation)

            // only with GENERIC_QUEUE_MULTITHREADED
            pthread_mutex_t *getMutex(T)(Queue(T) *)    // Get a pointer to the mutex lock


Notes on thread safety when using GENERIC_QUEUE_MULTITHREADED:

        `isEmpty` does not lock the queue (as it just does a single pointer comparison).

        The following pattern IS NOT THREAD SAFE (unless used in a multi-producer-single-consumer pattern)
        ```
        Queue(T) *q; // shared between threads
        void thread_fn(void *_) {
            if(!isEmpty(T)(q)) {
                // another thread may have already dequeued the last item in the queue
                // in which case this would be undefined behaviour
                T t = dequeue(T)(q);
            }
        }
        ```

        `tryDequeue` can be used instead

        ```
        void thread_fn(void *_) {
            T item;
            if(tryDequeue(T)(q, &item)) {
                // use item
            }
        }
        ```

    Example:
        // queue.h

        // #define GENERIC_QUEUE_MULTITHREADED // optional
        #include "generic_queue.h"
        DECLARATIONS_Queue(int);

        // queue.c
        #define GENERIC_QUEUE_IMPL
        #include "queue.h"
        DEFINITIONS_Queue(int);

        // source.c
        #include "queue.h"

        Queue(int) *q = newQueue(int)();
        enqueue(int)(q, 42);
        enqueue(int)(q, 23);
        assert(dequeue(int)(q) == 42);
        assert(getSize(int)(q) == 1);
        int item;
        assert(tryDequeue(q, &item));
        assert(item == 23);
        assert(isEmpty(int)(q));
        item = 3;
        assert(!tryDequeue(q, &item));
        assert(item == 3);
        deleteQueue(int)(q);
*/

#ifndef GENERIC_QUEUE_H
#    define GENERIC_QUEUE_H
#    include <assert.h>
#    include <stddef.h>
#    include <stdlib.h>

// Public Types

#    define Queue(T) struct Queue_##T

// Public Functions

#    define newQueue(T)               newQueue_##T
#    define FUNCTION_DECL_newQueue(T) Queue(T) * newQueue(T)()


#    define deleteQueue(T)               deleteQueue_##T
#    define FUNCTION_DECL_deleteQueue(T) void deleteQueue(T)(Queue(T) * q)

#    define enqueue(T)               enqueue_##T
#    define FUNCTION_DECL_enqueue(T) void enqueue(T)(Queue(T) * q, T i)


#    define dequeue(T)               dequeue_##T
#    define FUNCTION_DECL_dequeue(T) T dequeue(T)(Queue(T) * q)

#    define tryDequeue(T)               tryDequeue_##T
#    define FUNCTION_DECL_tryDequeue(T) int tryDequeue(T)(Queue(T) * q, T * item)

#    define getSize(T)               getSize_##T
#    define FUNCTION_DECL_getSize(T) size_t getSize(T)(Queue(T) * q)

#    define isEmpty(T)               isEmpty_##T
#    define FUNCTION_DECL_isEmpty(T) int isEmpty(T)(Queue(T) * q)

#    ifdef GENERIC_QUEUE_MULTITHREADED
#        include <pthread.h>
#        define getMutex(T)               getMutex_##T
#        define FUNCTION_DECL_getMutex(T) pthread_mutex_t *getMutex(T)(Queue(T) * q)
#    else
#        define FUNCTION_DECL_getMutex(T)
#    endif

// Public declarations
#    define DECLARATIONS_Queue(T)     \
        Queue(T);                     \
        FUNCTION_DECL_getMutex(T);    \
        FUNCTION_DECL_isEmpty(T);     \
        FUNCTION_DECL_getSize(T);     \
        FUNCTION_DECL_dequeue(T);     \
        FUNCTION_DECL_tryDequeue(T);  \
        FUNCTION_DECL_enqueue(T);     \
        FUNCTION_DECL_deleteQueue(T); \
        FUNCTION_DECL_newQueue(T);


#    ifdef GENERIC_QUEUE_IMPL
// Private Types

#        ifdef NDEBUG
#            define SE_ASSERT(X) (X)
#        else
#            define SE_ASSERT(X) assert(X)
#        endif

#        ifdef GENERIC_QUEUE_MULTITHREADED
#            define ADD_LOCK(L)     pthread_mutex_t L;
#            define INIT_LOCK(L)    SE_ASSERT(pthread_mutex_init(L, NULL) == 0)
#            define TAKE_LOCK(L)    SE_ASSERT(pthread_mutex_lock(L) == 0)
#            define RELEASE_LOCK(L) SE_ASSERT(pthread_mutex_unlock(L) == 0)
#            define DESTROY_LOCK(L) SE_ASSERT(pthread_mutex_destroy(L) == 0);
#        else
#            define ADD_LOCK(L)
#            define INIT_LOCK(L)
#            define TAKE_LOCK(L)
#            define RELEASE_LOCK(L)
#            define DESTROY_LOCK(L)
#        endif

#        define QueueItem(T) struct QueueItem_##T
#        define ItemPair(T)  ItemPair_##T##_t

#        define STRUCT_Queue(T)              \
            Queue(T) {                       \
                struct QueueItem_##T *front; \
                ADD_LOCK(lock)               \
            }


#        define STRUCT_QueueItem(T)         \
            QueueItem(T) {                  \
                struct QueueItem_##T *next; \
                T payload;                  \
            }


#        define STRUCT_ItemPair(T)            \
            typedef struct ItemPair_##T {     \
                struct QueueItem_##T *first;  \
                struct QueueItem_##T *second; \
            } ItemPair(T)


// Private Functions
#        define newQueueItem(T) newQueueItem_##T

#        define FUNCTION_DECL_newQueueItem(T) QueueItem(T) * newQueueItem(T)(T payload)

#        define FUNCTION_DEF_newQueueItem(T)                                    \
            FUNCTION_DECL_newQueueItem(T) {                                     \
                QueueItem(T) *q = (QueueItem(T) *)malloc(sizeof(QueueItem(T))); \
                q->next = NULL;                                                 \
                q->payload = payload;                                           \
                return q;                                                       \
            }

#        define deleteQueueItem(T) deleteQueueItem_##T

#        define FUNCTION_DECL_deleteQueueItem(T) void deleteQueueItem(T)(QueueItem(T) * qi)

#        define FUNCTION_DEF_deleteQueueItem(T) \
            FUNCTION_DECL_deleteQueueItem(T) {  \
                free(qi);                       \
            }

#        define findLastTwo(T) findLastTwo_##T

#        define FUNCTION_DECL_findLastTwo(T) ItemPair(T) findLastTwo(T)(QueueItem(T) * qi)

#        define FUNCTION_DEF_findLastTwo(T)                \
            FUNCTION_DECL_findLastTwo(T) {                 \
                assert(qi);                                \
                ItemPair(T) lastTwo = {qi, qi->next};      \
                if (!qi->next) return lastTwo;             \
                while (lastTwo.second->next) {             \
                    lastTwo.first = lastTwo.second;        \
                    lastTwo.second = lastTwo.second->next; \
                }                                          \
                return lastTwo;                            \
            }

#        define FUNCTION_DEF_newQueue(T)                            \
            FUNCTION_DECL_newQueue(T) {                             \
                Queue(T) *q = (Queue(T) *)malloc(sizeof(Queue(T))); \
                assert(q);                                          \
                q->front = NULL;                                    \
                INIT_LOCK(&q->lock);                                \
                return q;                                           \
            }

#        define FUNCTION_DEF_deleteQueue(T)             \
            FUNCTION_DECL_deleteQueue(T) {              \
                while (q->front) {                      \
                    QueueItem(T) *tmp = q->front->next; \
                    q->front->next = NULL;              \
                    deleteQueueItem(T)(q->front);       \
                    q->front = tmp;                     \
                }                                       \
                DESTROY_LOCK(&q->lock);                 \
                free(q);                                \
            }

#        define FUNCTION_DEF_enqueue(T)                      \
            FUNCTION_DECL_enqueue(T) {                       \
                assert(q);                                   \
                TAKE_LOCK(&q->lock);                         \
                QueueItem(T) *newFront = newQueueItem(T)(i); \
                newFront->next = q->front;                   \
                q->front = newFront;                         \
                RELEASE_LOCK(&q->lock);                      \
            }


#        define FUNCTION_DEF_dequeue(T)             \
            FUNCTION_DECL_dequeue(T) {              \
                T item;                             \
                SE_ASSERT(tryDequeue(T)(q, &item)); \
                return item;                        \
            }

#        define FUNCTION_DEF_tryDequeue(T)                      \
            FUNCTION_DECL_tryDequeue(T) {                       \
                assert(q);                                      \
                assert(item);                                   \
                                                                \
                if (!q->front) return 0;                        \
                                                                \
                TAKE_LOCK(&q->lock);                            \
                ItemPair(T) lastTwo = findLastTwo(T)(q->front); \
                                                                \
                if (lastTwo.second) {                           \
                    lastTwo.first->next = NULL;                 \
                    *item = lastTwo.second->payload;            \
                    deleteQueueItem(T)(lastTwo.second);         \
                } else {                                        \
                    *item = lastTwo.first->payload;             \
                    deleteQueueItem(T)(lastTwo.first);          \
                    q->front = NULL;                            \
                }                                               \
                RELEASE_LOCK(&q->lock);                         \
                return 1;                                       \
            }

#        define FUNCTION_DEF_getSize(T)         \
            FUNCTION_DECL_getSize(T) {          \
                TAKE_LOCK(&q->lock);            \
                QueueItem(T) *front = q->front; \
                size_t i;                       \
                for (i = 0; front; i++) {       \
                    front = front->next;        \
                }                               \
                RELEASE_LOCK(&q->lock);         \
                return i;                       \
            }

#        define FUNCTION_DEF_isEmpty(T) \
            FUNCTION_DECL_isEmpty(T) {  \
                return !q->front;       \
            }

#        ifdef GENERIC_QUEUE_MULTITHREADED
#            define FUNCTION_DEF_getMutex(T) \
                FUNCTION_DECL_getMutex(T) {  \
                    return &q->lock;         \
                }
#        else
#            define FUNCTION_DEF_getMutex(T)
#        endif


// Private definitions
#        define DEFINITIONS_Queue(T)          \
            STRUCT_Queue(T);                  \
            STRUCT_QueueItem(T);              \
            STRUCT_ItemPair(T);               \
            FUNCTION_DECL_deleteQueueItem(T); \
            FUNCTION_DECL_newQueueItem(T);    \
            FUNCTION_DEF_newQueueItem(T);     \
            FUNCTION_DEF_deleteQueueItem(T);  \
            FUNCTION_DEF_newQueue(T);         \
            FUNCTION_DEF_deleteQueue(T);      \
            FUNCTION_DECL_findLastTwo(T);     \
            FUNCTION_DEF_findLastTwo(T);      \
            FUNCTION_DEF_enqueue(T);          \
            FUNCTION_DEF_dequeue(T);          \
            FUNCTION_DEF_tryDequeue(T);       \
            FUNCTION_DEF_getSize(T);          \
            FUNCTION_DEF_isEmpty(T);          \
            FUNCTION_DEF_getMutex(T);


#    endif  // GENERIC_QUEUE_IMPL
#endif      // GENERIC_QUEUE_H
/*MIT License

Copyright (c) 2022-2024 dk949

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/