From 3d0386f27ca66379acf50199e1d1298386eeeeb8 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 6 May 2024 02:55:53 +0200 Subject: Adding upstream version 3.2.1. Signed-off-by: Daniel Baumann --- lib/generic/queue.h | 260 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 260 insertions(+) create mode 100644 lib/generic/queue.h (limited to 'lib/generic/queue.h') diff --git a/lib/generic/queue.h b/lib/generic/queue.h new file mode 100644 index 0000000..755e759 --- /dev/null +++ b/lib/generic/queue.h @@ -0,0 +1,260 @@ +/* Copyright (C) 2018 CZ.NIC, z.s.p.o. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + */ +/** + * @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 + * 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 +#include +#include +#include +#include + +/** @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. */ +void queue_init_impl(struct queue *q, size_t item_size); +void queue_deinit_impl(struct queue *q); +void * queue_push_impl(struct queue *q); +void * queue_push_head_impl(struct queue *q); + +struct queue_chunk; +struct queue { + size_t len; + uint16_t chunk_cap, item_size; + struct queue_chunk *head, *tail; +}; + +struct queue_chunk { + struct queue_chunk *next; /*< head -> ... -> tail */ + 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, in 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; + if (unlikely(!h)) + return NULL; + assert(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; + if (unlikely(!t)) + return NULL; + assert(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 */ + 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) */ + -- cgit v1.2.3