Structures in C: From Basics to Memory Alignment – Abstract Expression

Structures allow us to combine several variables to create a new data type. Some other languages support the same concept but call it “records”. If you come from object-oriented programming you can think about them as classes without methods.

Declaration

A structure is declared by the keyword struct followed by the name of the new structure and a list of its members enclosed in parentheses:

Here we declared a new structure with the name s that has the members a (a single character), b (an integer), c (a double), and d (a char array of size 10 which can store up to 9 characters and a terminating null character).

Using a Structure

To use our new structure type we have to declare a new variable of type struct s and from then on we can access all individual members by writing the variable name followed by a dot and the name of the member:

Output:

s1.a: H
s1.b: 42
s1.c: 3.140000
s1.d: Hello

Using a Structure via a Pointer

The dot syntax from the previous example works for direct access to a structure variable but it doesn’t work if we want to access a structure via a pointer. For this kind of access, we need to use the -> operator or you will get a compiler error.

If we declare a pointer to s1 and use it exclusively to access the members of s1, our previous example will look like this:

Output:

s1.>a: H
s1->b: 42
s1->c: 3.140000
s1->d: Hello

Declaring a Struct and Variables

The declaration of a struct can include the declaration of variables of the new struct:

This code declares the struct s as well as the variables example1 and example2, both of them being instances of s.

Initialization

If we declare a structure variable without initializing it, like any other variable in C, it will be uninitialized at first and may contain random values.

In the previous examples, we initialized our structure variables manually by setting each member individually. This is perfectly fine (as long as we don’t forget to do so) but we can also initialize a structure variable when we declare it.

The C89 Standard allows us to initialize a structure variable like this:

With this syntax, we have to provide the values in the same order in which the members of the structure are declared. The problem with this is that we can never be sure that the values are assigned to the right member unless we look up the structure declaration.

It is not much of a problem with a structure that has only four members as in this example. But in complex programs, a structure can easily have 20 members and more. Things will get even more problematic when a structure changes over time. In such a case it is easy to make some subtle mistakes and put some values on the wrong line. The compiler will refuse to compile such a program if at least one initialization value is incompatible with the corresponding member of the structure. But if they are compatible you are out of luck and the compiler will accept the program, and you might have a subtle bug that is hard to find.

In the past, people tried to mitigate this problem by adding a comment with the name of the structure member to be initialized behind every initialization value.

Fortunately, nowadays there is a better solution. The C99 Standard introduced the so-called designated initializers. This new syntax for initializing struct members allows you to make explicit which members are initialized with which value:

The new syntax is way superior to the old one. You should always prefer it. The only reason not to use it is if you are forced to work with a C89 compiler and can’t upgrade.

Comparing Structs

C does not support the comparison of struts. In fact, if we try to compare two structs (even of the same type) with the == operator we will get a compile error.

The only way to compare two structs in C is to compare them member by member and the best way to do this is to write a comparison function for each struct type we want to compare.

So say we have a struct named Vector2D that represents a two-dimensional vector:

And we want to be able to compare this type. The comparison function could look like this:

Declaring a Struct as a New Type

Whenever we want to use a struct that we declared previously, we have to prefix it with the keyword struct because structs live in their own namespace. But what if we want a struct to feel like a real C type?

In this case, we can just use typedef:

In this example, we first declare a struct named Vector2D and afterward, we use typedef to define struct Vector2D as the new type Vector2D. We can also combine the typedef and the declaration of the struct into one single declaration (which is the best way to do it):

Both declarations have the same effect. We can now use our vector type as if it were a built-in C type:

Dynamic Allocation

Until now we always declared our structs as normal variables and therefore created them on the stack. But of course, we can also allocate a structure dynamically on the heap.

To do this, we just call malloc with the size of the struct and store the resulting value in a pointer to our struct. We then have to check if the pointer returned by malloc is NULL. If this is the case the allocation failed (usually because the system is out of memory) and we have to handle this error condition (e.g. by making sure all data touched by the program is in a consistent state and exiting the program with an error message).

If the pointer is not NULL we have a newly allocated instance of your struct. The memory is uninitialized so it is a good idea to initialize it to zero bytes. We can do this by calling the memset function with the pointer to our new struct, the initialization value 0, and the size of our structure:

Of course, we must not forget to free this newly allocated struct once we don’t need it anymore with the following code:

Failing to do so will cause a memory leak.

Copying Structs

Before C99 compilers were not required to be able to copy structs. Therefore, the only way to pass them around was via pointers. So if you wanted to write a function that manipulates a struct you had to do it like this:

With C99 passing structs by value is an option:

Of course, this also means that you have to pass value to the function and assign the return value of the function to value when calling it:

Some people might argue that this is slower than passing around pointers. But in many cases, it is not. It might even be faster than passing pointers.

The only way to know for sure is by measuring it.

The great thing about this is that it allows us to omit to allocate structs with malloc on the heap. Instead, we could create a struct on the stack and pass it around by copying it. This opens the door to new approaches for writing safer C code.

Nested Structures

Structures can be nested. That means a structure can contain another structure. Let’s use our 2D vector as an example again:

We could then declare a structure type that represents a Sprite and uses our 2D vector type to represent the position of the sprite:

Of course, C also allows us to initialize our nested structure together with the containing structure:

Self Referential Structures

A structure can contain instances of other structures as members but it cannot contain members of its own type.

So if we tried to create a very simplistic binary tree like this:

we would get a compile error. The reason for this is that this would create an endless recursion and the structure would take up an infinite amount of memory.

The only way around this problem is to use pointers to the structure of the same type as a member:

Element Order and Addressing

The C Standard guarantees that all members of a structure occur in memory in the same order as in the declaration.

That means if we have a structure definition like this:

then the member a will always be the first element in memory, b will be placed after a, and c will be placed after b.

Now if we want to get the address of a member inside a structure it is as simple as this:

And with a pointer

If you don’t want to get the memory address of a member but just want to know how many bytes it starts from the beginning of the structure (its offset) you can use the very neat offsetof macro that is defined in stddef.h:

If this macro returned 8 for example this would mean that the member variable is located at the memory address of the struct plus 8 bytes.

This macro is useful to check if the compiler added any padding in between the members of the structure. It can also be used to get the memory address of the structure if you only have the address of one of its members and know what type of struct it is a member of. This is used in some advanced code e.g. the OOP implementation of the Linux Kernel.

Alignment and Padding

One might assume that the compiler puts all its members directly behind each other in memory with no gaps in between and that the size of each structure is exactly the same as the sum of the sizes of all of its members. Such a structure is called a packed structure:

This is NOT how a compiler usually lays out a structure in memory.

In the previous section, we already said that the C standard guarantees that struct members always appear in memory in the exact same order in which they are declared in code. In addition, the C standard also says the following things regarding the memory layout of structures:

• The first member must always start at the same memory address as the structure itself
• There may be padding before each other member of the structure to ensure that it is located at a memory address that complies with whatever rules the hardware platform defines for such a type
• There may be padding at the end of the structure

The possible padding as allowed by the C standard can be visualized like this:

The compiler is allowed to add padding at those locations shown in the graphic but it is not obliged to do so. There is no guarantee about the data that is stored in those areas that the compiler uses as padding. It might be all zeroed, it might be only ones or zeros or it might be a bit pattern. It could also be just random data.

Packed structures are so much nicer and they don’t waste any memory. Why doesn’t the standard enforce their use and why does it leave so many things open for the implementation to decide?

The most general reason is that one of the design goals of C was to be a language that can be implemented on as many hardware platforms as possible. Therefore the standard needs to be flexible to allow compilers to adapt the actual implementation to the specialties and quirks of their hardware respective platforms.

The other reason is that even on modern platforms it is faster to access data that is located at a memory address that is divisible by a certain number. Putting your data on such “even” addresses is called memory alignment. On some platforms (e.g. SPARC) memory alignment is even strictly necessary because memory access to unaligned addresses leads to a CPU exception and crashes the misbehaving program.

Thankfully, most modern hardware platforms (especially x64 and ARM64) follow the same rules for alignment. On modern platforms, all basic C types have to be self-aligned. This means that each basic type has to be located at a memory address that is a multiple of its size:

Data Type	Size in Bytes	Self-Alignment
char	1	None (any address is fine)
short	2	The address has to be a multiple of 2
int	4	The address has to be a multiple of 4
long	8	The address has to be a multiple of 8
Pointer	8	The address has to be a multiple of 8

Self-alignment rules of a modern 64-bit machine (e.g. x86-64 or ARM 64)

If we suppose for a moment for the sake of having nice and easy memory addresses that we could store data in the very first 64-bit word in memory which begins at address 0 (which in practice we can’t because this part of the memory is usually protected), then we could visualize the possible addresses of our basic data types like this:

Possible memory addresses of self-aligned basic data types

The reason for those rules is that on such a machine we have a load instruction that can read a full 64-bit word from memory. If we imagine memory as a sequence of 64-bit words then there starts a new word every 8 bytes (64 bits).

All those starting addresses of our machine words (0, 8, 16, 24, etc.) are “even”. Loading such a “regular” word from an “even” address is fast. But we can also load 8 bytes starting at any address of our choosing. Let’s say we load a word beginning at address 4. In this case, the word we load would span two machine words. It would consist of the last 4 bytes of the first machine word in memory and the first 4 bytes of the second machine word. Due to hardware limitations, a load operation that spans two machine words is slow.

And here you have it. If you look at the graphic of the possible self-aligned addresses of our basic data types again you can see that it is not possible for one of those variables to be in more than one machine word. This is the purpose of those rules.

There is one problem left. And that is arrays. Members of arrays are put in memory in sequence with no gaps between them. So arrays themselves have no padding. What would happen if we have a structure where all the members are carefully aligned but its total size is odd and we put another struct of the same type right behind it in memory? Right! We get array members that cross the boundaries of machine words and our carefully crafted alignment falls apart.

Just look at the diagram of our self-aligned data types and add 3 to all the starting addresses in your mind and you see what I mean. Add an 8 instead and everything is fine. Our data just moved to the second “regular” word in memory. Add a 2 and the shorts are fine (the chars are always fine). Add a 4 and the shorts and the ints are fine and only the 8-byte types live in two different machine words.

And here we already see the solution. A structure has to get enough trailing padding to align with its biggest data type. So if your structure contains an 8-byte type the total size of the structure has to be a multiple of 8. If your biggest type is 4 bytes the total size has to be a multiple of 4. And with the biggest type being 2 bytes – you guessed it – the size of the structure has to be a multiple of 2.

Example

Alignment and padding can be confusing topics.

So let’s look at some code to get a better feel for it:

First, we declare the struct that we also used at the beginning of this article. It contains a char variable, an integer variable, a double variable, and a char array of size 10.

We calculate the expected size of the struct by adding the values returned by sizeof for all of the types.

Then we print the offsets of all the members in the struct, followed by the expected size and the real size of the struct.

This program can be compiled with:

On an x64 machine running Linux, this program gives the following output:

expected offset of a: 0
real offsetof a: 0
expected offset of b: 1
offsetof b: 4
expected offset of c: 5
offsetof c: 8
expected offset of d: 13
offsetof d: 16

Expected struct size: 23
Real struct size: 32

The offsets are bigger than we would expect if there were no gaps between the members. From this output, we can deduce that the memory layout of our structure looks like this:

With clang, we can even make the compiler print us this padding information as warnings by compiling the program the -wpadded option:

This will yield the following warnings:

struct-align.c:6:9: warning: padding struct 'struct s' with 3 bytes to align 'b' [-Wpadded]
    int b;
        ^
struct-align.c:4:8: warning: padding size of 'struct s' with 6 bytes to alignment boundary [-Wpadded]
struct s {
       ^
2 warnings generated.

These warnings match up with the paddings we figured out on our own with the help of the offset macro. It is just much easier to let the compiler do the work for us which makes this especially useful if you have bigger structures in your program and wonder about their padding.

If you absolutely need a packed structure instead of what the compiler generates by default (e.g. because you want to map a file format or some hardware registers exposed in memory) you can use non-standard compiler extensions to force the compiler to create a structure without gaps.

With gcc and clang, you do this by using the packed attribute:

If we compile and run the program again with this modified structure declaration the output looks like this:

expected offset of a: 0
real offsetof a: 0
expected offset of b: 1
offsetof b: 1
expected offset of c: 5
offsetof c: 5
expected offset of d: 13
offsetof d: 13

Expected struct size: 23
Real struct size: 23

As we can see from this output our structure is now laid out in memory without any gaps and padding. The size of the struct is equal to the sum of the sizes of all members.

Don’t use this on all your structures from now on! Packed structures are a non-standard feature and they make your code run slower. On some architectures, they might even cause your program to crash. Depending on your architecture your compiler might have to create extra code to access the non-aligned members of your structure. If you pass around pointers to non-aligned members in your program not all compilers are smart enough to know that they need to generate this extra code when dereferencing those pointers and on some architectures (e.g. SPARC) this leads to a crash.

There are good reasons why normally the compiler adds padding to structures. The only good reason to use packed structures is when you need to map some memory (e.g. hardware registers exposed to memory) bit by bit to a structure.

Bitfields

Imagine you want to store eight flags in a structure. You could add 8 bool fields and be done with it:

But since each bool variable is one byte (8 bits) in size and a flag can be stored in a single bit you would waste 7 bytes because your flags could be stored in one single byte.

Thankfully, C supports so-called bitfields. Bitfields allow us to define fields of a certain data type but use only a freely defined number of bits. If we define more than one bitfield it is the compiler’s job to organize them in memory in a way that (hopefully) uses no more memory than necessary.

With bitfields can rewrite our flags example like this:

The “: 1” tells the compiler that each of our 8 bool fields should use only one bit. Therefore they fill exactly one byte and we store 8 bools in one bool variable. If we would declare less than 8 flags some bits would be unused. If we declared more than 8 the compiler would allocate enough additional bytes.

Don’t expect to save too much storage, though. Because of data alignment, the compiler will waste a lot of space anyway unless you hand-optimize the structure.

Of course, bit fields can’t only be used to save space when storing booleans.

For example, assume we would build an ancient terminal emulator and we would like to store a single character of 7-bit ASCII as well as its text and background color and some other simple text attributes in 32 bits of memory.

We could create a struct like this to achieve our goal:

Here we use 7 bits to store the ASCII character, 11 bits for the foreground and the background color each, and 3 bits in total to add attributes for bold, italic, and underline to our character.

Another use case for bitfields is to map hardware registers or file formats one by one. But this is a use case that should better be omitted because the memory organization of bit fields depends on the compiler and therefore such code will probably not be portable.

Most compilers try to pack bitfields as tightly as possible in memory but since they are quite implementation dependent when working with bitfields it is best to check for yourself how your compiler stores the data in the structure instead of relying on unproven assumptions.

Another thing to keep in mind is that – unlike with normal structure members – it is not possible to get the address of a bitfield member. So this code will not compile:

The following data types can be used for bitfields in C99 (some compilers support additional data types):

• unsigned int
• signed int (int)

Flexible Array Members

In C99 it is allowed to declare the last member of a structure as an array with no number of elements specified. The size of the struct will then be as if the last member did not exist.

This allows us to do something like this:

We have a struct called DynamicString that can store the length of a string and it has a char array of unspecified length as its last member. When we want to allocate such a dynamic string we have to allocate enough bytes for the struct itself plus the bytes needed for the number of elements we want the array to have. The nice thing is that we can choose freely how many elements we want the array to have whenever we create a new instance of DynamicString:

Now we have an array of chars that can take up to 29 characters plus the terminating null byte and knows its size. And we could create more such strings with all kinds of different sizes.

Further Reading

C: A Reference Manual (Fifth Edition), ISBN: 978-0130895929

The Lost Art of Structure Packing