Type Declarations in C ( Conceptual )

Question

This question is in general more of a conceptual question and not a coding problem essentially. I was curios as I came across these pieces of code and was wondering if they are valid or not. Or why basically , if someone could give me an explanation please ?

Here are some type declarations in C:

typedef struct Rec1 * Ptr1;
typedef struct Rec2 * Ptr2;

struct Rec1
{
    int data;
    Ptr2 next;
};

struct Rec2
{
    double data;
    Ptr2 next;
};

Should these be allowed? Are they allowed? Why or why not?

Answer 1

Are they valid?

Yes they are valid

Reason:

1. First two lines create Ptr1 and Ptr2 as type-definitions for a struct Rec1 * and struct Rec2 *.

2. Since they are pointers, and not structures themselves, they make the struct Rec1 and struct Rec2 as incomplete types, and they are just making Rec2 as recursive type (usually used in creating datastructures) and Rec1 as having a pointer to Rec2 object.

Should they be allowed?

How else can you create self-referencing structures?

Answer 2

The short version:

• Should it be allowed? Yes

• Are they (forward type type definitions)? Yes.

• Why or why not?

This is a commonly accepted way of doing forward type declaration. It allows one to declare a incomplete type and define it later. This isn't a big deal in simple cases like this, but can be absolutely necessary in cases that are more complex.

The Linux or Darwin kernel both make fairly extensive use of this technique to declare internal kernel structures in a way that allows definition of the data type in it's own header file, but allows the use of the data type before it's fully defined.

Without this mechanism complex, interdependent, definition of data types would be impossible.

Answer 3

According to the language standard, they are valid and therefore should be allowed.

Now, if you ask how this all works, it's pretty easy.

Pointers are merely memory addresses, usually. And you can have a pointer to any object in memory if the object is represented by an integral number of bytes (each of which has a unique address). I'm saying "integral" here because you can't have a pointer to structure bit fields (at least, you can't have a pointer to those that don't begin on a byte boundary and occupy an integral number of bytes).

So, Ptr2 is just a pointer type of a beforehand known size (if your CPU's address space is from 0 to 4 GB, 32 bits of address are sufficient to address every byte and 32 bits would be the native pointer size on this CPU) and you can allocate space for such a pointer in struct Rec1 and struct Rec2 even if what this pointer points to isn't yet known, which is what we have in the code in question. Ptr1 and Ptr2 are defined as incomplete types, that's the official name for this.

The rationale for implementing such incomplete pointer types in the language is very practical. If you want to create linked lists or trees, their elements or nodes have to point somehow to other elements or nodes they're linked with. You could, in theory, create distinct element/node types for the last element (or a leaf node) and then for the one that points to it and then for the one that points to that one and so on. But this doesn't scale well, if you have more than just a few elements or nodes. What if you want a million of them? Defining a million of nearly identical types is impractical at best. So, the language provides you with a short-cut to avoid this. You could also declare the next pointers as just void* pointers, but then you'd need to cast them everywhere to struct Rect1* or struct Rect2* and maintaining and debugging of such code is going to be error-prone. So, there, the language gives you a hand.

Answer 4

A typedef is just an alias for the actual type it refers to. You can think of it as a Macro, but it is not something which gets substituted in the pre-processing phase of compilation.

Just substituting all occurrences of Ptr1 with struct Rec1 * yields a valid code, that is the simplest way to confirm if the code is valid ;)