 # Structure in C - Storage, Pointers, Functions and Self-Referential Structure

Photo by Robby McCullough on Unsplash

We have variables of different data types such as `int`s, `char`s, `float`s, etc to store data. We have arrays to group together a collection of data of the same data type.

But in reality, we will not always have the luxury of having data of one type. That's where a structure comes into the picture.

### 0. Memory Allocation of a Structure

When a structure variable of some type is declared, structure members are allocated contiguous (adjacent) memory locations.

``````struct student
{
char name;
int roll;
char gender;
int marks;
} stu1;
``````

Here, the memory will be allocated to `name`, followed by `roll`, `gender` and `marks`. This implies that the size of the `st1` or `struct student` will be the sum of the size of its members. Isn't it? Let's check.

``````void main()
{
printf("Sum of the size of members = %I64d bytes\n", sizeof(stu1.name) + sizeof(stu1.roll) + sizeof(stu1.gender) + sizeof(stu1.marks));
printf("Using sizeof() operator = %I64d bytes\n",sizeof(stu1));
}

/* Output */
Sum of the size of members = 45 bytes
Using sizeof() operator = 48 bytes
``````

Using the `sizeof()` operator gives `3` more bytes than the sum of the size of members. Why? Where are those 3 bytes in the memory? Let's answer the second question first. We can print the addresses of the members to find the addresses of those `3` bytes.

``````void main()
{
printf("Address of member name = %d\n", &stu1.name);
printf("Address of member roll = %d\n", &stu1.roll);
printf("Address of member gender = %d\n", &stu1.gender);
printf("Address of member marks = %d\n", &stu1.marks);
}

/* Output */
Address of member name = 4225408
Address of member roll = 4225428
Address of member gender = 4225432
Address of member marks = 4225436
`````` We observe that array `marks` instead of being allocated from `4225433` has been allocated from `4224536`. But why?

#### Data Aligment

Before looking at data alignment, it is important to know how the processor reads data from the memory.

A processor reads one word in one cycle. This word is 4 bytes for a 32- bit processor and 8 bytes for a 64-bit processor. Lower the number of cycles, better is the performance of the CPU.

One way to achieve this is by aligning the data. Aligning means that a variable of any primitive data type of size `t` will always (by default) have an address that is a multiple of `t`. This essentially is data alignment. This takes place every time.

##### Aligned addresses for some data types
data type size ( in bytes) address
`char` 1 multiple of 1
`short` 2 multiple of 2
`int`, `float` 4 multiple of 4
`double`, `long`, `*` ( pointers) 8 multiple of 8
`long double` 16 multiple of 16

It may be required to insert some extra bytes between the members of the structure to align the data. These extra bytes are known as padding.

In our above example, the `3` bytes acted as padding. Without them, marks which is of type `int` (address multiple of 4) would have its base address as `4225433` (not a multiple of 4).

You can now probably see why structures can't be compared directly. #### Structure Member Alignment

To explain this, we will take another example (you'll understand why).

``````struct example
{
int i1;
double d1;
char c1;

} example1;

void main()
{
printf("size = %I64d bytes\n",sizeof(example1));
}
``````

What would be the output? Let's apply what we know.

`i1` is of 4 bytes. It will be followed by padding of 4 bytes because the address of `d1` should be divisible by 8. This will be followed by 8 and 1 byte respectively for `d1` and `c1`. Thus, the output should be 4 + 4 + 8 + 1 = 17 bytes.

`````` /* Output */
size = 24 bytes
``````

What? Wrong again! How? Through an array of `struct example`, we can understand better. We will also print the address of the members of `example2`.

``````void main()
{
struct example example2;
printf("Address of example2.i1 = %d\n", &example2.i1);
printf("Address of example2.d1 = %d\n", &example2.d1);
printf("Address of example2.c1 = %d\n", &example2.c1);

}

/* Output */
``````

Let's suppose the size of `example2` is 17 bytes. This implies that the address of `example2.i1` will be `4225425`. This isn't possible since the address of `int` should be a multiple of 4. Logically, the possible address for `example2.i1` seems to be `4225428`, a multiple of 4.

This is wrong as well. Did you find out? The address of `example2.d1` now will be (28 + 4 ( `i1`) + 3 ( padding)) `4225436` which is not a multiple of 8.

To avoid such misalignment, the compiler introduces alignment to every structure. This is done by adding extra bytes after the last member, known as structure member alignment. In the example discussed at the start of this section, it wasn't required ( hence, another example).

A simple way to remember is through this rule - Address of structure & structure length must be multiples of `t_max`. Here, `t_max` is the maximum size taken by a member in the structure.

For `struct example`, 8 bytes is the maximum size of `d1`. Therefore, there is a padding of 7 bytes to the end of the structure, making its size 24 bytes.

#### These two points will help you find the size of any structure -

1. Any data type stores its value at an address that is multiple of its size.

2. Any structure takes the size which is multiple of maximum bytes taken by a member.

Though we can lower the CPU cycles, there is a significant amount of memory going waste. One way to decrease the amount of padding to a possible minimum is by declaring the member variables in decreasing order of their size.

If we follow this in `struct example`, the size of the structure reduces to 16 bytes. The padding gets reduced from 7 to 3 bytes.

``````struct example
{
double d1;
int i1;
char c1;

} example3;

void main()
{
printf("size = %I64d bytes\n",sizeof(example3));
}

/* Output */
size = 16 bytes
``````

#### Strcture Packing

Packing is the opposite of padding. It prevents the compiler from padding and removes the unallocated memory. In the case of Windows, we use the `#pragma pack` directive, which specifies the packing alignment for structure members.

``````#pragma pack(1)

struct example
{
double d1;
int i1;
char c1;

} example4;

void main()
{
printf("size = %I64d bytes\n",sizeof(example4));
}

/* Output */
size = 13 bytes
`````` This ensures that the members are aligned on a 1-byte boundary. In other words, the address of any data type has to be as multiple of 1 byte or their size (whichever is lower).

### 1. Pointers

#### Pointer as a Member

A structure can have pointers as members as well.

``````struct student
{
char *name;
int *roll;
char gender;
int marks;
};

void main()
{   int alexRoll = 44;
struct student stu1 = { "Alex", &alexRoll, 'M', { 76, 78, 56, 98, 92 }};
}
``````

Using `.` (dot operator), we can again access the members. Since `roll` now has the address of `alexRoll`, we will have to dereference `stu1.roll` to get the value ( and not `stu1.(*roll)` ).

``````   printf("Name: %s\n", stu1.name);
printf("Roll: %d\n", *(stu1.roll));
printf("Gender: %c\n", stu1.gender);

for( int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n", i, stu1.marks[i]);

/* Output */
Name: Alex
Roll: 43
Gender: M
Marks in 0th subject: 76
Marks in 1th subject: 78
Marks in 2th subject: 56
Marks in 3th subject: 98
Marks in 4th subject: 92
``````

#### Pointer to Structure

Like integer pointers, array pointers and function pointers, we have pointer to structures or structure pointers as well.

``````struct student {
char name;
int roll;
char gender;
int marks;
};

struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}};

struct student *ptrStu1 = &stu1;
``````

Here, we have declared a pointer `ptrStu1` of type `struct student`. We have assigned the address of `stu1` to `ptrStu1`.

`ptrStu1` stores the base address of `stu1`, which is the base address of the first member of the structure. Increment by 1 would increase the address by `sizeof(stu1)` bytes.

``````printf("Address of structure = %d\n", ptrStu1);
printf("Adress of member `name` = %d\n", &stu1.name);
printf("Increment by 1 results in %d\n", ptrStu1 + 1);

/* Output */
Adress of member 'name' = 6421968
Increment by 1 results in 6422016
``````

We can access the members of `stu1` using `ptrStu1` in two ways. Using `*` (indirection operator) or using `->` (infix or arrow operator).

With `*`, we will continue to use the `.`(dot operator) whereas with `->` we won't need dot operator.

``````printf("Name w.o using ptrStu1 : %s\n", stu1.name);
printf("Name using ptrStu1 and * : %s\n", (*ptrStu1).name);
printf("Name using ptrStu1 and -> : %s\n", ptrStu1->name);

/* Output */
Name without using ptrStu1: Alex
Name using ptrStu1 and *: Alex
Name using ptrStu1 and ->: Alex
``````

Similarly, we can access and modify other members as well. Note that the brackets are necessary while using `*` since the dot operator(`.`) has higher precedence over `*`.

#### Array Of Structure

We can create an array of type `struct student` and use a pointer to access the elements and their members.

``````struct student stu;

/* Pointer to the first element (structure) of the array */
struct student *ptrStu_type1 = stu;

/* Pointer to an array of 10 struct student */
struct student (*ptrStu_type2) = &stu;
``````

Note that `ptrStu_type1` is a pointer to `stu` whereas `ptrStu_type2` is a pointer to the whole array of 10 `struct student`. Adding 1 to `ptrStu_type1` would point to `stu`.

We can use `ptrStu_type1` with a loop to traverse through the elements and their members.

``````for( int i = 0; i <  10; i++)
printf("%s, %d\n", ( ptrStu_type1 + i)->name, ( ptrStu_type1 + i)->roll);
``````

### 2. Functions

#### Function as a Member

Functions can not be a member of a structure. However, using function pointers, we can call functions using `.` (dot operator). However, it is not recommended.

`````` struct example
{
int i;
void (*ptrMessage)(int i);

};

void message(int);

void message(int i)
{
printf("Hello, I'm a member of a structure. This structure also has an integer with value %d", i);
}

void main()
{
struct example eg1 = {6, message};
eg1.ptrMessage(eg1.i);
}
``````

We have declared two members, an `int`eger `i` and a function pointer `ptrMessage` inside `struct example`. The function pointer points to a function that takes an `int`eger and returns `void`.

`message` is one such function. We initialized `eg1` with `6` and `message`. Then we use `.` to call the function using `ptrMessage` and pass `eg1.i`.

#### Structure as a Function Argument

Like variables, we can pass individual structure members as arguments.

``````#include <stdio.h>

struct student {
char name;
int roll;
char gender;
int marks;
};

void display(char a[], int b, char c, int marks[])
{
printf("Name: %s\n", a);
printf("Roll: %d\n", b);
printf("Gender: %c\n", c);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,marks[i]);
}
void main()
{
struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}};
display(stu1.name, stu1.roll, stu1.gender, stu1.marks);
}

/* Output */
Name: Alex
Roll: 43
Gender: M
Marks in 0th subject: 76
Marks in 1th subject: 98
Marks in 2th subject: 68
Marks in 3th subject: 87
Marks in 4th subject: 93
``````

Note that the structure `struct student` is declared outside `main()`, at the very top. This is to ensure that it is available globally and `display()` can use it.

If the structure is defined inside `main()`, its scope will be limited to `main()`.

Passing structure members are not efficient when they are in large no. Then structure variables can be passed to a function.

``````void display(struct student a)
{
printf("Name: %s\n", a.name);
printf("Roll: %d\n", a.roll);
printf("Gender: %c\n", a.gender);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,a.marks[i]);
}
void main()
{
struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}};
display(stu1);
}
``````

If the size of the structure is large, then passing a copy of it won't be very efficient. We could pass a structure pointer to a function. In this case, the address of the structure is passed as an actual argument.

``````void display(struct student *p)
{
printf("Name: %s\n", p->name);
printf("Roll: %d\n", p->roll);
printf("Gender: %c\n", p->gender);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,p->marks[i]);
}
void main()
{
struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}};
struct student *ptrStu1 = &stu1;
display(ptrStu1);
}
``````

Passing an array of structure to a function is similar to passing an array of any type to a function. The name of the array, which is the base address of the array of the structure is passed to the function.

``````void display(struct student *p)
{
for( int j = 0; j < 10; j++)
{
printf("Name: %s\n", (p+j)->name);
printf("Roll: %d\n", (p+j)->roll);
printf("Gender: %c\n", (p+j)->gender);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,(p+j)->marks[i]);
}
}

void main()
{
struct student stu1;
display(stu1);
}
``````

#### Structure as a Function Return

We can return a structure variable, just like any other variable.

``````#include <stdio.h>

struct student {
char name;
int roll;
char gender;
int marks;
};

struct student increaseBy5(struct student p)
{
for( int i =0; i < 5; i++)
if(p.marks[i] + 5 <= 100)
{
p.marks[i]+=5;
}
return p;
}

void main()
{
struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}};
stu1 = increaseBy5(stu1);

printf("Name: %s\n", stu1.name);
printf("Roll: %d\n", stu1.roll);
printf("Gender: %c\n", stu1.gender);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,stu1.marks[i]);
}

/* Output */
Name: Alex
Roll: 43
Gender: M
Marks in 0th subject: 81
Marks in 1th subject: 98
Marks in 2th subject: 73
Marks in 3th subject: 92
Marks in 4th subject: 98
``````

The function `increaseBy5()` increase the marks by 5 for subjects in which after increasing marks is less than or equal to 100. Note that the return type is a structure variable of type `struct student`.

While returning a structure member the return type has to be that of the member.

A structure pointer can also be returned by a function.

``````#include <stdio.h>
#include <stdlib.h>

struct rectangle {
int length;
};

struct rectangle* function(int length, int breadth)
{
struct rectangle *p  = (struct rectangle *)malloc(sizeof(struct rectangle));
p->length = length;
return p;
}

void main()
{
struct rectangle *rectangle1 = function(5,4);
printf("Length of rectangle = %d units\n", rectangle1->length);
printf("Area of rectangle = %d square units\n", rectangle1->length * rectangle1->breadth);
}

/* Output */
Length of rectangle = 5 units
Breadth of rectangle = 4 units
Area of rectangle = 20 square units
``````

Notice we have allocated the memory of size `struct rectangle` dynamically using `malloc()`. Since it returns a void pointer, we have to typecast it to a `struct rectangle` pointer.

### 3. Self-Referential Structure

We discussed that pointers can be a member of a structure too. What if the pointer is a structure pointer? The structure pointer can either be of same type as the structure or different.

Self-referential structures are those which have structure pointer(s) of the same type as their member(s).

``````struct student {
char name;
int roll;
char gender;
int marks;
struct student *next;
};
``````

This is a self-referential structure where `next` is a `struct student` type structure pointer. We will now create two structure variables `stu1` and `stu2` and initialize them with values. We will then store the address of `stu2` in `next` member of `stu1`.

``````void main()
{
struct student stu1 = {"Alex", 43, 'M', {76, 98, 68, 87, 93}, NULL};
struct student stu2 = { "Max", 33, 'M', {87, 84, 82, 96, 78}, NULL};
stu1.next = &stu2;
}
`````` We can now access the members of `stu2` using `stu1` and `next`.

``````void main()
{
printf("Name: %s\n", stu1.next->name);
printf("Roll: %d\n", stu1.next->roll);
printf("Gender: %c\n", stu1.next->gender);

for(int i = 0; i < 5; i++)
printf("Marks in %dth subject: %d\n",i,stu1.next->marks[i]);
}

/* Output */
Name: Max
Roll: 33
Gender: M
Marks in 0th subject: 87
Marks in 1th subject: 84
Marks in 2th subject: 82
Marks in 3th subject: 96
Marks in 4th subject: 78
``````

Suppose we want a different structure variable after `stu1`, that is insert another structure variable between `stu1` and `stu2`. This can be done easily.

``````void main()
{
struct student stu3 = { "Gasly", 23, 'M', {83, 64, 88, 79, 91}, NULL};
st1.next = &stu3;
stu3.next = &stu2;
}
`````` Now `stu1.next` stores the address of `stu3`. And `stu3.next` has the address of `stu2`. We can now access all three structures using `stu1`.

``````    printf("Roll Of %s: %d\n", stu1.next->name, stu1.next->roll);
printf("Gender Of %s: %c\n", stu1.next->next->name, stu1.next->next->gender);

/* Output */
Roll Of Gasly: 23
Gender Of Max: M
``````

Notice how we have formed a link between `stu1`, `stu3` and `stu2` using structure pointers. What we have discussed here forms the starting point of Linked List.

Self-Referential Structures are very useful in creating data structures such as linked list, stacks, queues, graphs etc.   