aboutsummaryrefslogtreecommitdiff
path: root/deque.c
diff options
context:
space:
mode:
Diffstat (limited to 'deque.c')
-rw-r--r--deque.c38
1 files changed, 36 insertions, 2 deletions
diff --git a/deque.c b/deque.c
index 93cbe92..eec6f42 100644
--- a/deque.c
+++ b/deque.c
@@ -5,11 +5,12 @@
5 5
6#include "util.h" 6#include "util.h"
7 7
8typedef int T;
9
10#define START_MAP_CAPACITY 4 8#define START_MAP_CAPACITY 4
11#define CHUNK_CAPACITY 17 9#define CHUNK_CAPACITY 17
12 10
11/* --8<-- deque_type */
12typedef int T;
13
13struct deque { 14struct deque {
14 T **map; 15 T **map;
15 16
@@ -20,7 +21,9 @@ struct deque {
20 size_t offset; 21 size_t offset;
21 size_t size; 22 size_t size;
22}; 23};
24/* -->8-- */
23 25
26/* --8<-- deque_allocate */
24static void * 27static void *
25allocate(size_t n, size_t sz) 28allocate(size_t n, size_t sz)
26{ 29{
@@ -30,7 +33,9 @@ allocate(size_t n, size_t sz)
30 } 33 }
31 return ptr; 34 return ptr;
32} 35}
36/* -->8-- */
33 37
38/* --8<-- deque_init */
34void 39void
35deque_init(struct deque *d) 40deque_init(struct deque *d)
36{ 41{
@@ -51,7 +56,9 @@ deque_init(struct deque *d)
51 } 56 }
52 } 57 }
53} 58}
59/* -->8-- */
54 60
61/* --8<-- deque_free */
55void 62void
56deque_free(struct deque *d) 63deque_free(struct deque *d)
57{ 64{
@@ -66,7 +73,9 @@ deque_free(struct deque *d)
66 free(d->map); 73 free(d->map);
67 d->map = NULL; 74 d->map = NULL;
68} 75}
76/* -->8-- */
69 77
78/* --8<-- deque_size */
70size_t 79size_t
71deque_size(struct deque *d) 80deque_size(struct deque *d)
72{ 81{
@@ -74,7 +83,9 @@ deque_size(struct deque *d)
74 83
75 return d->size; 84 return d->size;
76} 85}
86/* -->8-- */
77 87
88/* --8<-- deque_is_empty */
78bool 89bool
79deque_is_empty(struct deque *d) 90deque_is_empty(struct deque *d)
80{ 91{
@@ -82,7 +93,9 @@ deque_is_empty(struct deque *d)
82 93
83 return d->map_begin == d->map_end; 94 return d->map_begin == d->map_end;
84} 95}
96/* -->8-- */
85 97
98/* --8<-- deque_grow_map */
86static void 99static void
87grow_map(struct deque *d) 100grow_map(struct deque *d)
88{ 101{
@@ -116,7 +129,9 @@ grow_map(struct deque *d)
116 // set new map_capacity 129 // set new map_capacity
117 d->map_capacity = capacity; 130 d->map_capacity = capacity;
118} 131}
132/* -->8-- */
119 133
134/* --8<-- deque_map_append_chunk */
120static void 135static void
121map_append_chunk(struct deque *d) 136map_append_chunk(struct deque *d)
122{ 137{
@@ -133,7 +148,9 @@ map_append_chunk(struct deque *d)
133 d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map); 148 d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map);
134 d->map_end = next; 149 d->map_end = next;
135} 150}
151/* -->8-- */
136 152
153/* --8<-- deque_map_prepend_chunk */
137static void 154static void
138map_prepend_chunk(struct deque *d) 155map_prepend_chunk(struct deque *d)
139{ 156{
@@ -150,7 +167,9 @@ map_prepend_chunk(struct deque *d)
150 d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map); 167 d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map);
151 d->map_begin = prev; 168 d->map_begin = prev;
152} 169}
170/* -->8-- */
153 171
172/* --8<-- deque_map_remove_front_chunk */
154static void 173static void
155map_remove_front_chunk(struct deque *d) 174map_remove_front_chunk(struct deque *d)
156{ 175{
@@ -167,7 +186,9 @@ map_remove_front_chunk(struct deque *d)
167 186
168 d->map_begin = next; 187 d->map_begin = next;
169} 188}
189/* -->8-- */
170 190
191/* --8<-- deque_remove_tail_chunk */
171static void 192static void
172map_remove_tail_chunk(struct deque *d) 193map_remove_tail_chunk(struct deque *d)
173{ 194{
@@ -184,7 +205,9 @@ map_remove_tail_chunk(struct deque *d)
184 205
185 d->map_end = prev; 206 d->map_end = prev;
186} 207}
208/* -->8-- */
187 209
210/* --8<-- deque_get_at */
188bool 211bool
189deque_get_at(struct deque *d, size_t idx, T *data) 212deque_get_at(struct deque *d, size_t idx, T *data)
190{ 213{
@@ -204,7 +227,9 @@ deque_get_at(struct deque *d, size_t idx, T *data)
204 227
205 return true; 228 return true;
206} 229}
230/* -->8-- */
207 231
232/* --8<-- deque_set_at */
208bool 233bool
209deque_set_at(struct deque *d, size_t idx, T data) 234deque_set_at(struct deque *d, size_t idx, T data)
210{ 235{
@@ -223,7 +248,9 @@ deque_set_at(struct deque *d, size_t idx, T data)
223 248
224 return true; 249 return true;
225} 250}
251/* -->8-- */
226 252
253/* --8<-- deque_push_back */
227void 254void
228deque_push_back(struct deque *d, T data) 255deque_push_back(struct deque *d, T data)
229{ 256{
@@ -241,7 +268,9 @@ deque_push_back(struct deque *d, T data)
241 d->map[chunk_num][chunk_off] = data; 268 d->map[chunk_num][chunk_off] = data;
242 ++d->size; 269 ++d->size;
243} 270}
271/* -->8-- */
244 272
273/* --8<-- deque_push_front */
245void 274void
246deque_push_front(struct deque *d, T data) 275deque_push_front(struct deque *d, T data)
247{ 276{
@@ -259,7 +288,9 @@ deque_push_front(struct deque *d, T data)
259 d->map[chunk_num][d->offset] = data; 288 d->map[chunk_num][d->offset] = data;
260 ++d->size; 289 ++d->size;
261} 290}
291/* -->8-- */
262 292
293/* --8<-- deque_pop_back */
263bool 294bool
264deque_pop_back(struct deque *d, T *data) 295deque_pop_back(struct deque *d, T *data)
265{ 296{
@@ -284,7 +315,9 @@ deque_pop_back(struct deque *d, T *data)
284 315
285 return true; 316 return true;
286} 317}
318/* -->8-- */
287 319
320/* --8<-- deque_pop_front */
288bool 321bool
289deque_pop_front(struct deque *d, T *data) 322deque_pop_front(struct deque *d, T *data)
290{ 323{
@@ -310,6 +343,7 @@ deque_pop_front(struct deque *d, T *data)
310 343
311 return true; 344 return true;
312} 345}
346/* -->8-- */
313 347
314static void 348static void
315deque_show(struct deque *d) 349deque_show(struct deque *d)