deque.h (3395B)
1 #pragma once 2 3 #include <string.h> 4 5 #include "alloc.h" 6 #include "def.h" 7 8 #include "deque-defaults.h" 9 10 /* TODO: Storing power-of-2 cap as a usize is a waste. We could store the 11 * shift count as a u8 and then use the 7 saved bytes for, e.g., a reference 12 * counter an a flags field. */ 13 14 #define R_DEQUE_TYPEDEF(D, T)\ 15 typedef struct D { \ 16 T *arr; \ 17 usize cap; /* Always a power of 2 for fast mod */ \ 18 usize l; /* Left end of active region */ \ 19 usize r; /* 1 past right end of active region */ \ 20 } D; 21 22 /* Invariants: 23 * Empty iff l == cap && r == 0 24 * Full iff l == r */ 25 26 #define R_DEQUE_DECLARE(D, T, ...)\ 27 static inline UNUSED usize R_DEQUE_METHOD(len,##__VA_ARGS__)(D *d) { return d->l == d->r ? d->cap : (d->r - d->l) & (d->cap - 1); } \ 28 static inline UNUSED usize R_DEQUE_METHOD(cap,##__VA_ARGS__)(D *d) { return d->cap; } \ 29 R_DEQUE_STATIC UNUSED void R_DEQUE_METHOD(free,##__VA_ARGS__)(D *d); \ 30 R_DEQUE_STATIC UNUSED int R_DEQUE_METHOD(reserve,##__VA_ARGS__)(D *d, usize n); \ 31 R_DEQUE_STATIC UNUSED int R_DEQUE_METHOD(pushl,##__VA_ARGS__)(D *d, T e); \ 32 R_DEQUE_STATIC UNUSED int R_DEQUE_METHOD(pushr,##__VA_ARGS__)(D *d, T e); \ 33 R_DEQUE_STATIC UNUSED T R_DEQUE_METHOD(popl,##__VA_ARGS__)(D *d); \ 34 R_DEQUE_STATIC UNUSED T R_DEQUE_METHOD(popr,##__VA_ARGS__)(D *d); \ 35 static inline UNUSED T R_DEQUE_METHOD(peekl,##__VA_ARGS__)(D *d) { return d->arr[d->l]; } \ 36 static inline UNUSED T R_DEQUE_METHOD(peekr,##__VA_ARGS__)(D *d) { return d->arr[(d->r - 1) & (d->cap - 1)]; } \ 37 static inline UNUSED T *R_DEQUE_METHOD(idx,##__VA_ARGS__)(D *d, usize i) { return &d->arr[(d->l + i) & (d->cap - 1)]; } 38 39 #define R_DEQUE_DEFINE(D, T, ...)\ 40 void R_DEQUE_METHOD(free,##__VA_ARGS__)(D *d) { \ 41 R_DEQUE_FREE(d->arr); \ 42 *d = (D){0}; \ 43 } \ 44 int R_DEQUE_METHOD(reserve,##__VA_ARGS__)(D *d, usize n) { \ 45 usize rem = d->cap - R_DEQUE_METHOD(len,##__VA_ARGS__)(d); \ 46 if (n <= rem) \ 47 return 0; \ 48 usize need = n - rem; \ 49 usize ncap = MAX(d->cap, 1<<R_DEQUE_MIN_BITS); \ 50 while (need > ncap - d->cap) { \ 51 ncap <<= 1; \ 52 if (ncap == 0) \ 53 return -1; /* Overflow */ \ 54 } \ 55 if (R_DEQUE_REALLOCN(&d->arr, ncap, sizeof *d->arr) < 0) \ 56 return -1; \ 57 if (d->l == d->cap) { \ 58 d->l = ncap; /* Maintain invariant for empty deques */ \ 59 } else if (d->r <= d->l) { \ 60 /* Move as little as possible */ \ 61 if (d->r <= d->cap - d->l) { \ 62 memcpy(&d->arr[d->cap], &d->arr[0], d->r * sizeof *d->arr); \ 63 d->r += d->cap; \ 64 } else { \ 65 usize m = d->cap - d->l; \ 66 memcpy(&d->arr[ncap-m], &d->arr[d->l], m * sizeof *d->arr); \ 67 d->l = ncap - m; \ 68 } \ 69 } \ 70 d->cap = ncap; \ 71 return 0; \ 72 } \ 73 int R_DEQUE_METHOD(pushl,##__VA_ARGS__)(D *d, T e) { \ 74 if (R_DEQUE_METHOD(reserve,##__VA_ARGS__)(d, 1) < 0) \ 75 return -1; \ 76 d->l = (d->l - 1) & (d->cap - 1); \ 77 d->arr[d->l] = e; \ 78 return 0; \ 79 } \ 80 int R_DEQUE_METHOD(pushr,##__VA_ARGS__)(D *d, T e) { \ 81 if (R_DEQUE_METHOD(reserve,##__VA_ARGS__)(d, 1) < 0) \ 82 return -1; \ 83 d->arr[d->r] = e; \ 84 d->r = (d->r + 1) & (d->cap - 1); \ 85 if (d->l == d->cap) \ 86 d->l = 0; \ 87 return 0; \ 88 } \ 89 T R_DEQUE_METHOD(popl,##__VA_ARGS__)(D *d) { \ 90 T e = d->arr[d->l]; \ 91 d->l = (d->l + 1) & (d->cap - 1); \ 92 if (d->l == d->r) { \ 93 d->l = d->cap; \ 94 d->r = 0; \ 95 } \ 96 return e; \ 97 } \ 98 T R_DEQUE_METHOD(popr,##__VA_ARGS__)(D *d) { \ 99 d->r = (d->r - 1) & (d->cap - 1); \ 100 T e = d->arr[d->r]; \ 101 if (d->l == d->r) { \ 102 d->l = d->cap; \ 103 d->r = 0; \ 104 } \ 105 return e; \ 106 }