C resizing a dynamic array

Question

I'm creating a dynamic array data structure for a C class. I have most everything implemented and now I'm testing it out. It's currently getting stuck during a resize. I've used printf's to follow the issue. It looks like the resize is working, but when I go to add my next item post resize, it's stopping there.

I think it may have to do with my memory allocation or the way I'm pointing and freeing arrays during the resize. I'm new to C so these are my sticking points.

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

struct DynArr
{
    TYPE *data;     /* pointer to the data array */
    int size;       /* Number of elements in the array */
    int capacity;   /* capacity of the 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)
{   
    DynArr* newArr = newDynArr(newCap);     //Create new array with new cap
    int x;
    for(x = 0; x < sizeDynArr(v); x++){
        addDynArr(newArr, v->data[x]);      //copy data
    }
    freeDynArr(v);                  //free old v
    v->capacity = newCap;
    v->size = newArr->size;
    v = newArr;                 //point v to 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)
{
    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 */
    printf("size: %d\tcap: %d\n", v->size, v->capacity);
    if(v->size >= v->capacity) {
        printf("in resize..");
        _dynArrSetCapacity(v, 2 * v->capacity);
    }
    v->data[v->size] = val;         //after a resize this doesn't happen.
    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)
{
    /*returns data element at specified position within the array*/

    assert(pos < sizeDynArr(v) && pos >= 0);        //value is between zero and size
    return v->data[pos];                            //returns deferenced int value at position
}

/*  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 < sizeDynArr(v) && idx >= 0);

    for (i = idx; i < sizeDynArr(v)-1; i++){
        v[i].data = v[i+1].data;
    }
    v->size--;
}



/* ************************************************************************
    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)
{
    return (sizeDynArr(v) == 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);
}

/*  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)
{
    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)
{
    removeAtDynArr(v, sizeDynArr(v)-1);
}


int main(int argc, char* argv[]){
    DynArr* myD = newDynArr(5);
    int x;

    addDynArr(myD, 1);
    addDynArr(myD, 2);
    //printf("top: %d", sizeDynArr(myD));
    //printf("size: %d\ttop: %d\n", sizeDynArr(myD), topDynArr(myD));

    for(x = 0; x <= 5; x++){
        addDynArr(myD, x);
        //printf("size: %d\ttop: %d\n", sizeDynArr(myD), topDynArr(myD));
        pushDynArr(myD, x * 2);
        //printf("size: %d\ttop: %d\n", sizeDynArr(myD), topDynArr(myD));
    }


    printf("HI");

    deleteDynArr(myD);

    return 0;   
}

What do you mean by "stopping"? Is there an error message? A segfault? Can you run it through a debugger to find out the line? — Brendan Long
– Brendan Long, Commented Oct 11, 2012 at 20:15
You may want to take a look at realloc. It's used to resize an already allocated area in memory. — Paul
– Paul, Commented Oct 11, 2012 at 20:16
assert(r != 0); FYI, the null pointer is not defined to be 0 by the standard (it's not defined to have any specific value), and it is not 0 across all platforms. — Ed Swangren
– Ed Swangren, Commented Oct 11, 2012 at 20:16
@EdS. But 0 is a null pointer constant, so that's the same as r != NULL. — Daniel Fischer
– Daniel Fischer, Commented Oct 11, 2012 at 20:18
@BrendanLong "stopping" means that the console doesn't display anything beyond the resize. Not sure how to use the debugger to find a segfault. — hobbes131
– hobbes131, Commented Oct 11, 2012 at 20:18

Zeta · Accepted Answer · 2012-10-11 20:21:08Z

2

Your function _dynArrSetCapacity doesn't work as intended, the problem is in the following lines:

    v->capacity = newCap;
    v->size = newArr->size;
    v = newArr;                 //point v to new array
}

The last instruction is basically useless. v is a pointer. Changes won't affect the actual used pointer outside of _dynArrSetCapacity. Thus v->data is 0 in addDynArr and you'll get a segmentation fault:

    _dynArrSetCapacity(v, 2 * v->capacity);
}
v->data[v->size] = val;         //after a resize this doesn't happen.

Either use v->data = newArr->data or use a pointer on a pointer instead.

answered Oct 11, 2012 at 20:21

Zeta

106k13 gold badges205 silver badges249 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

hobbes131 Over a year ago

I think v->data = newArr->data may have been what they intended. If I implement that, what do I free at the end of the function? Do I still free(v)?

Zeta Over a year ago

@hobbes131: Have a look at freeDynArr. It frees v->data and sets the capacity and size to zero. The container itself (*v) hasn't been freed and can still be used. TL;DR: Keep using freeDynArr, but don't use free on v. For this you have deleteDynArr.

hobbes131 Over a year ago

freeDynArr(v); //free old v v->capacity = newCap; v->size = newArr->size; v->data = newArr->data; TL:DR This what I used, so far it seems to be working :)

Zeta Over a year ago

@hobbes131: You're welcome, it should work although I didn't studied your code enough to be a 100% sure. (Note: TL;DR means: too long, didn't read. Usually it is followed by a short summary, it wasn't that appropriate for my comment above ^^)

hobbes131 Over a year ago

hahaha TL;DR, I thought it was supposed to do a line break in the comments. That was noob-tastic!

Daniel Fischer · Accepted Answer · 2012-10-11 20:21:02Z

2

v = newArr;                 //point v to new array

That line just assigns newArr to the copy of the pointer that _dynArrSetCapacity received, it doesn't modify the pointer in the calling function.

To achieve that, you should pass the address of the pointer and have _dynArrSetCapacity receive a DynArr**.

void _dynArrSetCapacity(DynArr **v, int newCap)
{   
    DynArr* newArr = newDynArr(newCap);     //Create new array with new cap
    int x;
    for(x = 0; x < sizeDynArr(*v); x++){
        addDynArr(newArr, (*v)->data[x]);      //copy data
    }
    freeDynArr(*v);                  //free old v
    // v->capacity = newCap;  These are superfluous, since we change the pointer itself
    // v->size = newArr->size; 
    *v = newArr;                 //point v to new array
}

But the better solution is to only reallocate the array,

void _dynArrSetCapacity(DynArr *v, int newCap)
{   
    TYPE *temp = realloc(v->data,newCap * sizeof *temp);
    if (!temp) { // alloc failure
        exit(EXIT_FAILURE);
    }
    v->data = temp;
    v->capacity = newCap;
    v->size = newArr->size;
}

answered Oct 11, 2012 at 20:21

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

2 Comments

hobbes131 Over a year ago

This is such a great example of the joys of being a student, handcuffs... The function header was supplied so I cannot change it. And malloc (not realloc) is required. They want us to copy the data over. Boo.

Daniel Fischer Over a year ago

@hobbes131 Then you can still just malloc newCap*sizeof *temp, copy the data over to temp, and free(v->data); v-data = temp; afterward. realloc copies the data over for you and frees its old argument if successful, that's the only difference.

Collectives™ on Stack Overflow

C resizing a dynamic array

2 Answers 2

5 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related