libGimbal 0.1.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_array_deque.h
Go to the documentation of this file.
1/*! \file
2 * \brief GblArrayDeque container and related functions
3 * \ingroup containers
4 * \copydoc GblArrayDeque
5 *
6 * \todo
7 * - GblArrayDeque_erase()
8 *
9 * \author Falco Girgis
10 */
11
12#ifndef GIMBAL_ARRAY_DEQUE_H
13#define GIMBAL_ARRAY_DEQUE_H
14
15#include "gimbal_ring_buffer.h"
16
17#ifndef GBL_ARRAY_DEQUE_FORCE_POW2
18# define GBL_ARRAY_DEQUE_FORCE_POW2 1
19#endif
20
21#define GBL_SELF_TYPE GblArrayDeque
22
23GBL_DECLS_BEGIN
24
25/*! Circular array-based double-ended queue container
26 * \ingroup containers
27 *
28 * GblArrayDeque is a very flexible container type which
29 * combines the fast random access and cache coherency
30 * of a contiguous array with the semantics of a double-ended
31 * queue. This means that not only are random
32 * accesses extremely efficient, but also adding and
33 * removing entries from either end as well.
34 *
35 * This container is well-suited for data sets which can
36 * grow or shrink from either end, but which are typically
37 * accessed as an array.
38 *
39 * Operation |Time Complexity
40 * --------------------------|------------------
41 * iteration | O(N)
42 * insertion (back or front) | O(1)
43 * insertion (middle) | O(N)
44 * removal (back or front) | O(1)
45 * removal (middle) (WIP) | O(N)
46 * access (front or back) | O(1)
47 * random access (middle) | O(1)
48 *
49 * For reference, the following are the results of the
50 * profiler unit tests for some common operations shared
51 * between GblArrayList (comparable to std::vector) and
52 * GblArrayDeque (1024 pointer-sized entries):
53 *
54 * Test |GblArrayList|GblArrayDeque
55 * ----------|------------|-------------
56 * at |0.004 ms |0.008 ms
57 * pushBack |0.030 ms |0.030 ms
58 * pushFront |0.116 ms |0.027 ms
59 *
60 * \note
61 * This container can be seen as a slightly more specific,
62 * more optimized version of C++'s std::deque. A std::deque
63 * also allows for efficient insertion and removal to and
64 * from the middle of the array; however, this flexibility
65 * comes at the price of increased indirection overhead
66 * for random access and increased memory utilization.
67 * While GblArrayDeque does support random insertions and
68 * deletions, these are more costly than doing so from the
69 * front or back, as they require the shuffling around of
70 * surrounding elements in memory. We have decided that
71 * this trade-off is worth it, since we still support
72 * the operation, but fast lookups and lower memory
73 * utilization are much higher priorities.
74 *
75 * \note
76 * Internally this structure is implemented as an extension
77 * of the GblRingBuffer container, which is able to push
78 * from the front, pop from the back, and dynamically resize
79 * itself as it reaches its capacity.
80 *
81 * \note
82 * When the GBL_ARRAY_DEQUE_FORCE_POW2 macro is defined as 1
83 * (default) behavior), the capacity of the deque will always
84 * be rounded to the next power-of-two. This means any direct
85 * requests to GblArrayDeque_reserve() or
86 * GblArrayDeque_shrinkToFit() will not resize the container
87 * to the exact value specified. As a consequence of this,
88 * lookup times can be optimized by another 15-30% by reducing
89 * a modulo operation to a decrement + bitmask.
90 *
91 * \sa GblRingBuffer, GblArrayList
92 */
93typedef struct GblArrayDeque { // Size (32/64-bit)
94 GBL_PRIVATE_BEGIN
95 GblRingBuffer ringBuffer;
96 GBL_PRIVATE_END // 22/42 total
97} GblArrayDeque;
98
99// ===== Public methods =====
100GBL_EXPORT GBL_RESULT GblArrayDeque_construct (GBL_SELF,
101 uint16_t elementSize,
102 size_t capacity,
103 size_t initialSize,
104 const void* pInitialData,
105 GblContext* pCtx) GBL_NOEXCEPT;
106
107GBL_EXPORT GBL_RESULT GblArrayDeque_destruct (GBL_SELF) GBL_NOEXCEPT;
108GBL_EXPORT GBL_RESULT GblArrayDeque_copy (GBL_SELF, const GblArrayDeque* pOther) GBL_NOEXCEPT;
109GBL_EXPORT GBL_RESULT GblArrayDeque_move (GBL_SELF, GblArrayDeque* pOther) GBL_NOEXCEPT;
110
111GBL_EXPORT GblContext* GblArrayDeque_context (GBL_CSELF) GBL_NOEXCEPT;
112GBL_EXPORT size_t GblArrayDeque_capacity (GBL_CSELF) GBL_NOEXCEPT;
113GBL_EXPORT size_t GblArrayDeque_size (GBL_CSELF) GBL_NOEXCEPT;
114GBL_EXPORT size_t GblArrayDeque_elementSize (GBL_CSELF) GBL_NOEXCEPT;
115
116GBL_EXPORT GblBool GblArrayDeque_empty (GBL_CSELF) GBL_NOEXCEPT;
117GBL_EXPORT GblBool GblArrayDeque_full (GBL_CSELF) GBL_NOEXCEPT;
118
119GBL_EXPORT void* GblArrayDeque_at (GBL_CSELF, size_t index) GBL_NOEXCEPT;
120GBL_EXPORT void* GblArrayDeque_front (GBL_CSELF) GBL_NOEXCEPT;
121GBL_EXPORT void* GblArrayDeque_back (GBL_CSELF) GBL_NOEXCEPT;
122
123GBL_EXPORT GBL_RESULT GblArrayDeque_pushBack (GBL_SELF, const void* pData) GBL_NOEXCEPT;
124GBL_EXPORT void* GblArrayDeque_emplaceBack (GBL_SELF) GBL_NOEXCEPT;
125GBL_EXPORT GBL_RESULT GblArrayDeque_pushFront (GBL_SELF, const void* pData) GBL_NOEXCEPT;
126GBL_EXPORT void* GblArrayDeque_emplaceFront (GBL_SELF) GBL_NOEXCEPT;
127
128GBL_EXPORT void* GblArrayDeque_popBack (GBL_SELF) GBL_NOEXCEPT;
129GBL_EXPORT void* GblArrayDeque_popFront (GBL_SELF) GBL_NOEXCEPT;
130
131GBL_EXPORT void* GblArrayDeque_insert (GBL_SELF, size_t pos, const void* pData, size_t count) GBL_NOEXCEPT;
132GBL_EXPORT void* GblArrayDeque_emplace (GBL_SELF, size_t pos) GBL_NOEXCEPT;
133GBL_EXPORT GBL_RESULT GblArrayDeque_erase (GBL_SELF, size_t pos, size_t count ) GBL_NOEXCEPT;
134
135GBL_EXPORT void GblArrayDeque_clear (GBL_SELF) GBL_NOEXCEPT;
136GBL_EXPORT GBL_RESULT GblArrayDeque_reserve (GBL_SELF, size_t capacity) GBL_NOEXCEPT;
137GBL_EXPORT GBL_RESULT GblArrayDeque_resize (GBL_SELF, size_t size) GBL_NOEXCEPT;
138GBL_EXPORT GBL_RESULT GblArrayDeque_shrinkToFit (GBL_SELF) GBL_NOEXCEPT;
139
140GBL_DECLS_END
141
142//! \cond
143#define GblArrayDeque_construct(...)
144 GblArrayDeque_constructDefault_(__VA_ARGS__)
145#define GblArrayDeque_constructDefault_(...)
146 GblArrayDeque_constructDefault__(__VA_ARGS__, 0, 0, GBL_NULL, GBL_NULL)
147#define GblArrayDeque_constructDefault__(self, elem, cap, size, data, ctx, ...)
148 (GblArrayDeque_construct)(self, elem, cap, size, data, ctx)
149
150#define GblArrayDeque_insert(...)
151 GblArrayDeque_insertDefault_(__VA_ARGS__)
152#define GblArrayDeque_insertDefault_(...)
153 GblArrayDeque_insertDefault__(__VA_ARGS__, 1)
154#define GblArrayDeque_insertDefault__(self, pos, data, count, ...)
155 (GblArrayDeque_insert(self, pos, data, count))
156
157#define GblArrayDeque_erase(...)
158 GblArrayDeque_eraseDefault_(__VA_ARGS__)
159#define GblArrayDeque_eraseDefault_(...)
160 GblArrayDeque_eraseDefault__(__VA_ARGS__, 1)
161#define GblArrayDeque_eraseDefault__(self, pos, count, ...)
162 (GblArrayDeque_eraseDefault(self, pos, count))
163//! \endcond
164
165#undef GBL_SELF_TYPE
166
167#endif // GIMBAL_ARRAY_DEQUE_H
GBL_NULL
#define GBL_NULL
Definition gimbal_compiler.h:178
GBL_NOEXCEPT
#define GBL_NOEXCEPT
Definition gimbal_compiler.h:264
GBL_DECLS_BEGIN
#define GBL_DECLS_BEGIN
Definition gimbal_decls.h:23
GBL_PRIVATE_BEGIN
#define GBL_PRIVATE_BEGIN
Definition gimbal_decls.h:199
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:232
GBL_PRIVATE_END
#define GBL_PRIVATE_END
Private data structure.
Definition gimbal_decls.h:201
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GblArrayDeque
Circular array-based double-ended queue container.
Definition gimbal_array_deque.h:93