In this programming assignment, you will implement lonely party arrays (arrays that are broken into fragments that get allocated and deallocated on an as-needed basis, rather than being allocated all at once as one big array, in order to eliminate unnecessary memory bloat). This is an immensely powerful and awesome data structure, and it will ameliorate several problems we often encounter with arrays in C

typedef struct LonelyPartyArray {

int size; int num_fragments; int fragment_length; int num_active_fragments; int **fragments; int *fragment_sizes;

} LonelyPartyArray; 

This header file also contains definitions for UNUSED, LPA_SUCCESS and LPA_FAILURE, which you will use in some of the required functions described below.

Functions that need to be created using the pre-defined struct are listed below

Values for function parameters will be passed from a pre-made main() function

int delete(LonelyPartyArray *party, int index); 

Description: Set the value stored at the corresponding index of the lonely party array to UNUSED. As with the set() and get() functions, based on the index parameter passed to this

function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought.

If the cell being sought is not already set to UNUSED, then after writing UNUSED to that cell, decrement the structs size member so that it always has an accurate count of the total number of cells that are currently being used, and decrement the appropriate value in the structs fragment_size array so that it always has an accurate count of the number of cells currently being used in each fragment.

If deleting the value at this index causes the fragment containing that value to become empty (i.e., all of its cells are now UNUSED), deallocate that array, set the appropriate pointer in the structs fragments array to NULL, and update the structs num_active_fragments member. You should never loop through a fragment to see if all of its cells are unused. Instead, you should rely on the fragment_sizes array to keep track of whether or not a fragment is ready for deallocation.

Keep in mind that index could try taking you to a fragment that has not yet been allocated. Its up to you to avoid going out of bounds in an array and/or causing any segmentation faults.

Output: There are three cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .)

If calling this function results in the deallocation of a fragment in memory, print: -> Deallocated fragment

. (capacity: , indices: ..) For explanations of

, , , and , see the set() function description above.

If index is invalid (see definition of invalid index in the set() function description) and party is non-NULL, print: -> Bloop! Invalid access in delete(). (index: , fragment: , offset: ) For explanations of , , and , see the set() function description above. Note that if a cell is marked as UNUSED, but index is within range, you should not generate this error message.

IfpartyisNULL,print:-> Bloop! NULL pointer detected in delete().

Returns: Return LPA_FAILURE if this operation refers to an invalid index (as defined in the set() function description), if this function receives a NULL party pointer, if this operation refers to a cell that lies within an unallocated fragment, or if this operation refers to a cell whose value was already set to UNUSED when the function was called. Otherwise, return LPA_SUCCESS.

int printIfValid(LonelyPartyArray *party, int index); 

Description: Print the value stored at the corresponding index of the LonelyPartyArray. As with the set(), get(), and delete() functions, based on the index parameter passed to this function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought.

Output: Simply print the appropriate integer to the screen, followed by a newline character, . This function should not print anything if index is invalid (as defined in the set() function description), if index refers to a cell whose value is set to UNUSED, or if party is NULL.

Returns: Return LPA_SUCCESS if this function prints a value to the screen. Otherwise, return LPA_FAILURE.

LonelyPartyArray *resetLonelyPartyArray(LonelyPartyArray *party); 

Description: Reset the lonely party array to the state it was in just after it was created with createLonelyPartyArray(). Be sure to avoid any memory leaks or segmentation faults.

You will need to deallocate any array fragments that are currently active within party. You will also need to reset all the values in the structs fragments and fragment_sizes arrays. However, you should not re-allocate the fragments or fragment_sizes arrays; simply reset the values contained in those already-existing arrays.

You will also need to reset the structs size and num_active_fragments members. You should not, however, change the values of num_fragments or fragment_length.

Output: There are two cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .)

If party is non-NULL, print: -> The LonelyPartyArray has returned to its nascent state. (capacity: , fragments: ) Here, is the maximum

number of integers the lonely party array can hold, and is the value of the structs num_fragments member.

If party is NULL, be sure to avoid segmentation faults, and simply return from the functionafterprintingthefollowing:-> Bloop! NULL pointer detected in resetLonelyPartyArray().

Returns: This function should always return party. int getSize(LonelyPartyArray *party);

Description: This function simply returns the number of elements currently in the LPA (not including any elements marked as UNUSED). This should be a near-instantaneous function call; it should not loop through the cells in the LPA at all.

We provide this function to discourage other programmers from ever accessing party->size directly if they try to compile code that uses our fancy LPA data structure. That way, if we release this data structure to the public but then end up updating it a few months later to rename the size member of the LonelyPartyArray struct to something else, the programmers who have been using our code and end up downloading the latest version can get it working right out of the box; they dont have to go through their own code and change all instances of party->size

to something else, as long as we still provide them with a getSize() function that works as intended.3

Output: This function should not print anything to the screen. Returns: Return the number of elements currently in the LPA, or -1 if party is NULL.

int getCapacity(LonelyPartyArray *party); 

Description: This function should simply return the maximum number of elements that party can hold, based on the values of its num_fragments and fragment_length members. For example, for the lonely party array shown on pg. 4 of this PDF, getCapacity() would return 110, because when all of its array fragments are allocated, it will be able to hold up to 110 integer elements.

Note that in testing, we will never create a lonely party array whose capacity would be too large to store in a 32-bit int, so you dont need to worry about type casting when calculating this return value.

Output: This function should not print anything to the screen. Returns: Return the capacity of the LPA (as just described), or -1 if party is NULL.

int getAllocatedCellCount(LonelyPartyArray *party); 

Description: This function should return the maximum number of elements that party can hold without allocating any new array fragments. For example, for the lonely party array shown on pg. 4 of this PDF, getAllocatedCellCount() would return 40, because the non-NULL fragments are able to hold up to 40 integer elements in total.

Output: This function should not print anything to the screen. Returns: Return the number of allocated integer cells (as just described), or -1 if the party

pointer is NULL. long long unsigned int getArraySizeInBytes(LonelyPartyArray *party);

Description: This function should return the number of bytes that would be used if we were using a standard array rather than a LonelyPartyArray struct. For example, for the LPA struct shown on pg. 4 of this PDF, a traditional array representation would have 110 integer cells, which would occupy 110 * sizeof(int) = 440 bytes, and so this function should return 440 for that struct. For additional examples, please refer to the test cases included with this assignment.

3 Note, by the way, that it is common to use the term size to refer to the number of elements that have been inserted into a data structure, while length often refers to the number of cells in an array, whether those cells have been used or not. (I.e., length refers to the maximum capacity of an array, in terms of the number of elements it can hold.)

Note: This number could get quite large, and so as you perform the arithmetic here, you should cast to long long unsigned int. (For details, see Section 3 on pg. 7.)

Note: You should use sizeof() in this function (rather than hard-coding the size of an integer as 4 bytes), and cast the sizeof() values to long long unsigned int as appropriate.

Note: If your system does not use 32-bit integers for some reason, using sizeof() in this function could cause output mismatches on some test cases. For this function to work, you will need to ensure that youre testing on a system that uses 32-bit integers (which you almost certainly are). To check that, you can compile and run SanityCheck.c (included with this assignment), or simply run the test-all.sh script.

Output: This function should not print anything to the screen. Returns: The number of bytes (as just described), or 0 if the party pointer is NULL.

long long unsigned int getCurrentSizeInBytes(LonelyPartyArray *party); 

Description: This function should return the number of bytes currently taken up in memory by the LPA. You will need to account for all of the following:

The number of bytes taken up by the LPA pointer itself: sizeof(LPA*)

The number of bytes taken up by the LPA struct (which is just the number of bytes taken

up by the four integers and two pointers within the struct): sizeof(LPA)

The number of bytes taken up by the fragments array (i.e., the number of bytes taken

up by the pointers in that array).

The number of bytes taken up by the fragment_sizes array (i.e., the number of bytes taken up by the integers in that array).

The number of bytes taken up by the active fragments (i.e., the number of bytes taken up by all the integer cells in the individual array fragments).

The getArraySizeInBytes() and getCurrentSizeInBytes() functions will let you see, concretely, the amount of memory saved by using a lonely party array instead of a traditional C- style array.4

Note: This number could get quite large, and so as you perform the arithmetic here, you should cast to long long unsigned int. (For details, see Section 3 on pg. 7.)

Note: You should use sizeof() in this function (rather than hard-coding the sizes of any data types), and cast the sizeof() values to long long unsigned int as appropriate.

Output: This function should not print anything to the screen. Returns: The number of bytes (as just described), or 0 if the party pointer is NULL.