Please Explain this Example C Code

Question

This code comes from K&R. I have read it several times, but it still seems to escape my grasp.

#define BUFSIZE 100

char buf[BUFSIZE];
int bufp = 0;

int getch(void)
{
      return(bufp>0)?buf[--bufp]:getchar();
}

int ungetch(int c)
{
      if(bufp>=BUFSIZE)
            printf("too many characters");
      else buf[bufp++]=c;
}

The purpose of these two functions, so K&R says, is to prevent a program from reading too much input. i.e. without this code a function might not be able to determine it has read enough data without first reading too much. But I don't understand how it works.

For example, consider getch(). As far as I can see this is the steps it takes:

1. check if bufp is greater than 0.
2. if so then return the char value of buf[--bufp].
3. else return getchar().

I would like to ask a more specific question, but I literally dont know how this code achieves what it is intended to achieve, so my question is: What is (a) the purpose and (b) the reasoning of this code?

Thanks in advance.

NOTE: For any K&R fans, this code can be found on page 79 (depending on your edition, I suppose)

Answer 1

(a) The purpose of this code is to be able to read a character and then "un-read" it if it turns out you accidentally read a character too many (with a max. of 100 characters to be "un-read"). This is useful in parsers with lookahead.

(b) getch reads from buf if it has contents, indicated by bufp>0. If buf is empty, it calls getchar. Note that it uses buf as a stack: it reads it from right-to-left.

ungetch pushes a character onto the stack buf after doing a check to see if the stack isn't full.

Answer 2

The code is not really for "reading too much input", instead is it so you can put back characters already read.

For example, you read one character with getch, see if it is a letter, put it back with ungetch and read all letters in a loop. This is a way of predicting what the next character will be.

Answer 3

This block of code is intended for use by programs that make decisions based on what they read from the stream. Sometimes such programs need to look at a few character from the stream without actually consuming the input. For example, if your input looks like abcde12xy789 and you must split it into abcde, 12, xy, 789 (i.e. separate groups of consecutive letters from groups of consecutive digits) you do not know that you have reached the end of a group of letters until you see a digit. However, you do not want to consume that digit at the time you see it: all you need is to know that the group of letters is ending; you need a way to "put back" that digit. An ungetch comes in handy in this situation: once you see a digit after a group of letters, you put the digit back by calling ungetch. Your next iteration will pick that digit back up through the same getch mechanism, sparing you the need to preserve the character that you read but did not consume.

Answer 4

1. The other idea also shown here can be also called as a very primitive I/O stack mangement system and gives the implementation of the function getch() and ungetch().

2. To go a step further , suppose you want to design an Operating System , how can you handle the memory which stores all the keystrokes?

This is solved by the above code snippet.An extension of this concept is used in file handling , especially in editing files .In that case instead of using getchar() which is used to take input from Standard input , a file is used as a source of input.

Answer 5

I have a problem with code given in question. Using buffer (in form of stack) in this code is not correct as when getting more than one extra inputs and pushing into stack will have undesired effect in latter processing (getting input from buffer).

This is because when latter processing (getting input) going on ,this buffer (stack) will give extra input in reverse order (means last extra input given first).

Because of LIFO (Last in first out ) property of stack , the buffer in this code must be quene as it will work better in case of more than one extra input.

This mistake in code confused me and finally this buffer must be quene as shown below.

#define BUFSIZE 100

char buf[BUFSIZE];
int bufr = 0;
int buff = 0;

int getch(void)
{
      if (bufr ==BUFSIZE)
             bufr=0;

      return(bufr>=0)?buf[bufr++]:getchar();
}

int ungetch(int c)
{
      if(buff>=BUFSIZE && bufr == 0)
            printf("too many characters");
      else if(buff ==BUFSIZE) 
            buff=0;  

       if(buff<=BUFSIZE)
            buf[buff++]=c;
}