Computer Organization and Architecture

Your task is to explain why the two functions bad_vector_new() and also_bad_vector_new() are bad and fill in the functions vector_new(), vector_get(), vector_delete(), and vector_set() in vector.c so that our test code vector-test.c runs without any memory management errors. Comments in the code describe how the functions should work. Look at the functions already implemented to see how the data structures should be used. For consistency, it is assumed that all entries in the vector are 0 unless set by the user. Keep this in mind as malloc() does not zero out the memory it allocates. For explaining why the two bad functions are incorrect, keep in mind that one of these functions will actually run correctly (assuming correctly modified vector_new, vector_set, etc.) but there may be other problems; hint: think about memory usage.

vector_test.c file:

#include "vector.h" int main(int argc, char **argv) { vector_t *v; printf("Calling vector_new() "); v = vector_new(); printf("Calling vector_delete() "); vector_delete(v); printf("vector_new() again "); v = vector_new(); printf("These should all return 0 (vector_get()): "); printf("%d ", vector_get(v, 0)); printf("%d ", vector_get(v, 1)); printf("%d ", vector_get(v, 2)); printf("Doing a bunch of vector_set()s "); vector_set(v, 0, 98); vector_set(v, 11, 15); vector_set(v, 15, -23); vector_set(v, 24, 65); vector_set(v, 500, 3); vector_set(v, 12, -123); vector_set(v, 15, 21); vector_set(v, 25, 43); printf("These should be equal: "); printf("98 = %d ", vector_get(v, 0)); printf("15 = %d ", vector_get(v, 11)); printf("65 = %d ", vector_get(v, 24)); printf("-123 = %d ", vector_get(v, 12)); printf("21 = %d ", vector_get(v, 15)); printf("43 = %d ", vector_get(v, 25)); printf("0 = %d ", vector_get(v, 23)); printf("0 = %d ", vector_get(v, 1)); printf("0 = %d ", vector_get(v, 501)); printf("3 = %d ", vector_get(v, 500)); vector_delete(v); printf("Test complete. "); return 0; }

vector.h file

#ifndef CS61C_VECTOR_H_ #define CS61C_VECTOR_H_ /* vector.h originally written by Jeremy Huddleston  Sp2004 * * So it looks like you've decided to venture into the "other" files of this * lab. Good. C Header files (the .h extension) are a way of telling other .c * files what they can have access to. You usually include stdlib.h in your * C programs, and this process is identical to including this .h file with the * one change being: * * #include "file.h" * versus * #include  * * The difference is that the <> notation is for system header files and the "" * is for ones you provide yourself (in your local directory for instance). * * The header file starts off with * #ifndef CS61C_VECTOR_H_ * #define CS61C_VECTOR_H_ * * and ends with a final #endif. This prevents the file from being included * more than once which could've possibly resulted in an infinite loop of * file inclusions. * * First, we define the 'vector_t' datatype. This next line says that a 'vector_t' * is the same as a 'struct vector_t'. So anywhere in the code after this, we * can use 'vector_t *' to mean a pointer to a 'struct vector_t' (which is defined in * vector.c). We can get away with doing this even though we don't know what a * struct vector is because all struct pointers have the same representation in memory. */ #include  typedef struct vector_t vector_t; /* * Next, we provide the prototypes for the functions defined in vector.c. This * is a way of telling the .c files that #include this header what they will * have access to. */ /* Create a new vector */ vector_t *vector_new(); /* Free up the memory allocated for the passed vector */ void vector_delete(vector_t *v); /* Return the value in the vector */ int vector_get(vector_t *v, size_t loc); /* Set a value in the vector */ void vector_set(vector_t *v, size_t loc, int value); #endif

vector.c file:

/* Include the system headers we need */ #include  #include  /* Include our header */ #include "vector.h" /* Define what our struct is */ struct vector_t { size_t size; int *data; }; /* Utility function to handle allocation failures. In this case we print a message and exit. */ static void allocation_failed() { fprintf(stderr, "Out of memory. "); exit(1); } /* Bad example of how to create a new vector */ vector_t *bad_vector_new() { /* Create the vector and a pointer to it */ vector_t *retval, v; retval = &v; /* Initialize attributes */ retval->size = 1; retval->data = malloc(sizeof(int)); if (retval->data == NULL) { allocation_failed(); } retval->data[0] = 0; return retval; } /* Another suboptimal way of creating a vector */ vector_t also_bad_vector_new() { /* Create the vector */ vector_t v; /* Initialize attributes */ v.size = 1; v.data = malloc(sizeof(int)); if (v.data == NULL) { allocation_failed(); } v.data[0] = 0; return v; } /* Create a new vector with a size (length) of 1 and set its single component to zero... the RIGHT WAY */ vector_t *vector_new() { /* Declare what this function will return */ vector_t *retval; /* First, we need to allocate memory on the heap for the struct */ retval = /* YOUR CODE HERE */ /* Check our return value to make sure we got memory */ if (/* YOUR CODE HERE */) { allocation_failed(); } /* Now we need to initialize our data. Since retval->data should be able to dynamically grow, what do you need to do? */ retval->size = /* YOUR CODE HERE */; retval->data = /* YOUR CODE HERE */; /* Check the data attribute of our vector to make sure we got memory */ if (/* YOUR CODE HERE */) { free(retval); //Why is this line necessary? allocation_failed(); } /* Complete the initialization by setting the single component to zero */ /* YOUR CODE HERE */ = 0; /* and return... */ return retval; } /* Return the value at the specified location/component "loc" of the vector */ int vector_get(vector_t *v, size_t loc) { /* If we are passed a NULL pointer for our vector, complain about it and exit. */ if(v == NULL) { fprintf(stderr, "vector_get: passed a NULL vector. "); abort(); } /* If the requested location is higher than we have allocated, return 0. * Otherwise, return what is in the passed location. */ if (loc < /* YOUR CODE HERE */) { return /* YOUR CODE HERE */; } else { return 0; } } /* Free up the memory allocated for the passed vector. Remember, you need to free up ALL the memory that was allocated. */ void vector_delete(vector_t *v) { /* YOUR SOLUTION HERE */ } /* Set a value in the vector. If the extra memory allocation fails, call allocation_failed(). */ void vector_set(vector_t *v, size_t loc, int value) { /* What do you need to do if the location is greater than the size we have * allocated? Remember that unset locations should contain a value of 0. */ /* YOUR SOLUTION HERE */ }