6 * deque - type-preserving resizing circular deque
8 * This is a deque (double-ended queue, pronounced deck) implementation using
9 * a resizing circular buffer. At steady state, deque operations can proceed
10 * perpetually without mallocing. The initial capacity must be specified and
11 * is a lower bound when shrinking. Buffer capacity is doubled at enqueue
12 * to a full deque. Shrink behavior choices are never shrink, shrink to
13 * minimum when the queue is empty, or shrink by half when the queue is at 20%
14 * of capacity. Operation names are in the Perl/Ruby style.
17 * // Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.
18 * // Original: http://algs4.cs.princeton.edu/13stacks/EvaluateDeluxe.java.html
19 * #define _XOPEN_SOURCE 700 // only for getline(3) in this demo
24 * #include <ccan/deque/deque.h>
26 * static double eval(char op, double a, double b)
29 * case '+': return a + b;
30 * case '-': return a - b;
31 * case '/': return a / b;
32 * case '*': return a * b;
34 * errx(1, "bad op: %c", op);
37 * char opchr[] = { '(', ')', '+', '-', '*', '/' };
38 * int opprc[] = { 0 , 0 , 1 , 1 , 2 , 2 };
40 * static int precedence(char op)
43 * for (i = 0; i < sizeof(opchr); i++)
49 * #define ok(x) ({ int n = (x); if (n == -1) err(1, "%s", #x); n; })
51 * int main(int argc, char *argv[])
53 * DEQ_WRAP(char) *ops;
54 * DEQ_WRAP(double) *vals;
55 * char *ln = NULL, *p, op;
60 * ok(deq_new(ops, 8, DEQ_NO_SHRINK));
61 * ok(deq_new(vals, 8, DEQ_NO_SHRINK));
63 * while (getline(&ln, &lnsz, stdin) > 0) {
65 * for (p = ln; *p; p++) {
69 * if (precedence(*p) == -1) {
70 * if (sscanf(p, "%lf%n", &a, &n) != 1)
71 * errx(1, "parse fail: %s", p);
72 * ok(deq_push(vals, a));
78 * if (*p == '(' || deq_last(ops, &op) == 0 || (precedence(*p) > precedence(op))) {
79 * ok(deq_push(ops, *p));
83 * ok(deq_pop(ops, &op));
90 * if (deq_len(vals) < 2)
91 * errx(1, "out of values");
92 * ok(deq_pop(vals, &b));
93 * ok(deq_pop(vals, &a));
94 * ok(deq_push(vals, eval(op, a, b)));
99 * while (ok(deq_pop(ops, &op)) == 1) {
100 * if (deq_len(vals) < 2)
101 * errx(1, "out of values");
102 * ok(deq_pop(vals, &b));
103 * ok(deq_pop(vals, &a));
104 * ok(deq_push(vals, eval(op, a, b)));
107 * if ((n = deq_len(vals)) != 1)
108 * errx(1, "wrong number of values: %d", n);
110 * ok(deq_pop(vals, &a));
111 * printf("%.lf\n", a);
124 * Author: Dan Good <dan@dancancode.com>
127 * // uses statement expressions
128 * // supported by gcc, clang, icc, and some others, but not msvc
129 * // (see https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)
130 * objects_build_without_features FAIL
132 int main(int argc, char *argv[])
134 /* Expect exactly one argument */
138 if (strcmp(argv[1], "depends") == 0)
140 if (strcmp(argv[1], "testdepends") == 0) {
141 printf("ccan/failtest\n");