summaryrefslogtreecommitdiffstats
path: root/lib/generic/queue.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/generic/queue.h')
-rw-r--r--lib/generic/queue.h252
1 files changed, 252 insertions, 0 deletions
diff --git a/lib/generic/queue.h b/lib/generic/queue.h
new file mode 100644
index 0000000..418e19c
--- /dev/null
+++ b/lib/generic/queue.h
@@ -0,0 +1,252 @@
+/* Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+/**
+ * @file queue.h
+ * @brief A queue, usable for FIFO and LIFO simultaneously.
+ *
+ * Both the head and tail of the queue can be accessed and pushed to,
+ * but only the head can be popped from.
+ *
+ * @note The implementation uses a singly linked list of blocks ("chunks")
+ * where each block stores an array of values (for better efficiency).
+ *
+ * Example usage:
+ * @code{.c}
+ // define new queue type, and init a new queue instance
+ typedef queue_t(int) queue_int_t;
+ queue_int_t q;
+ queue_init(q);
+ // do some operations
+ queue_push(q, 1);
+ queue_push(q, 2);
+ queue_push(q, 3);
+ queue_push(q, 4);
+ queue_pop(q);
+ assert(queue_head(q) == 2);
+ assert(queue_tail(q) == 4);
+
+ // you may iterate
+ typedef queue_it_t(int) queue_it_int_t;
+ for (queue_it_int_t it = queue_it_begin(q); !queue_it_finished(it);
+ queue_it_next(it)) {
+ ++queue_it_val(it);
+ }
+ assert(queue_tail(q) == 5);
+
+ queue_push_head(q, 0);
+ ++queue_tail(q);
+ assert(queue_tail(q) == 6);
+ // free it up
+ queue_deinit(q);
+
+ // you may use dynamic allocation for the type itself
+ queue_int_t *qm = malloc(sizeof(queue_int_t));
+ queue_init(*qm);
+ queue_deinit(*qm);
+ free(qm);
+ * @endcode
+ *
+ * \addtogroup generics
+ * @{
+ */
+
+#pragma once
+
+#include "lib/defines.h"
+#include "contrib/ucw/lib.h"
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+/** @brief The type for queue, parametrized by value type. */
+#define queue_t(type) \
+ union { \
+ type *pdata_t; /* only the *type* information is used */ \
+ struct queue queue; \
+ }
+
+/** @brief Initialize a queue. You can malloc() it the usual way. */
+#define queue_init(q) do { \
+ (void)(((__typeof__(((q).pdata_t)))0) == (void *)0); /* typecheck queue_t */ \
+ queue_init_impl(&(q).queue, sizeof(*(q).pdata_t)); \
+ } while (false)
+
+/** @brief De-initialize a queue: make it invalid and free any inner allocations. */
+#define queue_deinit(q) \
+ queue_deinit_impl(&(q).queue)
+
+/** @brief Push data to queue's tail. (Type-safe version; use _impl() otherwise.) */
+#define queue_push(q, data) \
+ *((__typeof__((q).pdata_t)) queue_push_impl(&(q).queue)) = data
+
+/** @brief Push data to queue's head. (Type-safe version; use _impl() otherwise.) */
+#define queue_push_head(q, data) \
+ *((__typeof__((q).pdata_t)) queue_push_head_impl(&(q).queue)) = data
+
+/** @brief Remove the element at the head.
+ * The queue must not be empty. */
+#define queue_pop(q) \
+ queue_pop_impl(&(q).queue)
+
+/** @brief Return a "reference" to the element at the head (it's an L-value).
+ * The queue must not be empty. */
+#define queue_head(q) \
+ ( *(__typeof__((q).pdata_t)) queue_head_impl(&(q).queue) )
+
+/** @brief Return a "reference" to the element at the tail (it's an L-value).
+ * The queue must not be empty. */
+#define queue_tail(q) \
+ ( *(__typeof__((q).pdata_t)) queue_tail_impl(&(q).queue) )
+
+/** @brief Return the number of elements in the queue (very efficient). */
+#define queue_len(q) \
+ ((const size_t)(q).queue.len)
+
+
+/** @brief Type for queue iterator, parametrized by value type.
+ * It's a simple structure that owns no other resources.
+ * You may NOT use it after doing any push or pop (without _begin again). */
+#define queue_it_t(type) \
+ union { \
+ type *pdata_t; /* only the *type* information is used */ \
+ struct queue_it iter; \
+ }
+
+/** @brief Initialize a queue iterator at the head of the queue.
+ * If you use this in assignment (instead of initialization),
+ * you will unfortunately need to add corresponding type-cast in front.
+ * Beware: there's no type-check between queue and iterator! */
+#define queue_it_begin(q) \
+ { .iter = queue_it_begin_impl(&(q).queue) }
+
+/** @brief Return a "reference" to the current element (it's an L-value) . */
+#define queue_it_val(it) \
+ ( *(__typeof__((it).pdata_t)) queue_it_val_impl(&(it).iter) )
+
+/** @brief Test if the iterator has gone past the last element.
+ * If it has, you may not use _val or _next. */
+#define queue_it_finished(it) \
+ queue_it_finished_impl(&(it).iter)
+
+/** @brief Advance the iterator to the next element. */
+#define queue_it_next(it) \
+ queue_it_next_impl(&(it).iter)
+
+
+
+/* ====================== Internal for the implementation ================== */
+/** @cond internal */
+
+struct queue;
+/* Non-inline functions are exported to be usable from daemon. */
+KR_EXPORT void queue_init_impl(struct queue *q, size_t item_size);
+KR_EXPORT void queue_deinit_impl(struct queue *q);
+KR_EXPORT void * queue_push_impl(struct queue *q);
+KR_EXPORT void * queue_push_head_impl(struct queue *q);
+
+struct queue_chunk;
+struct queue {
+ size_t len; /**< the current number of items in queue */
+ uint16_t chunk_cap; /**< max. number of items in each chunk */
+ uint16_t item_size; /**< sizeof() each item */
+ struct queue_chunk *head, *tail; /*< first and last chunk (or NULLs) */
+};
+
+struct queue_chunk {
+ struct queue_chunk *next; /*< *head -> ... -> *tail; each is non-empty */
+ int16_t begin, end, cap, pad_; /*< indices: zero is closest to head */
+ /*< We could fit into uint8_t for example, but the choice of (3+1)*2 bytes
+ * is a compromise between wasting space and getting a good alignment.
+ * In particular, queue_t(type*) will store the pointers on addresses
+ * aligned to the pointer size, on both 64-bit and 32-bit platforms.
+ */
+ char data[];
+ /**< The item data. We use "char" to satisfy the C99+ aliasing rules.
+ * See C99 section 6.5 Expressions, paragraph 7.
+ * Any type can be accessed through char-pointer,
+ * so we can use a common struct definition
+ * for all types being held.
+ */
+};
+
+static inline void * queue_head_impl(const struct queue *q)
+{
+ assert(q);
+ struct queue_chunk *h = q->head;
+ assert(h && h->end > h->begin);
+ return h->data + h->begin * q->item_size;
+}
+
+static inline void * queue_tail_impl(const struct queue *q)
+{
+ assert(q);
+ struct queue_chunk *t = q->tail;
+ assert(t && t->end > t->begin);
+ return t->data + (t->end - 1) * q->item_size;
+}
+
+static inline void queue_pop_impl(struct queue *q)
+{
+ assert(q);
+ struct queue_chunk *h = q->head;
+ assert(h && h->end > h->begin);
+ if (h->end - h->begin == 1) {
+ /* removing the last element in the chunk */
+ assert((q->len == 1) == (q->head == q->tail));
+ if (q->len == 1) {
+ q->tail = NULL;
+ assert(!h->next);
+ } else {
+ assert(h->next);
+ }
+ q->head = h->next;
+ free(h);
+ } else {
+ ++(h->begin);
+ }
+ --(q->len);
+}
+
+
+struct queue_it {
+ struct queue_chunk *chunk;
+ int16_t pos, item_size;
+};
+
+static inline struct queue_it queue_it_begin_impl(struct queue *q)
+{
+ assert(q);
+ return (struct queue_it){
+ .chunk = q->head,
+ .pos = q->head ? q->head->begin : -1,
+ .item_size = q->item_size,
+ };
+}
+
+static inline bool queue_it_finished_impl(struct queue_it *it)
+{
+ return it->chunk == NULL || it->pos >= it->chunk->end;
+}
+
+static inline void * queue_it_val_impl(struct queue_it *it)
+{
+ assert(!queue_it_finished_impl(it));
+ return it->chunk->data + it->pos * it->item_size;
+}
+
+static inline void queue_it_next_impl(struct queue_it *it)
+{
+ assert(!queue_it_finished_impl(it));
+ ++(it->pos);
+ if (it->pos < it->chunk->end)
+ return;
+ it->chunk = it->chunk->next;
+ it->pos = it->chunk ? it->chunk->begin : -1;
+}
+
+/** @endcond (internal) */
+/** @} (addtogroup generics) */
+