Quash Shell  0.1
A simple yet powerfull shell program
deque.h
Go to the documentation of this file.
1 
7 #ifndef DEQUE_H
8 #define DEQUE_H
9 
10 #include <assert.h>
11 #include <stdlib.h>
12 #include <stdio.h>
13 #include <stdbool.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 
91 #define IMPLEMENT_DEQUE(struct_name, type) \
92  struct_name new_##struct_name(size_t); \
93  struct_name new_destructable_##struct_name(size_t, void (*)(type)); \
94  void destroy_##struct_name(struct_name*); \
95  void empty_##struct_name(struct_name*); \
96  bool is_empty_##struct_name(struct_name*); \
97  size_t length_##struct_name(struct_name*); \
98  type* as_array_##struct_name(struct_name*, size_t*); \
99  void apply_##struct_name(struct_name*, void (*)(type)); \
100  void push_front_##struct_name(struct_name*, type); \
101  void push_back_##struct_name(struct_name*, type); \
102  type pop_front_##struct_name(struct_name*); \
103  type pop_back_##struct_name(struct_name*); \
104  type peek_front_##struct_name(struct_name*); \
105  type peek_back_##struct_name(struct_name*); \
106  void update_front_##struct_name(struct_name*, type); \
107  void update_back_##struct_name(struct_name*, type); \
108  \
109  struct_name new_##struct_name(size_t init_cap) { \
110  struct_name ret; \
111  \
112  if (init_cap > 0) \
113  ret.cap = init_cap; \
114  else \
115  ret.cap = 1; \
116  \
117  ret.data = (type*) malloc(init_cap * sizeof(type)); \
118  \
119  if (ret.data == NULL) { \
120  fprintf(stderr, "ERROR: Failed to allocate struct_name" \
121  " contents"); \
122  exit(-1); \
123  } \
124  \
125  ret.front = ret.back = 0; \
126  ret.destructor = NULL; \
127  \
128  return ret; \
129  } \
130  \
131  struct_name new_destructable_##struct_name(size_t init_cap, \
132  void (*destructor)(type)){ \
133  struct_name ret = new_##struct_name(init_cap); \
134  ret.destructor = destructor; \
135  return ret; \
136  } \
137  \
138  void destroy_##struct_name(struct_name* deq) { \
139  assert(deq != NULL); \
140  \
141  if (deq->data == NULL) \
142  return; \
143  \
144  if (deq->destructor != NULL) \
145  apply_##struct_name(deq, deq->destructor); \
146  \
147  if (deq->data != NULL) \
148  free(deq->data); \
149  \
150  deq->data = NULL; \
151  deq->cap = deq->front = deq->back = 0; \
152  } \
153  \
154  void empty_##struct_name(struct_name* deq) { \
155  assert(deq != NULL); \
156  assert(deq->data != NULL); /* Make sure the structure is valid */ \
157  deq->front = deq->back = 0; \
158  } \
159  \
160  bool is_empty_##struct_name(struct_name* deq) { \
161  assert(deq != NULL); \
162  assert(deq->data != NULL); /* Make sure the structure is valid */ \
163  return deq->front == deq->back; \
164  } \
165  \
166  size_t length_##struct_name(struct_name* deq) { \
167  assert(deq != NULL); \
168  assert(deq->data != NULL); /* Make sure the structure is valid */ \
169  return (deq->back - deq->front + deq->cap) % deq->cap; \
170  } \
171  \
172  static void __reallign_##struct_name(struct_name* deq) { \
173  assert(deq != NULL); \
174  assert(deq->data != NULL); /* Make sure the structure is valid */ \
175  \
176  if (deq->front != 0) { \
177  type* old_data = deq->data; \
178  size_t len = length_##struct_name(deq); \
179  \
180  deq->data = (type*) malloc(deq->cap * sizeof(type)); \
181  \
182  if (deq->data == NULL) { \
183  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
184  " contents"); \
185  abort(); \
186  } \
187  \
188  size_t i; \
189  \
190  for (i = 0; i < len; ++i) \
191  deq->data[i] = old_data[(deq->front + i) % deq->cap]; \
192  \
193  free(old_data); \
194  \
195  deq->front = 0; \
196  deq->back = i; \
197  } \
198  } \
199  \
200  type* as_array_##struct_name(struct_name* deq, size_t* len) { \
201  assert(deq != NULL); \
202  assert(deq->data != NULL); /* Make sure the structure is valid */ \
203  \
204  __reallign_##struct_name(deq); \
205  \
206  type* ret = deq->data; \
207  \
208  if (len != NULL) \
209  *len = length_##struct_name(deq); \
210  \
211  deq->data = NULL; \
212  deq->cap = deq->front = deq->back = 0; \
213  \
214  return ret; \
215  } \
216  \
217  void apply_##struct_name(struct_name* deq, void (*func)(type)) { \
218  assert(deq != NULL); \
219  assert(deq->data != NULL); /* Make sure the structure is valid */ \
220  \
221  size_t len = length_##struct_name(deq); \
222  \
223  for (size_t i = 0; i < len; ++i) { \
224  func(deq->data[(deq->front + i) % deq->cap]); \
225  } \
226  } \
227  \
228  static void __on_push_##struct_name(struct_name* deq) { \
229  if (deq->front == (deq->back + 1) % deq->cap) { \
230  type* old_data = deq->data; \
231  size_t old_cap = deq->cap; \
232  \
233  deq->cap = 2 * deq->cap; \
234  deq->data = (type*) malloc(deq->cap * sizeof(type)); \
235  \
236  if (deq->data == NULL) { \
237  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
238  " contents\n"); \
239  abort(); \
240  } \
241  \
242  size_t i; \
243  \
244  for (i = 0; i < old_cap - 1; ++i) \
245  deq->data[i] = old_data[(deq->front + i) % old_cap]; \
246  \
247  free(old_data); \
248  \
249  deq->front = 0; \
250  deq->back = i; \
251  } \
252  } \
253  \
254  static void __on_pop_##struct_name(struct_name* deq) { \
255  if (is_empty_##struct_name(deq)) { \
256  fprintf(stderr, "ERROR: Cannot pop from of struct_name while it " \
257  "is empty\n"); \
258  abort(); \
259  } \
260  } \
261  \
262  void push_front_##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->front = (deq->front + deq->cap - 1) % deq->cap; \
267  deq->data[deq->front] = element; \
268  } \
269  \
270  void push_back_##struct_name(struct_name* deq, type element) { \
271  assert(deq != NULL); \
272  assert(deq->data != NULL); /* Make sure the structure is valid */ \
273  __on_push_##struct_name(deq); \
274  deq->data[deq->back] = element; \
275  deq->back = (deq->back + 1) % deq->cap; \
276  } \
277  \
278  type pop_front_##struct_name(struct_name* deq) { \
279  assert(deq != NULL); \
280  assert(deq->data != NULL); /* Make sure the structure is valid */ \
281  __on_pop_##struct_name(deq); \
282  size_t old_front = deq->front; \
283  deq->front = (deq->front + 1) % deq->cap; \
284  return deq->data[old_front]; \
285  } \
286  \
287  type pop_back_##struct_name(struct_name* deq) { \
288  assert(deq != NULL); \
289  assert(deq->data != NULL); /* Make sure the structure is valid */ \
290  __on_pop_##struct_name(deq); \
291  deq->back = (deq->back + deq->cap - 1) % deq->cap; \
292  return deq->data[deq->back]; \
293  } \
294  \
295  type peek_front_##struct_name(struct_name* deq) { \
296  assert(deq != NULL); \
297  assert(deq->data != NULL); /* Make sure the structure is valid */ \
298  assert(!is_empty_##struct_name(deq)); \
299  return deq->data[deq->front]; \
300  } \
301  \
302  type peek_back_##struct_name(struct_name* deq) { \
303  assert(deq != NULL); \
304  assert(deq->data != NULL); /* Make sure the structure is valid */ \
305  assert(!is_empty_##struct_name(deq)); \
306  return deq->data[(deq->back + deq->cap - 1) % deq->cap]; \
307  } \
308  \
309  void update_front_##struct_name(struct_name* deq, type element) { \
310  assert(deq != NULL); \
311  assert(deq->data != NULL); /* Make sure the structure is valid */ \
312  assert(!is_empty_##struct_name(deq)); \
313  deq->data[deq->front] = element; \
314  } \
315  \
316  void update_back_##struct_name(struct_name* deq, 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  deq->data[(deq->back + deq->cap - 1) % deq->cap] = element; \
321  }
322 
335 #define IMPLEMENT_DEQUE_MEMORY_POOL(struct_name, type) \
336  struct_name new_##struct_name(size_t); \
337  struct_name new_destructable_##struct_name(size_t, void (*)(type)); \
338  void destroy_##struct_name(struct_name*); \
339  void empty_##struct_name(struct_name*); \
340  bool is_empty_##struct_name(struct_name*); \
341  size_t length_##struct_name(struct_name*); \
342  type* as_array_##struct_name(struct_name*, size_t*); \
343  void apply_##struct_name(struct_name*, void (*)(type)); \
344  void push_front_##struct_name(struct_name*, type); \
345  void push_back_##struct_name(struct_name*, type); \
346  type pop_front_##struct_name(struct_name*); \
347  type pop_back_##struct_name(struct_name*); \
348  type peek_front_##struct_name(struct_name*); \
349  type peek_back_##struct_name(struct_name*); \
350  void update_front_##struct_name(struct_name*, type); \
351  void update_back_##struct_name(struct_name*, type); \
352  \
353  struct_name new_##struct_name(size_t init_cap) { \
354  struct_name ret; \
355  \
356  if (init_cap > 0) \
357  ret.cap = init_cap; \
358  else \
359  ret.cap = 1; \
360  \
361  ret.data = (type*) memory_pool_alloc(init_cap * sizeof(type)); \
362  \
363  if (ret.data == NULL) { \
364  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
365  " contents"); \
366  abort(); \
367  } \
368  \
369  ret.front = ret.back = 0; \
370  ret.destructor = NULL; \
371  \
372  return ret; \
373  } \
374  \
375  struct_name new_destructable_##struct_name(size_t init_cap, \
376  void (*destructor)(type)){ \
377  struct_name ret = new_##struct_name(init_cap); \
378  ret.destructor = destructor; \
379  return ret; \
380  } \
381  \
382  void destroy_##struct_name(struct_name* deq) { \
383  assert(deq != NULL); \
384  \
385  if (deq->data == NULL) \
386  return; \
387  \
388  if (deq->destructor != NULL) \
389  apply_##struct_name(deq, deq->destructor); \
390  \
391  deq->data = NULL; \
392  deq->cap = 0; \
393  deq->front = deq->back = 0; \
394  } \
395  \
396  void empty_##struct_name(struct_name* deq) { \
397  assert(deq != NULL); \
398  assert(deq->data != NULL); /* Make sure the structure is valid */ \
399  deq->front = deq->back = 0; \
400  } \
401  \
402  bool is_empty_##struct_name(struct_name* deq) { \
403  assert(deq != NULL); \
404  assert(deq->data != NULL); /* Make sure the structure is valid */ \
405  return deq->front == deq->back; \
406  } \
407  \
408  size_t length_##struct_name(struct_name* deq) { \
409  assert(deq != NULL); \
410  assert(deq->data != NULL); /* Make sure the structure is valid */ \
411  return (deq->back - deq->front + deq->cap) % deq->cap; \
412  } \
413  \
414  static void __reallign_##struct_name(struct_name* deq) { \
415  assert(deq != NULL); \
416  assert(deq->data != NULL); /* Make sure the structure is valid */ \
417  \
418  if (deq->front != 0) { \
419  type* old_data = deq->data; \
420  size_t len = length_##struct_name(deq); \
421  \
422  deq->data = (type*) memory_pool_alloc(deq->cap * sizeof(type)); \
423  \
424  if (deq->data == NULL) { \
425  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
426  " contents"); \
427  abort(); \
428  } \
429  \
430  size_t i; \
431  \
432  for (i = 0; i < len; ++i) \
433  deq->data[i] = old_data[(deq->front + i) % deq->cap]; \
434  \
435  deq->front = 0; \
436  deq->back = i; \
437  } \
438  } \
439  \
440  type* as_array_##struct_name(struct_name* deq, size_t* len) { \
441  assert(deq != NULL); \
442  assert(deq->data != NULL); /* Make sure the structure is valid */ \
443  \
444  __reallign_##struct_name(deq); \
445  \
446  type* ret = deq->data; \
447  \
448  if (len != NULL) \
449  *len = length_##struct_name(deq); \
450  \
451  deq->data = NULL; \
452  deq->cap = deq->front = deq->back = 0; \
453  \
454  return ret; \
455  } \
456  \
457  void apply_##struct_name(struct_name* deq, void (*func)(type)) { \
458  assert(deq != NULL); \
459  assert(deq->data != NULL); /* Make sure the structure is valid */ \
460  \
461  size_t len = length_##struct_name(deq); \
462  \
463  for (size_t i = 0; i < len; ++i) { \
464  func(deq->data[(deq->front + i) % deq->cap]); \
465  } \
466  } \
467  \
468  static void __on_push_##struct_name(struct_name* deq) { \
469  if (deq->front == (deq->back + 1) % deq->cap) { \
470  type* old_data = deq->data; \
471  size_t old_cap = deq->cap; \
472  \
473  deq->cap = 2 * deq->cap; \
474  deq->data = (type*) memory_pool_alloc(deq->cap * sizeof(type)); \
475  \
476  if (deq->data == NULL) { \
477  fprintf(stderr, "ERROR: Failed to reallocate struct_name" \
478  " contents\n"); \
479  abort(); \
480  } \
481  \
482  size_t i; \
483  \
484  for (i = 0; i < old_cap - 1; ++i) \
485  deq->data[i] = old_data[(deq->front + i) % old_cap]; \
486  \
487  deq->front = 0; \
488  deq->back = i; \
489  } \
490  } \
491  \
492  static void __on_pop_##struct_name(struct_name* deq) { \
493  if (is_empty_##struct_name(deq)) { \
494  fprintf(stderr, "ERROR: Cannot pop from of struct_name while it " \
495  "is empty\n"); \
496  abort(); \
497  } \
498  } \
499  \
500  void push_front_##struct_name(struct_name* deq, type element) { \
501  assert(deq != NULL); \
502  assert(deq->data != NULL); /* Make sure the structure is valid */ \
503  __on_push_##struct_name(deq); \
504  deq->front = (deq->front + deq->cap - 1) % deq->cap; \
505  deq->data[deq->front] = element; \
506  } \
507  \
508  void push_back_##struct_name(struct_name* deq, type element) { \
509  assert(deq != NULL); \
510  assert(deq->data != NULL); /* Make sure the structure is valid */ \
511  __on_push_##struct_name(deq); \
512  deq->data[deq->back] = element; \
513  deq->back = (deq->back + 1) % deq->cap; \
514  } \
515  \
516  type pop_front_##struct_name(struct_name* deq) { \
517  assert(deq != NULL); \
518  assert(deq->data != NULL); /* Make sure the structure is valid */ \
519  __on_pop_##struct_name(deq); \
520  size_t old_front = deq->front; \
521  deq->front = (deq->front + 1) % deq->cap; \
522  return deq->data[old_front]; \
523  } \
524  \
525  type pop_back_##struct_name(struct_name* deq) { \
526  assert(deq != NULL); \
527  assert(deq->data != NULL); /* Make sure the structure is valid */ \
528  __on_pop_##struct_name(deq); \
529  deq->back = (deq->back + deq->cap - 1) % deq->cap; \
530  return deq->data[deq->back]; \
531  } \
532  \
533  type peek_front_##struct_name(struct_name* deq) { \
534  assert(deq != NULL); \
535  assert(deq->data != NULL); /* Make sure the structure is valid */ \
536  assert(!is_empty_##struct_name(deq)); \
537  return deq->data[deq->front]; \
538  } \
539  \
540  type peek_back_##struct_name(struct_name* deq) { \
541  assert(deq != NULL); \
542  assert(deq->data != NULL); /* Make sure the structure is valid */ \
543  assert(!is_empty_##struct_name(deq)); \
544  return deq->data[(deq->back + deq->cap - 1) % deq->cap]; \
545  } \
546  \
547  void update_front_##struct_name(struct_name* deq, type element) { \
548  assert(deq != NULL); \
549  assert(deq->data != NULL); /* Make sure the structure is valid */ \
550  assert(!is_empty_##struct_name(deq)); \
551  deq->data[deq->front] = element; \
552  } \
553  \
554  void update_back_##struct_name(struct_name* deq, type element) { \
555  assert(deq != NULL); \
556  assert(deq->data != NULL); /* Make sure the structure is valid */ \
557  assert(!is_empty_##struct_name(deq)); \
558  deq->data[(deq->back + deq->cap - 1) % deq->cap] = element; \
559  }
560 
561 
562 // The following deque is for example and documentation purposes only
563 
570 typedef char Type;
571 
584 IMPLEMENT_DEQUE_STRUCT(Example, Type);
585 
784 PROTOTYPE_DEQUE(Example, Type);
788 #endif //DEQUE_H
Type
char Type
An example type used for example purposes only.
Definition: deque.h:570
IMPLEMENT_DEQUE_STRUCT
#define IMPLEMENT_DEQUE_STRUCT(struct_name, type)
Generates a structure for use with Double Ended Queues.
Definition: deque.h:33
Example
A data structure generated by IMPLEMENT_DEQUE_STRUCT() to store the state of a deque.
Definition: deque.h:584
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.13