eval-prefix-notation-fork-pipe.c

/** Prefix notation calculator implemented in terms of fork/pipe
    without recursion/stack.

    http://stackoverflow.com/questions/20165145/prefix-notation-calculation-using-fork-and-pipes-in-c-without-recursion-or-st

    It accepts input on stdin and writes the final result to stdout.

    It uses gmplib (-lgmp) to support arbitrary precision integer arithmetic.
*/

/* for fdopen and getdelim */
#if ! defined(_POSIX_C_SOURCE) || _POSIX_C_SOURCE < 200809L
#define _POSIX_C_SOURCE 200809L
#endif

#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

#include <gmp.h>

/* number of arguments */
#ifndef ARITY
#define ARITY 2
#endif

static int child = 0; /* whether we are in a child process relative to main()*/

static void report_error_and_exit(const char* msg) {
  perror(msg);
  (child ? _exit : exit)(EXIT_FAILURE);
}

/** get next space-separated token from stdin */
static ssize_t gettoken(char** tokenptr, size_t *n) {
  ssize_t len = getdelim(tokenptr, n, ' ', stdin);
  while (len > 0 && isspace((*tokenptr)[len-1])) {
    (*tokenptr)[--len] = '\0'; /* rstrip whitespace */
  }
  return len;
}

static int isoperator(char token) { /*XXX keep it in sync with operator() */
  return token == '+' || token == '-' || token == '*' || token == '/';
}

/** perform `args[0] = op(args[0], args[1], args[2], ...)` */
static void operator(char op, mpz_t* args, size_t n) {
  size_t i = 1;
  assert(isoperator(op));
  /* args[0] = op(op(op(args[0], args[1]), args[2]), args[3]) ... */
  for ( ; i < n; ++i) {
    switch(op) {
    case '+':
      mpz_add(args[0], args[0], args[i]);
      break;
    case '-':
      mpz_sub(args[0], args[0], args[i]);
      break;
    case '*':
      mpz_mul(args[0], args[0], args[i]);
      break;
    case '/':
      mpz_div(args[0], args[0], args[i]);
      break;
    default:
      report_error_and_exit("operator");
    }
  }
}

/** write `result` to `result_out_fd` and exit.

    Use human-readable form (decimal) if called from the parent process
*/
static void return_(mpz_t result, int result_out_fd) {
  FILE* fp = fdopen(result_out_fd, "w");
  if (fp == NULL)
    report_error_and_exit("fdopen");

  if (child)
    mpz_out_raw(fp, result);
  else {
    mpz_out_str(fp, 10, result); /* human readable */
    fputs("\n", fp);
  }

  if (fclose(fp) != 0)
    report_error_and_exit("fclose");
  mpz_clear(result);
  (child ? _exit : exit)(EXIT_SUCCESS);
}

/** read result from `fd` and put it into `result`

    Wait for child with `pid` to exit.
*/
static void getresult(int fd, pid_t pid, mpz_t result) {
  int status = -1;
  FILE* fp = fdopen(fd, "r");
  if (fp == NULL)
    report_error_and_exit("fdopen");

  mpz_inp_raw(result, fp);

  if (fclose(fp) != 0)
    report_error_and_exit("fclose");

  if (waitpid(pid, &status, 0) == -1)
    report_error_and_exit("waitpid");

  if (!(WIFEXITED(status) && WEXITSTATUS(status) == 0)) {
    fprintf(stderr, "error: failed to getresult()"
            " from pipe: %d child pid: %" PRIdMAX " got status: %d\n",
            fd, (intmax_t)pid, status);
    _exit(EXIT_FAILURE);
  }
}

int main(void) {
  int result_out_fd = STDOUT_FILENO;
  size_t capacity = 3; /* token + delimiter + '\0' */
  char* token = malloc(capacity);

  setbuf(stdin, NULL); /* unbuffer stdin (for child processes) */
  while(gettoken(&token, &capacity) > 0) {
    if (isoperator(*token)) {
      mpz_t args[ARITY];
      int i = 0;
      pid_t pid = 0;
      /* compute `result = op(args[0], args[1], ...)` */
      for ( ; i < ARITY; ++i) {
        int fd[2]; /* a pipe to pass individual arguments to the parent */

        /* create a child process to get argument */
        if (pipe(fd) == -1)
          report_error_and_exit("pipe");
        if ((pid = fork()) == -1)
          report_error_and_exit("fork");
        else if (pid == 0) { /* child */
          child = 1;
          close(fd[0]); /* unused */
          close(result_out_fd);
          result_out_fd = fd[1]; /* overwrite in child */
          break; /* one child -- one argument */
        }
        else { /* parent */
          mpz_init (args[i]);
          close(fd[1]); /* unused */
          /* read result, wait for child to exit */
          getresult(fd[0], pid, args[i]); /* got argument */
        }
      }
      if (pid && i == ARITY) { /* parent */
        /* compute `arg1 = op(arg1, arg2, arg3, ...)` */
        operator(*token, args, ARITY);
        for (i = 1; i < ARITY; ++i)
          mpz_clear(args[i]);
        /* write result, exit the process */
        return_(args[0], result_out_fd);
      }
    }
    else { /* token is a number */
      /* parse token string as an integer */
      mpz_t number;
      if (mpz_init_set_str(number, token, 10) == -1) {
        mpz_clear(number);
        report_error_and_exit("mpz_init_set_str");
      }
      /* write result, exit the process */
      return_(number, result_out_fd);
    }
  }
  free(token);
  exit(feof(stdin) ? EXIT_SUCCESS : EXIT_FAILURE);
}