gimbal_array_deque.h File Reference

Go to the source code of this file.

Data Structures
struct	GblArrayDeque

Macros
#define	GBL_ARRAY_DEQUE_FORCE_POW2

Functions
GBL_RESULT	GblArrayDeque_construct (GblArrayDeque *pSelf, uint16_t elementSize, size_t capacity, size_t initialSize, const void *pInitialData, GblContext *pCtx)
GBL_RESULT	GblArrayDeque_destruct (GblArrayDeque *pSelf)
GBL_RESULT	GblArrayDeque_copy (GblArrayDeque *pSelf, const GblArrayDeque *pOther)
GBL_RESULT	GblArrayDeque_move (GblArrayDeque *pSelf, GblArrayDeque *pOther)
GblContext *	GblArrayDeque_context (const GblArrayDeque *pSelf)
size_t	GblArrayDeque_capacity (const GblArrayDeque *pSelf)
size_t	GblArrayDeque_size (const GblArrayDeque *pSelf)
size_t	GblArrayDeque_elementSize (const GblArrayDeque *pSelf)
GblBool	GblArrayDeque_empty (const GblArrayDeque *pSelf)
GblBool	GblArrayDeque_full (const GblArrayDeque *pSelf)
void *	GblArrayDeque_at (const GblArrayDeque *pSelf, size_t index)
void *	GblArrayDeque_front (const GblArrayDeque *pSelf)
void *	GblArrayDeque_back (const GblArrayDeque *pSelf)
GBL_RESULT	GblArrayDeque_pushBack (GblArrayDeque *pSelf, const void *pData)
void *	GblArrayDeque_emplaceBack (GblArrayDeque *pSelf)
GBL_RESULT	GblArrayDeque_pushFront (GblArrayDeque *pSelf, const void *pData)
void *	GblArrayDeque_emplaceFront (GblArrayDeque *pSelf)
void *	GblArrayDeque_popBack (GblArrayDeque *pSelf)
void *	GblArrayDeque_popFront (GblArrayDeque *pSelf)
void *	GblArrayDeque_insert (GblArrayDeque *pSelf, size_t pos, const void *pData, size_t count)
void *	GblArrayDeque_emplace (GblArrayDeque *pSelf, size_t pos)
GBL_RESULT	GblArrayDeque_erase (GblArrayDeque *pSelf, size_t pos, size_t count)
void	GblArrayDeque_clear (GblArrayDeque *pSelf)
GBL_RESULT	GblArrayDeque_reserve (GblArrayDeque *pSelf, size_t capacity)
GBL_RESULT	GblArrayDeque_resize (GblArrayDeque *pSelf, size_t size)
GBL_RESULT	GblArrayDeque_shrinkToFit (GblArrayDeque *pSelf)

Detailed Description

GblArrayDeque container and related functions.

Circular array-based double-ended queue container.

GblArrayDeque is a very flexible container type which combines the fast random access and cache coherency of a contiguous array with the semantics of a double-ended queue. This means that not only are random accesses extremely efficient, but also adding and removing entries from either end as well.

This container is well-suited for data sets which can grow or shrink from either end, but which are typically accessed as an array.

Operation	Time Complexity
iteration	O(N)
insertion (back or front)	O(1)
insertion (middle)	O(N)
removal (back or front)	O(1)
removal (middle) (WIP)	O(N)
access (front or back)	O(1)
random access (middle)	O(1)

For reference, the following are the results of the profiler unit tests for some common operations shared between GblArrayList (comparable to std::vector) and GblArrayDeque (1024 pointer-sized entries):

Test	GblArrayList	GblArrayDeque
at	0.004 ms	0.008 ms
pushBack	0.030 ms	0.030 ms
pushFront	0.116 ms	0.027 ms

Note

This container can be seen as a slightly more specific, more optimized version of C++'s std::deque. A std::deque also allows for efficient insertion and removal to and from the middle of the array; however, this flexibility comes at the price of increased indirection overhead for random access and increased memory utilization. While GblArrayDeque does support random insertions and deletions, these are more costly than doing so from the front or back, as they require the shuffling around of surrounding elements in memory. We have decided that this trade-off is worth it, since we still support the operation, but fast lookups and lower memory utilization are much higher priorities.

Internally this structure is implemented as an extension of the GblRingBuffer container, which is able to push from the front, pop from the back, and dynamically resize itself as it reaches its capacity.

When the GBL_ARRAY_DEQUE_FORCE_POW2 macro is defined as 1 (default) behavior), the capacity of the deque will always be rounded to the next power-of-two. This means any direct requests to GblArrayDeque_reserve() or GblArrayDeque_shrinkToFit() will not resize the container to the exact value specified. As a consequence of this, lookup times can be optimized by another 15-30% by reducing a modulo operation to a decrement + bitmask.

See also

GblRingBuffer, GblArrayList

Todo:

• GblArrayDeque_erase()

Author

Falco Girgis

Definition in file gimbal_array_deque.h.

Macro Definition Documentation

GBL_ARRAY_DEQUE_FORCE_POW2

#define GBL_ARRAY_DEQUE_FORCE_POW2

Definition at line 18 of file gimbal_array_deque.h.