Quash Shell  0.1
A simple yet powerfull shell program
deque.h
Go to the documentation of this file.
1 
7 #ifndef SRC_DEQUE_H
8 #define SRC_DEQUE_H
9 
10 #include <assert.h>
11 #include <stdbool.h>
12 #include <stdio.h>
13 #include <stdlib.h>
14 
33 #define IMPLEMENT_DEQUE_STRUCT(struct_name, type) \
34  typedef struct struct_name { \
35  type* data; \
36  size_t cap; \
37  size_t front; \
38  size_t back; \
39  \
40  void (*destructor)(type); \
41  } struct_name;
42 
60 #define PROTOTYPE_DEQUE(struct_name, type) \
61  struct_name new_##struct_name(size_t); \
62  struct_name new_destructable_##struct_name(size_t, void (*)(type)); \
63  void destroy_##struct_name(struct_name*); \
64  void empty_##struct_name(struct_name*); \
65  bool is_empty_##struct_name(struct_name*); \
66  size_t length_##struct_name(struct_name*); \
67  type* as_array_##struct_name(struct_name*, size_t*); \
68  void apply_##struct_name(struct_name*, void (*)(type)); \
69  void push_front_##struct_name(struct_name*, type); \
70  void push_back_##struct_name(struct_name*, type); \
71  type pop_front_##struct_name(struct_name*); \
72  type pop_back_##struct_name(struct_name*); \
73  type peek_front_##struct_name(struct_name*); \
74  type peek_back_##struct_name(struct_name*); \
75  void update_front_##struct_name(struct_name*, type); \
76  void update_back_##struct_name(struct_name*, type); \
77  void update_and_destroy_front_##struct_name(struct_name*, type); \
78  void update_and_destroy_back_##struct_name(struct_name*, type);
79 
93 #define IMPLEMENT_DEQUE(struct_name, type) \
94  \
95  void apply_##struct_name(struct_name*, void (*)(type)); \
96  \
97  struct_name new_##struct_name(size_t init_cap) { \
98  struct_name ret; \
99  \
100  if (init_cap > 0) \
101  ret.cap = init_cap; \
102  else \
103  ret.cap = 1; \
104  \
105  ret.data = (type*) malloc(ret.cap * sizeof(type)); \
106  \
107  if (ret.data == NULL) { \
108  fprintf(stderr, "ERROR: Failed to allocate struct_name" \
109  " contents"); \
110  exit(-1); \
111  } \
112  \
113  ret.front = ret.back = 0; \
114  ret.destructor = NULL; \
115  \
116  return ret; \
117  } \
118  \
119  struct_name new_destructable_##struct_name(size_t init_cap, \
120  void (*destructor)(type)){ \
121  struct_name ret = new_##struct_name(init_cap); \
122  ret.destructor = destructor; \
123  return ret; \
124  } \
125  \
126  void destroy_##struct_name(struct_name* deq) { \
127  assert(deq != NULL); \
128  \
129  if (deq->data == NULL) \
130  return; \
131  \
132  if (deq->destructor != NULL) \
133  apply_##struct_name(deq, deq->destructor); \
134  \
135  if (deq->data != NULL) \
136  free(deq->data); \
137  \
138  deq->data = NULL; \
139  deq->cap = deq->front = deq->back = 0; \
140  } \
141  \
142  void empty_##struct_name(struct_name* deq) { \
143  assert(deq != NULL); \
144  assert(deq->data != NULL); /* Make sure the structure is valid */ \
145  \
146  if (deq->destructor != NULL) \
147  apply_##struct_name(deq, deq->destructor); \
148  \
149  deq->front = deq->back = 0; \
150  } \
151  \
152  bool is_empty_##struct_name(struct_name* deq) { \
153  assert(deq != NULL); \
154  assert(deq->data != NULL); /* Make sure the structure is valid */ \
155  return deq->front == deq->back; \
156  } \
157  \
158  size_t length_##struct_name(struct_name* deq) { \
159  assert(deq != NULL); \
160  assert(deq->data != NULL); /* Make sure the structure is valid */ \
161  return (deq->back - deq->front + deq->cap) % deq->cap; \
162  } \
163  \
164  static void __reallign_##struct_name(struct_name* deq) { \
165  assert(deq != NULL); \
166  assert(deq->data != NULL); /* Make sure the structure is valid */ \
167  \
168  if (deq->front != 0) { \
169  type* old_data = deq->data; \
170  size_t len = length_##struct_name(deq); \
171  \
172  deq->data = (type*) malloc(deq->cap * sizeof(type)); \
173  \
174  if (deq->data == NULL) { \
175  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
176  " contents"); \
177  abort(); \
178  } \
179  \
180  size_t i; \
181  \
182  for (i = 0; i < len; ++i) \
183  deq->data[i] = old_data[(deq->front + i) % deq->cap]; \
184  \
185  free(old_data); \
186  \
187  deq->front = 0; \
188  deq->back = i; \
189  } \
190  } \
191  \
192  type* as_array_##struct_name(struct_name* deq, size_t* len) { \
193  assert(deq != NULL); \
194  assert(deq->data != NULL); /* Make sure the structure is valid */ \
195  \
196  __reallign_##struct_name(deq); \
197  \
198  type* ret = deq->data; \
199  \
200  if (len != NULL) \
201  *len = length_##struct_name(deq); \
202  \
203  deq->data = NULL; \
204  deq->cap = deq->front = deq->back = 0; \
205  \
206  return ret; \
207  } \
208  \
209  void apply_##struct_name(struct_name* deq, void (*func)(type)) { \
210  assert(deq != NULL); \
211  assert(deq->data != NULL); /* Make sure the structure is valid */ \
212  \
213  size_t len = length_##struct_name(deq); \
214  \
215  for (size_t i = 0; i < len; ++i) { \
216  func(deq->data[(deq->front + i) % deq->cap]); \
217  } \
218  } \
219  \
220  static void __on_push_##struct_name(struct_name* deq) { \
221  if (deq->front == (deq->back + 1) % deq->cap) { \
222  type* old_data = deq->data; \
223  size_t old_cap = deq->cap; \
224  \
225  deq->cap = 2 * deq->cap; \
226  deq->data = (type*) malloc(deq->cap * sizeof(type)); \
227  \
228  if (deq->data == NULL) { \
229  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
230  " contents\n"); \
231  abort(); \
232  } \
233  \
234  size_t i; \
235  \
236  for (i = 0; i < old_cap - 1; ++i) \
237  deq->data[i] = old_data[(deq->front + i) % old_cap]; \
238  \
239  free(old_data); \
240  \
241  deq->front = 0; \
242  deq->back = i; \
243  } \
244  } \
245  \
246  static void __on_pop_##struct_name(struct_name* deq) { \
247  if (is_empty_##struct_name(deq)) { \
248  fprintf(stderr, "ERROR: Cannot pop from of struct_name while it " \
249  "is empty\n"); \
250  abort(); \
251  } \
252  } \
253  \
254  void push_front_##struct_name(struct_name* deq, type element) { \
255  assert(deq != NULL); \
256  assert(deq->data != NULL); /* Make sure the structure is valid */ \
257  __on_push_##struct_name(deq); \
258  deq->front = (deq->front + deq->cap - 1) % deq->cap; \
259  deq->data[deq->front] = element; \
260  } \
261  \
262  void push_back_##struct_name(struct_name* deq, type element) { \
263  assert(deq != NULL); \
264  assert(deq->data != NULL); /* Make sure the structure is valid */ \
265  __on_push_##struct_name(deq); \
266  deq->data[deq->back] = element; \
267  deq->back = (deq->back + 1) % deq->cap; \
268  } \
269  \
270  type pop_front_##struct_name(struct_name* deq) { \
271  assert(deq != NULL); \
272  assert(deq->data != NULL); /* Make sure the structure is valid */ \
273  __on_pop_##struct_name(deq); \
274  size_t old_front = deq->front; \
275  deq->front = (deq->front + 1) % deq->cap; \
276  return deq->data[old_front]; \
277  } \
278  \
279  type pop_back_##struct_name(struct_name* deq) { \
280  assert(deq != NULL); \
281  assert(deq->data != NULL); /* Make sure the structure is valid */ \
282  __on_pop_##struct_name(deq); \
283  deq->back = (deq->back + deq->cap - 1) % deq->cap; \
284  return deq->data[deq->back]; \
285  } \
286  \
287  type peek_front_##struct_name(struct_name* deq) { \
288  assert(deq != NULL); \
289  assert(deq->data != NULL); /* Make sure the structure is valid */ \
290  assert(!is_empty_##struct_name(deq)); \
291  return deq->data[deq->front]; \
292  } \
293  \
294  type peek_back_##struct_name(struct_name* deq) { \
295  assert(deq != NULL); \
296  assert(deq->data != NULL); /* Make sure the structure is valid */ \
297  assert(!is_empty_##struct_name(deq)); \
298  return deq->data[(deq->back + deq->cap - 1) % deq->cap]; \
299  } \
300  \
301  void update_front_##struct_name(struct_name* deq, type element) { \
302  assert(deq != NULL); \
303  assert(deq->data != NULL); /* Make sure the structure is valid */ \
304  assert(!is_empty_##struct_name(deq)); \
305  deq->data[deq->front] = element; \
306  } \
307  \
308  void update_back_##struct_name(struct_name* deq, type element) { \
309  assert(deq != NULL); \
310  assert(deq->data != NULL); /* Make sure the structure is valid */ \
311  assert(!is_empty_##struct_name(deq)); \
312  deq->data[(deq->back + deq->cap - 1) % deq->cap] = element; \
313  } \
314  \
315  void update_and_destroy_front_##struct_name(struct_name* deq, \
316  type element) { \
317  assert(deq != NULL); \
318  assert(deq->data != NULL); /* Make sure the structure is valid */ \
319  assert(!is_empty_##struct_name(deq)); \
320  \
321  size_t idx = deq->front; \
322  \
323  if (deq->destructor != NULL) \
324  deq->destructor(deq->data[idx]); \
325  \
326  deq->data[idx] = element; \
327  } \
328  \
329  void update_and_destroy_back_##struct_name(struct_name* deq, \
330  type element) { \
331  assert(deq != NULL); \
332  assert(deq->data != NULL); /* Make sure the structure is valid */ \
333  assert(!is_empty_##struct_name(deq)); \
334  \
335  size_t idx = (deq->back + deq->cap - 1) % deq->cap; \
336  \
337  if (deq->destructor != NULL) \
338  deq->destructor(deq->data[idx]); \
339  \
340  deq->data[idx] = element; \
341  }
342 
343 // The following deque is for example and documentation purposes only
344 
346 typedef char Type;
347 
360 // The following is the struct created by the expansion of
361 // IMPLEMENT_DEQUE_STRUCT(Example, Type);
362 typedef struct Example {
363  Type* data;
364  size_t cap;
365  size_t front;
366  size_t back;
368  void (*destructor)(Type);
376 } Example;
631 PROTOTYPE_DEQUE(Example, Type);
632 
633 #endif //SRC_DEQUE_H
Type
char Type
An example type used for example purposes only.
Definition: deque.h:346
Example::front
size_t front
Definition: deque.h:365
Example::back
size_t back
Definition: deque.h:366
Example
A data structure generated by IMPLEMENT_DEQUE_STRUCT() to store the state of a deque.
Definition: deque.h:362
Example::cap
size_t cap
Definition: deque.h:364
Example::data
Type * data
Definition: deque.h:363
Example
struct Example Example
This way you do not have to type "struct Example" each time you wish to refer to an Example structure...
Example::destructor
void(* destructor)(Type)
Definition: deque.h:368
PROTOTYPE_DEQUE
#define PROTOTYPE_DEQUE(struct_name, type)
Generates prototypes for functions that manipulate Double Ended Queue structures. ...
Definition: deque.h:60
Generated by   doxygen 1.8.11