deque.h

// SPDX-License-Identifier: MIT
// Copyright (c) 2021 Michael Bäck <mhcoma@gmail.com>

#ifndef __CCTL_DEQUE_H__
#define __CCTL_DEQUE_H__

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#include "cctl.h"

#define cctl_deque_chunk_max 512

// Deque Chunk

/// `chunk(T)` ⇒ `T_chunk`
/// 
/// Generates the internal chunk container type name for `deque(T)`.
#define chunk(T) cctl_join(T, chunk)

/// `chunk_func(FUNC, T)` ⇒ `T_chunk_FUNC`
/// 
/// Generates a mangled function identifier for `chunk(T)`.
#define chunk_func(FUNC, T) cctl_join(chunk(T), FUNC)

/// `chunk_struct(T)` ⇒ `struct T_chunk_struct`
/// 
/// Generates the underlying structure tag for `chunk(T)`.
#define chunk_struct(T) cctl_join(chunk(T), struct)

/// ```c
/// T* chunk_front(T, chunk(T)* p_c)
/// ```
/// Returns a pointer to the first element in the chunk.
#define chunk_front(T, p_c) chunk_func(at, T)(p_c, 0)

/// ```c
/// T* chunk_back(T, chunk(T)* p_c)
/// ```
/// Returns a pointer to the last element in the chunk.
#define chunk_back(T, p_c) chunk_func(at, T)(p_c, (p_c)->size - 1)

/// Declares chunk struct and function prototypes in a header file.
#define chunk_imp_h(T) \
	typedef struct chunk_struct(T) chunk(T); \
	\
	struct chunk_struct(T) { \
		T* p_data; \
		size_t begin; \
		size_t size; \
	}; \
	\
	void chunk_func(init, T)(chunk(T)* p_c); \
	void chunk_func(free, T)(chunk(T)* p_c); \
	void chunk_func(clear, T)(chunk(T)* p_c); \
	bool chunk_func(push_front, T)(chunk(T)* p_c, T item); \
	bool chunk_func(pop_front, T)(chunk(T)* p_c); \
	bool chunk_func(push_back, T)(chunk(T)* p_c, T item); \
	bool chunk_func(pop_back, T)(chunk(T)* p_c); \
	T* chunk_func(at, T)(chunk(T)* p_c, size_t index);

/// Implements chunk functions in a source file.
#define chunk_imp_c(T) \
	void chunk_func(init, T)(chunk(T)* p_c) { \
		memset(p_c, 0, sizeof(chunk(T))); \
	} \
	\
	void chunk_func(free, T)(chunk(T)* p_c) { \
		if (p_c->p_data) free(p_c->p_data); \
		chunk_func(init, T)(p_c); \
	} \
	\
	void chunk_func(clear, T)(chunk(T)* p_c) { \
		p_c->begin = 0; \
		p_c->size = 0; \
	} \
	\
	bool chunk_func(push_front, T)(chunk(T)* p_c, T item) { \
		if (p_c->size == cctl_deque_chunk_max) return false; \
		if (!p_c->p_data) { \
			if (!(p_c->p_data = (T*) malloc(cctl_deque_chunk_max * sizeof(T)))) return false; \
		} \
		p_c->begin = (p_c->begin + cctl_deque_chunk_max - 1) % cctl_deque_chunk_max; \
		*(p_c->p_data + p_c->begin) = item; \
		p_c->size++; \
		return true; \
	} \
	\
	bool chunk_func(pop_front, T)(chunk(T)* p_c) { \
		if (p_c->size == 0) return false; \
		p_c->begin = (p_c->begin + 1) % cctl_deque_chunk_max; \
		p_c->size--; \
		return true; \
	} \
	\
	bool chunk_func(push_back, T)(chunk(T)* p_c, T item) { \
		if (p_c->size == cctl_deque_chunk_max) return false; \
		if (!p_c->p_data) { \
			if (!(p_c->p_data = (T*) malloc(cctl_deque_chunk_max * sizeof(T)))) return false; \
		} \
		size_t end_index = (p_c->begin + p_c->size) % cctl_deque_chunk_max; \
		*(p_c->p_data + end_index) = item; \
		p_c->size++; \
		return true; \
	} \
	\
	bool chunk_func(pop_back, T)(chunk(T)* p_c) { \
		if (p_c->size == 0) return false; \
		p_c->size--; \
		return true; \
	} \
	\
	T* chunk_func(at, T)(chunk(T)* p_c, size_t index) { \
		return p_c->p_data + ((p_c->begin + index) % cctl_deque_chunk_max); \
	}


// Deque Iterator

/// `deque_iterator(T)` ⇒ `T_deque_iterator`
/// 
/// Generates the iterator type name for `deque(T)`.
#define deque_iterator(T) cctl_join(T, deque_iterator)

/// `deque_iterator_func(FUNC, T)` ⇒ `T_deque_iterator_FUNC`
/// 
/// Generates a mangled function identifier for `deque_iterator(T)`.
#define deque_iterator_func(FUNC, T) cctl_join(deque_iterator(T), FUNC)

/// `deque_iterator_struct(T)` ⇒ `struct T_deque_iterator_struct`
/// 
/// Generates the underlying structure tag for `deque_iterator(T)`.
#define deque_iterator_struct(T) cctl_join(deque_iterator(T), struct)

/// ```c
/// T* deque_iterator_get(T, deque_iterator(T)* p_it)
/// ```
/// Returns a pointer to the element currently referenced by the iterator.
#define deque_iterator_get(T, p_it) deque_func(at, T)((p_it)->p_d, (p_it)->index)

/// ```c
/// bool deque_iterator_is_valid(T, deque_iterator(T)* p_it)
/// ```
/// Checks whether the iterator currently points to a valid element within bounds.
#define deque_iterator_is_valid(T, p_it) ((p_it)->p_d && (p_it)->index < (p_it)->p_d->size)

/// ```c
/// bool deque_iterator_is_equal(T, deque_iterator(T)* p_it1, deque_iterator(T)* p_it2)
/// ```
/// Checks whether two iterators point to the same deque and index.
#define deque_iterator_is_equal(T, p_it1, p_it2) ((p_it1)->p_d == (p_it2)->p_d && (p_it1)->index == (p_it2)->index)

/// ```c
/// void deque_iterator_next(T, deque_iterator(T)* p_it)
/// ```
/// Advances the iterator forward to the next element.
#define deque_iterator_next(T, p_it) ((p_it)->index++)

/// ```c
/// void deque_iterator_prev(T, deque_iterator(T)* p_it)
/// ```
/// Moves the iterator backward to the previous element.
#define deque_iterator_prev(T, p_it) ((p_it)->index--)

/// ```c
/// bool deque_iterator_insert_after(T, deque_iterator(T)* p_it, T item)
/// ```
/// Inserts `item` immediately after the current iterator position.
#define deque_iterator_insert_after(T, p_it, item) deque_iterator_func(insert_after, T)(p_it, item)

/// ```c
/// bool deque_iterator_insert_before(T, deque_iterator(T)* p_it, T item)
/// ```
/// Inserts `item` immediately before the current iterator position.
#define deque_iterator_insert_before(T, p_it, item) deque_iterator_func(insert_before, T)(p_it, item)

/// ```c
/// bool deque_iterator_remove(T, deque_iterator(T)* p_it)
/// ```
/// Removes the element at the current iterator position.
#define deque_iterator_remove(T, p_it) deque_iterator_func(remove, T)(p_it)

/// Declares deque iterator struct and function prototypes in a header file.
#define deque_iterator_imp_h(T) \
	typedef struct deque_iterator_struct(T) deque_iterator(T); \
	struct deque_iterator_struct(T) { \
		deque(T)* p_d; \
		size_t index; \
	}; \
	\
	bool deque_iterator_func(insert_after, T)(deque_iterator(T)* p_it, T item); \
	bool deque_iterator_func(insert_before, T)(deque_iterator(T)* p_it, T item); \
	bool deque_iterator_func(remove, T)(deque_iterator(T)* p_it);

/// Implements deque iterator functions in a source file.
#define deque_iterator_imp_c(T) \
	bool deque_iterator_func(insert_after, T)(deque_iterator(T)* p_it, T item) { \
		if (!p_it || !deque_iterator_is_valid(T, p_it)) return false; \
		T none; \
		memset(&none, 0, sizeof(T)); \
		if (!deque_func(push_back, T)(p_it->p_d, none)) return false; \
		for (size_t i = p_it->p_d->size - 1; i > p_it->index + 1; i--) { \
			T* p_curr = deque_func(at, T)(p_it->p_d, i); \
			T* p_prev = deque_func(at, T)(p_it->p_d, i - 1); \
			*p_curr = *p_prev; \
		} \
		*deque_func(at, T)(p_it->p_d, p_it->index + 1) = item; \
		return true; \
	} \
	\
	bool deque_iterator_func(insert_before, T)(deque_iterator(T)* p_it, T item) { \
		if (!p_it || !deque_iterator_is_valid(T, p_it)) return false; \
		T none; \
		memset(&none, 0, sizeof(T)); \
		if (!deque_func(push_back, T)(p_it->p_d, none)) return false; \
		for (size_t i = p_it->p_d->size - 1; i > p_it->index; i--) { \
			T* p_curr = deque_func(at, T)(p_it->p_d, i); \
			T* p_prev = deque_func(at, T)(p_it->p_d, i - 1); \
			*p_curr = *p_prev; \
		} \
		*deque_func(at, T)(p_it->p_d, p_it->index) = item; \
		p_it->index++;\
		return true; \
	} \
	\
	bool deque_iterator_func(remove, T)(deque_iterator(T)* p_it) { \
		if (!p_it || !deque_iterator_is_valid(T, p_it)) return false; \
		for (size_t i = p_it->index; i < p_it->p_d->size - 1; i++) { \
			T* p_curr = deque_func(at, T)(p_it->p_d, i); \
			T* p_next = deque_func(at, T)(p_it->p_d, i + 1); \
			*p_curr = *p_next; \
		} \
		deque_func(pop_back, T)(p_it->p_d); \
		return true; \
	}


// Deque

/// `deque(T)` ⇒ `T_deque`
/// 
/// Generates the double-ended queue container type name for `T`.
#define deque(T) cctl_join(T, deque)

/// `deque_chunk_func(FUNC, T)` ⇒ `T_deque_chunk_FUNC`
/// 
/// Generates a mangled function identifier for internal deque chunk operations.
#define deque_chunk_func(FUNC, T) cctl_join(cctl_join(deque(T), chunk), FUNC)

/// `deque_func(FUNC, T)` ⇒ `T_deque_FUNC`
/// 
/// Generates a mangled function identifier for `deque(T)`.
#define deque_func(FUNC, T) cctl_join(deque(T), FUNC)

/// `deque_struct(T)` ⇒ `struct T_deque_struct`
/// 
/// Generates the underlying structure tag for `deque(T)`.
#define deque_struct(T) cctl_join(deque(T), struct)

/// ```c
/// void deque_init(T, deque(T)* p_d)
/// ```
/// Initializes the deque to an empty state.
/// 
/// `p_d` is a pointer to the deque instance. Must be called before any other operations.
#define deque_init(T, p_d) deque_func(init, T)(p_d)

#define deque_new_1(T) deque_func(new, T)(0)
#define deque_new_2(T, size) deque_func(new, T)(size)

/// ```c
/// deque(T) deque_new(T, [size_t size])
/// ```
/// Constructs and returns an initialized deque, optionally pre-allocated and zero-initialized with `size` elements.
#define deque_new(...) cctl_dispatch(deque_new, __VA_ARGS__)(__VA_ARGS__)

/// ```c
/// deque(T) deque_from_items(T, ...)
/// ```
/// Constructs and returns an initialized deque containing all items provided in `...`.
#define deque_from_items(T, ...) \
	deque_func(from_items, T)((const T[]) { __VA_ARGS__ }, sizeof((const T[]) { __VA_ARGS__ }) / sizeof(T))

/// ```c
/// bool deque_extend_items(T, deque(T)* p_d, ...)
/// ```
/// Appends multiple items provided in `...` to the end of the deque.
#define deque_extend_items(T, p_d, ...) \
	deque_func(extend_items, T)(p_d, (const T[]) { __VA_ARGS__ }, sizeof((const T[]) { __VA_ARGS__ }) / sizeof(T))

/// ```c
/// void deque_free(T, deque(T)* p_d)
/// ```
/// Frees all dynamically allocated memory of the deque and resets it to an empty state.
#define deque_free(T, p_d) deque_func(free, T)(p_d)

/// ```c
/// void deque_clear(T, deque(T)* p_d)
/// ```
/// Clears all elements from the deque and deallocates active chunks.
#define deque_clear(T, p_d) deque_func(clear, T)(p_d)

/// ```c
/// bool deque_resize(T, deque(T)* p_d, size_t size)
/// ```
/// Resizes the deque to contain `size` elements.
#define deque_resize(T, p_d, size) deque_func(resize, T)(p_d, size)

/// ```c
/// bool deque_push_front(T, deque(T)* p_d, T item)
/// ```
/// Prepends `item` to the beginning of the deque.
/// 
/// Returns `true` on success, or `false` on allocation failure.
#define deque_push_front(T, p_d, item) deque_func(push_front, T)(p_d, item)

/// ```c
/// bool deque_pop_front(T, deque(T)* p_d)
/// ```
/// Removes the first element from the deque.
/// 
/// Returns `true` on success, or `false` if the deque is empty.
#define deque_pop_front(T, p_d) deque_func(pop_front, T)(p_d)

/// ```c
/// bool deque_push_back(T, deque(T)* p_d, T item)
/// ```
/// Appends `item` to the end of the deque.
/// 
/// Returns `true` on success, or `false` on allocation failure.
#define deque_push_back(T, p_d, item) deque_func(push_back, T)(p_d, item)

/// ```c
/// bool deque_pop_back(T, deque(T)* p_d)
/// ```
/// Removes the last element from the deque.
/// 
/// Returns `true` on success, or `false` if the deque is empty.
#define deque_pop_back(T, p_d) deque_func(pop_back, T)(p_d)

/// ```c
/// chunk(T)* deque_chunk_front(T, deque(T)* p_d)
/// ```
/// Returns a pointer to the first active chunk in the deque.
#define deque_chunk_front(T, p_d) deque_chunk_func(at, T)(p_d, 0)

/// ```c
/// chunk(T)* deque_chunk_back(T, deque(T)* p_d)
/// ```
/// Returns a pointer to the last active chunk in the deque.
#define deque_chunk_back(T, p_d) deque_chunk_func(at, T)(p_d, (p_d)->chunk_count - 1)

/// ```c
/// T* deque_at(T, deque(T)* p_d, size_t index)
/// ```
/// Returns a pointer to the element at `index` in the deque.
#define deque_at(T, p_d, index) deque_func(at, T)(p_d, index)

/// ```c
/// T* deque_front(T, deque(T)* p_d)
/// ```
/// Returns a pointer to the first element in the deque, or `NULL` if empty.
#define deque_front(T, p_d) ((p_d)->size ? chunk_front(T, deque_chunk_front(T, p_d)) : NULL)

/// ```c
/// T* deque_back(T, deque(T)* p_d)
/// ```
/// Returns a pointer to the last element in the deque, or `NULL` if empty.
#define deque_back(T, p_d) ((p_d)->size ? chunk_back(T, deque_chunk_back(T, p_d)) : NULL)

/// ```c
/// bool deque_is_empty(T, deque(T)* p_d)
/// ```
/// Checks whether the deque contains no elements.
#define deque_is_empty(T, p_d) ((p_d)->size == 0)

/// ```c
/// size_t deque_size(T, deque(T)* p_d)
/// ```
/// Returns the current number of elements in the deque as a read-only rvalue.
#define deque_size(T, p_d) ((size_t)((p_d)->size))

/// ```c
/// size_t deque_capacity(T, deque(T)* p_d)
/// ```
/// Returns the total element capacity of the currently allocated chunks as a read-only rvalue.
#define deque_capacity(T, p_d) ((size_t)((p_d)->chunk_count * cctl_deque_chunk_max))

/// ```c
/// bool deque_shrink_to_fit(T, deque(T)* p_d)
/// ```
/// Reduces chunk allocation to fit the active chunks and frees empty buffers.
/// 
/// Returns `true` on success, or `false` on reallocation failure.
#define deque_shrink_to_fit(T, p_d) deque_func(shrink_to_fit, T)(p_d)

/// ```c
/// deque_iterator(T) deque_begin(T, deque(T)* p_d)
/// ```
/// Returns an iterator pointing to the first element in the deque.
#define deque_begin(T, p_d) deque_func(begin, T)(p_d)

/// ```c
/// deque_iterator(T) deque_end(T, deque(T)* p_d)
/// ```
/// Returns an iterator pointing past the last element in the deque.
#define deque_end(T, p_d) deque_func(end, T)(p_d)

/// ```c
/// deque_iterator(T) deque_rbegin(T, deque(T)* p_d)
/// ```
/// Returns a reverse iterator pointing to the last element in the deque.
#define deque_rbegin(T, p_d) deque_func(rbegin, T)(p_d)

/// ```c
/// deque_iterator(T) deque_rend(T, deque(T)* p_d)
/// ```
/// Returns a reverse iterator pointing before the first element in the deque.
#define deque_rend(T, p_d) deque_func(rend, T)(p_d)

/// ```c
/// deque_iterator(T) deque_seek(T, deque(T)* p_d, size_t index)
/// ```
/// Returns an iterator pointing to the element at `index`.
#define deque_seek(T, p_d, index) deque_func(seek, T)(p_d, index)

/// ```c
/// deque_foreach(T, deque(T)* p_d, IT_NAME)
/// ```
/// Iterates over all elements in the deque in forward order.
#define deque_foreach(T, p_d, it) for (deque_iterator(T) it = deque_begin(T, p_d); deque_iterator_is_valid(T, &it); deque_iterator_next(T, &it))

/// ```c
/// deque_rforeach(T, deque(T)* p_d, IT_NAME)
/// ```
/// Iterates over all elements in the deque in reverse order.
#define deque_rforeach(T, p_d, it) for (deque_iterator(T) it = deque_rbegin(T, p_d); deque_iterator_is_valid(T, &it); deque_iterator_prev(T, &it))

/// Forward declares the `deque(T)` container type for prior references.
#define deque_fd(T) \
	typedef struct deque_struct(T) deque(T);

/// Declares deque struct and function prototypes in a header file.
#define deque_imp_h(T) \
	chunk_imp_h(T); \
	deque_iterator_imp_h(T); \
	\
	struct deque_struct(T) { \
		chunk(T)* p_data; \
		size_t chunk_begin; \
		size_t chunk_count; \
		size_t chunk_capacity; \
		size_t size; \
	}; \
	\
	void deque_func(init, T)(deque(T)* p_d); \
	deque(T) deque_func(new, T)(size_t size); \
	deque(T) deque_func(from_items, T)(const T* p_items, size_t count); \
	bool deque_func(extend_items, T)(deque(T)* p_d, const T* p_items, size_t count); \
	void deque_func(free, T)(deque(T)* p_d); \
	void deque_func(clear, T)(deque(T)* p_d); \
	bool deque_func(resize, T)(deque(T)* p_d, size_t size); \
	bool deque_func(shrink_to_fit, T)(deque(T)* p_d); \
	\
	bool deque_chunk_func(reserve, T)(deque(T)* p_d, size_t capacity); \
	chunk(T)* deque_chunk_func(at, T)(deque(T)* p_d, size_t index); \
	bool deque_chunk_func(push_front, T)(deque(T)* p_d); \
	bool deque_chunk_func(push_back, T)(deque(T)* p_d); \
	bool deque_chunk_func(pop_front, T)(deque(T)* p_d); \
	bool deque_chunk_func(pop_back, T)(deque(T)* p_d); \
	\
	bool deque_func(push_front, T)(deque(T)* p_d, T item); \
	bool deque_func(pop_front, T)(deque(T)* p_d); \
	bool deque_func(push_back, T)(deque(T)* p_d, T item); \
	bool deque_func(pop_back, T)(deque(T)* p_d); \
	T* deque_func(at, T)(deque(T)* p_d, size_t index); \
	deque_iterator(T) deque_func(begin, T)(deque(T)* p_d); \
	deque_iterator(T) deque_func(end, T)(deque(T)* p_d); \
	deque_iterator(T) deque_func(rbegin, T)(deque(T)* p_d); \
	deque_iterator(T) deque_func(rend, T)(deque(T)* p_d); \
	deque_iterator(T) deque_func(seek, T)(deque(T)* p_d, size_t index);

/// Implements deque functions in a source file.
#define deque_imp_c(T) \
	chunk_imp_c(T); \
	deque_iterator_imp_c(T); \
	\
	void deque_func(init, T)(deque(T)* p_d) { \
		memset(p_d, 0, sizeof(deque(T))); \
	} \
	\
	deque(T) deque_func(new, T)(size_t size) { \
		deque(T) d; \
		deque_func(init, T)(&d); \
		if (size > 0) { \
			if (!deque_func(resize, T)(&d, size)) { \
				deque_func(free, T)(&d); \
			} \
		} \
		return d; \
	} \
	\
	deque(T) deque_func(from_items, T)(const T* p_items, size_t count) { \
		deque(T) d; \
		deque_func(init, T)(&d); \
		if (p_items && count > 0) { \
			if (!deque_func(extend_items, T)(&d, p_items, count)) { \
				deque_func(free, T)(&d); \
			} \
		} \
		return d; \
	} \
	\
	bool deque_func(extend_items, T)(deque(T)* p_d, const T* p_items, size_t count) { \
		if (!p_d || !p_items || count == 0) return true; \
		for (size_t i = 0; i < count; i++) { \
			if (!deque_func(push_back, T)(p_d, p_items[i])) return false; \
		} \
		return true; \
	} \
	\
	void deque_func(free, T)(deque(T)* p_d) { \
		deque_func(clear, T)(p_d); \
		if (p_d->p_data) free(p_d->p_data); \
		deque_func(init, T)(p_d); \
	} \
	\
	void deque_func(clear, T)(deque(T)* p_d) { \
		for (size_t i = 0; i < p_d->chunk_count; i++) { \
			chunk_func(free, T)(deque_chunk_func(at, T)(p_d, i)); \
		} \
		p_d->size = 0; \
		p_d->chunk_begin = 0; \
		p_d->chunk_count = 0; \
	} \
	\
	bool deque_func(resize, T)(deque(T)* p_d, size_t size) { \
		if (p_d->size == size) return true; \
		if (p_d->size > size) { \
			while (p_d->size > size) { \
				if (!deque_func(pop_back, T)(p_d)) return false; \
			} \
			return true; \
		} \
		else { \
			T none; \
			memset(&none, 0, sizeof(T)); \
			while (p_d->size < size) { \
				if (!deque_func(push_back, T)(p_d, none)) return false; \
			} \
			return true; \
		} \
	} \
	\
	bool deque_chunk_func(reserve, T)(deque(T)* p_d, size_t capacity) { \
		if (p_d->chunk_capacity >= capacity) return true; \
		size_t new_capacity = p_d->chunk_capacity == 0 ? 4 : p_d->chunk_capacity; \
		while (new_capacity < capacity) new_capacity <<= 1; \
		chunk(T)* p_new_data = (chunk(T)*)calloc(new_capacity, sizeof(chunk(T))); \
		if (!p_new_data) return false; \
		for (size_t i = 0; i < p_d->chunk_count; i++) { \
			size_t old_index = (p_d->chunk_begin + i) % p_d->chunk_capacity; \
			p_new_data[i] = p_d->p_data[old_index]; \
			p_d->p_data[old_index].p_data = NULL; \
		} \
		for (size_t i = 0; i < p_d->chunk_capacity; i++) { \
			if (p_d->p_data[i].p_data) free(p_d->p_data[i].p_data); \
		} \
		free(p_d->p_data); \
		p_d->p_data = p_new_data; \
		p_d->chunk_begin = 0; \
		p_d->chunk_capacity = new_capacity; \
		return true; \
	} \
	\
	chunk(T)* deque_chunk_func(at, T)(deque(T)* p_d, size_t index) { \
		return &p_d->p_data[(p_d->chunk_begin + index) % p_d->chunk_capacity]; \
	} \
	\
	bool deque_chunk_func(push_front, T)(deque(T)* p_d) { \
		if (!deque_chunk_func(reserve, T)(p_d, p_d->chunk_count + 1)) return false; \
		p_d->chunk_begin = (p_d->chunk_begin + p_d->chunk_capacity - 1) % p_d->chunk_capacity; \
		p_d->chunk_count++; \
		return true; \
	} \
	\
	bool deque_chunk_func(push_back, T)(deque(T)* p_d) { \
		if (!deque_chunk_func(reserve, T)(p_d, p_d->chunk_count + 1)) return false; \
		p_d->chunk_count++; \
		return true; \
	} \
	\
	bool deque_chunk_func(pop_front, T)(deque(T)* p_d) { \
		if (p_d->chunk_count == 0) return false; \
		chunk_func(free, T)(deque_chunk_front(T, p_d)); \
		p_d->chunk_begin = (p_d->chunk_begin + 1) % p_d->chunk_capacity; \
		p_d->chunk_count--; \
		return true; \
	} \
	\
	bool deque_chunk_func(pop_back, T)(deque(T)* p_d) { \
		if (p_d->chunk_count == 0) return false; \
		chunk_func(free, T)(deque_chunk_back(T, p_d)); \
		p_d->chunk_count--; \
		return true; \
	} \
	\
	bool deque_func(push_front, T)(deque(T)* p_d, T item) { \
		if (p_d->chunk_count == 0) { \
			if (!deque_chunk_func(push_front, T)(p_d)) return false; \
		} \
		chunk(T)* p_chunk = deque_chunk_front(T, p_d); \
		if (!chunk_func(push_front, T)(p_chunk, item)) { \
			if (!deque_chunk_func(push_front, T)(p_d)) return false; \
			p_chunk = deque_chunk_front(T, p_d); \
			if (!chunk_func(push_front, T)(p_chunk, item)) return false; \
		} \
		p_d->size++; \
		return true; \
	} \
	\
	bool deque_func(pop_front, T)(deque(T)* p_d) { \
		if (p_d->size == 0) return false; \
		chunk(T)* p_chunk = deque_chunk_front(T, p_d); \
		if (!chunk_func(pop_front, T)(p_chunk)) return false; \
		if (p_chunk->size == 0) { \
			if (!deque_chunk_func(pop_front, T)(p_d)) return false; \
		} \
		p_d->size--; \
		return true; \
	} \
	\
	bool deque_func(push_back, T)(deque(T)* p_d, T item) { \
		if (p_d->chunk_count == 0) { \
			if (!deque_chunk_func(push_back, T)(p_d)) return false; \
		} \
		chunk(T)* p_chunk = deque_chunk_back(T, p_d); \
		if (!chunk_func(push_back, T)(p_chunk, item)) { \
			if (!deque_chunk_func(push_back, T)(p_d)) return false; \
			p_chunk = deque_chunk_back(T, p_d); \
			if (!chunk_func(push_back, T)(p_chunk, item)) return false; \
		} \
		p_d->size++; \
		return true; \
	} \
	\
	bool deque_func(pop_back, T)(deque(T)* p_d) { \
		if (p_d->size == 0) return false; \
		chunk(T)* p_chunk = deque_chunk_back(T, p_d); \
		if (!chunk_func(pop_back, T)(p_chunk)) return false; \
		if (p_chunk->size == 0) { \
			if (!deque_chunk_func(pop_back, T)(p_d)) return false; \
		} \
		p_d->size--; \
		return true; \
	} \
	\
	T* deque_func(at, T)(deque(T)* p_d, size_t index) { \
		if (index >= p_d->size) return NULL; \
		chunk(T)* p_first_chunk = deque_chunk_front(T, p_d); \
		if (index < p_first_chunk->size) { \
			return chunk_func(at, T)(p_first_chunk, index); \
		} \
		index -= p_first_chunk->size; \
		size_t chunk_offset = 1 + (index / cctl_deque_chunk_max); \
		size_t index_in_chunk = index % cctl_deque_chunk_max; \
		return chunk_func(at, T)(deque_chunk_func(at, T)(p_d, chunk_offset), index_in_chunk); \
	} \
	\
	deque_iterator(T) deque_func(begin, T)(deque(T)* p_d) { \
		deque_iterator(T) it = { p_d, 0 }; \
		return it; \
	} \
	\
	deque_iterator(T) deque_func(end, T)(deque(T)* p_d) { \
		deque_iterator(T) it = { p_d, p_d ? p_d->size : 0 }; \
		return it; \
	} \
	\
	deque_iterator(T) deque_func(rbegin, T)(deque(T)* p_d) { \
		deque_iterator(T) it = { p_d, (p_d && p_d->size > 0) ? p_d->size - 1 : (size_t)-1 }; \
		return it; \
	} \
	\
	deque_iterator(T) deque_func(rend, T)(deque(T)* p_d) { \
		deque_iterator(T) it = { p_d, (size_t)-1 }; \
		return it; \
	} \
	\
	deque_iterator(T) deque_func(seek, T)(deque(T)* p_d, size_t index) { \
		deque_iterator(T) it = { p_d, (p_d && index < p_d->size) ? index : (size_t)-1 }; \
		return it; \
	} \
	\
	bool deque_func(shrink_to_fit, T)(deque(T)* p_d) { \
		if (!p_d) return false; \
		if (p_d->size == 0) { \
			deque_func(clear, T)(p_d); \
			if (p_d->p_data) { \
				free(p_d->p_data); \
				p_d->p_data = NULL; \
			} \
			p_d->chunk_capacity = 0; \
			return true; \
		} \
		if (p_d->chunk_count == p_d->chunk_capacity) return true; \
		chunk(T)* p_new_data = (chunk(T)*)calloc(p_d->chunk_count, sizeof(chunk(T))); \
		if (!p_new_data) return false; \
		for (size_t i = 0; i < p_d->chunk_count; i++) { \
			size_t old_index = (p_d->chunk_begin + i) % p_d->chunk_capacity; \
			p_new_data[i] = p_d->p_data[old_index]; \
			p_d->p_data[old_index].p_data = NULL; \
		} \
		for (size_t i = 0; i < p_d->chunk_capacity; i++) { \
			if (p_d->p_data[i].p_data) free(p_d->p_data[i].p_data); \
		} \
		free(p_d->p_data); \
		p_d->p_data = p_new_data; \
		p_d->chunk_begin = 0; \
		p_d->chunk_capacity = p_d->chunk_count; \
		return true; \
	}

#endif