LCOV - code coverage report
Current view: top level - lib/generic - queue.h Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 16 17 94.1 %
Date: 2019-03-12 03:31:59
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*  Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
       2             : 
       3             :     This program is free software: you can redistribute it and/or modify
       4             :     it under the terms of the GNU General Public License as published by
       5             :     the Free Software Foundation, either version 3 of the License, or
       6             :     (at your option) any later version.
       7             : 
       8             :     This program is distributed in the hope that it will be useful,
       9             :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      10             :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      11             :     GNU General Public License for more details.
      12             : 
      13             :     You should have received a copy of the GNU General Public License
      14             :     along with this program.  If not, see <http://www.gnu.org/licenses/>.
      15             :  */
      16             : /**
      17             :  * @file queue.h
      18             :  * @brief A queue, usable for FIFO and LIFO simultaneously.
      19             :  *
      20             :  * Both the head and tail of the queue can be accessed and pushed to,
      21             :  * but only the head can be popped from.
      22             :  *
      23             :  * @note The implementation uses a singly linked list of blocks
      24             :  * where each block stores an array of values (for better efficiency).
      25             :  *
      26             :  * Example usage:
      27             :  * @code{.c}
      28             :         // define new queue type, and init a new queue instance
      29             :         typedef queue_t(int) queue_int_t;
      30             :         queue_int_t q;
      31             :         queue_init(q);
      32             :         // do some operations
      33             :         queue_push(q, 1);
      34             :         queue_push(q, 2);
      35             :         queue_push(q, 3);
      36             :         queue_push(q, 4);
      37             :         queue_pop(q);
      38             :         assert(queue_head(q) == 2);
      39             :         assert(queue_tail(q) == 4);
      40             : 
      41             :         // you may iterate
      42             :         typedef queue_it_t(int) queue_it_int_t;
      43             :         for (queue_it_int_t it = queue_it_begin(q); !queue_it_finished(it);
      44             :              queue_it_next(it)) {
      45             :                 ++queue_it_val(it);
      46             :         }
      47             :         assert(queue_tail(q) == 5);
      48             : 
      49             :         queue_push_head(q, 0);
      50             :         ++queue_tail(q);
      51             :         assert(queue_tail(q) == 6);
      52             :         // free it up
      53             :         queue_deinit(q);
      54             : 
      55             :         // you may use dynamic allocation for the type itself
      56             :         queue_int_t *qm = malloc(sizeof(queue_int_t));
      57             :         queue_init(*qm);
      58             :         queue_deinit(*qm);
      59             :         free(qm);
      60             :  * @endcode
      61             :  *
      62             :  * \addtogroup generics
      63             :  * @{
      64             :  */
      65             : 
      66             : #pragma once
      67             : 
      68             : #include "lib/defines.h"
      69             : #include "contrib/ucw/lib.h"
      70             : #include <assert.h>
      71             : #include <stdbool.h>
      72             : #include <stddef.h>
      73             : #include <stdint.h>
      74             : #include <stdlib.h>
      75             : 
      76             : /** @brief The type for queue, parametrized by value type. */
      77             : #define queue_t(type) \
      78             :         union { \
      79             :                 type *pdata_t; /* only the *type* information is used */ \
      80             :                 struct queue queue; \
      81             :         }
      82             : 
      83             : /** @brief Initialize a queue.  You can malloc() it the usual way. */
      84             : #define queue_init(q) do { \
      85             :         (void)(((__typeof__(((q).pdata_t)))0) == (void *)0); /* typecheck queue_t */ \
      86             :         queue_init_impl(&(q).queue, sizeof(*(q).pdata_t)); \
      87             :         } while (false)
      88             : 
      89             : /** @brief De-initialize a queue: make it invalid and free any inner allocations. */
      90             : #define queue_deinit(q) \
      91             :         queue_deinit_impl(&(q).queue)
      92             : 
      93             : /** @brief Push data to queue's tail.  (Type-safe version; use _impl() otherwise.) */
      94             : #define queue_push(q, data) \
      95             :         *((__typeof__((q).pdata_t)) queue_push_impl(&(q).queue)) = data
      96             : 
      97             : /** @brief Push data to queue's head.  (Type-safe version; use _impl() otherwise.) */
      98             : #define queue_push_head(q, data) \
      99             :         *((__typeof__((q).pdata_t)) queue_push_head_impl(&(q).queue)) = data
     100             : 
     101             : /** @brief Remove the element at the head.
     102             :  * The queue must not be empty. */
     103             : #define queue_pop(q) \
     104             :         queue_pop_impl(&(q).queue)
     105             : 
     106             : /** @brief Return a "reference" to the element at the head (it's an L-value).
     107             :  * The queue must not be empty. */
     108             : #define queue_head(q) \
     109             :         ( *(__typeof__((q).pdata_t)) queue_head_impl(&(q).queue) )
     110             : 
     111             : /** @brief Return a "reference" to the element at the tail (it's an L-value).
     112             :  * The queue must not be empty. */
     113             : #define queue_tail(q) \
     114             :         ( *(__typeof__((q).pdata_t)) queue_tail_impl(&(q).queue) )
     115             : 
     116             : /** @brief Return the number of elements in the queue (very efficient). */
     117             : #define queue_len(q) \
     118             :         ((const size_t)(q).queue.len)
     119             : 
     120             : 
     121             : /** @brief Type for queue iterator, parametrized by value type.
     122             :  * It's a simple structure that owns no other resources.
     123             :  * You may NOT use it after doing any push or pop (without _begin again). */
     124             : #define queue_it_t(type) \
     125             :         union { \
     126             :                 type *pdata_t; /* only the *type* information is used */ \
     127             :                 struct queue_it iter; \
     128             :         }
     129             : 
     130             : /** @brief Initialize a queue iterator at the head of the queue.
     131             :  * If you use this in assignment (instead of initialization),
     132             :  * you will unfortunately need to add corresponding type-cast in front.
     133             :  * Beware: there's no type-check between queue and iterator! */
     134             : #define queue_it_begin(q) \
     135             :         { .iter = queue_it_begin_impl(&(q).queue) }
     136             : 
     137             : /** @brief Return a "reference" to the current element (it's an L-value) . */
     138             : #define queue_it_val(it) \
     139             :         ( *(__typeof__((it).pdata_t)) queue_it_val_impl(&(it).iter) )
     140             : 
     141             : /** @brief Test if the iterator has gone past the last element.
     142             :  * If it has, you may not use _val or _next. */
     143             : #define queue_it_finished(it) \
     144             :         queue_it_finished_impl(&(it).iter)
     145             : 
     146             : /** @brief Advance the iterator to the next element. */
     147             : #define queue_it_next(it) \
     148             :         queue_it_next_impl(&(it).iter)
     149             : 
     150             : 
     151             : 
     152             : /* ====================== Internal for the implementation ================== */
     153             : /** @cond internal */
     154             : 
     155             : struct queue;
     156             : /* Non-inline functions are exported to be usable from daemon. */
     157             : void queue_init_impl(struct queue *q, size_t item_size);
     158             : void queue_deinit_impl(struct queue *q);
     159             : void * queue_push_impl(struct queue *q);
     160             : void * queue_push_head_impl(struct queue *q);
     161             : 
     162             : struct queue_chunk;
     163             : struct queue {
     164             :         size_t len;
     165             :         uint16_t chunk_cap, item_size;
     166             :         struct queue_chunk *head, *tail;
     167             : };
     168             : 
     169             : struct queue_chunk {
     170             :         struct queue_chunk *next; /*< head -> ... -> tail */
     171             :         int16_t begin, end, cap, pad_; /*< indices: zero is closest to head */
     172             :         /*< We could fit into uint8_t for example, but the choice of (3+1)*2 bytes
     173             :          * is a compromise between wasting space and getting a good alignment.
     174             :          * In particular, queue_t(type*) will store the pointers on addresses
     175             :          * aligned to the pointer size, in both 64-bit and 32-bit platforms.
     176             :          */
     177             :         char data[];
     178             :         /**< The item data.  We use "char" to satisfy the C99+ aliasing rules.
     179             :          * See C99 section 6.5 Expressions, paragraph 7.
     180             :          * Any type can be accessed through char-pointer,
     181             :          * so we can use a common struct definition
     182             :          * for all types being held.
     183             :          */
     184             : };
     185             : 
     186         273 : static inline void * queue_head_impl(const struct queue *q)
     187             : {
     188         273 :         assert(q);
     189         273 :         struct queue_chunk *h = q->head;
     190         273 :         if (unlikely(!h))
     191           0 :                 return NULL;
     192         273 :         assert(h->end > h->begin);
     193         273 :         return h->data + h->begin * q->item_size;
     194             : }
     195             : 
     196             : static inline void * queue_tail_impl(const struct queue *q)
     197             : {
     198             :         assert(q);
     199             :         struct queue_chunk *t = q->tail;
     200             :         if (unlikely(!t))
     201             :                 return NULL;
     202             :         assert(t->end > t->begin);
     203             :         return t->data + (t->end - 1) * q->item_size;
     204             : }
     205             : 
     206         138 : static inline void queue_pop_impl(struct queue *q)
     207             : {
     208         138 :         assert(q);
     209         138 :         struct queue_chunk *h = q->head;
     210         138 :         assert(h && h->end > h->begin);
     211         138 :         if (h->end - h->begin == 1) {
     212             :                 /* removing the last element in the chunk */
     213         119 :                 q->head = h->next;
     214         119 :                 free(h);
     215             :         } else {
     216          19 :                 ++(h->begin);
     217             :         }
     218         138 :         --(q->len);
     219         138 : }
     220             : 
     221             : 
     222             : struct queue_it {
     223             :         struct queue_chunk *chunk;
     224             :         int16_t pos, item_size;
     225             : };
     226             : 
     227             : static inline struct queue_it queue_it_begin_impl(struct queue *q)
     228             : {
     229             :         assert(q);
     230             :         return (struct queue_it){
     231             :                 .chunk = q->head,
     232             :                 .pos = q->head ? q->head->begin : -1,
     233             :                 .item_size = q->item_size,
     234             :         };
     235             : }
     236             : 
     237             : static inline bool queue_it_finished_impl(struct queue_it *it)
     238             : {
     239             :         return it->chunk == NULL || it->pos >= it->chunk->end;
     240             : }
     241             : 
     242             : static inline void * queue_it_val_impl(struct queue_it *it)
     243             : {
     244             :         assert(!queue_it_finished_impl(it));
     245             :         return it->chunk->data + it->pos * it->item_size;
     246             : }
     247             : 
     248             : static inline void queue_it_next_impl(struct queue_it *it)
     249             : {
     250             :         assert(!queue_it_finished_impl(it));
     251             :         ++(it->pos);
     252             :         if (it->pos < it->chunk->end)
     253             :                 return;
     254             :         it->chunk = it->chunk->next;
     255             :         it->pos = it->chunk ? it->chunk->begin : -1;
     256             : }
     257             : 
     258             : /** @endcond (internal) */
     259             : /** @} (addtogroup generics) */
     260             : 

Generated by: LCOV version 1.13