FIFO getch/ungetch Functions

Question

I'm currently working myself through K&R and just read about implementing getch() and ungetch().

In K&R these functions are implemented like this:

#include <stdio.h>

#define BUFSIZE 100
char buf[BUFSIZE];     /* buffer for ungetch */
int bufp = 0;          /* next free position in buf */

int getch(void) /* get a (possibly pushed-back) character */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)    /* push character back on input */
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}

As you can see this is implemented like a stack (last in -> first out). This somehow bothers me. In the example:

ungetch('a');
ungetch('b');
ungetch('c');

getch()will return 'c' at the first function call. 'b' on the second function call and 'a' on the third function call. I liked the idea of getting the first 'ungetch()'-ed char at the start and the last 'ungetch'-ed char in the end.

This is what I did:

#include <stdio.h>

#define BUFSIZE 10
static int reorder_buf(void);

char buf[BUFSIZE];
int bufrp = 0;    //buffer read position
int bufwp = 0;    //buffer write position

int getch(void)
{
    if (bufrp < bufwp)
        return buf[bufrp++];
    else {
        if(bufwp != 0)
            bufwp = bufrp = 0;

        return getchar();
    }
}

void ungetch(int c)
{
    if (bufwp < BUFSIZE)
        buf[bufwp++]=c;
    else
    {
        if (reorder_buf() != 0)     //successful reorder
        {
            buf[bufwp++]=c;
        } else                      //full buffer
        {
            printf("Failed to ungetch(%c).\n", c);
        }
    }
}

/**
 * Tries to move buffer content to the start of the buffer.
 *
 * @return 1 on successful reorder, 0 otherwise
 */
static int reorder_buf(void)
{
    if (bufrp > 0)
    {
        int i;
        for(i = 0; bufrp < bufwp; bufrp++, i++)
             buf[i] = buf[bufrp];

        bufrp = 0;
        bufwp = i;
        return 1;
     } else
     {
         return 0;
     }
}

I also had the idea to replace the error message in ungetch() with returning an int, which includes the information if the unget process was successful and provides it to the caller.

Answer 1

reorder_buf() is horribly inefficient, and it's unnecessary if you use the buffer as a circular-list. What you want is called a ring buffer.

/* Store up to 10 characters */
#define BUFSIZE 11

char buf[BUFSIZE];
int qhead = 0, qtail = 0;

int getch(void) {
    if (qhead != qtail) {
        int c = buf[qhead];
        qhead = (qhead + 1) % BUFSIZE;
        return c;
    } else {
        return getchar();
    }
}

void ungetch(int c) {
    if ((qtail + 1) % BUFSIZE == qhead) {
        fprintf(stderr, "Buffer full, dropped %c.\n", c);
    } else {
        buf[qtail] = c;
        qtail = (qtail + 1) % BUFSIZE;
    }
}

Errors should go to stderr rather than stdout.

Answer 2

Your ungetch has very strange behavior on error.
I'm not quite sure whether it's better or worse than On Error Resume Next, but it's certainly in the same class.

Either handle it yourself, which means reporting an error to stderr and aborting the program, or report it to the caller (see the docs on ungetc for a way).
At the moment, you print an error-message (which might get lost in the output, and anyway there's a human actively and attentively monitoring things), but then happily move on with data-loss and without informing the caller.