Passing and using pointers to structures into functions

Need help with C, C++, perl, python, etc?

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-21 12:42

neuraleskimo wrote:
PsySc0rpi0n wrote:The function of appending the nodes to the list needs some guidance so that I can understand it. I mean, I understand the code, what I might not see straight forward is the reasoning behind the checks and the way the code is the way it is. I think I need a fully functional and minimal code to print out some memory addresses to see if I can understand what is going on. Or maybe what I really want to see is the code "avoiding" the potential problems, such has that initial dummy node, etc.

So, to make that happen, I think I only need to write the main() function, compile, run and add some strings to see the code working, no? Or is any other critical function/step yet missing?

Correct. Your main function could be something like this.
Code: Select all
Blockchain* chain = createBlockChain();
chain = appendToChain(chain, "some string");

You can instrument the functions with print statements.


Yes, that part is the easy part. :)

But how you connect the list (container) and the nodes (blocks) ? For instance, can you access a node's data using the container variable?
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-21 17:51

In the meantime I created these 2 functions to print blocks alone an to print the whole chain.

Now, I want to understand better the appendToChain() function.

https://ideone.com/iRDHkS
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-21 19:20

Looks really good.

Your printChain() function could take a BlockChain* and then the printChain() call would look a little simpler...
Code: Select all
void printChain(BlockChain *chain){
    Block *tmp = chain->pgen;
 
    while(tmp != NULL){
        printBlock(tmp);
        tmp = tmp->next;
    }
}
...
printChain(myChain);

It is a small change, but reduces repetitive code.

On appendToChain(), the general idea is...
Line 1) Allocate memory and initialize in one function (I omitted the error checking, but you should make sure malloc didn't fail)

Line 2) For the new node, its previous node is whatever is at the tail of the list. If the list is empty, this value will be null: exactly what we want! It's almost like we planned it that way. ;-)

Line 3) Because we are appending,the new node will be (by definition) the last block in the list. Therefore, its next node is always NULL. These previous two steps have now made the new node "aware" of its position in the list. Now, on to the previous last node.

Line 4) The previous last node is no longer the last node and we need to "tell it so." If the list is empty, there is no previous last, and nothing to do. If the list is not empty, then there is a previous last node. Line 5 set the next pointer to the new node we just added. Now, the previous last node "knows" that it is no longer the last node.

Line 6) Important: the following must happen after the above lines! Now that the previous last node and the new last node "know" about each other, we want to "tell" the list about our changes. This line sets the tail of the list to the new node.

Line 7 and 8 ) If the list is empty, the node we are adding is also the head. That is, the first node is both the head and the tail. Otherwise, the list is not empty, so there is nothing to do.

Line 9) Having successfully completed all of the steps above, we increment the size to capture the new length of out list.

Now, can you work through what happens when you add the second node?

Hope this helps...
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-21 23:39

neuraleskimo wrote:Looks really good.

Your printChain() function could take a BlockChain* and then the printChain() call would look a little simpler...
Code: Select all
void printChain(BlockChain *chain){
    Block *tmp = chain->pgen;
 
    while(tmp != NULL){
        printBlock(tmp);
        tmp = tmp->next;
    }
}
...
printChain(myChain);

It is a small change, but reduces repetitive code.

On appendToChain(), the general idea is...
Line 1) Allocate memory and initialize in one function (I omitted the error checking, but you should make sure malloc didn't fail)

Line 2) For the new node, its previous node is whatever is at the tail of the list. If the list is empty, this value will be null: exactly what we want! It's almost like we planned it that way. ;-)

Line 3) Because we are appending,the new node will be (by definition) the last block in the list. Therefore, its next node is always NULL. These previous two steps have now made the new node "aware" of its position in the list. Now, on to the previous last node.

Line 4) The previous last node is no longer the last node and we need to "tell it so." If the list is empty, there is no previous last, and nothing to do. If the list is not empty, then there is a previous last node. Line 5 set the next pointer to the new node we just added. Now, the previous last node "knows" that it is no longer the last node.

Line 6) Important: the following must happen after the above lines! Now that the previous last node and the new last node "know" about each other, we want to "tell" the list about our changes. This line sets the tail of the list to the new node.

Line 7 and 8 ) If the list is empty, the node we are adding is also the head. That is, the first node is both the head and the tail. Otherwise, the list is not empty, so there is nothing to do.

Line 9) Having successfully completed all of the steps above, we increment the size to capture the new length of out list.

Now, can you work through what happens when you add the second node?

Hope this helps...



Yes, it helps. I just think I wouldn't get there by myself. And I would like to be able to have gotten there by myself. Anyways, thanks for the explanations.

I changed my printChain() function to what you suggested.

Now, about the appendToChain() function.

If I understand, something like this happens, when the list is empty:

Image

Bur when I try to do the same when the list is not empty, I think I don't understand the following line:

Code: Select all
pChain->tail->next =  newBlock;


For instance, let's assume the list is not empty and pChain is 1000 (memory address), pChain->prev is NULL and pChain->tail is 1128.
Now we create a new block and it gets assigned the following memory position: newBlock is 3512.

Code: Select all
BlockChain *appendToChain(BlockChain *pChain, char *pstring){
    Block *newBlock = createBlock(pstring);
 
    newBlock->prev = pChain->tail;
    newBlock->next = NULL;
    if(pChain->tail != NULL)
        pChain->tail->next = newBlock;
    pChain->tail = newBlock;
    if(pChain->gen == NULL)
        pChain->gen = newBlock;
    pChain->len++;
 
    return pChain;
}


So, following the code:

newBlock->prev is assigned to 1128 (which is pChain->tail content)
newBlock->next is assigned to NULL
then the if statement is True, so we enter it and this line means what? Does this means that the field 'next' of the block that lies in memory position 1128 will point to this newBlock memory address? And if so, why can't we refer to this block at memory position 1128 by it's name as we refer to 'newBlock'? I mean, variable names are just some kind of aliases to memory positions, right? So, why can't we refer to that block at 1128 by it's name?
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-21 23:53

PsySc0rpi0n wrote:Bur when I try to do the same when the list is not empty, I think I don't understand the following line:
Code: Select all
pChain->tail->next =  newBlock;


Because I see you are online, here is a quick answer to this.

We need to find the last block in the chain and then update its next pointer to point to the new node (or block). That is all the code does, I just wrote it in a terse form. A more verbose form is:
Code: Select all
 node* old_last_node = pChain->tail;
old_last_node->next = newBlock;


We are about to start dinner. Will think about the rest and reply later...
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-22 00:23

neuraleskimo wrote:
PsySc0rpi0n wrote:Bur when I try to do the same when the list is not empty, I think I don't understand the following line:
Code: Select all
pChain->tail->next =  newBlock;


Because I see you are online, here is a quick answer to this.

We need to find the last block in the chain and then update its next pointer to point to the new node (or block). That is all the code does, I just wrote it in a terse form. A more verbose form is:
Code: Select all
 node* old_last_node = pChain->tail;
old_last_node->next = newBlock;


We are about to start dinner. Will think about the rest and reply later...


But we already know the last block in the chain. It's memory location is saved in pChain->tail, no?
(I think I'm already mixing names. I started with myChain and now I'm calling it pChain)

Enjoy dinner. I'm not sure I'll still around. It's 1:10 am here. :)

PS:
And another thing I want to ask is about free(). When the program exits, where do we have to place the free(newBlock); line of code?
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-22 17:01

PsySc0rpi0n wrote:PS:
And another thing I want to ask is about free(). When the program exits, where do we have to place the free(newBlock); line of code?

It should be at the end of all execution paths. That is, if you exit early due to an error, you need to free all memory allocated up to that point. This can get tricky in C and is the source of a large number of memory leaks. For you program now, it should be at the end of main(). As your program gets more complex, pay careful attention to program flow.

However, what you have won't work. You need something like this:
Code: Select all
void free_list(list* l)
{
    while (l->head != NULL) {
        node* current = l->head;
        l->head = current->next;
        free(current);
    }
    free(list);
}


Anyway, this is an area where C++ starts to be a good choice. Destructors give you the ability to manage resources without caring about execution paths. You also get really high quality data structures.
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-22 17:11

PsySc0rpi0n wrote:
neuraleskimo wrote:
PsySc0rpi0n wrote:Bur when I try to do the same when the list is not empty, I think I don't understand the following line:
Code: Select all
pChain->tail->next =  newBlock;


We need to find the last block in the chain and then update its next pointer to point to the new node (or block). That is all the code does, I just wrote it in a terse form. A more verbose form is:
Code: Select all
 node* old_last_node = pChain->tail;
old_last_node->next = newBlock;

But we already know the last block in the chain. It's memory location is saved in pChain->tail, no?
(I think I'm already mixing names. I started with myChain and now I'm calling it pChain)

Correct. Lets call the first node "node1" and the second node "node2".

After the first append, node1 will be the only node in the list and list->head and list-> will point to node1. Also, node1->prev and node1->next will be NULL.

After the line of code you are asking about executes, node1->next will point to node2.
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-22 17:19

Just for comparison, in C++ your code would look like this:
Code: Select all
int main()
{
    std::list<std::string> chain;
    chain.push_back("node1");
    chain.push_back("node2");

    for (const auto& node : chain) {
        std::cout << node << "\n";
    }

    return 0;
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-22 17:44

Ok, I understand the free() thing. My question was rather about the fact that my free() function at the end of main() was only free'ing myChain memory, so how would one free each block memory.

About c++, I never felt attracted to it. And when you tell me that C can be hard to keep track of where memory needs to be free'ed, I wonder how devs manage huge programs line Linux kernels and many other big applications written in C. I think linux kernels are pure C, right? Not c++. Correct if I'm wrong.

I'll go to code the free function for my small program.
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-23 19:53

PsySc0rpi0n wrote:Ok, I understand the free() thing. My question was rather about the fact that my free() function at the end of main() was only free'ing myChain memory, so how would one free each block memory.

The code I gave you above does that. The while loop frees each node and, once the list is empty, it frees the list.

PsySc0rpi0n wrote:About c++, I never felt attracted to it. And when you tell me that C can be hard to keep track of where memory needs to be free'ed, I wonder how devs manage huge programs line Linux kernels and many other big applications written in C. I think linux kernels are pure C, right? Not c++. Correct if I'm wrong.

It is Ok if you don't like C++, but don't completely reject it. It may be the best solution for a given problem. If there is anything to takeaway from my posts on this forum, it is always be pragmatic and I don't suffer religion in technical arguments.

Correct, Linux is written almost exclusively in C (with a small amount of assembly). Other operating systems not so much. Some use a mix of C and C++ as they see fit. The same is true for compilers and interpreted languages like Python or Java. For example, Python (as I recall) is written largely in C and Java (technically the JVM and tools) is written largely in C++. Years ago, the decision on language of choice, was based on solid technical reasons with some religion thrown in. Now, most of the old arguments are moot. There are new languages on the horizon (e.g., Rust) that may become the defacto standard, but I doubt it. There is no good reason to throw away working code. Of course, if that does happen, I will learn the new language and go on with my life.

As to how they do it, it is really hard. If you look through the bugs and CVEs, you will see lots of memory leaks, use after free, and similar errors. Good programming, testing, code reviews, tooling, etc. really help.
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Re: Passing and using pointers to structures into functions

Postby PsySc0rpi0n » 2020-03-24 20:34

neuraleskimo wrote:
PsySc0rpi0n wrote:Ok, I understand the free() thing. My question was rather about the fact that my free() function at the end of main() was only free'ing myChain memory, so how would one free each block memory.

The code I gave you above does that. The while loop frees each node and, once the list is empty, it frees the list.


Yes, I've done that in the past. But didn't remember how to do it.

neuraleskimo wrote:
PsySc0rpi0n wrote:About c++, I never felt attracted to it. And when you tell me that C can be hard to keep track of where memory needs to be free'ed, I wonder how devs manage huge programs line Linux kernels and many other big applications written in C. I think linux kernels are pure C, right? Not c++. Correct if I'm wrong.


It is Ok if you don't like C++, but don't completely reject it. It may be the best solution for a given problem. If there is anything to takeaway from my posts on this forum, it is always be pragmatic and I don't suffer religion in technical arguments.

Correct, Linux is written almost exclusively in C (with a small amount of assembly). Other operating systems not so much. Some use a mix of C and C++ as they see fit. The same is true for compilers and interpreted languages like Python or Java. For example, Python (as I recall) is written largely in C and Java (technically the JVM and tools) is written largely in C++. Years ago, the decision on language of choice, was based on solid technical reasons with some religion thrown in. Now, most of the old arguments are moot. There are new languages on the horizon (e.g., Rust) that may become the defacto standard, but I doubt it. There is no good reason to throw away working code. Of course, if that does happen, I will learn the new language and go on with my life.

As to how they do it, it is really hard. If you look through the bugs and CVEs, you will see lots of memory leaks, use after free, and similar errors. Good programming, testing, code reviews, tooling, etc. really help.


Yes, I guess I might have to give the religion away.
I'm learning python, so I'm trying to keep up with the evolution. But unfortunately my job is not on the programming area. At least for now!

Ok, next step on this code is to link each block with hash keys of the blocks themselves. But maybe I'll create a new thread for that if I can't handle it. As of this code, I'll probably keep the thread going as I still need to create some other functions related to searching blocks in the list, save the data to a file, load the same data from the file, etc. I might even try to implement a fancier search algorithm just for the fun such as some bubble sort or binary tree searches if applicable!
User avatar
PsySc0rpi0n
 
Posts: 188
Joined: 2012-10-24 13:54
Location: Portugal

Re: Passing and using pointers to structures into functions

Postby neuraleskimo » 2020-03-24 20:40

PsySc0rpi0n wrote:Ok, next step on this code is to link each block with hash keys of the blocks themselves. But maybe I'll create a new thread for that if I can't handle it. As of this code, I'll probably keep the thread going as I still need to create some other functions related to searching blocks in the list, save the data to a file, load the same data from the file, etc. I might even try to implement a fancier search algorithm just for the fun such as some bubble sort or binary tree searches if applicable!


I think that sounds like a good plan!
User avatar
neuraleskimo
 
Posts: 174
Joined: 2019-03-12 23:26
Location: Bloomington, Indiana, USA

Previous

Return to Programming

Who is online

Users browsing this forum: No registered users and 3 guests

fashionable