Array Lists

In this lab you will be creating a data structure referred to (in Java) as an array list. You may see these data structures referred to by a variety of names, including vectors, dynamic arrays, or mutable arrays, but we will stick with the Java naming convention just for the sake of familiarity. We will use the word "array" to often mean "pointer to a memory block", even though arrays and pointers are not exactly the same thing.

Array lists are a specific type of structure which maintains an array internally and grows that array as required by the content. This allows the array to maintain a particular amount of empty space in order to accommodate increasing amounts of data. As you add data to your array list, it will grow toward some preset number of elements (as arrays have a foxed length). Once your array list has something added to it which would fall to the end of the range of its internal array, it will automatically resize the array by some fixed scalar known as a growth factor. The growth factor of array lists vary by programming language, but a basic growth factor is 2, with alternatives existing in the compiler world. For example, the ArrayList class in Java uses a growth factor of 3/2, or 1.5. The Rust Vec Type uses a growth factor of 2.

There are debates about what the most useful growth factor is, with 1.5 allowing the reuse of old memory blocks by eventually allowing the "remainder" of a variety of memory resizes to equal a full memory block width (thus making it reusable by the system), while still other frameworks, such as Microsoft .NET, use a doubling factor with an increase to the next prime, in order to better space their hash values for buckets. For the sake of simplicity, in this implementation we will use a growth factor of 2. In this lab, you will be expected to provide a definition for an Array List which matches the specifications below.

3.1 Creating an Initial Array List

Your array list implementation will be using a struct to contain the data most relevant to an array list. Since C cannot dynamically type the data your array list holds in a simple way, you will need to store data in each array location as a void pointer (void*). Generally, the void type refers to a lack of type and is often associated exclusively with nothing. However, we can create void pointers (void*) which , instead of dealing with nothing, instead allow you to hold a memory block with no type. Any data stored in a void pointer is considered generic byte-stored data and you can't do anything with it without telling C to treat it as a valid data type (aside from void*). Since any information about the data you're storing in a void pointer will be lost, you also need to keep track of the data's size and the data's type, which will be included as fields in your struct.

In addition to the data being stored, the array list must also have an understanding of both its maximum size and its current size. Since an array list is dynamically allocated based on its growth factor of 2, your array will have a maximum size, but not all of the array indexes will be filled with data. As a general rule, your array is only as long as the explicit data it holds and should never store a NULL pointer as a valid element. Rather than making an index within the explicit data NULL, you will instead remove it from the array completely. This means your array list, starting from index 0, must have data in every position up to the size-1 index, after which the indexes are ignored until another element is added.

When you create your initial ArrayList struct, it should have field for an initial maximum size defined by the user

(maxSize), a field for an initial current size of 0 (size), an initial data type (type) and data type size (itemSize) provided by the user, with an array (arr) allocated enough memory to contain maxSize void pointers.

3.2 Adding Elements to an Array List

You will need to write a series of functions for adding values to the array list. The first rule of adding to an array list is that an element may only be added between of the ends of the current list, which is always in [0, size]. Adding an element to a position inside the range [0, size-1] will insert the incoming value before the element in the current index. This will force all elements after the current index (and including it) to move one to the right. If you attempt to add an element to the end of the list, it will be inserted in an index equal to the current size value.

All values added to the array list should be copies of the original values. You should not save the original pointers. You will need to allocate an amount of space based on the itemSize, then copy the element into that memory space. The string.h library has a function called memcpy which can be used to copy the data in a void pointer to another void pointer.

Every time an element is successfully added, the size value of the array list should increase by 1. If there is an attempt to add an element to an invalid index, the add should not proceed. If an element should be added, but

size==maxSize, then the array list should be resized before the add is completed.

3.3 Removing Elements from an Array List

You will need to write a function for removing a value from a specific index. Whenever a remove is attempted, the index should be in [0,size-1]. If it is not, then the remove should not proceed. Since our array lists only grow larger, there is never a need for you to resize an array list to be smaller when removing an element from the list. To remove an element from a list, you can deallocate the data at the given index, then iterate through [index+ 1,size-1] to move every value to the left. When the remove is completed, size should decrease by 1.

3.4 Clearing an Array List

You will need to write a function for clearing the array list. Clearing an array list is as simple as freeing every index in [0, size-1] and then setting the size value to 0.

3.5 Getting an Element from an Array List

You will need to write a function for returning an element from the list at a given index. Make sure the index is within the bounds of the array's current size. You will need to return a copy of the void pointer to the data, and it is up to the user to store it in a data type that they're expecting from the list.

3.6 Finding the Index of an Element in an Array List

You will need to write a function which returns the index of a given element in your array list. To achieve this, you must iterate through the list and compare each element to the provided value. The string.h library has a function called memcmp which can be used to compare the first n bytes of data in two void pointers. If the element is found in the list, you should return the index where it is located. If the element is not found, return

3.7 Destroying an Array List

You will need to write a function which destroys an array list. Your function should free every element in your array list, free the array, free the stored data type, then free the entire ArrayList.

3.8 Resizing an Array List

Finally, you will need to write a function which resizes an array list. As mentioned above, when size==maxSize, you will need to increase the size of the array stored in your array list structure. To do that, you can multiply the maximum size by the growth factor of 2 and then use realloc to reallocate the amount of memory currently stored in your array.

3.9 Interacting with an Array List

When using your array list, it is not necessary to cast it to a type every time. Doing so will clutter your code and make it far less readable, as using a returned value in place (if your array list holds integers, for example) would require something ugly like *((int)*alist_get(arrayList,3)). Instead, create a pointer variable of the type you'd like to use and always return values into it. Since your array list functions will return void pointers, they will always automatically defer to the type they are being stored in. After your pointer is stored, it should only require a simple dereference to use it in the future.

Your array list will store a data type as a string (char*), which you can access any time, as well as the size of that data type. You can access these at any time to determine how to best use your array list. It will be helpful for understanding how much your variables should allocate, which array list (if you have multiple) is holding which type of value, etc.

5.1.1 Problem

You must create a structure and set of functions for managing an array list.

5.1.2 Preconditions

You are required to write a program for handling array lists, which consists of array list.c, which should contain all of your function implementations, and array list.h, which should contain your structure definition, any necessary typedefs, and all of your forward function declarations. When you compile, you will need to include the source file in your command in order to ensure the functions exist during the linking process. You may include any additional helper functions as you see fit, although they will likely not be necessary. Since you are dealing with pointers, you will need to check all of your pointers to ensure they are not null. Trying to perform operations on null will lead to segmentation faults or other program crashes at run-time.

Your array list will hold a specific data type (and that data type only) as defined by the initialization parameters. The size of the data type held is provided, as is the name. Each element stored in the array list should be of the given size in bytes. For example, if your array list is initialized as an int array list, then the item size will be 4 and the type name will be "int".

Your array list will also be given a starting size value in the initialization parameters. This value should be used as the starting maximum size for your array list, which is necessary for allocating the initial memory block. The default value for the starting size is 10.

The details of the array list functionality are described in the Array Lists section of this document. The bool type referenced in this contract is found in .

You are expected to do basic error checking (such as checking for null pointers and correct index boundaries).

Your array list program must include the following struct (typedef-ed appropriately):

5.1.3 Postconditions

Your program should be capable of producing and destroying ArrayList ( AList) structures. All of the functions should be capable of executing without crashing. Failure states should be handled by return values. If a function with a void return type fails, it does not need to be reported. If you attempt to open a file and the file does not exist (or the system was unable to create a file pointer), you may exit the program with an appropriate error. Under normal circumstances, any functions beginning with an underscore are meant for internal use only, and will only be called for verification purposes during marking.

During marking, expect the marking script to iterate through the underlying array in your ArrayList struct manually in order to verify its contents and size.

5.1.4 Restrictions

None.

5.1.5 File Requirements

This contract requires you to provide a C source file named array list.c and a C header file named array list.h. Your header files should contain your forward declarations, struct definitions and typedefs, as well as any library imports (includes) you may need. Always protect your header with a define guard. Your source files must not contain any main functions, or your program will fail during marking.

In addition to the C files, you will also be required to make a Makefile for the array list program. Your program will be compiled by executing make. Your Makefile should produce both an array list.o file and an array list executable file by compiling your code with the arrayM.o file located in CI/objects/array list. Your source, header, and make files should be placed in the Lab5/array list/ directory in your GitLab repository.

5.1.6 Testing

To test your code, you can compile your source files with the arrayM.o object file found in CI/objects/array list. Your program can then be executed as normal. The object file contains a main function, so you do not need to provide your own. Using a Makefile for compiling these files together can save you a lot of time.

5.1.7 Sample Inputs and Outputs

There are no sample inputs or outputs. The main object file for this program will test your various functions on an int ArrayList. Your code should minimally be able to complete the test main function in the object file, but you may find it more convenient to test your functions with your own main function first.

The question is 5.1 Array List, array_list program must include the structure and the functions included in the 5.1.2 preconditions.