git.ozlabs.org Git - ccan/blob - ccan/deque/_info

   1 #include "config.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 /**
   6  * deque - type-preserving resizing circular deque
   7  *
   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.
  15  *
  16  * Example:
  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
  20  *      #include <stdio.h>
  21  *      #include <stdlib.h>
  22  *      #include <ctype.h>
  23  *      #include <err.h>
  24  *      #include <ccan/deque/deque.h>
  25  *
  26  *      static double eval(char op, double a, double b)
  27  *      {
  28  *              switch (op) {
  29  *              case '+': return a + b;
  30  *              case '-': return a - b;
  31  *              case '/': return a / b;
  32  *              case '*': return a * b;
  33  *              }
  34  *              errx(1, "bad op: %c", op);
  35  *      }
  36  *
  37  *      char opchr[] = { '(', ')', '+', '-', '*', '/' };
  38  *      int  opprc[] = {  0 ,  0 ,  1 ,  1 ,  2 ,  2  };
  39  *
  40  *      static int precedence(char op)
  41  *      {
  42  *              int i;
  43  *              for (i = 0; i < sizeof(opchr); i++)
  44  *                      if (opchr[i] == op)
  45  *                              return opprc[i];
  46  *              return -1;
  47  *      }
  48  *
  49  *      #define ok(x) ({ int n = (x); if (n == -1) err(1, "%s", #x); n; })
  50  *
  51  *      int main(int argc, char *argv[])
  52  *      {
  53  *              DEQ_WRAP(char) *ops;
  54  *              DEQ_WRAP(double) *vals;
  55  *              char *ln = NULL, *p, op;
  56  *              size_t lnsz = 0;
  57  *              double a, b;
  58  *              int n;
  59  *
  60  *              ok(deq_new(ops,  8, DEQ_NO_SHRINK));
  61  *              ok(deq_new(vals, 8, DEQ_NO_SHRINK));
  62  *
  63  *              while (getline(&ln, &lnsz, stdin) > 0) {
  64  *
  65  *                      for (p = ln; *p; p++) {
  66  *                              if (isspace(*p))
  67  *                                      continue;
  68  *
  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));
  73  *                                      p += n - 1;
  74  *                                      continue;
  75  *                              }
  76  *
  77  *                              while (1) {
  78  *                                      if (*p == '(' || deq_last(ops, &op) == 0 || (precedence(*p) > precedence(op))) {
  79  *                                              ok(deq_push(ops, *p));
  80  *                                              break;
  81  *                                      }
  82  *
  83  *                                      ok(deq_pop(ops, &op));
  84  *
  85  *                                      if (op == '(') {
  86  *                                              assert(*p == ')');
  87  *                                              break;
  88  *                                      }
  89  *                                      else {
  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)));
  95  *                                      }
  96  *                              }
  97  *                      }
  98  *
  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)));
 105  *                      }
 106  *
 107  *                      if ((n = deq_len(vals)) != 1)
 108  *                              errx(1, "wrong number of values: %d", n);
 109  *
 110  *                      ok(deq_pop(vals, &a));
 111  *                      printf("%.lf\n", a);
 112  *              }
 113  *
 114  *              if (ferror(stdin))
 115  *                      err(1, "getline");
 116  *
 117  *              deq_free(ops);
 118  *              deq_free(vals);
 119  *              free(ln);
 120  *              exit(0);
 121  *      }
 122  *
 123  * License: APACHE-2
 124  * Author: Dan Good <dan@dancancode.com>
 125  */
 126 int main(int argc, char *argv[])
 127 {
 128         /* Expect exactly one argument */
 129         if (argc != 2)
 130                 return 1;
 131
 132         if (strcmp(argv[1], "depends") == 0)
 133                 return 0;
 134         if (strcmp(argv[1], "testdepends") == 0) {
 135                 printf("ccan/failtest\n");
 136                 return 0;
 137         }
 138
 139         if (strcmp(argv[1], "ccanlint") == 0) {
 140                 /* uses statement expressions
 141                  * supported by gcc, clang, icc, and some others, but not msvc
 142                  * (see https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) */
 143                 printf("objects_build_without_features FAIL\n");
 144                 return 0;
 145         }
 146
 147         return 1;
 148 }