2

I must dynamically allocate a contiguous block of storage to hold a 2D array of an arbitrary data type.
It can only use a single call to malloc.
Part of the memory must include the mixed data types of "pointer to data type" and the data type itself.
The arbitrary data type is called Type. Full disclosure: yes, this is for an assignment. I've been beating my head on this for a good 30+ hours trying to figure this out. I cannot use C99+ standards. It must be Pre-C99.

I so far have this:

Type **Create2D(size_t rows, size_t cols) {
    Type **ptr = (Type **)SafeMalloc(rows * sizeof(Type*) + rows * cols * sizeof(Type)); 
    //  rows*sizeof(Type*) is total memory needed for the elements to store the pointers. 
    //  rows*cols*sizeof(Type) is the memory needed to store the actual array data
    //  The sum of the above two gives the total amount of contiguous memory needed

    int index;
    for (index = 0; index < (int)rows; index++)
        ptr[index] = &ptr + rows*sizeof(Type *) + index * cols * sizeof(Type);
        //  in my mind, this assigns the pointers to the address of each column
        //  to the first address blocks allocated by malloc
}

the Type data type is defined by a provided header file using a typedef as follows:

#define ELEMENTS 9
typedef signed char Type[ELEMENTS];
#undef ELEMENTS

the SafeMalloc function just contains an error check along with the malloc call

static Type **SafeMalloc(size_t size) {
    void *vp;       
    if ((vp = malloc(size)) == NULL) {
        fputs("Out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }
    return(vp);
}

My Create2D function is called from main as follows, where rows and cols are set to varying values provided by a for loop so that they change each run through the listed code here:

Type **ppobj;
int rows, cols;
ppobj = Create2D((size_t)rows, (size_t)cols);

The array is called and tested in another loop here:

int x = Test2D(ppObj, rows, cols);

Defined as:

int Test2D(Type **ppObj, int dim0, int dim1) {
    signed char testValue;
    int row, col, ix;       
    Type item;

    testValue = SCHAR_MIN;  
    for (row = 0; row < dim0; ++row) {
        for (col = 0; col < dim1; ++col) {
            for (ix = 0; ix < (int)(sizeof(item) / sizeof(item[0])); ++ix) {                
                ppObj[row][col][ix] = testValue;
                //  throws an exception in above step while stepping through at col = 1.
                if (testValue == SCHAR_MAX)
                    testValue = SCHAR_MIN;
                else
                   ++testValue;
            }
        }
    }
    ....
}

Finally, I think what I have is close. Given a 1x27 array, it will make it through this, but when my function for freeing the memory is called and then a 2x26 array is called it will error in the above step. It's made it to the 3x25 array and erred above as well. My free function looks like this:

void Free2D(void *ptr) {
    free(ptr);
}

it is called using this sytax, from the above main function:

Free2D((void *)ppObj);

I've also run it through and seen the dim1 variable change in the middle of the nested for loops from it's set value from the passed arguments to something just huge like 1830342 or some sort. It makes me believe the free() function is not being used properly by me.

5
  • 30+ hours! wow, that's a long time... you got the idea, but the method to compute the pointers is incorrect, you must compute byte offsets from ptr cast as a byte pointer. See my answer for additional details. Commented Feb 13, 2016 at 21:26
  • The address of the elements past rows * sizeof(Type*) - the pointers - is not guaranteed to be suitably aligned for use to store a value of Type. For example, if rows is odd, sizeof( Type * ) is 4 bytes, and Type has an 8-byte alignment restriction. Unless you want to get into doing alignment calculations, you're better off doing two allocations - one for the array of pointers, and one for the array data. Commented Feb 13, 2016 at 21:42
  • " It must be Pre-C99." - I guess this is the same reason they teach Latin at high school Commented Feb 13, 2016 at 22:14
  • I must dynamically allocate a contiguous block of storage to hold a 2D array Please stop calling a Pointer =>> Array. Commented Feb 13, 2016 at 23:15
  • pointer to pointer is hard to manage (you have two arrays to deallocate: the array itself and the array of pointers to the start of each row) and is bad performance if not restricted. use linear indexing if you can. Commented Feb 14, 2016 at 2:45

1 Answer 1

3

Your code is almost correct, the formula to compute ptr[index] is incorrect: you must compute byte offsets from ptr cast as a byte pointer.

Here is a better version:

Type **Create2D(size_t rows, size_t cols) {
    Type **ptr = (Type **)SafeMalloc(rows * sizeof(Type*) + rows * cols * sizeof(Type)); 
    //  rows*sizeof(Type*) is total memory needed for the elements to store the pointers. 
    //  rows*cols*sizeof(Type) is the memory needed to store the actual array data
    //  The sum of the above two gives the total amount of contiguous memory needed

    size_t index;
    for (index = 0; index < rows; index++) {
        ptr[index] = (Type*)((unsigned char*)ptr + rows * sizeof(Type *) + index * cols * sizeof(Type));
       //  in my mind, this assigns the pointers to the address of each column
       //  to the first address blocks allocated by malloc
    }
    return ptr;
}

There is still a potential alignment issue: Type may require a stricter alignment than Type*. To account for this, you can compute the index size separately and align the data part on a multiple of the size of Type:

Type **Create2D(size_t rows, size_t cols) {
    size_t index_size = (size_t)((unsigned long long)(rows * sizeof(Type*)) * sizeof(Type) / sizeof(Type));
    Type **ptr = (Type **)SafeMalloc(index_size + rows * cols * sizeof(Type)); 
    //  index_size is total memory needed for the elements to store the pointers. 
    //  rows*cols*sizeof(Type) is the memory needed to store the actual array data
    //  The sum of the above two gives the total amount of contiguous memory needed

    size_t index;
    for (index = 0; index < rows; index++) {
        ptr[index] = (Type*)((unsigned char*)ptr + index_size + index * cols * sizeof(Type));
    }
    return ptr;
}
Sign up to request clarification or add additional context in comments.

7 Comments

That's also not guaranteed to meet any alignment restrictions on Type.
@AndrewHenle: malloc return value ptr is guaranteed to meet alignment restrictions on Type, adding a multiple of sizeof(Type) keeps this constraint verified. How do you think the alignment restriction is not met?
Thank you for the advice. I have tried the first of the two samples and it works. I understand the typecasting the entire index calculation to a (Type*), but I don't understand the typecast of (unsigned char*)ptr. I've tried removing that portion and my program hangs on the free(ptr) function. could you help me understand what that typecast is doing? @AndrewHenle I completely agree that doing this in two allocations is far easier. Sadly I'm restricted in my ability to do that right now due to the scope of my instructions.
Casting ptr as (unsigned char*) or (char*) allows pointer arithmetic to be performed on byte addresses as opposed to multiples of the size of Type. In the second code, it is possible to with a different cast: ptr[index] = (Type*)ptr + index_size / sizeof(Type) + index * cols; but I find it less explicit.
That rings clear as a bell. Thank you so much for the explanation.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.