How does this segment of C code for a priority queue work?

Question

I'm a bit overwhelmed at this line specifically:

 Entry** newHeap = (Entry**)malloc(sizeof(Entry*) * newHeapLength);

in this code:

 /**
     * Expands the heap array of the given priority queue by 
     *   replacing it with another that is double its size.
     *
     * @param  pq  the priority queue whose heap is to be doubled in size
     * return  1 for successful expansion or an error code:
     */
    int expandHeap (PriorityQueue *pq)
    {
        int returnCode = 1;
        int newHeapLength = pq->heapLength * 2;
        Entry** newHeap = (Entry**)malloc(sizeof(Entry*) * newHeapLength);
        if (newHeap != NULL) 
        {
            int index;
            for (index = 0; index < pq->heapLength; index++) 
            {
                newHeap[index] = pq->heap[index];
            }
            free(pq->heap);
            pq->heap = newHeap;
            pq->heapLength = newHeapLength;
        }
        else
        {
            returnCode = -1;  // TODO: make meaningful error codes
        }
        return returnCode;
    }

That line isn't well-written C. In C, you should never cast the result of `malloc`. Don't feel bad; the author also didn't seem to know C too well. — Kerrek SB, Mar 05 '12 at 06:13
@KerrekSB: is there anything in the excerpt that says it can't be non-idiomatic C++? — Alexey Frunze, Mar 05 '12 at 06:37
It is not so much complex to understand. Have one thing in mind. All pointers in C are unsigned integers. So in the code, the author allocates newHeapLength number of pointers to Entry. It means newHeapLength number of unsigned integers to store the address of newHeapLength number of address to Entry. And I don't think type casting the malloc returned void pointer is a bad idea. — theB, Mar 05 '12 at 07:09
@KerrekSB this is a very strange claim. How else could its result be used, being a `void*`??? — Will Ness, Mar 05 '12 at 09:11
@WillNess In C, a `void*` is implicitly converted to any other pointer type on assignment. Casting the return value of `malloc` is considered bad practice (because it's C++ style ;). — Daniel Fischer, Mar 05 '12 at 15:32
@DanielFischer guess I learned it from wrong C++ book then. Schmidt if memory serves. Or maybe it doesn't. :) — Will Ness, Mar 05 '12 at 15:52
@WillNess You can't learn C from a C++ book, generally. And if your memory inadvertently substituted Schmidt for Schildt, then it definitely was the wrong book - whichever of Schildt's it was. — Daniel Fischer, Mar 05 '12 at 16:24

score 2 · Answer 1 · answered Mar 05 '12 at 06:08

Entry** newHeap = (Entry**)malloc(sizeof(Entry*) * newHeapLength);
      |                      |
newHeap is a             malloc allocates a chunk in memory that is the size of 
pointer to a             a pointer to an Entry times newHeapLength
pointer to an Entry

Will Ness · Accepted Answer · 2012-03-05T16:34:22.533

It just allocates an array for you, at run-time. Usually the size of array must be specified at compile-time. But here it is specified at run-time, it's newHeapLength. Each entry ("cell") in that array must be capable of storing a value of type Entry* in it. In C, arrays are contiguous, so the total size of the array, in bytes, is just a product of the two numbers: sizeof(Entry*) * newHeapLength. Now newHeap can be used to address this array in a usual manner: e.g. newHeap[8]. Of course, if 8 >= newHeapLength, this would be accessing past the allocated area, which is bad.

For array storing 10 ints, int ia[10];, the type of ia is int * (correction: almost. but we can pretend that it is, for the purposes of this explanation). Here, similarly, for array storing values of type Entry*, the type is (Entry*)*. Simple. :)

And of course you must cast the return value of malloc to your type, to be able to address that array with it. malloc by itself returns an address as void*. Meaning. the size of memory cell which it points to, is proclaimed unknown. When we say that ia is of type int*, what we actually saying is that memory cell pointed to by it has size of sizeof(int). So when we write ia[3], it is actually translated into *(ia+3) which is actually *(int*)(void*)( (unsigned int)(void*)ia + 3*sizeof(int) ). In other words, the compiler just adds sizeof(int) three times to the starting address, thus "hopping over" three sizeof(int)-wide cells of memory. And for newHeap[8] it will just "hop" over 8 sizeof(Entry*)-wide memory cells, to get the address of the 9-th entry in that array (counting from 1).

Also, see hashed array tree for an alternative to the geometric expansion, which is what that code is doing.

Accessing past the allocated area is not merely _bad_, it's undefined behaviour. With the declaration `int ia[10];`, the type of `ia` is not `int*`, it is `int[10]`, array of 10 `int`s. In C, the prevailing opinion is that one should _not_ cast the return value of `malloc`, since that can hide errors (e.g. not having included `stdlib.h`). — Daniel Fischer, Mar 05 '12 at 15:38
@DanielFischer thanks! found [this answer](http://stackoverflow.com/a/3477952/849891). Though it says prior to C89 it *was* required... :) so, what is the type of `(ia+3)`? — Will Ness, Mar 05 '12 at 16:04
The type of `(ia+3)` - or `(ia+0)` - is indeed `int *`. In most expression contexts, arrays are converted to pointers, for example when passed as function arguments, or in pointer arithmetic. That caused the widespread misconception that in C arrays and pointers are the same. They are not, they only behave the same in many contexts. — Daniel Fischer, Mar 05 '12 at 16:21
@DanielFischer thanks again. :) one last thing, could you just point me somewhere on the web please where to find the spec. I searched and couldn't find. — Will Ness, Mar 05 '12 at 16:32
The last (as far as I know) draft for the C11 standard [published last December] is [n1570](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf). The published standard itself is not freely available, you can buy it from your national standards body (or ISO, I think), if you really need it. — Daniel Fischer, Mar 05 '12 at 16:39

How does this segment of C code for a priority queue work?

2 Answers2