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

In K&amp;R these functions are implemented like this:


#include &lt;stdio.h&gt;

#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 &gt; 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)    /* push character back on input */
{
    if (bufp &gt;= 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 &lt;stdio.h&gt;

#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 &lt; bufwp)
        return buf[bufrp++];
    else {
        if(bufwp != 0)
            bufwp = bufrp = 0;

        return getchar();
    }
}

void ungetch(int c)
{
    if (bufwp &lt; 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 &gt; 0)
    {
        int i;
        for(i = 0; bufrp &lt; 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.
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.