path: root/lib/generic/queue.h

/*  Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    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 <http://www.gnu.org/licenses/>.
 */
/**
 * @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 <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. */
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) */