Topic: The Buffer data structure.
This page last updated: Sunday September 27, 1998 01:07This is a review of C coding style, data structures, and memory management. It prepares you to better understand the type of internal data structures used by the interpreter you will be building this term.
Complete the following two-part C program and test it thoroughly.
- Part 1:
- Complete the coding for a "Buffer" data structure and its supporting functions.
Use the function prototypes given below. Write the associated code.
- Part 2:
- Use the buffer data structure to prompt and read lines of text from standard input and print the lines and their lengths. Use the main program and the my_prompt() function prototype exactly as given below. The input loop in main() will terminate on EOF or the input line "done".
- When all the lines have been read, print the size of the largest buffer used to handle the input lines. (See the last printf() statement in the given main() function.)
- A line of text contains all characters until the EOF or newline.
- Your program must not overflow any buffers, no matter how long the input string is. Your buffer manager must grow the buffer (using realloc()) as required.
- When the instructions require you to code "exactly as given", please pay attention. You may adjust the formatting, comments, and names of local variables; but, do not change the names of functions or the function calling and return sequences.
Here is the "buffer" data structure:
typedef struct Buffer {
char *buf; /* pointer returned by malloc */
int maxsize; /* size of space allocated by malloc */
int cursize; /* amount of space currently used */
int incr; /* increment to add when growing maxsize */
} Buffer;
Here are the supporting functions for the buffer data structure:
static Buffer *bf_alloc( int size, int incr );
- allocates a new Buffer structure
- gives the internal buffer the given initial "size"
using malloc(); copies the given "size" into maxsize
- saves the value of "incr" in the buffer structure for
later use by bf_addch()
- returns a pointer to the buffer structure on success
- returns NULL on error
static Buffer *bf_addch( Buffer *buf, char ch );
- adds the character ch to the end of the given Buffer
- if the buffer is full, it adds incr bytes to maxsize
and uses realloc() to make the buffer larger before
adding the character
- increments cursize by one to count the character added
- returns a pointer to the buffer structure on success
- returns NULL on error
static void bf_clear( Buffer *buf );
- re-initializes the given Buffer, such that the next call to
bf_addch will put the character at the start of the buffer
- does not alter maxsize, buf, or incr
- does not need to overwrite the existing contents
static void bf_valid( Buffer *buf );
- tests that the given pointer is a valid Buffer
- are all Buffer values consistent with each other?
- prints an error message and exits the program on error
static void bf_free(Buffer *buf);
- de-allocates the Buffer and any memory it may contain
What value should be passed as incr when calling bf_alloc?
When cursize reaches maxsize, the buffer is full and needs to grow. incr tells the bf_addch function by how much the buffer grows, when the buffer needs to expand to accept more data. incr is added to maxsize before using realloc to reallocate the buffer at the new, larger size.
You might set incr to 1, to make the buffer grow by only one character, in which case it would have to grow every time a new character needed to be added. (This would be rather inefficient, since every growth requires a call to realloc, and realloc may have to copy the entire contents of the buffer.)
You might set incr to a million, to make the buffer grow by 1,000,000 characters, in which case it may not grow more than once; but, most of the buffer may never get used and you may "waste" a lot of memory. (On some computers, notably DOS and Windows computers, you will not be able to allocate more than 64K of memory in a single "chunk" unless you specifically tell the C compiler to use a "large" or "huge" memory model.)
Here is the main function that uses the buffer data structure to read lines from stdin and print them. You need to pick suitable values to define for MY_INIT and MY_INCR. The function my_prompt() does most of the work; it is described below:
#define EQ(s1,s2) (strcmp(s1,s2) == 0) /* string equality macro */
int
main(void) {
Buffer *buf;
/* Allocate a Buffer */
buf = bf_alloc(MY_INIT, MY_INCR);
if( buf == NULL ){
eprintf("Could not create initial buffer size %d",
MY_INIT);
exit(1);
}
/* Loop, filling the Buffer with one line and printing it */
do {
bf_clear(buf);
buf = my_prompt("Enter a string: ", buf);
printf("String is '%s', size %d\n",
buf->buf, buf->cursize);
} while( ! EQ(buf->buf,"done") && ! feof(stdin) );
printf("Buffer maximum size grew to %d characters\n",
buf->maxsize);
/* Free the Buffer */
bf_free(buf);
return 0; /* Success */
}
You need to write the my_prompt() function using the following prototype:
static Buffer *my_prompt( char *prompt, Buffer *buf );
- prints the prompt on the terminal only if standard input
is a terminal -- see isatty() and fileno()
- accepts a pointer to an initialized Buffer
- uses bf_addch() to put characters in the buffer until
EOF or a newline
- bf_addch() grows the buffer as needed
- terminates the buffer with a NUL character when done
- returns a pointer to the buffer
- no error return value; any errors cause the program to exit
Here is the eprintf() error printing function declaration and definition. You will find similar examples of functions taking variable numbers of arguments in the help files and manual pages for your C Library:
#include <string.h>
#include <stdarg.h>
static void eprintf(char *fmt, ...);
/*VARARGS1*/
static void
eprintf( char *fmt, ... ){
va_list ap;
va_start(ap, fmt);
(void)vfprintf(stderr, fmt, ap);
va_end(ap);
/* Make sure error messages end in a newline */
if( strchr(fmt,'\n') == NULL )
fprintf(stderr,"\n");
}