Passing and using pointers to structures into functions

[PsySc0rpi0n]

Hello.

This is a subject that I always struggled with.
Simple pointers are ok.

I know that when we have, inside the same scope:

Code: Select all

int var = 5;


and then we use:

Code: Select all

printf("var: %p\n", &var);


we are accessing the variable position in memory.

Then, if we use:

Code: Select all

int *var = NULL;


We are supposing to use var to hold a memory position.

So, when we use:

Code: Select all

printf("var: %p\n", (void *) &var);


(I had to type cast it to void * to match the specifier flag %p).

we are also accessing the variable memory position too.
I get a 'nil' keyword if I try to access it the same way but without the '&'. Not sure what that stands for.

And if I want to access the actual value stored in that memory position, I use:

Code: Select all

printf("var: %d\n", *var);


Now, raising a bit the complexity, I always struggle when it comes to pass pointers to functions and I never get it right when it comes to passing pointers to pointers or pointers to arrays or pointers to structures into functions.

So, for instance, if I have:

Code: Select all

typedef struct node{
   ...;
   ...;
}Node;

int main(void){
   Node root = NULL;
   Node *head = NULL;

   printf("Test: %p\n", (void *) &root);
   printf("Test: %p\n", (void *) &head);
   return 0;
}


I understand we are accessing only memory positions.

Now, what I want to do is to create a double linked list of structs and I don't want to use global variables at all.
I guess 99% of the search results either from youtube or google, uses global variables to build linked lists.
But I want to pass all variables via pointers, avoiding global variables. And the only global thing is the struct.

So this is how I start:

Code: Select all

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

typedef struct node{
   ...;
}Node;

int main(void){
   Node *root = NULL;
   
   return 0;
}


And questions starts right here, because what I do now, will change the rest of the program.
I have several options, or at least 2.
Create a variable to initialize the root struct or initialize it in the main() function. I can't decide which is better and more solid practice.

Then, depending on the way to go, I'll have to deal with how to pass the variables to functions and how and what to return.

So, to start, what would be the best and more solid practice?

[neuraleskimo]

A good place to start is to not write your own list (unless you are doing it for fun). Here are two examples of ready to go lists you can use: https://developer.gnome.org/glib/2.64/glib-Singly-Linked-Lists.html and https://developer.gnome.org/glib/2.64/glib-Doubly-Linked-Lists.html.

If you want to write your own, I would do something like this:

Code: Select all

struct node {
    node* parent;
    node* child;
    void* data;
};

node* create_list(void* data)
{
    /*
        allocate a node
        set parent to null
        set child to null
        save data
        return node
    */
}

node* destroy_list(node*);
node* append_data(node* n, void* data);
node* remove_node(node*, void* data);
/* ... */


Does that help?

Also, try the following code...

Code: Select all

    int    v = 42;
    int*   p = &v;
    int** pp = &p;

    printf("%d %d %d\n", v, *p, **pp);
    printf("%p %p %p\n", (void*)&v, (void*)p, (void*)*pp);
    printf("%p %p\n", (void*)&p, (void*)pp);
    printf("%p\n", (void*)&pp);

    printf("lets get tricky...\n");
    printf("%d %d %d\n", v, *&v, *&*&v);
    printf("%d %d %d\n", v, **&p, **pp);


As always, don't hesitate to ask questions or for me to elaborate on any of the above (this post covered A LOT of ground).

[PsySc0rpi0n]

Yes, I'm doing this for fun. I was learning how to build a BlockChain in Python and I wanted to compare it to C programming language.

I should already know how to do this almost from memory. I've been doing somethings in C language but as I don't do C programming language in a regular basis, there are always many concepts that gets lost in memory.

I want to do this on my own. I don't want to use pre-made things or I'll learn/practice less.

So, if you're available to help me, I'll ask you help in specific situations and I'll be pasting my code here or in some fancier site so that the synta gets highlighted and etc, like ideone.com.

So, I'll start by creating the structure as:

Code: Select all

typedef struct node{
   int index;
   Node *prev;
   Node *next;
}Node;


This is the basic structure. Let's keep it that way for now.

Now, if I recall, we work with lists, node by node, right?
I mean, we don't create a variable to hold an array of these structs, do we? We just create a single node and fill the *prev and *next fields to keep them connected, right?

[PsySc0rpi0n]

Well, I started with this code.
I leave the link to ideone which has some syntax highlighting.

https://ideone.com/iRDHkS

My question is at line 79 to 82 where I ask for a string with fgets but I can't get rid of an extra '\n' that my terminal shows when I print the string.
I know that a string automatically adds a '\0' at the end of the string but before it, I guess fgets captures the '\n' that I hit when I enter the string.
I try to remove it from the string but somehow it still's there.


Ok, this one is fixed!

[neuraleskimo]

I should already know how to do this almost from memory. I've been doing somethings in C language but as I don't do C programming language in a regular basis, there are always many concepts that gets lost in memory.

I have been programming C/C++ for a very long time too and I forget a lot. Don't feel bad.

So, I'll start by creating the structure as:

Code: Select all

typedef struct node{
   int index;
   Node *prev;
   Node *next;
}Node;


This is the basic structure. Let's keep it that way for now.

A fine starting point!

Now, if I recall, we work with lists, node by node, right?
I mean, we don't create a variable to hold an array of these structs, do we? We just create a single node and fill the *prev and *next fields to keep them connected, right?

Correct, you always start at the head or tail of a list and visit every node (i.e., node-by-node). Also correct, on the "create a single node and fill the *prev and *next fields to keep them connected." On the array part of your question, correct again. Arrays and list are different data structures. Arrays are contiguous memory regions filled with the same (or castable to the same) type. Nodes in an array are potentially scattered throughout memory. Arrays allow random access while lists only support sequential access. On and on...

[neuraleskimo]

Well, I started with this code.
My question is at line 79 to 82 where I ask for a string with fgets but I can't get rid of an extra '\n' that my terminal shows when I print the string.
I know that a string automatically adds a '\0' at the end of the string but before it, I guess fgets captures the '\n' that I hit when I enter the string.
I try to remove it from the string but somehow it still's there.

I think line 80 should read:

Code: Select all

if(root->str[strlen(root->str) - 1] == '\n'){

If the string is "debian10\n", then strlen() will return 9 (unless I have forgotten how to count). Because arrays are zero indexed, str[9] is the null terminator. str[8] is the newline. Its an easy typo to make.

Your code looks good. I have one suggestion that will improve the runtime should you want to leave the index in the final code (might be useful). Create list type that contains the head node and tail node of the list along with the length. Then all operations on a list know the head node, tail node, and length. If you do this, you will need to update that index every time you add or remove a node. Every node can still hold its index (or position), but not walking the list on every insert will save some time.

[Edit: BTW, if every node holds its position, then removing a node from the middle of the list will leave "holes" in your numbering scheme. Maybe not tragic. Call it a feature and you will be fine.]

[PsySc0rpi0n]

Thank you for keeping me in the right track.

In the meantime I have proceeded a bit in the code. However, I have a situation that most searches I've seen in DDG/Google try to avoid with dummy first nodes. I don't want to avoid it, I want to tackle it. And I've not been able yet to tackle it.

At this moment, my createNode() functions is like this:

Code: Select all

Node *createNode(Node *root, Node *node){
    Node *tmp = NULL;

    node = calloc(1, sizeof(Node));
    if(root == NULL){
       root = node;
       return root;
    }else{
        tmp = root;
        while(tmp->next != NULL)
            tmp = tmp->next;
        node->prev = tmp;
        tmp->next = node;
        node->next = NULL;
        return node;
    }
}


But I don't think this will work. I haven't tried it yet, but I don't think it will work.
I know we have to handle 2 situations when adding nodes which is when the list is empty and when it is not.
When it is empty, the newly created node will be the root node, when the list is not empty, we need to iterate the list until the last node, and then update the prev and next pointers to the correct new values. But I think I'm running around in circles, changing to one way, then to another way, then to a different way and at the end I think I back to the beginning and I can't find the correct way!

So, some help is appreciated!

[neuraleskimo]

However, I have a situation that most searches I've seen in DDG/Google try to avoid with dummy first nodes. I don't want to avoid it, I want to tackle it. And I've not been able yet to tackle it.

The current thinking is that uninitialized values are the source of many errors, complicate code, and should be avoided. I think you are starting to discover some of the difficulties. Having said that, "undefined behavior" (UB) is a cornerstone of C/C++ performance (among other attributes). The trick is UB is a technique like any other and should be reserved for the right situations. I think you will gain some valuable experience thinking about these types of things, so keep going.

At this moment, my createNode() functions is like this:

Code: Select all

Node *createNode(Node *root, Node *node){
    Node *tmp = NULL;

    node = calloc(1, sizeof(Node));
    if(root == NULL){
       root = node;
       return root;
    }else{
        tmp = root;
        while(tmp->next != NULL)
            tmp = tmp->next;
        node->prev = tmp;
        tmp->next = node;
        node->next = NULL;
        return node;
    }
}


But I don't think this will work. I haven't tried it yet, but I don't think it will work.
I know we have to handle 2 situations when adding nodes which is when the list is empty and when it is not.
When it is empty, the newly created node will be the root node, when the list is not empty, we need to iterate the list until the last node, and then update the prev and next pointers to the correct new values. But I think I'm running around in circles, changing to one way, then to another way, then to a different way and at the end I think I back to the beginning and I can't find the correct way!

So, some help is appreciated!

First, let's start with a way to work around some problems, in pseudocode

Code: Select all

// separate creating a list and appending a list into two distinct operations and
// separate the concept of a list and a node into two distinct classes

struct node
    node* prev
    node* next
    T data

struct list
    node* head
    node* tail
    size_t length

// always make an empty list
list* create_list()
    allocate a list
    set head to null
    set tail to null
     set length to zero

// alway make a valid node
node* create_node(T node_data)
     allocate node
    set node->data to node_data

list* list_append(list* l, T node_data)
    n = create_node(node_data)
    n->prev = l->tail
    n->next = null
    if l->tail != null
        l->tail->next = n
    l->tail = n
    if l->head == null
        l->head = n
    list->length++


I hope there are no bugs and that this helps...

[EDIT: fix a bug ]

[PsySc0rpi0n]

Hum, ok. I'll try that.

But in that case, what I said/ask previously about to create a linked list we would only be worried about single nodes and building the linked list node by node, is not valid anymore, I guess, because we are now creating (reserving memory) for a list and creating (reserving memory) for single nodes. Right?

Also, we are creating 2 different types of structures. IS this really mandatory to avoid dummy nodes at the beginning?

Am I wrong or is this list we are creating, up to some extent, the dummy node I've seen around the web? If I'm correct, we are not avoiding the dummy node. Isn't there any other way? We really need to stick to it?

[PsySc0rpi0n]

Ok, I think I have executed your pseudoCode:

I have pasted it in an online site because the code tags here are not preserving indentation.

https://ideone.com/iRDHkS

But, I want to know the reasoning behind this approach and why can't I make the linked list the way I was doing it!

[neuraleskimo]

But in that case, what I said/ask previously about to create a linked list we would only be worried about single nodes and building the linked list node by node, is not valid anymore, I guess, because we are now creating (reserving memory) for a list and creating (reserving memory) for single nodes. Right?

Correct, but in either case, you will build a list node-by-node. That part hasn't changed. What I am encouraging you to try is have a single type for a list and a single type for a node. Think of a list as a container of nodes. This will simplify your tasks ahead and, yes, renders your question invalid. As I would put it, avoids the problem you were asking about. Having said that, it is certainly true that your approach will work, but you will find the programming harder because you will be making your node class (well struct) represent two (related but different) concepts. I am just trying to help steer you around some pitfalls that lie ahead.

On the memory portion of your question, correct. However, the cost of that extra memory allocation is small when amortized over the cost of creating a typical list. If memory allocation and speed are a concern, an array is the only solution most of the time. The typical advice is to use an array unless you really, really need a list.

Also, we are creating 2 different types of structures. IS this really mandatory to avoid dummy nodes at the beginning?

I don't know if having two structures it is mandatory, but it is a good idea and consistent with a lot of libraries. Also, I am not saying that you MUST do this or that. I am only giving advice. I also think exploring alternate solutions is beneficial.

Am I wrong or is this list we are creating, up to some extent, the dummy node I've seen around the web? If I'm correct, we are not avoiding the dummy node. Isn't there any other way? We really need to stick to it?

Very good question. There are some differences that I would argue are significant. A list is not an empty node, it is a container of nodes (zero nodes still makes a valid container). A node is always valid (never empty and always initialized with valid data). If you allow empty (uninitialized) nodes, you may have to check that a node is not empty on every list operation. This will complicate your code and increase the potential for bugs. If you assume that every node is valid (non-empty) then you won't need to do those checks. To some degree this all reduces to a question of making the smallest and simplest preconditions, postconditions, and invariants for your design. I am suggesting that this will make your programming tasks much easier. Think in terms of the UNIX philosophy: one tool does one job well.

I hope this helps.

[neuraleskimo]

Ok, I think I have executed your pseudoCode:

I have pasted it in an online site because the code tags here are not preserving indentation.

https://ideone.com/iRDHkS

But, I want to know the reasoning behind this approach and why can't I make the linked list the way I was doing it!

Your code looks good.

My previous post (which I was writing as you posted this) answers your question somewhat. You can make the list as you were doing it, it just may be a bit harder in the long run. I certainly don't want to make you to do something you don't want to do.

BTW, I had forgotten you mentioned blockchain. In that area, some people may implement their own linked lists (instead of using existing libraries) for a variety of reasons that have to do less with avoiding dummy nodes (uninitialized nodes) and more to do with performance along the most typical execution path.

[neuraleskimo]

Here is a simple example of what I mean by simplifying your code.

Assume you want to find the first node with some data.

Code: Select all

// using the list approach
node* find_in_list(list* l, T node_data)
    node* n = l->head
    while n is not null
        if n->data equals node_data
            return node
        n = n->next

// using nodes only
node* find_in_list(node* root, T node_data)
    check that the node is empty (not valid)
        exit if empty
    now do the loop in the list version above


It is a small difference, but adding that check to ever operation on your blockchain will probably need to be in every operation. It adds repetitive code, which most people (including me) will screwup. It also adds more code to execute and an extra comparison which costs a few CPU cycles. Etc...

[PsySc0rpi0n]

Please rest that I don't fell forced to do things your way. I rather feel impelled to. I mean, at this point, that I'm struggling, I see your suggestions as the best way to follow. So, that's what I'll do.

Ok, so about the code.

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?

[neuraleskimo]

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.