In today's lab:
To complete this lab you should be familiar with these topics:
As with primitive C arrays, a growable array of size S has valid indices 0 through (S - 1). So, if the end-user sets a value at an index greater than or equal to S, the array will "grow" to fit the new data.
Header file garray.h contains this structure definition to represent an instance of a growable array:
typedef struct garray_s {
int sz; /* size of data buffer */
int * data; /* data buffer */
} GArray;
You are given a simple file, garray_example.c that shows how a GArray may be used:
/* Initialize an array of size 8 */
GArray * ga = init(8);
/* set value at index 3 to 42 */
if ( set_val(ga,3,42) == GA_ERR )
printf("Call to set_val() failed\n");
...
/* grow array - set value at index 15 */
if ( set_val(ga,15,42) == GA_ERR )
printf("Call to set_val() failed\n");
The array should grow to be exactly the size needed to store the new item. So if the current size is 16, and the user sets a value at index 20, then the array will grow to size 21 (with valid indices 0 through 20).
An alternative approach would be to always grow the array by some factor, for example to double the size of the array whenever it must be resized. So in the above example, the array of size 16 would grow to size 32, even though space for only 21 integers is immediately necessary. Doubling the size of the array has the advantage of minimizing the number of times that the array buffer needs to be resized. However, for this lab we will only grow the array to the exact size needed to keep the problem simple.
You will want to use the function realloc in stdlib.h when you need to grow your growable array. realloc resizes a block of memory that has already been dynamically allocated. The above link describes realloc.
You should check the return type of malloc() and realloc() in your code.
As described below, functions init(), set_value(), and increment() should return an error code if memory allocation fails.
(Already implemented in garray.c)
Allocates memory for a new growable array, and initializes the array so that the array size is init_size. In other words, the array initially has a buffer with enough space to store init_size integers. All cells in the array have a default value of zero.
Returns a pointer to the new growable array, or NULL in case of error.
Sets the value at index idx to val. If idx is greater than or equal to the current array size then the array buffer should be resized to be able to store idx integers.
Returns GA_ERR in case of memory allocation error, otherwise returns GA_OK. (Both of these macros are defined in garray.h.)
Returns the value at index idx.
If this value has not yet been set by a call to set_val() or increment(),
then the array's default value of zero is returned.
This includes cases where idx is greater than or equal
to the current array size.
Increments the value at index idx by one. If idx is greater than or equal to the current array size, then the array should grow in size, as described above.
Returns GA_ERR in case of memory allocation error, otherwise returns GA_OK.
Returns the current capacity of *pa.
Frees all memory that is allocated dynamically for use with *pa. (This function should call free().)
Consider multiple cases when testing each function. For example, you may want to test function ga_size() both before and after an GArray has been resized.
When you are finished test program ga_test.c should contain tests for each of the above functions.
You are given program ga_count.c as a staring point. Submit your work in the same file.
You are given the files simple.dat, in1.dat, and in2.dat to test your program. Your results should look something like this:
$ cat simple.dat 20 30 30 30 30 40 50 50 60 90 $ ./ga_count < simple.dat 20: 1 30: 4 40: 1 50: 2 60: 1 90: 1
The expected outputs for files in1.dat and in2.dat are in files out1.dat and out2.dat. Recall that you can use the command line tool diff to compare your output with the expected output.
$ ./ga_count < in1.dat > myout1.dat $ diff out1.dat myout1.dat $See Lab 3, Exercise 3 for a review of diff.
Lab 10 is due: Saturday, September 3 at 11:59pm
These files will be evaluated for Lab 10: garray.c, ga_test.c, ga_count.c. You may submit other source code and data files with your lab (but remove compiled binary files.)
Also include a simple README file in your lab10 directory with your name, username, and any other comments or questions for the Lab TA.
You will submit this lab with the hwsubmit program.
$ hwsubmit cspp50101lab <path to your lab10 directory>
prepared by Sonjia Waxmonsky