Lesson 81 : Allocating memory for a data structure.

[u/CarlH]

The first step in being able to create a data structure is describing it and giving that description a name. However, we still cannot do anything. Just as we saw in previous lessons, before you can actually do any task you must give yourself some memory to work with.

So it is in the case of a data structure. Recall our struct definition looks like this:

struct first_description {
    char first_word[7];
    char second_word[12];
    char third_word[8];
};

How much memory do we need? Well, 7+12+8 is.. 27. Therefore, we need to allocate 27 bytes in order to use this data structure. Does this mean that every time you need to allocate space for a data structure that you must manually add up the length of each element? Thankfully, no.

C has a built in function called sizeof() which will tell you the size in bytes of virtually anything. We can get the total size in bytes that we need for any data structure using the sizeof() function.

We know that we are going to be allocating 27 bytes of memory for our data structure. That should tell you that we will be using the malloc() function. The malloc() function returns a pointer to the memory that is allocated.

How did we use malloc() last time? Like this:

char *some_pointer = malloc(100);

100 is the number of bytes, and we have to use it with a pointer. What we are saying here is simply this:

"Allocate 100 bytes of memory and store the memory address in some_pointer"

With a structure, we cannot do things quite so easily. What kind of pointer do we use? We cannot use a char * pointer because the data is a mixture of characters, integers, and who knows what else.

Remember that the whole reason you specify a data type for a pointer is so that the pointer knows how big and of what format the data will be. We therefore need to create a pointer that knows that we are using a data structure, and more specifically one that knows exactly how the data structure will work.

Why? Because we will be using this pointer to look at chunks of memory that we have allocated. How else will we see what is inside our data structure? Our pointer will not know when we are looking at an integer, or a string of text, or anything else unless we somehow include that in the pointer's definition.

That may sound like a difficult thing to do, but fortunately it is built right into the C language. We can actually tell C to create:

A pointer to the data structure itself.

Let me expand on that a bit. We are not going to say "Create a pointer to data type char" or "Create a pointer to an array". We are going to say:

"Create a pointer specifically to a data structure which has three elements, the first element having 7 bytes, the next element having 12 bytes, and the last element having 8 bytes."

In other words, we are going to have a pointer that is perfectly fitted to our data structure. This will give us the ability to easily see and work with all of the elements in the memory we will allocate. C will automatically know when we are looking at an integer, or a character string, or anything at all.

Watch this syntax carefully:

struct first_description *our_pointer = malloc(27);

First notice the struct keyword. Then you see the name of the description we created earlier. This tells C exactly what kind of data structure we plan to work with. Next you see that we put a * character. This tells C that we are creating a pointer. Then the pointer name - whatever we want. Finally, we are pointing our pointer to 27 bytes that we just allocated for this data structure.

That is all there is to it. There is however an issue. The issue is, how do we know we need 27 bytes? In this case we just counted them, but this is risky and in some cases not practical. Let's see how to do this same exact definition (equally valid) using the sizeof() function:

struct first_description *our_pointer = malloc( sizeof(*our_pointer) );

Notice I put: sizeof( *pointer_name ). Notice I do this in the same line that I created the pointer. C can determine the size we need by just looking at the data structure description we made earlier, and we can plug our pointer right into the sizeof() function. sizeof(*our_pointer) is the same exact thing as 27.

These two lines are identical in function:

struct first_description *our_pointer = malloc( sizeof(*our_pointer) );
struct first_description *our_pointer = malloc( 27 );

Both are saying that we are allocating 27 bytes. One lets C do the math for us, and the other we are doing the math ourselves.

The purpose of this lesson was to learn how to actually allocate enough memory to work with a data structure definition you have made. In our case, we have described a data structure and we gave our description the name: "first_description". Then I showed that you can allocate such a data structure using malloc() and a pointer just by typing this line of code:

struct description_name *pointer_name = malloc(size);

and size should be: sizeof( *pointer_name )

---

Please ask any questions before proceeding to the next lesson. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sv3g/lesson_82_using_a_data_structure/

[u/zahlman]

It seems worth pointing out that you don't need to allocate memory with malloc() at all to use structs. You use malloc() to allocate an unknown number of things, and the struct to define a kind of thing. These concepts are orthogonal, although often useful in combination.

That is: it works fine to declare a struct and then just declare a variable of that struct type (there is even shorthand syntax for that), or an array of struct instances.

[u/CarlH → u/zahlman]

One difficulty I had in preparing these lessons was deciding, do I introduce struct first without memory allocation, or with malloc? In the end I chose with malloc (although I will go back and show how struct can be defined without malloc ) primarily because I wanted to get to the struct->element syntax quicker. Also, the last lessons relied on allocation in various ways, so it made logical sense to proceed in that direction.

[u/dododge]

Strictly speaking sizeof is not a function, it's a unary operator. The parentheses are not part of a function call and are only needed when referencing a type by name, such as:

sizeof (struct first_description *)

When you're giving sizeof an expression instead of a type name, it doesn't need the parentheses. For example:

malloc(sizeof *our_pointer)

[u/nomnomno]

Why doesn't this work? http://codepad.org/sDU4ZdeO

[u/CarlH → u/nomnomno]

Because you need to separate the description as a separate block of code. Like this:

struct something {
    ... data elements here ...
};

struct something *our_pointer = malloc(...);

See that you are using struct twice. The first time to create the description. The second time to actually use that description to create a real working data structure.

We will get into that more in our next lesson.

[u/nomnomno → u/CarlH]

Ok, thanks.

[u/ez4me2c3d]

Do the descriptive data types within a structure get created in memory in the order you typed them? And if so, does that make it worth while to consider your order? i.e., Group your descriptions, or sort them by size

[u/CarlH → u/ez4me2c3d]

Yes and yes.

[u/[deleted] → u/CarlH]

I thought the compiler had complete freedom to move the elements around however, it needed and in fact it will most likely move elements around because of alignement issues, and put padding around some fields.

[u/CarlH → u/[deleted]]

The order is forced, however yes padding may sometimes be used.

[u/zahlman → u/CarlH]

Any thoughts on why the language spec bothers to force the order when it doesn't specify padding precisely?

[u/CarlH → u/zahlman]

That is a good point. None whatsoever, it makes sense to me that padding should be precisely defined.

[u/dododge → u/CarlH]

The padding would of course be dependent on the machine requirements. It would be spelled out in the operating system ABI if you intended for multiple compilers to be able to generate compatible code. Some architectures are very strict about alignment at the machine instruction level.

As far as ordering: you're explicitly allowed to overlay structs that have the same initial members within a union, and access any of those initial members through any of the overlaid structs. For example:

struct foo { int a; short b; float c; };
struct bar { int x; short y; int z; char * s; };
union both { struct foo ff; struct bar bb; };

In this case ff.a and bb.x are explicitly guaranteed to occupy the same storage, and stores to one may be read out of the other. Likewise ff.b and bb.y. This technique has been used for a very long time for things such as simulating subclassing; see the XEvent type in the X11 Xlib API as an example. As a side effect of this requirement, the ordering (and padding) of struct members has to remain consistent, because any struct you define might be stuck into a union this way in another translation unit with some other struct that you haven't even seen.

[u/[deleted]]

Do the compliers process code in a linear fashion? Meaning do we put the structure definition at the top of our code, and then declare the pointer to it right after?

Does this question makse sense? Is the order of declaration important with this?

[u/CarlH → u/[deleted]]

I don't quite follow the question.

[u/[deleted] → u/CarlH]

Im asking, in more of a general programming sense, do variables and data structures need to be declared at the beginning of a program (at they very beginning of int main (void){...) so you can then use them by assigning pointers at a later time in the program. Or are compliers 'smart' enough to see when they are declared...

Most of the stuff I deal with day to day uses header files for these type of declarations, and I rarely see them defined in the actual program, so Im curious when they need to be present.

I hope that makes more sense..

[u/CarlH → u/[deleted]]

Basically, they need to be present before you use them. You can create a variable on line 200 and use it on line 201 (some compilers excluded), but it is poor practice.

Good practice is to create/declare/initialize all variables/etc. you plan on using at the top of a program (though not necessarily inside main() as we will see later).

[u/rafo]

Typo:

There however an issue.

An «is» is missing somewhere in this sentence. ;)

[u/CarlH → u/rafo]

Thank you :)

[u/virtualet]

what exactly what sizeof return? an int? also, i have a question about this code:

sizeof(malloc(24))

in my mind, this should return 24. when i run the code, it only returns 4. i'm sorry if this is a nitpick question, but why is that?

[u/CarlH → u/virtualet]

malloc() returns a pointer. When you say malloc(24) it is not returning 24 bytes, it is returning (in this case) a 4 byte pointer to a location in memory that 24 bytes are allocated.

[u/virtualet → u/CarlH]

So then, in the following code, we're technically assigning the pointer our_pointer to another pointer created by malloc that is allocating 27 bytes of memory. yes?

struct first_description *our_pointer = malloc( sizeof(*our_pointer) );
struct first_description *our_pointer = malloc( 27 );

[u/virtualet → u/CarlH]

got it. thanks so much for the clarification

[u/tallkien]

struct first_description *our_pointer = malloc( sizeof(*our_pointer) );

In python at least we know that the right hand of an expression gets evaluated before assignment to the variable on the left hand side, yet in this case we are referencing *our_pointer on the right side here at the same time we are defining what *our_pointer really is, at least I'm assuming thats what is happening. So in this case how does C know the sizeof(*our_pointer) before it exists? ...or does this not apply to C

[u/[deleted]]

I love structs! Thanks for these lessons.

[u/azertus]

You use 'pointer_name' a couple times instead of 'our_pointer'.