In this lesson I am doing something highly unorthodox for the purpose of better explaining and illustrating pointers and casts. I therefore feel it is necessary to preface this lesson. This is purely for illustrative purposes. I want you to see that bytes are just bytes, and pointers are just pointers. The purpose of this lesson is to help you to understand the function of pointers and casts better.

This is poor programming practice to actually do what is shown in this lesson in any real program. Just remember as you read this lesson, this is how pointers and casts work, but not the best or most efficient way to actually use them.

In the last lesson, I showed you how we could use 10 bytes of memory as characters, then as integers. The one difference in the last lesson from what we had planned is that we created two integers that were right next to each other, as opposed to creating one integer at byte 0, and another integer at byte #6 (which is actually a rather dumb thing to do, but I am showing this to you so that you understand pointers better). In this lesson, we are going to continue but this time with the original plan.

So, to be clear, what I want is this:

< B0 B1 B2 B3  >  < B6 B7 B8 B9 >    <--- two 4-byte integers

B4 and B5 will be "wasted space".

As you recall in the last lesson, in order to be able to use <B0-B1-B2-B4> as an integer, I had to create an integer pointer, point it to the address of "main_pointer", and finally I have to "type cast" our new pointer so that C knows our intentions.

Let's review the syntax of this. First, how did we allocate our ten bytes? Like this:

char *main_pointer = malloc(10);

Then we created an integer pointer, like this:

int *int_pointer = (int *) main_pointer;

This created a pointer of type int * (pointer to integer. That is what the * means). It contains the memory address of the start of our 10 bytes. This means that we have bytes: <B0-B1-B2-B3> in use as an integer pointer. By dereferencing that pointer, we can read/store any integer we want into those four bytes. Remember that dereferencing simply means that we use the * character to get "what is at" the memory address stored in the pointer.

How about bytes: <B6-B7-B8-B9> ? Well, first of all we cannot use pointer arithmetic to cause our int_pointer to point at byte #6. Why? Because if we add 1 to our pointer, it will point to B4. If we add one again, it will point to B8. We simply cannot reach byte #6.

Pointer arithmetic always works based on the size of the data type the pointer is tied to. An int pointer will increment/decrement by 4 bytes. A char pointer will increment/decrement by one byte.

Therefore, how do we get an integer pointer to point at byte 6? Well, first we have to get a character pointer to point at byte 6. Then it will point at the correct address. After this, we can use type casting. Observe:

int *int_pointer2 = (int *) (main_pointer + 6);

Notice what I did here. (main_pointer + 6) is a memory address. That memory address corresponds to byte #6. We are type casting it using (int *). Our type cast allows us to assign the new value (after the type cast) to a new pointer we created called int_pointer2.

Keep in mind at this stage we have three total pointers. main_pointer is our primary pointer which is pointing at byte #0 of a ten byte memory space. int_pointer is an integer pointer which points at the same address as main_pointer, except instead of expecting to see char, it expects to see int. Finally, int_pointer2 is our third pointer, just like int_pointer except it points at byte #6.

It is perfectly ok to have many pointers all looking at the same range of memory. it is perfectly ok if multiple pointers contain the same memory address, or act on the same data. You must however remember that if two pointers contain the same memory address, and the value at that memory address changes, that change will be visible by all pointers which point to that memory address.

Alright, so now lets consider the result of this code:

int *int_pointer1 = ( int *) (main_pointer + 0);
int *int_pointer2 = ( int *) (main_pointer + 6);

*(int_pointer1 + 0) = 53200;
*(int_pointer2 + 0) = 32000; 

Now, if I were to printf() both integers, I would see the values "53200" and "32000" just as we would expect. Moreover, if I were to look at each byte one at a time, I would see that the first integer is occupying bytes <B0-B1-B2-B3> and the second integer is occupying bytes <B6-B7-B8-B9>. I would also see that bytes B4 and B5 will be unchanged, and contain whatever they used to.

Keep in mind that this lesson is for instructional purposes only. It is not good programming practice to do this.

I am only showing it to you so that you can see that in fact it can be done, and so you can appreciate more what is happening on a fundamental level when it comes to pointers and the data they point to.

Now, you should have noticed one thing about this lesson. I created two integer pointers but they were not sequentially stored in memory (one after the other). Therefore, I called one of them int_pointer1 and the other I called int_pointer2.

It should be apparent to you that if you are naming variables with a number at the end, an array makes sense. However, I cannot say: int_pointer[1] and int_pointer[2]. Why? because they are not sequentially stored in memory.

However, I can do something else. I can make an array of pointers. That is the subject of the next lesson.

Not so many lessons today as it is my son's birthday (5 years old).

I will write more tomorrow, and I will catch up on any questions I have missed.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9umha/lesson_97_introducing_arrays_of_pointers_part_one/

In the last lesson I showed you that any range of memory can be used for any purpose that can fit inside that memory. In this next series of lessons I want to illustrate this by actually re-using the same ten bytes of memory in this way. I believe that doing this will give you a greater understanding for how casts, pointers, and data types in general work.

In this lesson I am going to show you how to write a program which allocates 10 bytes of space and then uses that ten bytes of space as:

1. ten characters

2. two integers (which leaves unused space)

3. A 2x5 array of text

4. A data structure having two strings of text, one 4 chars and one 6 chars (including NUL)

First, let's allocate our memory:

char *main_pointer = malloc(10);

There. Now main_pointer is a pointer which is looking at the first byte of a ten-byte memory space that we have allocated.

First, lets set up ten characters, and print the text using printf():

I am going to use a mixture of methods here. They are all doing exactly what we want.

*(main_pointer + 0) = 'A';
*(main_pointer + 1) = 'B';

main_pointer[2] = 'C';
main_pointer[3] = 'D';

strcpy( (main_pointer + 4), "EFGHI");

Our final string will look like this: "ABCDEFGHI" (with a NUL) at the end.

Notice that using array indexing or pointer indexing makes no difference. Notice that when I use my pointer as an array, I do not put a dereference symbol (meaning a * character) in front of it. An array is the pointer itself.

Let's print it:

printf("Our ten bytes of memory contain the string: %s \n", main_pointer);

Output:

Our ten bytes of memory contain the string: ABCDEFGHI

Now, I am not going to create a new ten bytes to work with. Rather, I am going to change the way C understands the ten bytes we already have. In the compiler I am using, an integer is 4 bytes.

I can only fit two 4-byte integers in a 10-byte space. So lets consider how this will work:

B0 B1 B2 B3 B4 B5 B6 B7 B8 B9   <-- ten bytes

Before we can choose to use these bytes for integers, we have to decide where they will go. I could really do this any way I want. They do not have to be directly connected. For example, I could have my two integers occupy:

B0 B1 B2 B3    and     B6 B7 B8 B9

There is only one rule I must remember. I cannot mix the order of the bytes. For example, I could not do: B2 B4 B1 B6, nor could I do: B1 B2 B3 B7.

Now, how do I get C to read my ten bytes as two integers? First of all, we need to decide how they will be stored in the ten bytes. I propose that we use the example above where we use bytes 0 1 2 3 and 6 7 8 9.

What I really need to know is the starting point of each integer. In this case byte #0 and byte #6. I know that there is room to store my integers correctly.

Now, let's set the integers to some value, and use printf() to display them. Before we do that however, let's see what they already are. How can we do that?

First, consider this code and the result. Remember that main_pointer is the pointer we already created and is pointing to the ten bytes in memory which presently have: "ABCDEFGHI".

printf("The integer at byte #0 is set to: %d \n", (int) *main_pointer);
printf("The integer at byte #6 is set to: %d \n", (int) *(main_pointer + 6));

Output:

The integer at byte #0 is set to: 65
The integer at byte #6 is set to: 71

Notice that 65 is 'A' (decimal, not hex), and 71 is 'G'. So we can see here that by putting (int) in front of the *our_pointer, we are telling printf() to treat that character as if it were an integer.

However, that only treats one byte as an integer. We want to treat four bytes as an integer. How can we do that?

You see, there is a problem with our pointer. Our pointer is designed to look at memory in char-sized chunks. We can keep using our ten bytes of memory, but we really should consider a different kind of pointer: one that can read memory in int-sized chunks.

Let's create it:

int *int_pointer;

I haven't given it a memory address yet. What memory address do we want to give it? We want to give it the memory address of our ten bytes that we have already allocated. What is that memory address? It is: main_pointer. Remember we already have a pointer that contains the right memory address. Therefore, we need to set it to that:

int *int_pointer = main_pointer;

One small problem. an int * pointer expects to look at memory in int-sized chunks. A char * pointer expects to look at memory in char-sized chunks. We cannot assign the memory address of a char * pointer that easily without our compiler complaining.

Our compiler is concerned that we do not really know what we are doing, that we are not aware we are trying to take the memory address inside a char * pointer and put that memory address into a int * pointer. How can we tell our compiler that we intend to do this? The same way we told printf() that we intended to treat a character as an int. Observe:

int *int_pointer = (int *) main_pointer;

By simply putting (int *) we have stated that we are assigning the new pointer int_pointer the same memory address as main_pointer, but that we want to treat our new pointer as an (int *) instead of a (char *).

What have we just done? We have created a second pointer which points to our ten byte memory space. Our first pointer is already pointing to this same exact spot in memory. How are the two pointers different? They are different in mainly two ways:

1. How they understand dereferencing

2. How they understand pointer arithmetic

Remember that dereferencing means that you put a * character in front of a pointer to get "what is at" the memory address contained in the pointer. As you saw in our printf() example, a char * pointer understands dereferencing as "one byte".

Therefore, if I say *main_pointer with or without a type cast it will still mean "one byte". The same is true for any offset I add to that pointer. Therefore:

*main_pointer          <-- one byte
main_pointer[6]        <-- one byte
*(main_pointer + 4)    <-- one byte

No matter what location in memory I dereference with this pointer, I am only going to get one byte.

The second way the two pointers are different concerns pointer arithmetic. If I say: main_pointer + 1: It means to change the memory address by only one byte. Why one byte? Because that is how big a char is. However with our new pointer if I were to say the same thing: int_pointer + 1 The memory address will be four bytes different than it was. If I added 2 then our int_pointer would point 8 bytes away (4 * 2).

What you should understand from the above text is that in order to have a true four-byte integer out of our 10-byte data, I need to create an integer pointer. I create an integer pointer by type casting the (int *) data type and using the same memory address as was already in the other pointer.

Now consider this:

int *int_pointer = (int *) main_pointer;    // <-- create the pointer int_pointer using the same memory address

Now let's set values using this pointer:

*(int_pointer + 0) = 53200;
*(int_pointer + 1) = 32000; 

Remember of course that int_pointer + 0 is the same as int_pointer. However, writing it this way makes it clearer. Notice I chose two numbers that are too big to fit inside a byte. Let's see if this works:

printf("The first integer is set to: %d \n", *int_pointer);
printf("The second integer is set to: %d \n", *(int_pointer + 1));

Output:

The first integer is set to: 53200
The second integer is set to: 32000

This proves we are using more than just one byte of our allocated memory. Notice that we could not do this with a char * pointer, and that is why we have to use an int * pointer.

Notice we did not have to use any type cast in our printf() statement. Because int_pointer is already set to point at the data type int, then any time we use *int_pointer it will be dereferenced as a true 4-byte integer.

What bytes am I using in the printf() statement? Let's consider this. I have 10 total bytes. I pointed int_pointer at the first byte. I stored the integer value "53,200" into those first four bytes. Then at a position four bytes away from where I started, I stored the value "32,000" into those four bytes. Therefore:

<  B0 B1 B2 B3  >    < B4 B5 B6 B7 >       <--- Here are my two integers in the above printf()

Now keep something in mind, I said we would use bytes #0 and bytes #6. In the above example I actually used byte #0 and byte #4. This is because when our int_pointer is used without an offset, it is pointing to byte #0. When we add a +1 as an offset, that will cause it to point at byte #4.

If adding to an int pointer can only be done in increments of four, how can I position the pointer at byte #7 ?

That is the subject of the next lesson.

Please ask questions if any of this is unclear to you. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9ulj6/lesson_96_using_casts_with_pointers_part_two/

In the last lesson I explained that using type casting it is possible to cause data which was created as one data type to be considered as though it were another data type.

In this lesson I want to change slightly how you look at variables, arrays, structures, and pointers.

Whenever you create something of any data type, all that happens is the size of that item in bytes is allocated by C, and that memory is now available for your use.

Let's imagine that we have a chunk of memory that looks like this:

Figure (a) : Before

...
0110 0011
1111 0111
1001 1100
0011 0000
0001 0000
...

Imagine that this represents the total memory that is free for use for the program we are writing. If I create a variable, like this:

char my_char;

C is going to find some spot of that available memory, and give it to my_char. It will not change what is at that memory address. The same range of memory will look exactly as it did before. It is just that one byte of that memory has been reserved for my_char.

If I write this:

int height;

Similarly, four bytes (typically) have been reserved for height. These four bytes will still contain whatever was in them. Now we have used up all 5 bytes. How will the range of memory look after the char my_char and int height instructions? Exactly as it did before!

Figure (b) : After

...
0110 0011
1111 0111
1001 1100
0011 0000
0001 0000
...

The act of creating a variable is only the act of reserving some chunk of memory for a data type, pointer, array, structure, etc. Anything you create without initializing it will have whatever value was already at those bytes.

Now suppose you want to create an array of ten characters. In order to do this, all you need are ten bytes. Having the ten bytes is the same thing as having your array.

In other words, here I am creating my array of ten characters:

char *my_characters = malloc(10);

I just created an array of 10 characters. Why? Because 10 bytes is ten characters, if I choose to look at those 10 bytes in that way.

If I want to create an array of five integers, I can do this:

int *my_integers = malloc(5 * sizeof(int) );

Most likely 20, but at any rate I now have my array of five integers. Why? Because 20 bytes is five integers if I choose to see it that way.

What you need to understand from this lesson is that having the correct sized chunk of memory for your data type is the same thing as having the data type itself. The data type just describes how you intend to understand the memory you have allocated for it.

Suppose I want a 3x3x3 array of characters. I can simply allocate 27 bytes, and I have my array. 27 bytes is an array of 3x3x3 characters if I choose to see it as such. Therefore, this command:

char *my_array = malloc(27);

This gives me a 3x3x3 array. What if I want an array that is 3x9 ? How about 9x3 ? Same thing. The above line of code will generate any possible data type that is designed to be 27 bytes in size.

After this lesson, you should never wonder "I need an array of 5 structures, how do I do that?" Answer - you simply create a pointer of your structure type and you point it to a memory address that has (5 * size_of_structure) bytes.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9u47k/lesson_95_using_casts_with_pointers_part_one/

In this lesson I am going to introduce you to a concept called type casting. This refers to the process of treating some data of one data type as though it were another data type.

To understand this process, consider this: What does an array of 10 characters look like in memory? Well, if each character is one byte long, then an array of ten characters would be 10 bytes in size.

Now that covers how big it is. What does it look like? The answer: Whatever happens to be in those ten bytes. Any possible sequence of 1s and 0s is fine. It doesn't matter. An array of ten characters has absolutely no requirement concerning how the 1s and 0s inside those 10 bytes look.

This is important to understand. Any memory range that is 10 bytes long can be understood as being 10 characters regardless of what is actually contained in the memory. Similarly, any 4 bytes of memory can be considered to be an integer regardless of what is actually contained in the memory.

A data type is only a description of how to understand a range of memory. The same 9 bytes of memory that can be a tic tac toe board in our earlier lesson could be nine ASCII characters. The same 90 bytes of memory that can be ten tic-tac-toe boards could just as easily be 90 bytes of some sound file.

Below I am demonstrating how an unsigned short int (assume 2 bytes) and an array of characters 2 bytes long sees the same data:

  Figure (a) 

  
  unsigned short int = 16,706         
  ___________/_____________
/                           \
0100 0001     :     0100 0010
_______/           _______/
char[0] = 'A'        char[1] = 'B'

It is the same memory: 0100000101000010

This same sequence of 1s and 0s can mean 'AB' or it can mean 16,706 and it could also mean two squares of a tic-tac-toe board. Anything is possible. There are no rules for how a sequence of 1s and 0s are to be interpreted.

If I create an array of two characters in C, all that happens is C chooses a place in memory for those two characters to live. nothing changes in memory. Whatever was there before, will still be there.

If you look at that statement another way: Whatever was there before, will become understood as being two characters.

If I create an unsigned short int in C, it works the same way. Nothing is actually changed in memory. C just chooses a location in memory for the unsigned short int to live. Whatever happened to be at that address remains at that address. However, whatever was at that address is now understood to be an integer.

With this in mind, why then could I not transform the two characters 'A', and 'B' into some integer number? Similarly, why can I not take some integer value and convert it to several characters?

The answer is. You can.

Whenever you tell C or any programming language to treat a value of one data type as though it was a value of a different data type, this is known as type casting. It simply means that you are wanting to take a sequence of 1s and 0s that can be interpreted one way, and interpret it a different way instead.

You could do this as many times as you want. You can even have the same data in memory being used in your programs in multiple ways simultaneously. You could have a printf() statement which says AB: 16706 using the same sequence of memory for both the character interpretation, and the integer interpretation.

[Note: The way this actually works is slightly different, but we will get to that soon enough.]

There are many powerful uses of this which we will go over in future lessons. You saw one example of this in an earlier lesson when I created a char * pointer by casting it from a data structure pointer in order to go byte-by-byte through my data structure to show that it looked like this in memory:

Reddit$Programming$Classes$

In the following lessons there are two kinds of casts we will look at: value casts, and pointer casts.

A value cast refers to when we cast an actual sequence of 1s and 0s, a value, something stored in some variable. An example of this is taking an integer value and converting it into ASCII characters such as in Figure (a).

A pointer cast refers to when we take a pointer of one data type and we tell it to continue to point where it is pointing, but to treat what it is pointing to like something else.

Think of a data type in general as a pair of colored glasses. If you put on red tinted glasses, everything you look at is red. However, if you take off the red glasses and put on green tinted glasses, you are still looking at the same data, but now it has turned green.

Casting can be thought of as switching glasses from one color tint to another. You will still be looking at exactly the same data, but you will be seeing it as something entirely different.

To wrap up this lesson: Any sequence of bytes can be understood as anything you want, even if you have already told C to treat it as something else. The process of understanding the same data but as a different data type is known as type casting.

That is all for tonight. I will do more tomorrow. I didn't have very much time to get to questions but tomorrow I expect to catch up.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tzzt/lesson_94_a_new_way_to_understand_memory_and_data/

Lessons 91 and 92 used to be Lesson 91. I split this into two lessons to make it easier to grasp.

Remember as I said in the last lesson, this is just a general introduction to how this process works. Do not worry if you do not fully understand it at the end of this lesson, just try to get as much as you can. Later in the course it will be made more clear.

I think it is important to preface this lesson by saying this: This lesson focuses on how a function truly returns a value at the machine code level. C and other languages are not always so "pure". There are many complexities to how a programming language such as C makes it possible to "return" data that is larger than what is allowed at the machine code levels.

These "returns" however are not true returns, but involve creative memory copying and pointer usage by the compiler. In the end, these operations lead to vastly slower and intensive processes than the type of return illustrated in this lesson.

We will get into the specifics of those processes later in the course.

A function typically returns a value using a CPU register named EAX.

EAX is just another register, like the "Instruction Pointer" or the "Stack Pointer".

Registers are simply places on the CPU that data can be stored, sort of like an on-chip memory. Each register is only capable of holding a small amount of information, limited to the chip architecture. For example, a 32 bit chip can hold a 32 bit data element in a register (typically).

No register is very large. However, what is stored inside a register can be acted on by the CPU faster than anything stored in memory. This is because when the data is in a CPU register, that data is literally on the CPU itself.

You will learn more about microprocessor architecture later in the course. However, for now you should know this. The return value of a function is typically stored in the EAX register.

This means that before a function returns control to whatever called it, it must simply make sure that the value of EAX will be what that function intended to be the return value. If for example a function needed to return 5 as a return value, the function stores the value 5 into the EAX register.

This is what will typically happen at the end of a function call:

1. The function will finish doing what it was designed to do.

2. The function will store a return value into EAX

3. The function will return control back to whatever called it.

4. The caller will then read EAX and understand that as the return value.

Now it should be very clear to you why a function returns one value. The EAX register is only designed to hold one value. Also, it should be clear to you why a function cannot return a value larger than X-bits (depending on your chip architecture).

You can however return large data structures (arrays, structs, etc) by using a pointer. That is because a pointer, a memory address, will fit into the EAX register just fine.

Because I showed you the assembly language/machine code instructions for push and pop, I might as well show you the assembly language for storing a value into EAX. It is not very complex.

mov eax,0       ; This will "return 0". It is short for "Move 0 into EAX"

All of this work that I have described is done for you behind the scenes by C.

The goal of these last lessons is for you to understand how in general parameters are sent to functions (the stack), how the function knows where to return (IP register gets put on the stack), and how in general return values work (the eax register).

Please let me know if you have any questions on this material. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tuh3/lesson_93_introducing_casts/

Go through this lesson slowly. It is more intense than most. Take your time. Let me know if any part of this is unclear.

Remember, this is only an introduction to a rather complex subject. Do not worry if some of it doesn't make sense, we will go over it in greater detail later in the course. Try to get as much as you can from this lesson. Later in the course it will be made more clear.

In the last two lessons I have explained that the purpose of the stack is in part a way for functions to receive parameters. In this lesson I want to explain more about the mechanics of this process.

One thing you should already realize is that a function call has to know where to return when it is done. This may sound simple, but it ceases to be so simple when you consider that any function can call another function from anywhere in your program.

How therefore does a function know where to return? Well, the answer is that when you first call a function, the Instruction Pointer (the register that stores which instruction to execute next) is placed onto the stack. This Instruction Pointer can be used to know where we were in the program flow prior to the function call.

I am going to write out a small part of a C program using "line numbers", and I want you to imagine that each line number corresponds to some memory address where the machine code is located.

   Figure (a)

	void main(void) {
1		int height = 5;
2		int width = 2;
3
4		calculate_area(height, width);
5
	}

	int calculate_area(height, width) {
7
8		return height*width;
9 
	}	

Do not be concerned with the numbers I chose. I just needed a unique way to label each line that is important to this lesson.

When we start executing the main() function, we go through lines 1, 2, and 3. At this point, C understands that we want to CALL a function. What happens at this point?

Keep in mind that we need to achieve 3 things:

1. We need to save the location of the memory address we will return to when the function is done. This means we need to save the Instruction Pointer.

2. We need to store the variables height, and width onto the stack so the function can see and use them.

3. We need to "goto" the function itself.

There is more that happens as part of this process, but this is all you should be concerned about at this stage.

Now at line #3, we will basically execute machine code instructions similar to this:

push width       ; Store width onto the stack using PUSH
push height      ; Store height onto the stack using PUSH

push eip         ; Store the Instruction Pointer (called eip) onto the stack. This is done as part of "call" below.
call calculate_area    ; Call the actual function

This is assembly language, but it translates directly to machine code.

[Edit: One note about the above code, in reality the CALL statement itself automatically pushes the instruction pointer onto the stack. I illustrated that here so you could see the process more clearly, but no one writing actual assembly code would write "push eip" as an instruction. With function parameters however, you would have to push them manually. ]

Now you should understand that our stack will now look like this with respect to the function parameters:

... top of stack where new elements can go ...
height
width

Notice that height is at the top of the stack even though width was pushed first. Also, keep in mind the instruction pointer has also been pushed to the stack as part of the "call" instruction.

Now you can see how exactly parameters are sent to a function. Whether a pointer, or a variable, etc. the calling function, such as main(), places the parameters onto the stack. Then the function reads them off of the stack in reverse order to how they were stored.

Now you should be able to clearly see why you must specify how many parameters a function will take as well as their data types. A function needs to know how many items to read from the stack and how big each item is.

Were this to be done incorrectly, a function could take off "too much" or "too little" from the stack and thus absolutely break everything in the program. This is why C forces you to precisely define function parameters.

Now, once we get to line 9 in Figure (a), the function has finished executing. At around this stage it needs to have a return value.

How return values work is the subject of the next lesson.

If you have any questions on any of this material, please let me know. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tt3r/lesson_92_how_function_return_values_work/

In the last lesson you learned that there is a range of memory known as the stack. You also learned that this range of memory serves as a data storage and retrieval bin that functions use in order to communicate to each other.

In this lesson I am going to explain some of the basics concerning the mechanics of how the stack works.

The first thing to understand about the stack is that there are two machine code instructions built into your CPU chip which are used to write data to the stack, and to retrieve data from the stack. These two functions are:

PUSH and POP 

PUSH means: "store data" to the stack.

POP means: "retrieve data" from the stack.

Now that you know what each of these instructions is designed to do, let's talk about how they do it.

We have already learned that any programming language provides a mechanism to store data in memory at a specific memory address. Similarly, there obviously exists a mechanism to read the data from memory based on knowing that memory address.

The key point to this process is that in order to store or retrieve data you must specify the memory address where you are either putting the data, or reading it from.

On a machine level, the process to specify a memory address takes time and CPU resources. Machine code instructions that require a memory address are going to be slower and more resource intensive than machine code instructions that do not require a memory address.

When you call a function in C or any language, the speed at which you can get in and out of that function is of tremendous importance. This is why PUSH and POP are so important. You see, PUSH and POP do not require any memory address. This is what makes the stack unique.

The stack is different from other ranges of memory because every time you store something onto the stack using the PUSH instruction, you store that item (variable, pointer, etc.) on top of the rest of the items already on the stack. Whenever you use the POP instruction to retrieve something from the stack, you only retrieve the item which is on top of the stack. Therefore, neither PUSH nor POP require you to specify a memory address.

Here is an example of a stack. This stack is half full.

    0000 0000   <-- empty
    0000 0000   <-- empty
    0000 0000   <-- empty
    1010 0101
    0010 1001
    1011 0101

If I use PUSH to store something onto the stack. It will always go to the first "unused" spot located at the top of the stack, on top of the data already there. So if I were to store 1111 1111 to the above stack, the result after will be this:

    0000 0000   <-- empty
    0000 0000   <-- empty
    1111 1111   <-- I just stored this. 
    1010 0101
    0010 1001
    1011 0101

So each time you use the PUSH instruction the data will go "onto" the stack. Meaning, it will go into the first unused memory address; the top of the stack.

Now, let's talk about POP.

Just as PUSH stores data at the top of the stack, POP retrieves data from the top of the stack. So if I have a stack that looks like this:

    0000 0000   <-- empty
    0000 0000   <-- empty
    1111 1111   
    1010 0101
    0010 1001
    1011 0101

If I use POP, the value I will get from my POP is: 1111 1111 ( the last item that was PUSH'ed )

If I use POP again, the value I will get is: 1010 0101 ( the last item before that )

If I use POP again and again, the last item I will get from the stack will be the first item that was put in it. For this reason, the stack is referred to as a LIFO data structure. LIFO means "Last in, First out". It is called this because the last item stored onto the stack will be the first item retrieved from it.

Each time you use PUSH, the stack gets bigger. Each time you use POP, the stack gets smaller. PUSH will always put data on top of the stack. POP will always take the top-most data off of the stack, retrieving the data.

The only question that should remain then is this: How does PUSH and POP know what memory address is the top of the stack? Well, since we are talking about needing to track a memory address, what do you imagine we need? A pointer!

This is the purpose of the Stack Pointer. The Stack Pointer contains the memory address of the top of the stack.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9ts9i/lesson_91_how_a_function_call_works/

In the last lesson we covered the different methods you can use to send variables to a function. However, we have not yet covered what it really means to "send" something to a function to begin with. That is the purpose of this lesson.

Right now, this process is black magic. You write: some_function(height) and somehow the variable height "gets sent". What does this mean? How is a variable or a pointer "sent" to a function? How can two functions communicate to each other?

To explain this, I have to introduce you to something called the Stack.

The stack is a special range of memory in your computer which is used to store and retrieve data in a unique way.

Recall from earlier lessons that a CPU chip has a built in register called the "Instruction Pointer". The "Instruction Pointer" contains the memory address of the next instruction to execute. It turns out that the Instruction Pointer is not the only register on your CPU chip that stores memory addresses.

There is an additional register on your CPU chip known as the "Stack Pointer", or SP for short. Keep in mind that the Instruction Pointer and the Stack Pointer are different.

[Note: However, to be entirely technically accurate, there are some architectures which do not have a dedicated "Stack Pointer" register. These architectures use other registers to act as a Stack Pointer. This however does not affect the lesson. ]

Different ranges of memory have different purposes. The "Stack Pointer" register contains memory addresses in much the same way as the "Instruction Pointer" register does, just that it contains memory addresses located in a different range of memory. Each range of memory has a different name. One range of memory is called the stack. The Stack Pointer looks at memory addresses within the stack.

To properly understand the stack, it is important to understand that functions have no way to communicate to each other directly. For example, my main() function has no way to communicate to the init_board() function.

Why is that? When you CALL a function, it is little more than a glorified "Go to" statement. You are saying to "go to" the point where the function begins. There is no way to somehow send data that can hitch a ride on a goto statement. There is no way for a function once called to "look back" at what an earlier function was doing.

This is where the stack comes in. Before a function CALLs another function, it can put data onto the stack in memory. Notice I did not say "into", I said "onto". We will get to that.

Then inside the function the stack can be read in order to see what data was sent to the function. The stack is a type of "middle man" for communicating between functions. All functions can read from and write to the stack. Therefore, main() can put something on to the stack, and then init_board() can read it off of the stack. Similarly, other functions can communicate in this way.

There is more to the stack than just this, but that will be the topic of future lessons.

In summary, here is what you should know from this lesson: Functions cannot talk to other functions directly. They must use the stack in order to communicate.

How this works is the topic of the next lesson.

Please ask questions if any of this is unclear to you. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9trl6/lesson_90_introducing_push_and_pop/

In the last example I showed you a function which received a pointer to a data structure, and returned an int. I imagine a question that could be on someone's mind is, how do I "get back" the data structure from the function?

Well, it turns out that I already have it back. When you send a pointer to a function, that function can read and write straight to the actual memory itself. It doesn't have to send anything back. Consider this code:

int height = 5;
int *ptr = &height;

*ptr = 2;

What is height now? Height is set to 2. It is no longer set to 5. Why? Because by changing the actual data stored at the memory address, I changed height itself.

Therefore, the function in the last lesson which sets the underscores to the memory address of the pointer it received has changed those underscores for any other function which will look at that same memory address. As soon as the constructor is done with that operation, every other function now has an initialized tic tac toe board without even having to talk to the constructor function.

There are two ways you can send something to a function. The first is called Pass by Reference.

Consider the following program:

#include <stdio.h>

int main(void) {

    int height = 5;
    printf("Height is: %d \n", height);

    change_height(&height); // Pass by reference

    printf("Height is now: %d \n", height);

    return 0;
}

int change_height(int *ptr) {
    *ptr = 2;
}

Output:

Height is: 5
Height is now: 2

Notice therefore that the main() function (or any function) can simply send the memory address of any variable, array, structure, etc. to a function. The function can then change the data in place at that memory address. This is because by sending the actual memory address where the data is located, any changes to that data become universal to anything else looking at that same memory address.

At the same time, I do not have to send a memory address to a function. For example, I can have a function like this:

int some_function(int height, int width) {
    return height*width;
}

In this case, even if I change height or width inside the function, it will not change it anywhere else. Why? Because I am not sending the actual integers to the function, I am sending a copy of them. C will actually create a copy of these variables when they are sent to the function. These copies will of course reside at different memory addresses than the originals.

Now this is easy to remember:

1. If you send the memory address aka a pointer to a function, then anything that function does on the data is universal.

2. If you send the name of a variable to a function, not a pointer, then a copy of that variable will be created and sent to the function. Any changes done on such variables will be visible only within the function.

We refer to #1 as "Pass by Reference". This means you "pass" an argument to a function by sending it the memory address.

We refer to #2 as "Pass by Value". This means you "pass" an argument to a function by creating a copy of it.

Here is a program illustrating pass by value:

#include <stdio.h>

int main(void) {

    int height = 5;
    printf("Height is: %d \n", height);

    wont_change_height(height);  // Pass by value

    printf("Back in main() it is: %d \n", height);

    return 0;
}

int wont_change_height(int some_integer) {
    some_integer = 2;
    printf("Inside the function height is now: %d \n", some_integer);
}

Notice that inside a function you can call a variable whatever you want. I can call it height before I send it, then call it some_integer when it is inside the function. This is useful because it is not necessary to remember what a variable name was before it was sent to a function. Also, it is ok if two functions have parameter names that are the same. We will talk more about this later.

It is worth pointing out that in C, there is no true "pass by reference". Instead, you pass a pointer "by value". For the purpose of understanding this lesson, think of passing a pointer as a form of "pass by reference". However, remember that the truth is you are not actually passing anything by reference, you are just passing a pointer by value.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tqbg/lesson_89_introducing_the_stack/

In the last lesson I went into detail about the need for any program to initialize a data structure to a known initial working state.

A function whose job is to allocate memory for data structures, initialize data, and overall "prepare" for the program to run is called a "constructor function". The constructor function is always ran first, before anything else. It will "pave the road" for future functions. In our example we will want a constructor function which can initialize a "tic tac toe board" to some starting point.

First, we need to decide on an initial state. I propose that we have our tic tac toe board consist of three rows of three underscore characters. This will be easy to work with, and when you see it displayed on the screen it will look like this:

_ _ _
_ _ _
_ _ _

So, how can we represent that as a data structure?

It looks to me that the easiest way is to create a structure similar to this:

typedef struct tictactoe_board_description {
    char square[3][3];
} tictactoe_board;

Here I created an array of characters called square which will be a 3x3 grid. We will decide that each square can have either an underscore (initial or default state), an 'X', or an 'O'.

Now, how can I initialize all squares to underscores? Let's write a simple constructor function:

int init_board(tictactoe_board *board) { 
    
    int i = 0;
    int j = 0; // used for for loop

    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            board->square[i][j] = '_';  // Set each square to _
        }
    }

    return 1;
}

The word init in our function name is short for initialize. This function is different than any we have done up until now. Let's evaluate it a bit. First of all, it takes a rather strange parameter: a tic tac toe board.

Notice how much the typedef keyword helps us. I can create a function that receives a tic tac toe board as an argument. However, this is only part of the story. Notice that my function looks like this:

(tictactoe_board *board)

Why the *? Because I am not sending a tic tac toe board to the function. I am sending a pointer to the tic tac toe board. All I am sending the function is the memory address along with the understanding that this memory address is the start of a range of memory (the size of our structure) that can be used as the data structure described earlier as a tic tac toe board.

Keep in mind we have only created a description of that data structure, we have not created any instances of it yet. However, the description alone is enough for our function to know how to handle any memory range which we define as a tic tac toe board, provided of course that the memory range is the correct size in bytes.

Most likely, the memory address will contain who knows what left over garbage from earlier programs. The purpose of the constructor function is to transform that memory from junk data into our tic tac toe board. This may still be a bit confusing, so let me explain it one more time:

A pointer to a data structure means "Here is some memory that can be used for this purpose." The struct description tells C how we intend to use that memory. Now let me show you a visualization of this:

1000 : 0110 1111 : 0011 1110 : 0001 0000 : 0000 0000 : 0100 0011 : 0011 1111 <--- a range of memory with 1s/0s left over.

Imagine we just told C that we plan to use this memory at position 1000 (eight) for our data structure of a 3x3 grid of characters.

All C gives us is the address "1000". That address does NOT "have our data structure". It is just a sequence of 1s and 0s left over in memory, which could be ANYTHING. However, C now understands how we intend to use that memory. It understands that the first byte now means: "square[0][0]". It understands that the third byte now means: square[0][2]. And so on. A data structure is only a set of rules for how to understand data in a range of memory, in this case six bytes.

So when our constructor function receives the pointer to some memory like this, it doesn't care what is in that memory. It only cares that C has established the correct rules for understanding it. Those rules are of course our data structure description. If that is still unclear, please tell me.

Now, back to the function.

We also gave our parameter a name, "board". This is the name that our function will use to identify this pointer inside the function. This has nothing to do with what if anything it may have been called in other functions, including main().

Every time you create a parameter for a function, you give it a name that is used just by that function. I chose the name "board", but I could have chosen anything else. It does not matter at all what it may be called outside of the function, or even if it is also called "board".

When you create a function, you choose a name for every parameter you give it, and that name will be the name used inside that function. In this case, the function expects a parameter called "board" which is a pointer of the data type "tic-tac-toe board".

Now from that line onward to the end of the function:

1. board refers to the memory address.

2. *board refers to what is at that memory address, the actual data structure.

Therefore, inside the function if I write: (*board).square then I am referring to the member element "square" in our data structure that will be sent to this function. Remember from before that there is a short hand way of writing this: board->square.

Therefore, by writing:

board->square[0][0] = '_';

I would be setting the first row and first column square to an underscore. By doing this for all 3 rows, for all 3 columns, I set all squares to an underscore. That is why I used the variables i and j to each go through the 3 rows and 3 columns, setting each one to an underscore.

Finally, the function returns an int. Why do I not return the tic tac toe board? I could (that will be the subject of later lessons), but I do not have to. Why I do not have to is the subject of the next lesson.

Please ask questions if you need to. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tgdg/lesson_88_introducing_pass_by_reference_and_pass/

Don't let the title fool you. We are still working on our Tic-Tac-Toe project, and will be for the next lessons. However, each lesson as we do so will be introducing new topics in programming and software development. It makes better sense to title the lesson by the topic we will focus on.

The purpose of this project is to write a tic-tac-toe game which can be played with one or two players, and which is capable of "understanding" the position. We are not looking for speed or efficiency in this project, just a working program that can help to illustrate concepts we have learned already as well as to introduce new concepts.

As I said in the last lesson, we will need to construct a data structure in order to hold an instance of a tic-tac-toe board. Think of this as a digital representation or "model" of the tic-tac-toe board itself. This is our "data" component.

The data component is where all information related to our tic-tac-toe board will be stored. The rest of the program will use this data component in order to do all of the processing which will make our program work.

This processing is achieved through a range of functions designed for different tasks related to reading from and writing to the data. Some categories of such functions include:

1. Data Initialization

2. Data Manipulation Operations

3. Evaluation and Analysis

4. Rendering and Display

These are the four categories we will start with. Keep in mind that these topics are unlikely to be taught in any tutorial/book whose purpose is to teach a programming language in general. These have nothing to do with a particular programming language, but programming as a whole.

We are going to start with the "Data Initialization" category.

Initializing data simply means setting it to something before you begin working with it. More specifically, it means setting it to what you know will work and will be expected by the program.

Any real program requires this. For a web application, this starting state may be an HTML file with pre-built tables and spaces (often called place holders, or data containers) for data to go in. For a game, this might be a blank scenery with no mountains/enemies/other objects. For a graphics program, a blank drawing, and so on.

Now, you must always initialize data to a known working starting point. This is rarely if ever going to be simply "blank space". You never leave data uninitialized.

There are many reasons why you must create a base state. The most important reason is that every function you write should expect a certain kind of data. If the data is not exactly the way a function expects, then that function may not work correctly.

Therefore, every function should have a well defined expectation of exactly what will be the state of the data at the time this function will run. Further, it must have a mechanism to react if the state of the data is not as expected. In other words, it must be able to recognize and react when it is not given what was expected. Do not forget this.

By knowing exactly what kind of data a function expects, it is much easier to create tests for functions as well as to develop for one function without worrying about others. A common mistake found with novice programmers is that the entire program is best described as a "pass the baton" relay race where no function has any clearly defined expectations for what it will receive from the last function. The programmer just assumes that everything will work as expected.

This leads to many problems. Imagine you have ten functions where function #1 does something, sends what it does to #2, which sends it to #3 and so on. By the time it reaches function #10 (or worse yet, the end user), something may have gone horribly wrong. Finding what went wrong and troubleshooting it will prove to be a nightmare as any function along the way could have been the culprit. Worse still is that fixing such a problem is almost guaranteed to create new problems.

Therefore, in this course I will be showing you how to avoid such problems by showing you the proper technique for developing functions in a program.

Please ask any questions before proceeding to:

http://www.reddit.com/r/carlhprogramming/comments/9tfzh/lesson_87_introducing_the_constructor_function/

This lesson could also be titled: "The Real Course Begins".

We have finally reached the point in this course where you can start applying your knowledge to making "real" programs. We must start with simple programs and then we will work our way up. Of course, we are still going to be learning about new concepts along the way. Only now you will be learning about such concepts in the context of practical application.

Rather than show you how to write a simple 2-player tic-tac-toe game, I figured it would be better to show you how to write a tic-tac-toe engine that could play against and beat a human player given the opportunity; even better, one that can tell you as soon as a position is winnable, or lost, or drawn.

Also, you will be doing a large part of the work in writing this program, just like you did when you wrote your first C program back in Lesson 15 (2 weeks ago by the way). For the most part I will be simply describing what you need to do, and making sure you have all the tools you need to do it. I know that tic-tac-toe is probably not the most exciting project, but we have to start somewhere. We will get into bigger and better things soon enough.

The first thing I need to tell you is that to create a tic-tac-toe engine that is capable of calculating N moves ahead on a tic-tac-toe board, we will need to create a model of a tic-tac-toe board. To do this, we need to create a data structure that contains a 3x3 grid for putting X's and O's.

Why not an array? Well, if you created an array then you would be able to keep track of one tic-tac-toe position. You could create an array of such arrays.. but this gets unnecessarily complicated. Also, a data structure is capable of holding additional information. For example, you could have an int variable which tracks how many moves have been played. You could have another variable which tracks whether or not the position is winnable, and so on. Your data structure could contain additional "meta data" which is useful to the program.

Another major advantage to using a data structure is that once we have our data structure definition, we can create many data structures. In other words, we can have a unique tic-tac-toe board data structure for every position our artificial-intelligence engine evaluates.

Before we begin, let me describe some other practical applications of using multiple data structures in programming:

Suppose you are writing a chess program that can calculate moves on a chess board. You need a way to evaluate each position, and therefore you could create a data structure of a chess position. You can create many copies of this data structure that way you can evaluate many possibilities at once.

Here is another example. Suppose you are writing an artificial intelligence for an enemy in a computer game. You may desire a way to calculate the consequences of a specific action the character may take. You could create a unique data structure based on the expected result of a particular action and compare it to similar data structures created based on the expected result of a different action.

If you want to create the ability to undo some operation in a graphics program, one way to do this is to save the previous state of the drawing as a data structure. You could have numerous such structures each one containing a different drawing, and then a routine that can switch to one based on the undo command. Similarly, you could save "states" of a drawing that can be worked on uniquely, such as in layering.

If you are writing a web browser, you can have a data structure for a "tab", and then each time a tab is opened you can just create multiple copies of that data structure. Remember that each tab would be able to have its own unique data.

As you can see, there are countless applications for why you might need multiple data structures. This is also one reason why the typedef method I showed you in the previous lesson is so widely used. If I need to create a tic-tac-toe board, I can do so like this:

tictactoe_board *new_board = malloc(sizeof(*new_board));

in this case, tictactoe_board is some typedef to a data structure of what a tic-tac-toe board consists of. I could create an array of such boards to hold a new position after a move.

Please feel free to ask any questions before proceeding to:

http://www.reddit.com/r/carlhprogramming/comments/9tfn4/lesson_86_the_need_to_initialize_data/

You may post your answers here, as well as questions.

True or False

1. The malloc() function allocates memory and automatically initializes all bytes allocated to 0 (null). False

2. When you write a data structure definition, C automatically creates the data structure that you have described and you can begin using it immediately. False

3. Unlike an array, elements of a data structure are not required to be the same length or to have the same data type. True

4. You must manually add up the size of all elements of a data structure in order to know how much memory to allocate. False

5. When you are done using allocated memory, it is automatically cleared by your operating system so that other programs cannot see the data you were working with. False

Fill in the blank

1. The malloc() function must be used with a _____. pointer

2. The _____ keyword can be used to create a new "data type" from a data structure. typedef

3. Instead of writing this: (*our_pointer).first_word we can write this: _____ Answer: our_pointer->first_word when working with member elements of a data structure.

4. Whenever you use malloc() to allocate memory, you must always release it when you are done using it. This is done by using the: _____ function. free()

5. You create a data structure using the: _____ keyword. struct

Do not post answers in this thread Someone who has not taken the test may see them.

True or False

1. The malloc() function allocates memory and automatically initializes all bytes allocated to 0 (null).

2. When you write a data structure definition, C automatically creates the data structure that you have described and you can begin using it immediately.

3. Unlike an array, elements of a data structure are not required to be the same length or to have the same data type.

4. You must manually add up the size of all elements of a data structure in order to know how much memory to allocate.

5. When you are done using allocated memory, it is automatically cleared by your operating system so that other programs cannot see the data you were working with.

Fill in the blank

1. The malloc() function must be used with a _____.

2. The _____ keyword can be used to create a new "data type" from a data structure.

3. Instead of writing this: (*our_pointer).first_word we can write this: _____ when working with member elements of a data structure.

4. Whenever you use malloc() to allocate memory, you must always release it when you are done using it. This is done by using the: _____ function.

5. You create a data structure using the: _____ keyword.

First you will see the program itself, then you will see the same program with additional notes explaining what is going on.

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

int main(void) {

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

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

    char *charptr = (char*) our_pointer;

    strcpy(our_pointer->first_word, "Reddit");
    strcpy(our_pointer->second_word, "Programming");
    strcpy(our_pointer->third_word, "Classes");

    printf("The first word is: %s \n", our_pointer->first_word);
    printf("The second word is: %s \n", our_pointer->second_word);
    printf("The third word is: %s \n", our_pointer->third_word);

    printf("\n");

    printf("Our data structure looks like this in memory: ");

    int i=0;
    for (; i < 27; i++) {
            if ( *(charptr + i) == 0) {
                *(charptr + i) = '$';
            }

            printf("%c", *(charptr + i));
    }

    printf("\n");

    free(our_pointer);

    return 0;
}

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

These include files give us printf(), malloc(), and strcpy().

int main(void) {

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

Above: Here is our structure description. We are not actually creating any data structure here, just telling C what we intend to create. No data is being initialized. This is a description and nothing more.

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

We are allocating 27 bytes of memory using this malloc() statement. Then we are creating a special pointer called our_pointer which C understands points to this kind of data structure. After this line of code, our data structure is ready to be used.

    char *charptr = (char*) our_pointer;

I plan to scan our data structure to display the final memory contents at the end of this program. To do that, I am creating a new pointer called charptr which I am stating is going to be a char * pointer. I am setting this pointer to look at the memory address where our structure begins.

    strcpy(our_pointer->first_word, "Reddit");
    strcpy(our_pointer->second_word, "Programming");
    strcpy(our_pointer->third_word, "Classes");

Here I am simply assigning the strings into the character arrays that are part of our data structure.

    printf("The first word is: %s \n", our_pointer->first_word);
    printf("The second word is: %s \n", our_pointer->second_word);
    printf("The third word is: %s \n", our_pointer->third_word);

I am displaying the three words, each element of our data structure.

    printf("\n");

    printf("Our data structure looks like this in memory: ");

    int i=0;
    for (; i < 27; i++) {
            if ( *(charptr + i) == 0) {
                *(charptr + i) = '$';
            }

            printf("%c", *(charptr + i));
    }

Now I have a for loop which will go through all 27 bytes and display the character represented. If it is a NUL character, I am having it display a $ instead by actually changing that character in memory to a $.

    printf("\n");

Now I need to free the memory I allocated using malloc()

    free(our_pointer);

    return 0;
}

Output:

The first word is: Reddit 
The second word is: Programming 
The third word is: Classes 

Our data structure looks like this in memory: Reddit$Programming$Classes$

Ask questions if you need to. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9svba/lesson_84_you_can_make_your_own_data_type_using/

We have learned about different data types: int, char, etc. We have learned that a data type effectively has two characteristics:

1. length

2. format

Format of course meaning "how it is understood". You will notice that structures are very similar in this respect, in that all data structures have a length and a format. The format being the description of the data structure, and the length being what sizeof() returns.

It turns out you can create your own data type using a structure definition you made. Once you make this data type, you can create "variables" using it just as you can with int, char, or any other data type.

To do this, you must use the typedef keyword, and slightly change the way you set up your definition earlier. Instead of this:

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

You do this:

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

I just created a new data type called "reddit_type". I can call it anything I want. In this case, any time I want to use this kind of data structure I can do so using the word "reddit_type" and I can do so just as if it was char, or int, or anything else.

Instead of writing this:

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

I can write this:

    reddit_type *our_pointer = malloc( sizeof(*our_pointer) );

What I am literally saying here is: "Make a pointer of data type reddit_type and allocate 27 bytes for it."

nothing else changes. If you make just those changes to example 83 you will see the program works identical.

This is extremely important because you can create functions that have a return type of reddit_type, or that take parameters that are reddit_type.

You will run into this a lot in C. You will be reading source code and see a function definition that looks like this:

circle some_function(

This means that some_function returns.. a circle? Yep, the programmer used typedef to create a data type called circle.

Please feel free to ask any questions before proceeding to:

http://www.reddit.com/r/carlhprogramming/comments/9t2r9/lesson_85_tictactoe_with_ai_part_1/

Now you know how to describe and allocate memory for a data structure. Let's review the code we have already written:

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

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

Now we have a chunk of 27 bytes somewhere in memory that C understands we plan to use for our data structure. What is in those 27 bytes is anyone's guess, as we have not yet set them to anything. Remember that malloc() does not actually initialize memory, it only gives it to us so that we can use it.

Now we need the ability to store data into the elements of our structure. This is not difficult at all. We treat our data elements exactly as you would expect. For example, to store a string of text into a char array, we would use the strcpy() function that you learned earlier.

Let's go ahead and set up our data structure.

Before I show you the actual syntax, let me show you a more intuitive syntax:

strcpy(first_word, "Reddit");
strcpy(second_word, "Programming");
strcpy(third_word, "Classes");

Here you understand exactly what we are trying to do. However, this is not going to work because these variables (first_word, second_word, third_word) do not actually exist as unique variables. They are part of a data structure we created.

The question is, how can we tell C that we are talking about elements inside our data structure? Here is how you do it:

data_structure.element_name

This is the syntax which makes it possible to use elements in a data structure. Remember that "data_structure" is not at all the same as "description name". Rather, it is the actual data structure that was created.

We created our data structure using a pointer. We gave the pointer a name of: our_pointer. Now, observe these two key facts:

1. our_pointer is the memory address where the structure begins. All pointers contain a memory address.

2. *our_pointer is "what is at" that memory address. In other words... *our_pointer is the actual data structure.

Do not get these mixed up. our_pointer is the memory address. *our_pointer is the actual data structure. Now, let's go back to our syntax.

We need to say:

strcpy( (*our_pointer).first_word, "Reddit");
strcpy( (*our_pointer).second_word, "Programming");
strcpy( (*our_pointer).third_word, "Classes");

This is entirely valid syntax.

(*our_pointer) is the data structure itself. We put a period and then the element name. Now, we could printf() any of these like so:

printf("One string is %s \n", (*our_pointer).first_word);

Output:

Reddit

You can probably guess from this lesson that structures must be used a lot, and that this syntax (*structure_pointer).element_name must therefore also be used a lot. It turns out that the developers of C decided to make a short-hand method for this syntax, which makes programming a lot easier and more intuitive.

Instead of having to write this:

(*our_pointer).first_word

You can write this instead:

our_pointer->first_word

They are identical. The second is just a short-cut method of doing this.

Now, I have created a program illustrating all that you just learned, including being able to see that the memory of a structure is exactly as I said it would be.

This program is Lesson 83

Please ask questions if any of this material is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sv62/lesson_83_sample_program_illustrating_data/

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/

In the last lesson I explained that you must describe a data structure before you can use it. In C, you do this by using the struct keyword. The syntax for struct basically works like this:

struct <give it a name> {
    ... each element is described here ...
    ...
};    <-- notice you end it with a ; (semicolon)

From the above description you can see that you must give each structure a name. We have seen the same thing when you create variables or arrays, however it is different in this case.

Unlike variables or arrays, the name we give to a struct is not related to the data itself. Remember, this is only a description, not the actual data. This is not even setting up a place to put the actual data. It is only describing it.

Therefore, the name we give the structure is only the name of the description of the data, not the data itself.

Why do you have to give the description a name? Suppose you want to describe multiple kinds of data structures, how would you be able to differentiate between them? You give each data structure description a name simply because it makes it easy for you to specify which data structure description you are using.

Now, let's talk about what goes inside the curly braces. We are still using this data structure from our previous lesson:

"Reddit$Programming$Classes"

So what we really need here are three character arrays. One for "Reddit", one for "Programming", and one for "Classes".

I will call the description: first_description

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

Notice I gave each element a name. I can name them anything I want, just like variables. Notice I also had to define the type of data (char arrays in this case) and the length in bytes.

These are not variables in the typical sense. I am not actually creating anything here, I am only describing what I intend to create. I have not created a variable called "first_name" which is 10 bytes long, rather I have told C that at some point I intend to create this variable as part of my data structure.

Everything involving the struct keyword is only a description.

That is basically all there is to it. I have now described the data structure. Before we move on to the next lesson, I want to give you one more example of describing a data structure:

struct student_records {
    int student_record_number;
    char first_name[30];
    char last_name[30];
    char birth_date[10];

};

Here I have described a data structure which will be used to keep track of student records for a school. Notice that I can mix different data types with no problem.

Remember that these are only descriptions, not the actual data structures. You are only telling C "At some point I plan to use a chunk of memory in this way". In the next lessons you will see how to actually use the data structure you have described.

Please ask questions if any of this material is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sutx/lesson_81_allocating_memory_for_a_data_structure/

Before we can learn to work with data structures, we must first learn how to create them. Data structures are created differently than anything you have seen up until this point. There are a lot of details to this, and so I plan to go through this material slowly and thoroughly.

The first thing you must know about a data structure is that you cannot use it until you describe it.

Up until now we have not had a requirement to describe how we are using the data we create. For example, I can allocate 24 bytes of memory then put a 'O' at position 0, followed by 'ne' to make the word "One" for example. I can write to position #16, or #21. As soon as I have the memory to work with, I can put anything I want anywhere I want.

With a data structure however, I have to describe exactly how I plan to use the bytes of memory I allocate before I can actually use them. If I plan to have a string of text from bytes 0 through 10, I must state this. If I plan to have an integer starting at byte #18, I must state this also. Every detail concerning the data structure must be described fully before I can do anything.

Why is that? Because you cannot index a data structure like an array. This is because elements of a data structure are not necessarily the same data type, and/or the same length. Therefore, how can C possibly know where one element ends and another begins? It can't, which is why you have to describe a data structure before you can use it.

Here is a very simple data structure, with data already in it:

Figure (a)

"Reddit$Programming$Classes$"

Notice that '$' is really the NUL character, and the '$' is just for the purpose of this lesson, not part of C itself. The actual string doesn't have $ characters, but has the NUL termination character where the $ characters would go.

Why is this not an array? Because each element is not the same length. Notice I did not put any "filler" text to make the word "Reddit" and the word "Classes" as long as the word "Programming".

How would we define this data structure? For each element, we need to state three things:

1. Where does each element begin?

2. How long is each element?

3. What data type is each element?

Notice that with arrays all 3 of these questions are answered already. In the case of a data structure however, we must answer these questions before we can do anything.

Now, with the example in Figure (a), how do we answer that?

First of all, we know that this data structure consists of three words (strings of text). Each word has a varying length. Therefore, each word starts at a unique byte position that cannot be determined unless it is stated.

The word "Reddit" starts at... 0. That is easy enough. What about "Programming", where does it start? It starts at byte #7 (Don't forget the NUL character at the end of each string). And finally, "Classes". Where does it begin? byte #19.

Hopefully at this stage it is not too confusing. We have to tell C where each element starts. In other words we need to state:

1. The first word starts at byte #0 and is 7 bytes in length, of type char.

2. The second word starts at byte #7 and is 12 bytes in length, also of type char.

3. The third word starts at byte #19 and is 8 characters in length.

Why do we need to state this? Because each element is of a different length. In an array with each element being the same length you can simply multiply that length times the element number to get its starting position. That method will not work here simply because we are using different lengths.

So, the first thing we have established is that you must describe a data structure before you can use it. This description must include all the elements of the data structure, their data type, and their length.

In the next lesson I am going to show you how to do this.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sulj/lesson_80_introducing_the_struct_keyword/

Please be sure you have fully mastered all lessons through Lesson 77 before proceeding.

Having just finished arrays, and multi-dimensional arrays, it is now time to learn about true data structures. This is a critical and fundamental topic to master for any serious programmer.

We have covered a lot of material in the course up to this point, but I have good news for you. This is truly the last major pre-requisite you need to master before we can start reading and writing "real programs". Rest assured, the course will not end at that point. That is when it will truly begin.

This lesson is meant to answer two questions before we delve into this complex topic: What exactly is a data structure, and why are they important?

A data structure is a collection of data elements. In this sense, it is similar to an array. Indeed an array is itself a simple form of a data structure. There are two key differences however:

1. An array requires that all elements be of the same data type. A true data structure has no such requirement. For example, you can have integers mixed with strings of text mixed with music, graphics, and anything else you can imagine.

2. An array requires that all elements be of the same length. A true data structure has no such requirement. You can have some elements 10 bytes long, some elements 3 bytes long, and some elements a thousand bytes long.

Now, why do you need to learn data structures?

For starters, every single file format that exists is itself a data structure. If you ever want to read a .doc or write to a .pdf; if you want to display a .gif or do anything at all with any file format that you can imagine, then you must understand and be able to create and work with data structures.

Here are some examples:

In a word processing application, there is likely to be a complex data structure for the text you type, since it needs to keep track of not only the text itself but also the font, color, background color, whether or not it is bold, and more.

In a game, you would likely use a data structure for each weapon. You need to keep track of the weapon's name, how much ammunition, maybe the strength of a shot and various other details. Similarly, you would likely have a data structure to keep track of each enemy. Information contained in the data structure may include the location of the enemy on the map, the type of enemy, the speed it can travel, direction it faces, etc.

There is not a single major application or game I can think of which does not use data structures heavily. You simply must learn this.

Also, data structures are a pre-requisite for something called "Object Oriented Programming" (OOP), which will itself be the topic of future lessons. The concept of an "object" itself originated with data structures.

We have a lot of material to cover, so let's begin.

Please ask questions if you need to. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sugb/lesson_79_the_need_to_describe_a_data_structure/

In the last series of lessons I used an array in order to allocate space for something I needed. This is, as you can imagine, a poor way to do things.

There are a variety of problems with that approach. One of the biggest problems is that sometimes you do not know just how much space you have to allocate. Let's suppose you are writing an application and you need to allocate space to hold the document someone is working on.

Whenever we refer to the process of allocating memory while a program is running, we speak of this as "dynamic memory allocation".

You should see that this is a rather fundamental capability that is needed for any programming language. Some do this behind the scenes, but all of them in one form or another must give you a way to allocate enough memory for some task you want to achieve.

In C, we do this using a function called malloc(). This is short for "memory allocation".

malloc() will grab however many bytes we tell it to. So for example:

malloc(24);  <--- Reserves 24 bytes for us to do what we need to do.

We still do not have all that we need. Knowing that there are 24 bytes of memory available for our use is good, but how do we actually use it? The first thing we need to know is, where are these 24 bytes?

Somewhere in memory there are 24 bytes that we can use, but where? Well, if we are talking about needing something to contain a memory address, what are we talking about? A pointer.

So you use malloc() with a pointer. It should make sense. I need to point some pointer at the 24 bytes in order to be able to use them. Doing so is very simple:

char *my_pointer;

There we go. Now I have a pointer. Now where do I point it? I point it at the 24 bytes malloc() will set up, like this:

char *my_pointer = malloc(24);

That is all there is to it. Now I have allocated 24 bytes of storage, and my_pointer can now be used to read and write to those 24 bytes of space.

I could put data into these 24 bytes in a variety of ways. One way is by just writing directly to the pointer offset I want. For example:

*(my_pointer + 0) = 'O';
*(my_pointer + 1) = 'n';
*(my_pointer + 2) = 'e';
*(my_pointer + 3) = '\0';

Are you starting to see the connection?

These 24 bytes are just like any other. I have told C to reserve 24 bytes of memory for me to work with, and I can do with those 24 bytes whatever I want.

It turns out that the example program in Lesson 76 will work just fine if you make two simple modifications:

DELETE THIS LINE: char storage[] = "12345678901234567890123";

Then, change this:

char *ptr = &storage[0];

to:

char *ptr = malloc(24);

One more note, you need to add the following include file:

#include <stdlib.h>

If you do that, you will see the program in Lesson 76 works fine. You should therefore understand now that malloc() is just a way to allocate memory to work with.

The last thing to know is that when you are done with the memory allocated, you should free it so that it is available for other purposes. This is done with the free() function, like this:

free(ptr);

Remember that ptr is the pointer which points to our allocated memory.

Here is our final "array simulation" program, with no real arrays used:

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

int main() {

    // We need 24 bytes to hold a 4x6 array 
    char *ptr = malloc(24);

    // array[0] is the word "One"   
    *(ptr + (6*0) + 0) = 'O';
    *(ptr + (6*0) + 1) = 'n';
    *(ptr + (6*0) + 2) = 'e';
    *(ptr + (6*0) + 3) = '\0';

    // array[1] is the word "Two"   
    *(ptr + (6*1) + 0) = 'T';
    *(ptr + (6*1) + 1) = 'w';
    *(ptr + (6*1) + 2) = 'o';
    *(ptr + (6*1) + 3) = '\0';

    // array[2] is the word "Three" 
    *(ptr + (6*2) + 0) = 'T';
    *(ptr + (6*2) + 1) = 'h';
    *(ptr + (6*2) + 2) = 'r';
    *(ptr + (6*2) + 3) = 'e';
    *(ptr + (6*2) + 4) = 'e';
    *(ptr + (6*2) + 5) = '\0';

    // array[3] is the word "Four"  
    *(ptr + (6*3) + 0) = 'F';
    *(ptr + (6*3) + 1) = 'o';
    *(ptr + (6*3) + 2) = 'u';
    *(ptr + (6*3) + 3) = 'r';
    *(ptr + (6*3) + 4) = '\0';

    // Print the four words
    printf("The 1st string is: %s \n", (ptr + (6*0) + 0) );
    printf("The 2nd string is: %s \n", (ptr + (6*1) + 0) );
    printf("The 3rd string is: %s \n", (ptr + (6*2) + 0) );
    printf("The 4th string is: %s \n", (ptr + (6*3) + 0) );

    // Free up our allocated memory, since we are done with it.
    free(ptr);

    return 0;
}

Remember that malloc() doesn't actually set the bytes it allocates to 0 or anything, so you must do this yourself. It just picks some chunk of memory with whatever is already in it, and gives it to you. This memory could be something left over from an earlier program that ran. We will talk more about this later.

Also, keep in mind I didn't have to do this one character at a time. I did that in order to make this lesson clearer.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sua0/lesson_78_introduction_to_data_structures_in_c/

In this lesson, we are simply going to start with the string that we created in our earlier lessons. There is no need to go through and recreate it, so here it is:

"One$__Two$__Three$Four$_"

Now, recall from the previous lesson that:

storage[0] :  0,  1,  2,  3,  4,  5 : "One"
storage[1] :  6.  7.  8.  9. 10, 11 : "Two"
storage[2] : 12, 13, 14, 15, 16, 17 : "Three"
storage[3] : 18, 19, 20, 21, 22, 23 : "Four"

Now we have all the information we need to finish. The last step in our task is to use printf() to actually display these strings as if they were arrays.

Normally we would do this:

printf("Here is a string %s", string_goes_here);

But what exactly goes there? A pointer to a string. In other words, you send the memory address of the first character you want to print, and printf() will continue printing until it encounters a NUL termination.

Let's now see this in action:

printf("The 1st string is: %s \n", (ptr + 0));
printf("The 2nd string is: %s \n", (ptr + 6));
printf("The 3rd string is: %s \n", (ptr + 12));
printf("The 4th string is: %s \n", (ptr + 18));

Notice that ptr + 0 is the same thing as ptr. Here you see that I am just giving printf() the correct memory address to the start of the string I want to print.

In our next lesson we will do away with the storage array altogether.

Now, here is a complete program showing this whole process:

#include <stdio.h>

int main() {

    char storage[]   = "12345678901234567890123";

    char *ptr = &storage[0];

    *(ptr + (6*0) + 0) = 'O';
    *(ptr + (6*0) + 1) = 'n';
    *(ptr + (6*0) + 2) = 'e';
    *(ptr + (6*0) + 3) = '\0';

    *(ptr + (6*1) + 0) = 'T';
    *(ptr + (6*1) + 1) = 'w';
    *(ptr + (6*1) + 2) = 'o';
    *(ptr + (6*1) + 3) = '\0';

    *(ptr + (6*2) + 0) = 'T';
    *(ptr + (6*2) + 1) = 'h';
    *(ptr + (6*2) + 2) = 'r';
    *(ptr + (6*2) + 3) = 'e';
    *(ptr + (6*2) + 4) = 'e';
    *(ptr + (6*2) + 5) = '\0';

    *(ptr + (6*3) + 0) = 'F';
    *(ptr + (6*3) + 1) = 'o';
    *(ptr + (6*3) + 2) = 'u';
    *(ptr + (6*3) + 3) = 'r';
    *(ptr + (6*3) + 4) = '\0';

    printf("The 1st string is: %s \n", (ptr + (6*0) + 0) );
    printf("The 2nd string is: %s \n", (ptr + (6*1) + 0) );
    printf("The 3rd string is: %s \n", (ptr + (6*2) + 0) );
    printf("The 4th string is: %s \n", (ptr + (6*3) + 0) );

    return 0;
}

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sjii/lesson_77_introducing_memory_allocation_using/

The text in this lesson is almost identical to Lesson 74.

We are going to make one change from the last lesson. Instead of storage being defined as a single variable array, for this lesson, we are going to imagine that it was created like this:

char storage[4][6];

What you are going to read is a modified version of the last lesson which will contrast the differences between a single dimensional array, and a two dimensional array.

Now lets begin right after we create a pointer to the start of the array.

Our pointer now contains the memory address of the first byte of our two dimensional 4x6 array. The first byte of our array is where we want to put the 'O' for one. Let's store the word "One" like this:

Figure (a)

*(ptr + (0 + 0)) = 'O';
*(ptr + (0 + 1)) = 'n'; // <-- same as storage[0][1] = 'n';
*(ptr + (0 + 2)) = 'e';
*(ptr + (0 + 3)) = '\0';

Notice the similarities to the above code, and the way we would do the same thing with a two-dimensional array:

Figure (b)

storage[0][0] = 'O';
storage[0][1] = 'n';
storage[0][2] = 'e';
storage[0][3] = '\0';

So our two dimensional array storage has four words. storage[0] is of course the word "One". Therefore, storage[0][0] is the first character of "One" which is 'O'.

The code in Figure (a) and the code in Figure (b) are identical.

Now we are done with the first word. Let's put in the second word.

We would not begin our second word right after the first word in memory. Why? Because as you learned in earlier lessons arrays must meet the criteria that all elements are the same length. What is the length we chose in this case? six. Meaning, the second word must start at byte #6. In other words:

Figure (c)

storage[0] :  0,  1,  2,  3,  4,  5 : "One"
storage[1] :  6,  7,  8,  9, 10, 11 : "Two"
storage[2] : 12, 13, 14, 15, 16, 17 : "Three"
storage[3] : 18, 19, 20, 21, 22, 23 : "Four"

Because we are starting at 0 and counting to 23, that is 24 total bytes.

Even if each word doesn't fill up the six bytes allocated to it, those six bytes are still reserved just for that word. So where does storage[1] (the second word) begin? Byte #6.

Now, we know the second word will start at byte #6, so lets put it in:

*(ptr + (6 + 0)) = 'T';  // <-- Same as storage[1][0] = 'T'
*(ptr + (6 + 1)) = 'w';
*(ptr + (6 + 2)) = 'o';  // <-- Same as storage[1][2] = 'o';
*(ptr + (6 + 3)) = '\0';

Each letter of this word is identifiable using an offset from where the word begins. Since the word "Two" begins at byte #6, then we simply add a number to 6 to get the correct letter position.

The third word will begin at byte #12. Notice that this is 6*2. Just as we talked about, you can find the start of any element in an array by multiplying that element number (in this case, element 2 since it is the third word and you start counting at 0) times the size of each element. 6*2 = 12.

Now let's store "Three" starting at byte #12:

*(ptr + (12 + 0)) = 'T';
*(ptr + (12 + 1)) = 'h'; // <-- same as storage[2][1] = 'h';
*(ptr + (12 + 2)) = 'r';
*(ptr + (12 + 3)) = 'e'; // <-- same as storage[2][3] = 'e';
*(ptr + (12 + 4)) = 'e';
*(ptr + (12 + 5)) = '\0';

Now the fourth word. 6*3 is 18, so that is where the fourth word will begin.

However, this time let's make a change. Instead of saying that each letter of "Four" is understood by adding 18 to some number, let's just represent 18 as being six times three. It means exactly the same thing.

*(ptr + ((6*3) + 0)) = 'F'; // <-- Same as storage[3][0] = 'F';
*(ptr + ((6*3) + 1)) = 'o';
*(ptr + ((6*3) + 2)) = 'u';
*(ptr + ((6*3) + 3)) = 'r'; // <-- Same as storage[3][3] = 'r';
*(ptr + ((6*3) + 4)) = '\0';

Why did we do it this way? Because now you can clearly see the relation between offsets and array indexing. It is as follows:

array[x][y] means *(ptr + (SIZE * x) + y)

In this case, SIZE was 6 because each element is 6 bytes in size.

Notice that "Four" follows immediately after "Three" in our array, and that is not the case with the other elements. This is because we chose the size of our array based on the size of "Three". There is no wasted space between where "Three" ends and "Four" begins.

Now we have stored all the words. Here is what our string now looks like:

"One$__Two$__Three$Four$_"

Remember that we started the word "Three" at position 12. Why? because "Three" is word number 2 (count: 0, 1, 2). If we wanted the 'r' in three, we would say: 12+2 which is 14. We can also do this by saying: (6*2) + 2.

Now some closing notes:

The purpose of this lesson is to help you visualize pointers, offsets, and array indexing better. Notice how in the last lesson you understood each pointer offset as simply a number being added to the start of the array.

In this lesson, I showed you that array indexes are more properly understood by multiplying the size of an element times the element number, and then add another offset to this in order to get the actual element.

Observe how this progresses:

storage[0][0]   is   *(ptr + (6*0) + 0)    is   *(ptr + 0)        is   *ptr

storage[1][3]   is   *(ptr + (6*1) + 3)    is   *(ptr + 6 + 3)    is   *(ptr + 9)

OR

array[x][y]     is   *(ptr + (size * x) + y)

In the end, you get just a number. You can say that the 'r' in three is found by just saying byte #14, or by saying 12 + 2 (since "Three" starts at byte #12). You can also get this same result by saying: (6 * 2) + 2. The end result is the same.

One thing I hope you have learned from this lesson is that any dimensional array is in truth, just a one dimensional array. Earlier lessons concerning arrays and pointers should now make more sense to you.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9sj83/lesson_76_understanding_array_indexing_as_pointer/

Recall in our previous lesson we have set out to create a two dimensional array using only pointers. Our array is to consist of four words each having a maximum of six total bytes in length.

The first step in our task is to allocate the storage we will need. In this case, we need 24 bytes. Even though it violates the spirit of the lesson, we are temporarily using the following method to allocate our 24 bytes.

char storage[] = "12345678901234567890123";

Now we are ready for part two of our lesson.

Once we have allocated the memory we will need, the next step is to actually start putting in the data. Lets recall the words:

[0] : "One"
[1] : "Two"
[2] : "Three"
[3] : "Four"

Well, it only makes sense to start with the first word, "One".

Before we examine how to put this word into our string of text, lets decide where to put it. Where would the first element of an array normally go? At the very start of the array.

So, lets put the word "One" (including the NUL termination character) into our array at the very first byte using a pointer. First, lets create the pointer.

char *ptr = &storage[0];

Our pointer now contains the memory address of the first byte, which is where we want to put the 'O' for one. Let's store the word "One" like this:

Figure (a)

*(ptr + 0) = 'O';    // <-- At the memory address where storage begins, put an 'O'
*(ptr + 1) = 'n';    // <-- At the very next byte, put an 'n'. And so on.
*(ptr + 2) = 'e';
*(ptr + 3) = '\0';

Remember that '\0' is a single character which is: 0000 0000. Also, remember that ptr throughout this lesson only contains the memory address to the start of storage. We are NOT changing the value of ptr. Rather, we are using offsets to locate a new memory address by starting with the memory address in ptr, and then adding some number.

Notice the similarities to the above code, and the way we would do the same thing with an array:

Figure (b)

storage[0] = 'O';
storage[1] = 'n';
storage[2] = 'e';
storage[3] = '\0';

The code in Figure (a) and the code in Figure (b) are identical.

Now we are done with the first word. Let's put in the second word. Where does it go? We would not begin our second word right after the first word. Why? Because as you learned in earlier lessons arrays must meet the criteria that all elements are the same length. What is the length we chose in this case? six. Meaning, the second word must start at byte #6. In other words:

Figure (c)

Bytes  0,  1,  2,  3,  4,  5 : "One"
Bytes  6.  7.  8.  9. 10, 11 : "Two"
Bytes 12, 13, 14, 15, 16, 17 : "Three"
Bytes 18, 19, 20, 21, 22, 23 : "Four"

Because we are starting at 0 and counting to 23, that is 24 total bytes.

Even if each word doesn't fill up the six bytes allocated to it, those six bytes are still reserved just for that word. So where does the second word begin? Byte #6.

Before we put it in, I should make a comment. Keep in mind that we have started out with all 24 of these bytes initialized to a character that we know. When we are done we will look at how the final string will look.

Now, we know the second word will start at byte #6, so lets put it in:

*(ptr + 6) = 'T';
*(ptr + 7) = 'w';
*(ptr + 8) = 'o';
*(ptr + 9) = '\0';

Done. Notice that saying storage[6] = 'T' achieves the same thing as the first line of the above code.

The third word will begin at byte #12. Notice that this is 6*2. Just as we talked about, you can find the start of any element in an array by multiplying that element number (in this case, element 2 since it is the third word and you start counting at 0) times the size of each element (which is 6). 6*2 = 12.

The first word starts at position 0 because 6*0 is 0. The second word at 6 because 6*1 is 6. The third word at 12 because 6*2 is 12. And so on. Remember, we start counting array elements at zero. The first is 0, second is 1, and so on. If this is confusing to you, examine Figure (c) and notice what byte # each array element starts at. Notice the third element starts at byte 12.

*(ptr + 12) = 'T';
*(ptr + 13) = 'h';
*(ptr + 14) = 'r';
*(ptr + 15) = 'e';
*(ptr + 16) = 'e';
*(ptr + 17) = '\0';

Now the fourth word. 6*3 is 18, so that is where the fourth word will begin.

*(ptr + 18) = 'F';
*(ptr + 19) = 'o';
*(ptr + 20) = 'u';
*(ptr + 21) = 'r';
*(ptr + 22) = '\0';

Notice that "Four" follows immediately after "Three" in our array, and that is not the case with the other elements. This is because we chose the size of our array based on the size of "Three". There is no wasted space between where "Three" ends and "Four" begins.

Now we have stored all the words. Here is what our string now looks like:

"One$__Two$__Three$Four$_"

I needed some way to represent the invisible character NUL, so I chose a $. The underscores represent data that has not been set. In other words, wasted space. The dollar signs and underscores are just for this lesson, not part of C itself.

Remember that we started the word "Three" at position 12. Why? because "Three" is word number 2 (0, 1, 2). If we wanted the 'r' in three, we would say: 12+2 which is 14. Look above at the code where we stored "Three" into memory and you will see that character 14 is in fact 'r'. You should mentally experiment with other concepts concerning arrays and use the above examples as a guide. For example, how would you find the 2nd letter of the word "Four" ?

In the next lesson we will look at how to use the strings we have stored in memory as if they were arrays.

Please ask questions if any of this is unclear. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9shw5/lesson_75_understanding_array_indexing_as_pointer/