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, Oct 11 '12 at 20:15
You may want to take a look at `realloc`. It's used to resize an already allocated area in memory. — Paul, Oct 11 '12 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 S., Oct 11 '12 at 20:16
@EdS. But `0` is a null pointer constant, so that's the same as `r != NULL`. — Daniel Fischer, Oct 11 '12 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, Oct 11 '12 at 20:18
@DanielFischer: No, because `NULL` does not have to be 0. Just because it has been in every project you've worked on doesn't mean that it is so across the board. There exist systems in which 0 is a valid address and `NULL != 0`. This is why the standard does not specify and only speaks in terms of "the null pointer". Point being, use the macro, not the literal 0. — Ed S., Oct 11 '12 at 20:18
@ascii-lime - malloc and free are provided/required by the class. I didn't write init or new functions, just the add and resize. — hobbes131, Oct 11 '12 at 20:19
@EdS. That's very wrong. It's not defined to be "all bits 0", that is true. The bitpattern is implementation defined. But the integer constant 0 is defined to be a null pointer in pointer contexts. — John Kugelman, Oct 11 '12 at 20:20
@EdS. Are you sure? It certainly has to be in C++, from the spec "A null pointer constant is an integral constant expression (5.19) rvalue of integer type that evaluates to zero." — Benj, Oct 11 '12 at 20:20
@EdS. - That line of code was provided. I don't think that's what's tripping this thing up. (Not that I would really know)... — hobbes131, Oct 11 '12 at 20:22
@JohnKugelman: You (and Daniel and Benj) are correct, I was wrong, thank you. Just found it in the standard: *An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.* — Ed S., Oct 11 '12 at 20:23
OT for Ed (et'al) the standard defines NULL as a 0 cast to a void*, but ironically `if (p == NULL)` does not necessarily mean `p is (void*)0` if that condition returns true, and anyone that has ever written C for an AS/400 is familiar with why. For most sane people ( you have to be *nuts* to program to AS/400 these days) it is, but there that compiles that to simply mean "is p a valid pointer" Its an entirely different discussion, but sometimes a null-pointer check in the opcode sense world isn't what you think it is (literally). — WhozCraig, Oct 11 '12 at 20:35
If you're using Linux, you should be able to just do `gcc -g file.c; gdb a.out` (the `-g` adds debug symbols which will make the output more useful), then type `run` I think. In an IDE like Visual Studio or Eclipse, there should just be a "debug" button (frequently green and bug-shaped). — Brendan Long, Oct 11 '12 at 20:36

score 2 · Answer 1 · answered Oct 11 '12 at 20:21

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;
}

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. — hobbes131, Oct 11 '12 at 20:31
@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 `free`s its old argument if successful, that's the only difference. — Daniel Fischer, Oct 11 '12 at 20:33

score 2 · Accepted Answer · answered Oct 11 '12 at 20:21

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 '12 at 20:21

Zeta

103,620
13
194
236

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)? – hobbes131 Oct 11 '12 at 20:35
@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`. – Zeta Oct 11 '12 at 20:37
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 :) – hobbes131 Oct 11 '12 at 20:43
@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 ^^) – Zeta Oct 11 '12 at 20:45
hahaha TL;DR, I thought it was supposed to do a line break in the comments. That was noob-tastic! – hobbes131 Oct 11 '12 at 21:45

C resizing a dynamic array

2 Answers2

Linked