C - Structure's pointer

Question

I'm having trouble understanding pointers in general I think. I can't seem to follow the logic of this code:

    typedef struct StackRecord
{
    int Capacity;
    int TopOfStack;
    int* Array;
}*Stack;

In the following structure, *Stack was declared to receive addresses of StackRecord structure type via simply stating Stack due to typedef

BUT code below the return another receiver of addresss of StackRecord structure type. Why isn't it returning the address? But rather return same type of pointer to itself?

Stack CreateStack(int MaxElements)
{
    Stack S;

    if (MaxElements < MinStackSize)
    {
        printf("Error : Stack size is too small");
        return 0;
    }
    S = (Stack)malloc(sizeof(struct StackRecord));

    if (S == NULL)
    {
        printf("FatalError : Out of Space!!!");
        return 0;
    }

    S->Array = (int*)malloc(sizeof(char)* MaxElements);

    if (S->Array == NULL)
    {
        printf("FatalError : Out of Space!!!");
        return 0;
    }
    S->Capacity = MaxElements;
    MakeEmpty(S);

    return S;
}

Answer 1

In the typedef, the type identifier Stack is a pointer to a struct. The function prototype for CreateStack() specifies a return value of type Stack, which is a pointer to a StackRecord struct. S is declared to be of type Stack in the function body, so the function does return a pointer to a StackRecord struct.

Answer 2

Getting rid of the typedef may make things a little clearer, believe it or not:

struct StackRecord
{
    int Capacity;
    int TopOfStack;
    int* Array;
};

/**
 * Return a pointer to a new, dynamically allocated instance
 * of struct StackRecord
 */
struct StackRecord *CreateStack(int MaxElements) 
{
    struct StackRecord *S;

    if (MaxElements < MinStackSize)
    {
        printf("Error : Stack size is too small");
        return 0;
    }
    S = malloc(sizeof *S); // no need for cast, sizeof *S is same as sizeof (struct StackRecord)

    if (S == NULL)
    {
        printf("FatalError : Out of Space!!!");
        return 0;
    }

    /**
     * Allocate the memory for the Array member of
     * the new stack record instance.
     */
    S->Array = malloc( sizeof *S->Array * MaxElements );

    if (S->Array == NULL)
    {
        printf("FatalError : Out of Space!!!");
        return 0;
    }
    S->Capacity = MaxElements;
    MakeEmpty(S);

    return S;
}

In the code you posted, Stack is basically a synonym for struct StackRecord *. The function creates a new instance of struct StackRecord using malloc, initializes the contents of that record, and returns a pointer to that new instance.

A note on the malloc calls - in C, you do not need to cast the result of malloc, and doing so is generally considered bad practice¹. Also, the operand to sizeof doesn't have to be a type name - it can be an expression of the type you want to allocate. IOW, given a declaration like

T *p;

both sizeof (T) and sizeof *p do the same thing - the expression *p has type T. So the general form of a malloc call can be written as

T *p = malloc( sizeof *p * N );

or

T *p;
...
p = malloc( sizeof *p * N );

That's simpler to write and easier to maintain than

p = (T *) malloc( sizeof (T) * N );

<rant>

Hiding the pointer-ness of a type behind a typedef is bad juju, especially when the user of that type has to be aware that he or she is dealing with a pointer type. Assigning the result of malloc to S means that S must be a pointer type. Using the -> to access members of S means that S must be a pointer to a struct or union type. Since you have to be aware that S is a pointer, it makes no sense to hide that pointerness behind the typedef. Similarly, if the user has to be aware of the struct-ness of the type, you shouldn't hide that struct-ness behind a typedef either.

Abstraction is a powerful tool, but partial (leaky) abstractions like the original code just make life more confusing for everyone (as you have discovered for yourself).

</rant>

---

1. This is not true for C++, because C++ doesn't allow implicit conversions between void * and other pointer types the way C does. But, if you're writing C++, you shouldn't be using malloc anyway.

Answer 3

In comments on @DavidBowling's answer you express this apparent misconception:

Stack is a pointer to StackRecord which means pointer must contain another address to which it is pointing to.

The typedef declares the identifier Stack to be an alias for the type struct StackRecord *. That would perhaps be clearer if it were rewritten in this wholly equivalent form:

struct StackRecord
{
    int Capacity;
    int TopOfStack;
    int* Array;
};

typedef struct StackRecord *Stack;

No object of type struct StackRecord is declared, only that type itself and type Stack.

When function CreateStack() allocates memory sufficient for a struct StackRecord ...

malloc(sizeof(struct StackRecord));

... it is perfectly reasonable to convert the resulting pointer to type struct StackRecord *. Indeed, type Stack is exactly the same type as struct StackRecord *, so that's precisely what the code in fact does. The converted pointer still points to the same memory, and when that pointer is returned, the return value also points to the same memory.