Tail Program
Pointers
Print pointer values:
Edit the explore.c file to add printf statements to print both variable values and values of the pointers to variables and/or array[0] where indicated. Note that if you print a pointer value you should use %p as the format. For all other values, you should use %x format. Remember to build your program using the –m32 option for a 32-bit application.
You should find that as automatic variables are allocated memory or as arguments are pushed onto the stack to be passed to a function (foobar) that the addresses of the locations in memory are decreasing.
In the main program printf loop for array[i], it should be sufficient to print for i = 0 to i < 6. Can you find the locations that have been assigned for the automatic variables and can you see their values?
In the foobar function printf loop for array[i], it should be sufficient to print for i = 0 to i < about 40 or 50. Can you find the locations that have been assigned for the automatic variable and the argument list variables? Can you see the same data that you printed above in the main program further back on the stack?
Write a memo.txt file to document your findings.
Do K&R Exercise 5-13:
The program takes lines from standard input and keeps the last n of them in memory as it goes through standard input. When it gets to an EOF, it prints the last n lines out. You may assume n is less than 2000 and each individual line is not longer than 1000 including the newline and the null terminator.
Use two source files plus a header file for this, just to show you know how to make multiple source files work together.
tail.c: interprets the command line argument.
Calls init_lineholder(intnlines) with the number from the command line.
Does a loop calling getline and insert_line(char *line).
When getline returns 0 (indicating EOF on stdin), it calls print_lines().
lineholder.c: contains a static array of pointers for lines.
Implements init_lineholder, insert_line, and print_lines.
Init_lineholder initializes the “first” slot and related variables.
Insert_line adds a line to the array.
It must allocate memory for the new line.
It must free the memory for a line no longer needed, if any.
Print_lines prints the lines in the array and frees the memory used for them.
lineholder.h: just has prototypes for the three calls with appropriate comments explaining what they do for the caller.
Write a makefile that compiles tail.c and lineholder.c, with the appropriate dependencies, and builds the executable “tail”. (tail should be the default target.) Also provide “make clean” to remove the intermediate object files. Also include the option to build the executable using the –m32 switch for a 32-bit application.
Only the last n lines should be held in memory, not all the lines. You should set up an array of char * pointers as on page 108. Instead of alloc, use malloc (see p. 143 for an example of the use of malloc.). When you are done with a line, use free(pointer) to release the memory previously allocated with malloc. You only need one buffer of length 1000. All the mallocs should be of just the right length to hold the actual line.
Be sure you explain your method of adding the n+1st line and freeing lines no longer needed in a good header comment at the beginning of lineholder.c. You have a choice of methods for adding the n+1’st line to the array of n lines. Here are two ideas:
Ripple the pointers down one slot in the array and put the new one at slot n-1. First you need to free the one at slot 0. Similarly treat each succeeding line.
Maintain a moving “first” slot variable, that stays at 0 for the first n line additions, now moves to slot 1. Free the old line at slot 0 and put the new one there. When another line comes in, release the one at slot 1 and put the new one there, and make “first” be 2. When you print them all out, wrap around from slot n-1 to slot 0 and back to slot first-1.
You can generate your own test1.in, test2.in, etc. files, or to use test files provided tail0.in, tail1.in etc., to test all special cases that your tail program might encounter and generate test1.out, test2.out, etc. files.
Solution
part1
Here are the findings:
(1) Variables a, b, c are stored in the lower address space because they are static variables.
They are stored in the static data section.
(2) Variable d and the array are stored in a higher address space because they are automatic
variables. They are stored in the function calling frame space (stack).
(3) When the array is printed in foobar function, the value of the parameters are also printed.
This indicate that the parameters are also saved in the calling frame space (stack). They are
also considered automatic variables.
(4) I cannot see the same data on the stack in the main function. main function is called by the
system.
part2
lineholder.c
#include
#include
#include
#include “lineholder.h”
/**
* The line holder uses a cyclic buffer to store the last nlines.
* It maintains one index “first” indicate where the first line is
* in the pointer array. It also maintains a counter to indicate
* how many lines are currently saved into the pointer array.
*
* Thus, When to add the n + 1 line, the line saved as buffer[first] is first
* released. Then we decrease the counter and increase the first location,
* so we can save the copy of the new line into buffer[(first + counter) % CAPACITY].
* see insert_line(char *line) function for more detail.
*/
#define CAPACITY 2000
static char *buffer[CAPACITY];
staticint n; /* save up to n lines into the array */
staticint first;
staticint count;
voidinit_lineholder(intnlines) {
if (nlines<= 0 || nlines> CAPACITY) {
fprintf(stderr, “could not save more than %d lines\n”, CAPACITY);
exit(0);
}
/* initialize the first and counter, which indicate
* the cyclic buffer (lines) is empty. */
n = nlines;
first = 0;
count = 0;
}
voidinsert_line(const char *line) {
char *copy;
if (count == n) {
/* we already have enough lines. Thus, we need to remove
* the old line first before we put the new one into */
char *old_line = buffer[first];
first = (first + 1) % CAPACITY;
free(old_line);
count –;
}
/* save a copy of the line into the buffer */
copy = (char *)malloc(strlen(line) + 1);
strcpy(copy, line);
buffer[(first + count) % CAPACITY] = copy;
count ++;
}
voidprint_lines() {
int i = 0;
/* print each line, since its cyclic buffer, the index
* of the line must use % to calculate. */
while (i < count) {
printf(“%s”, buffer[(first + i) % CAPACITY]);
i ++;
}
}
lineholder.h
#ifndef LINEHOLDER_H_
#define LINEHOLDER_H_
/* setup the lineholder so that it saves the last up to nlines.
* nlines must be no more than 2000. */
voidinit_lineholder(intnlines);
/* insert a new line to the lineholder. */
voidinsert_line(const char *line);
/* print the lines saved in the line holder. */
voidprint_lines();
#endif
tail.c
#include
#include
#include
#include “lineholder.h”
int main(intargc, char *argv[]) {
/* only one buffer is needed */
char *line = malloc(1000);
size_t size = 1000;
intnlines;
/* get the nlines from the parameter */
if (argc != 2) {
printf(“Usage: %s nlines\n”, argv[0]);
exit(0);
}
nlines = atoi(argv[1]);
/* initialize the lineholder and starts to add the line
* read from standard input into the lineholder. */
init_lineholder(nlines);
while (getline(&line, &size, stdin) != EOF) {
insert_line(line);
}
/* print the last n lines */
print_lines();
return 0;
}