Lab 10: The Arraylist
CS 3410 Spring 2018
Due: Sunday, April 15, 2018 at 11:59 PM. Submit all required files on CMS.
Overview
In this lab we will implement 3 functions in the file lab10.c for an arraylist of ints: arraylist_add, arraylist_insert, and arraylist_free.
References. Searching the Internet will generally find an answer to nearly any conceivable question about the C programming language. However, information on the Web is not always accurate or complete. We recommend reference books over web sites. In particular, C: A Reference Manual (5th Edition) by Samuel P. Harbison and Guy L. Steele Jr. is a great textbook for this class and should be the source for reliable information on C.
Structs
Just like in your previous languages, C allows you define your own types. Somewhat like classes (but without methods!), structs are a way to define a group of fields to be stored together. They're often the basis of data structures.
typedef struct {
void** buffer;
unsigned int buffer_size;
unsigned int length;
} arraylist;
You can use a . to access the fields of a struct (again, like classes). If you have a pointer to a struct, you can use -> to both dereference and access.
arraylist a; a.length = 5; arraylist *a_ptr = &a; a_ptr->length = 10; (*a_ptr).length = 15;That is,
a->b is the same as (*a).b, but more readable.
Dynamic Memory
In C, primitive values and even arrays are often declared on the stack. This is known as static allocation, which uses static memory. This is fast and efficient, but a major drawback is that the size of objects on the stack must be known at compile-time. Therefore, such common tasks as dealing with variable-length arrays cannot be done using only static memory.
C also allows the programmer to use dynamic allocation, which is asking the operating system for more memory at runtime, and then using that newly allocated memory. While allocating memory does take time, dynamic memory is incredibly flexible and powerful, since any amount of memory can be requested and used at runtime (only limited by the amount of memory on the system).
First, note that the sizeof operator returns the size in bytes of any type defined in the program. You will often use it while working with the functions below.
There are many functions in C to deal with memory; most are defined in stdlib.h. These are the ones you may find useful:
-
malloc(size_in_bytes)allocates new dynamic memory. It takes a single argument, the amount of bytes to allocate, and returns avoid*pointer to the newly allocated memory. Avoid*pointer can point to objects of any type (e.g.int,float, or even a structpotato_salad) and can be cast to the appropriate type the programmer wants to use.int *int_ptr = (int*)malloc(sizeof(int)); //allocates room for one int int *int_ptr = (int*)malloc(5 * sizeof(int)); //allocates room for five ints free(pointer)frees dynamic memory that you have allocated. It takes a single argument, the pointer to the block of memory that you allocated previously. You must eventually free all memory that you allocate during a program - otherwise your program will have a memory leak. Warning: do not use memory that you have freed, as doing so will result in undefined behavior.realloc(pointer, new_size_in_bytes)resizes a block of dynamic memory that you've already allocated. It takes two arguments: a pointer to a block, and the new desired size of the block in bytes. It returns a pointer to the new block, which may be different from the pointer you gave it!reallocpreserves all the data that was in the original block. It's a good idea to overwrite or clear out the original pointer you pass in, because using it again might result in undefined behavior.memcpy(destination_ptr, src_ptr, num_bytes_to_copy)copiesnum_bytesof memory from one block to another.
The code below is a simple example of dynamic memory in C, including the use of pointers as arrays.
int *int_ptr;
int_ptr = (int*)malloc(sizeof(int));
*int_ptr = 5;
printf("I stored the int %d at address %p\n", *int_ptr, int_ptr);
free(int_ptr); // don't forget to free memory when you're done with it!
/* Since arrays in C are just contiguous regions of bytes, pointers can also
* be used to point to arrays. */
int *int_arr;
int i;
// here, we malloc enough space for 5 ints - creating an int array of length 5!
int_arr = (int*)malloc(5 * sizeof(int));
for (i = 0; i < 5; i++) {
int_arr[i] = i;
}
// now, int_arr points to the int array [0;1;2;3;4]
free(int_arr);
The Arraylist
You can find the lab10.c file in your github repository.
Step 1: Implement the arraylist_add(arraylist* a, void* x) function
The elements of an arraylist are stored consecutively in a dynamically allocated array. This function takes a pointer to an arraylist and a value, and appends that value to the end of the arraylist. It should also increment the length of the arraylist to include the new element.
If this is a conceptual drawing of what the arguments to the function look like at the beginning of a call to arraylist_add:
Then this is a conceptual drawing of what the arguments should look like at the end of the function arraylist_add:
If the arraylist is currently at capacity when arraylist_add is called, you should create a new dynamic array that is twice the size of the old one and copy over all the elements currently in the arraylist. You may find that the standard library function realloc is useful for doing this.
Step 2: Implement the arraylist_insert(arraylist* a, unsigned int index, void* x) function
This function should take advantage of your arraylist_add to insert an element at an arbitrary location in your arraylist. You do not have to worry about attempting to insert to locations beyond the end of the arraylist (doing so it undefined behavior). Hint: Use memmove()
Step 3: Implement the arraylist_free(arraylist* a) function
The arraylist_free simply has to free all the resources used by an arraylist. Note that the arraylist struct contains a pointer!
Step 4: Test
When you are done implementing the functions, compile your program using gcc and run it.
$ gcc -ggdb -Wall -Werror -std=c99 -o lab10 lab10.c $ ./lab10
The program is meant to output:
[0, 1, 2, 3, 4, 5] Insert position 0: [100, 0, 1, 2, 3, 4, 5] Insert position 1: [0, 100, 1, 2, 3, 4, 5] Insert position 2: [0, 1, 100, 2, 3, 4, 5] Insert position 3: [0, 1, 2, 100, 3, 4, 5] Insert position 4: [0, 1, 2, 3, 100, 4, 5] Insert position 5: [0, 1, 2, 3, 4, 100, 5] Clean: [0, 1, 2, 3, 4, 5]
Step 5: Valgrind
You should use valgrind to check your code for memory leaks.
$ valgrind -q --leak-check=full ./lab10
When validating memory leaks, make sure you're using valgrind to verify that there are no leaks. However, if you're struggling to figure out the output from valgrind or other errors in your code, we offer another tool on the VM called scan-build (Clang static analyzer). To run this, call (scan-build -k -V ./lab10). It will generate an HTML page that will show existing issues in the code if it can detect some. This tool will not detect all the same issues though that valgrind will, so you cannot rely on it as proof of no leaks in your code.