Dynamic Array Functions in C - setting capacity and creating a larger array

Question

I'm building functions for a dynamic array in C. For the most part, they seem to be working fine, until the array's capacity needs to be expanded. I seem to be having two problems with my function _dynArrSetCapacity.

/* Resizes the underlying array to be the size cap

param:  v       pointer to the dynamic array
param:  cap     the new desired capacity
pre:    v is not null
post:   v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
    assert(v != NULL);
    struct DynArr largerArray; /*create a new dynamic array*/
    initDynArr(&largerArray, newCap); /*initialize the new array*/
    int i;
    /*copy the old array into the new array*/
    for(i = 0; i < v->size; i++) {
       largerArray->data[i] = v->data[i];
       largerArray->size++;
    }
freeDynArr(v); /*free memory of the old array*/
v = &largerArray; /*point to the new array*/
}

First, I am getting the error message "invalid type argument of '->' (have struct DynArr)" for each of the two statements within the for loop. This is a new error that has suddenly appeared, although I have not made changes to this particular function and it was not initially giving me the error. Second, when this function returns back to the function that called it, the size and capacity of the array return to their former values. My statement "v = &largerArray;" does not seem to have the desired effect, namely to assign all the pointers and values of the new array to v. The full code is provided below for context. Any suggestions for fixing these two issues would be greatly appreciated. Thanks in advance.

#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"

struct DynArr
{
   TYPE *data;      /* pointer to the data array */
   int size;        /* Number of elements in the array */
   int capacity;    /* capacity ofthe array */
};


/* ************************************************************************
Dynamic Array Functions
 ************************************************************************ */

/* Initialize (including allocation of data array) dynamic array.

param:  v       pointer to the dynamic array
param:  cap     capacity of the dynamic array
pre:    v is not null
post:   internal data array can hold cap elements
post:   v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
    assert(capacity > 0);
    assert(v!= 0);
    v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
    assert(v->data != 0);
    v->size = 0;
    v->capacity = capacity;
}

    /* Allocate and initialize dynamic array.

param:  cap     desired capacity for the dyn array
pre:    none
post:   none
ret:    a non-null pointer to a dynArr of cap capacity
        and 0 elements in it.
    */
DynArr* newDynArr(int cap)
{
    assert(cap > 0);
    DynArr *r = (DynArr *)malloc(sizeof( DynArr));
    assert(r != 0);
    initDynArr(r,cap);
    return r;
}

/* Deallocate data array in dynamic array.

param:  v       pointer to the dynamic array
pre:    none
post:   d.data points to null
post:   size and capacity are 0
post:   the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
   if(v->data != 0)
   {
       free(v->data);   /* free the space on the heap */
       v->data = 0;     /* make it point to null */
   }
   v->size = 0;
   v->capacity = 0;
}

/* Deallocate data array and the dynamic array ure.

param:  v       pointer to the dynamic array
pre:    none
post:   the memory used by v->data is freed
post:   the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
    freeDynArr(v);
    free(v);
}

/* Resizes the underlying array to be the size cap

param:  v       pointer to the dynamic array
param:  cap     the new desired capacity
pre:    v is not null
post:   v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
 {
    assert(v != NULL);
        struct DynArr largerArray; /*create a new dynamic array*/
    initDynArr(&largerArray, newCap); /*initialize the new array*/
    int i;
    /*copy the old array into the new array*/
    for(i = 0; i < v->size; i++) {
       largerArray->data[i] = v->data[i];
       largerArray->size++;
}

     freeDynArr(v); /*free memory of the old array*/
     v = &largerArray; /*point to the new array*/
}

/* Get the size of the dynamic array

param:  v       pointer to the dynamic array
pre:    v is not null
post:   none
ret:    the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
    int i;
     v->size = 0;
     for (i = 0; i < v->capacity; i++) {
         if (!(EQ(v->data[i], NULL))) {
            v->size++;
    }
}
return v->size;
}

 /*     Adds an element to the end of the dynamic array

param:  v       pointer to the dynamic array
param:  val     the value to add to the end of the dynamic array
pre:    the dynArry is not null
post:   size increases by 1
post:   if reached capacity, capacity is doubled
post:   val is in the last utilized position in the array*/
void addDynArr(DynArr *v, TYPE val)
{
    /* Check to see if a resize is necessary */
    assert(v != NULL);

   if(v->size >= v->capacity) {
           _dynArrSetCapacity(v, 2 * v->capacity);
   }
   v->data[v->size] = val;
   printf("Added %d to Array to position %d\n", v->data[v->size], v->size);
   v->size++;
}

/*  Get an element from the dynamic array from a specified position

param:  v       pointer to the dynamic array
param:  pos     integer index to get the element from
pre:    v is not null
pre:    v is not empty
pre:    pos < size of the dyn array and >= 0
post:   no changes to the dyn Array
ret:    value stored at index pos
*/

TYPE getDynArr(DynArr *v, int pos)
{
   assert(pos < v->size && pos >= 0);
   return v->data[pos];
}

/*  Put an item into the dynamic array at the specified location,
overwriting the element that was there

param:  v       pointer to the dynamic array
param:  pos     the index to put the value into
param:  val     the value to insert
pre:    v is not null
pre:    v is not empty
pre:    pos >= 0 and pos < size of the array
post:   index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
    assert(pos >= 0 && pos < v->size);

    v->data[pos] = val;
    v->size++;
}

/*  Swap two specified elements in the dynamic array

param:  v       pointer to the dynamic array
param:  i,j     the elements to be swapped
pre:    v is not null
pre:    v is not empty
pre:    i, j >= 0 and i,j < size of the dynamic array
post:   index i now holds the value at j and index j now holds the value at i
 */
void swapDynArr(DynArr *v, int i, int  j)
{
    int temp = 0;
    assert(i >= 0 && i < v->size);
    assert(j >= 0 && j < v->size);
    temp = v->data[i];
    v->data[i] = v->data[j];
    v->data[j] = temp;

}

/*  Remove the element at the specified location from the array,
shifts other elements back one to fill the gap

param:  v       pointer to the dynamic array
param:  idx     location of element to remove
pre:    v is not null
pre:    v is not empty
pre:    idx < size and idx >= 0
post:   the element at idx is removed
post:   the elements past idx are moved back one
*/
 void removeAtDynArr(DynArr *v, int idx)
{
    int i;
    assert(idx < v->size && idx >= 0);

        printf("%d is being removed from array\n", v->data[idx]);
    v->data[idx] = 0;
    for (i = idx; i < v->size; i++) {
        v->data[i] = v->data[i + 1];
    }

    v->size--;
    v->data[v->size+1] = NULL;
}



/* ************************************************************************
    Stack Interface Functions
************************************************************************ */

/*  Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.

param:  v       pointer to the dynamic array
pre:    the dynArr is not null
post:   none
ret:    1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
   if(v->size == 0) return 1;
       return 0;
}

/*  Push an element onto the top of the stack

param:  v       pointer to the dynamic array
param:  val     the value to push onto the stack
pre:    v is not null
post:   size increases by 1
        if reached capacity, capacity is doubled
        val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
    addDynArr(v, val);
    printf("Pushed %d on Stack\n",val);
}

/*  Returns the element at the top of the stack

param:  v       pointer to the dynamic array
pre:    v is not null
pre:    v is not empty
post:   no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
    assert(sizeDynArr(v) != 0);
    return getDynArr(v, sizeDynArr(v) - 1);
}

/* Removes the element on top of the stack

param:  v       pointer to the dynamic array
pre:    v is not null
pre:    v is not empty
post:   size is decremented by 1
        the top has been removed
*/
void popDynArr(DynArr *v)
{
    assert(sizeDynArr(v) != 0);
    removeAtDynArr(v, sizeDynArr(v) - 1);
    v->size--;
}

/* ************************************************************************
Bag Interface Functions
 ************************************************************************ */

/*  Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0

param:  v       pointer to the dynamic array
param:  val     the value to look for in the bag
pre:    v is not null
pre:    v is not empty
post:   no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{

int i;
    for (i = 0; i < v->size; i++) {
        if(EQ(v->data[i], val)) {
            return 1;
        }
     }
    return 0;
}

/*  Removes the first occurrence of the specified value from the collection
if it occurs

param:  v       pointer to the dynamic array
param:  val     the value to remove from the array
pre:    v is not null
pre:    v is not empty
post:   val has been removed
post:   size of the bag is reduced by 1
 */
 void removeDynArr(DynArr *v, TYPE val)
 {
    int i;
    for (i = 0; i < v->size; i++) {
            if (EQ(val, v->data[i])) {
                 removeAtDynArr(v, i);
                 return;
            }
    }
}

int main(int argc, char** argv){
    printf("Program: Dynamically-allocated Array\n");
    int cap = 10;
    int i;

DynArr *r;
r = newDynArr(cap);


    for (i = 0; i < cap; i++) {
        pushDynArr(r, i);
    }

    r->size = sizeDynArr(r);
    if(isEmptyDynArr(r) == 1) {
        printf("Array is empty\n");
    }

    else if(isEmptyDynArr(r) == 0) {
        printf("Array is not empty\n");
    }
    removeDynArr(r, 5);

    printf("Before adding to array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array before push is %d\n", topDynArr(r));

    for (i = r->size; i < cap + 4; i++) {
       pushDynArr(r,i);
    }

    printf("After adding to array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array after push is %d\n", topDynArr(r));

    printf("The top of the array before remove is %d\n", topDynArr(r));
    printf("Before removing from array, size is %d and capacity is %d\n", r->size, r->capacity);

    for (i = r->size; i < cap; i++) {
        pushDynArr(r,i);
    }

    printf("After removing from array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array after remove is %d\n", topDynArr(r));

    if (containsDynArr(r, 3) == 1) {
        printf("Value 30 is in the array.\n");
    }

    printf("The top of the array before pop is %d\n", topDynArr(r));
    popDynArr(r);
    printf("The top of the array after pop is %d\n", topDynArr(r));

deleteDynArr(r);

   return 0;
}

Answer 1

Forget the stack. largerArray is automatically managed. That object will be destroyed when _dynArrSetCapacity returns.

When you pass to functions in C, you're passing by value. What this means is that the function receives a copy of the data in a new object, rather than the old object. If you change the new object, the old object remains unchanged. v = &largerArray; is ineffective because v is a copy, not the original. Note that in the example below, the int x in parse_by_value_example is not the same object as the int x in main.

#include <stdio.h>
int parse_by_value_example(int x);
int main(void) {
    int x = 0, y;
    y = parse_by_value_example(x);
    printf("Value of x: %d. Value of y: %d\n", x, y);
    return 0;
}
int parse_by_value_example(int x) {
    x = 42;
    return x;
}

I think you're confusing the definition of "array" in C. In C, an array is such that sizeof (array) will be the product of the number of elements and the size of an element, and the entirety of the array is one contiguous allocation. For example, the following code will not cause any assertion failures:

size_t array_capacity = 42;
int array[array_capacity];
assert(sizeof (array) == sizeof (array_capacity) * sizeof (array[0]));

The array[] subscript operator is actually a pointer subscript operator; arrays decay to pointers unless they're in expressions such as &array, sizeof (array) or they're used in initialisations.

Which book are you reading? It seems like you're having troubles with it. I have confidence that, providing you do the exercises as you encounter them (don't skip them), you'll benefit from K&R 2E.

Answer 2

struct DynArr largerArray is a stack variable, it only exists on the current stack. v = &largerArray makes v point to a memory address on the stack. Then your function returns and the stack gets destroyed, so v points to non-existing memory that will further be overridden when other functions recycle this stack space.

You also never really create a dynamic array.

DynArr *r;
initDynArr(r, cap);

r is a pointer to a DynArray, that's its type, yet you don't initialize it to actually point to such an array and initDynArr() assumes that r already points to a DynArray, which is not the case, it's uninitialized. Correct would either be

DynArr r;
initDynArr(&r, cap);

in which case the DynArray exist on the stack or

DynArr *r = malloc(sizeof(*r));
initDynArr(r, cap);

in which case the DynArray exist on the heap.

There is so much wrong with your code in regards to memory management that I don't even know where to start.

Maybe you should have a look at this page. This guy has implemented pretty much the thing you are trying to implement here.

Answer 3

In _dynArrSetCapacity, you only change local pointer v to point to your local stack variable, which will not affect the real data pointed by v. You need to use

*v = largerArray;

to copy from largerArray.