C resizing a dynamic array

问题:

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

回答1:

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.

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