Pointer to node!

[gaurav_13191]

Hi, I have the code to add elements at the end of the linked list using recursion.

//Adds an element at end using recursion

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

struct node
{
 int data;
 struct node *link;
};

void addatend(struct node **,int);
void display(struct node *);

int main()
{

 struct node *p=NULL;
 clrscr();
 addatend(&p,14);
 addatend(&p,20);
 addatend(&p,31);
 display(p);
 getch();
 return 0;
}

void addatend(struct node **ptr,int value)
{
 if(*ptr==NULL)
 {
  *ptr=malloc(sizeof(struct node));
  (*ptr)->data=value;
  (*ptr)->link=NULL;
 }
 else
  addatend(&((*ptr)->link),value);
}

void display(struct node *ptr)
{
 struct node *q;
 q=ptr;
 while(q!=NULL)
 {
  printf("%d\t",q->data);
  q=q->link;
 }
}

I have just a small confusion, I think the pointer ptr should point to the last node after we add nodes at the end. But according to the program output, it points to the first node in the linked list. Please explain.

[N1GHTS]

A few suggestions...

You are not freeing the memory after you malloc it. Thats a memory leak, just for your info.

Also, instead of using malloc(), use calloc() and you don't have to do (*ptr)->link=NULL;

One more thing... if this was an entirely recursive program, your display function should also match the style of addatend():

void display(struct node *ptr)
{
  if (ptr!=NULL) {
    printf("%d\t",ptr->data);
    display(ptr->link);
  }
}

Anyways, as for why its not working, beats me. I don't have enough time to put it through a debugger and check it for you, so hopefully someone else can.

[Narue]

>instead of using malloc(), use calloc() and you don't have to do (*ptr)->link=NULL;
I wouldn't recommend relying on that. calloc zero fills the bytes, and a null pointer isn't required to be represented by all bits zero.

>Anyways, as for why its not working, beats me.
It is working, he just doesn't understand why p points to the head of the list and not the tail after calling addatend.

[N1GHTS]

>I wouldn't recommend relying on that. calloc zero fills the bytes, and a null pointer isn't required to be represented by all bits zero.

Thats true, so all places which use NULL should be changed to 0 to take advantage of calloc(). Personally I redefine NULL in my applications since -1 or any other interpretation is not very useful compared to 0.

As for why p points to the head of the list... its because its the first instance of your linked list. I mean, isn't that what this whole recursive concept is all about? You always start at the head and "trickle down" to the tail by calling the same function with the child parameter, but always first starting at the head.

All this becomes clear if you look at the first line of your main function. That line defines the head, and since you keep using the p instance in the main function, you keep using the head.

Hope that was clear enough.

[Narue]

>Thats true, so all places which use NULL should be changed to 0 to take advantage of calloc().
Um, no. For the sake of this concept, you should think of NULL and 0 as being exactly the same thing[1]. There's confusion because a literal 0 in pointer context means a null pointer, but that doesn't mean the underlying bit representation of a null pointer is all zeros[2].

calloc initializes the allocated memory to zero bytes, and because a null pointer may not be represented internally by all zero bytes, you can't assume that pointers are initialized properly to NULL (or 0).

>Personally I redefine NULL in my applications since -1 or any other interpretation is not very useful compared to 0.
What? Why in the world would you want to redefine the macro for a null pointer constant? That sounds like a fantastic way to introduce bugs.

[1] NULL can be correctly implemented as #define NULL 0 , though traditionally in C it's been #define NULL ((void*)0) .
[2] Described another way, a null pointer doesn't have to point to address 0.

[N1GHTS]

I do this in my core header:

#ifndef NULL
#define NULL ((void*)0)
#endif

Honestly I didn't put much thought into the idea that its actually a pointer to zero rather than a value resolving to zero. I figured the (void *) was a way to make it compatible with pointers of any type or as a parameter to a function of any type.

Very interesting information. Makes me wonder what in the world zero is really pointing to and why they chose that technique for NULL rather than zero as a value.

Does the compiler or system typically do anything with position zero of the local process memory? Who and when defines that position as zero? Is it random?

One additional question: If calloc() is used in a structure containing a pointer, doesn't the pointer automatically point to (void*)0 ? The pointer is a pointer, and as you say NULL is also a pointer to zero, so aren't they both pointing to the same place?

[N1GHTS]

I've been thinking about this problem and realized that I never had it wrong in the first place. NULL is not used in any context other than comparrion. When is it ever practical to use NULL as a pointer to a meaningful value?

As such, calloc(), being a function that takes a newly created block of memory and copies each new byte with zero is by itself is not assigning it NULL explicitly, but if the destination of that memory is a structure containing a pointer, it will be pointing to the exact same place as NULL.

In other words, calloc() creates NULL, because they both point to the same garbage pointer, which is position zero. calloc() creates implicit NULL's if its destination is a structure with a pointer.

Therefore, unless NULL is redefined as something other than (void*)0, then my suggestion is completely correct.

[Narue]

>I do this in my core header
Hopefully because you want to use NULL, but don't want all of the extra stuff in the headers where it's defined. That's really the only good excuse for defining your own NULL exactly the way the implementation would.

>Does the compiler or system typically do anything with position zero of the local process memory?
It's typically reserved for system level stuff. Oddly enough, catching null pointer dereferences is not uncommon. ;)

>If calloc() is used in a structure containing a pointer, doesn't the pointer automatically point to (void*)0 ?
Let's look at this from a low level perspective:

int **p = calloc(1, sizeof *p);

You know that calloc is logically nothing more than a paired call to malloc and then memset:

int **p = malloc(1 * sizeof *p);

memset(p, 0, 1 * sizeof *p);

And memset is pretty stupid in that all it does is copy the value into each byte:

int **p = malloc(1 * sizeof *p);
char *dst = (char*)p;

while (dst < (char*)p + (1 * sizeof *p))
    *dst++ = 0;

Now *p is set to all bits zero: 0x00000000. But what if the implementation uses 0xdeadbeef as the internal representation of a null pointer? The compiler can easily recognize that *p = 0 or *p = (void*)0 is assigning a null pointer constant and automatically convert that constant to the internal value of 0xdeadbeef before assignment, but it can't do that when you manually copy the bytes into *p with memset.

If the representation of a null pointer is all bits zero, you're solid. But the code is far from portable. Your problem is confusing the literal value 0 with the actual value of a null pointer. It's a common, common misconception that the value of a null pointer is guaranteed to be all bits zero, and that misconception stems from the fact that a null pointer constant in the source code is 0.

[N1GHTS]

Yeah, like I said, if NULL is not pointing to zero, the calloc() pointer will no longer be compatible with NULL.

I would argue, though, that since NULL is a macro, and since macro's allow for better portability in C, that it is "safe" to redefine NULL within the context of your code if you choose to let calloc() or memset() do your NULL assignment for you. Personally I think its safer to have those functions set all your structures to zero in case you forget to initialize the structure or use a complex system of nested or recursive malloc's to structures. I would assume that 0xdeadbeef helps alert someone who is debugging their code that a pointer with NULL was not assigned a value, which would be easier to identify than "attempt to access 0x00000000" errors.

Either way, I understand your point and this really boils down to preference, not portability, since as I said, its a C macro and its completely legal to redefine it within your own programs context.

[Narue]

You really don't see the problem, do you? I don't care that you redefine NULL. That's not the problem. I find it strange, but if it floats your boat, whatever. The problem is you're advocating the horribly unsafe practice of letting calloc initialize pointers to null, which is not guaranteed to work.

[N1GHTS]

Umm... well I guess I'll just agree with you and let it be.

And in your honour, whenever I talk about calloc() as a method to initialize structures with pointers in them I will put up a warning about how it is not considered portable to depend on that as a short-cut to initialize pointers to NULL unless they are absolutely sure they know what they are doing and risking the portability of their code.

[Narue]

>Umm... well I guess I'll just agree with you and let it be.
...I see I wasted my time trying to teach you. Next time I'll just say you're wrong and not bother explaining why unless someone who's willing to learn asks.

[sree_ec]

>Umm... well I guess I'll just agree with you and let it be.
...I see I wasted my time trying to teach you. Next time I'll just say you're wrong and not bother explaining why unless someone who's willing to learn asks.

I was curiously watching this discussion.

I understood what Narue has explained as

1. We can use calloc and assume that it will fill the memory location it return with 0
2. In the case of a pointer,lets say p, inside a structure and we are allocating space for that structure using calloc, we cannot guarantee that 'p' is pointing to NULL only because It is filled with 0's. This is because, even though in most of the systems we have NULL as (void*)0, there can be situations where NULL is something else as you said 0xdeadbeef . So such an assumption will make the code non portable.

Is it correct?

If yes @Narue, Have you come across any implementation like that where NULL is not (void*)0 ? [Just for information]

[Narue]

>Is it correct?
Yes and no, there's confusion about the NULL macro. The definition of NULL is irrelevant[1]. If a null pointer is not represented by all bits zero, you open a can of worms by initializing a pointer to all bits zero. calloc essentially uses memset to initialize the block, and memset fills the data with all bits zero, so using memset on a pointer and expecting it to compare equal to a null pointer is wrong:

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

int main(void)
{
    struct foo { int *data; } *p = calloc(1, sizeof *p);

    if (p != NULL)
        puts(p->data == 0 ? "null" : "not null");

    return 0;
}

The above program is not required to print "null", because calloc need not initialize the pointer member to a null pointer.

[1] It's irrelevant because NULL is nothing more than a convenient symbol for a null pointer constant. A null pointer constant is absolutely guaranteed to be some variant of a constant expression evaluating to 0. This constant is then converted to the internal pointer representation when used. So, once again assuming the internal representation is 0xdeadbeef, when the compiler sees this:

int *p = 0;

It converts it to the equivalent of this:

int *p = (int*)0xdeadbeef;

Null pointer constants are thus portable regardless of the underlying representation of a pointer. The existence of the NULL macro is really just a convenience that makes your intentions clear. If you use 0, readers may not realize that the expression is in a pointer context, but NULL (if used correctly) leaves no doubt that you're working with pointers.

[N1GHTS]

The reason I stopped arguing and just accepted that you were right was because you were so sure that you were right it was impossible to get you to see some very subtle but important flaws in your logic, which after reading your latest explanation, simply confirms that I was right on track with my gut feeling on this topic.

This is the bottom line... A pointer is nothing more than a 4 byte memory space (2 or 1 byte in some systems) whose meaning is changed when used in a pointer context and instead points to somewhere else. Its just the same as how you use int's in assembly language. All you do there and refer to your int as a memory pointer (square brackets) and the meaning changes.

You explained that NULL, a macro usually pointing to 0, doesn't usually point to zero in some implementations, and I accept that. But if it were implemented as ((void *)0), that's exactly the same (when you assemble the code into OP codes) as 0 (all 4 bytes are stored as zero), because the (void *) simply tells the compiler to use it as a pointer context, not as the integer that it really is, but either way its a zero stored in memory.

If NULL were 0xdeadbeef or even ((void *)0xdeadbeef), the compiler does NOT care, its a frickin' macro. Just to be sure, I tested this on gcc before posting this message and the tests show that your explanation that int *p = 0; will be converted to int *p = (int*)0xdeadbeef; just because some silly macro "NULL" is defined as pointing to 0xdeadbeef doesn't work, and frankly just doesn't make much sense, and would be quite disastrous if it were true.

Just to tell you why I know that pointers are nothing magical, When I work on non ANSI C code written for specific machines, I often use pointers as both a (A) pointer to something and (B) a simple int if the pointer is not supposed to point to anything. This saves me 4 bytes right there, which is important if the structure is malloc'd. I do this by casting the pointer straight to (int), and it works like a charm, never has any unexpected behavior. So, unless I am trying to keep my code portable (where pointers might be less than 4 bytes), I could save the extra 4 bytes by passing another int along with the pointer and just use the pointer dual purpose.

As such, the main focus of this argument should not be if its "not guaranteed to work", as that is completely not true if you know what you are doing, but rather, how "portable" the technique is and weather or not to involve the standard NULL macro as is, which I agree is incorrect unless you redefine it or create a new macro, perhaps called #define ZERO ((void*)0). And in all cases, as long as these things I just mentioned are considered, in my opinion the code would still be portable and would still be legal ANSI C.

[Narue]

>you were so sure that you were right
I am right. You're just too stubborn to imagine that you're wrong. Drop the ego for a moment and consider that someone else might just know something you don't.

>it was impossible to get you to see some very subtle but important flaws in your logic
Just because you don't understand doesn't mean my logic is flawed.

>If NULL were 0xdeadbeef or even ((void *)0xdeadbeef), the compiler does NOT care, its a frickin' macro.
Let's pretend that the NULL macro doesn't exist, because it's just confusing the issue. The problem exists whether you use NULL or not, it's the difference between a null pointer and a pointer with all bits set to zero that matters. Now go read my posts again.

[N1GHTS]

Here is the better explanation of your point Narue:

Read First: http://c-faq.com/null/null1.html
Read Second: http://c-faq.com/null/null2.html

So to clarify,

int *p = 0;

will compile to a "Null Pointer" (Not to be confused with the NULL macro), a special internal pointer guaranteed not to point to something meaningful, which may or may not be 0.

But to do this:

typedef struct { int *p; } P;

P *p = calloc(sizeof(P));

Probably won't accomplish the same thing because the compiler does not know (or need to know) the content of the structure in order to properly assign *P->p the "Null Pointer" appropriate for that pointer type.

So basically, the compiler keeps track of ((void *)0), a value with a very special meaning to a C compiler (not to be confused by the macro NULL), and when it encounters it or an implied ((void*)0) (as with int *p=0;), the compiler will look at the type of pointer at its destination, in the case of my first example an int pointer, checks its own settings of ranges of valid pointer locations for that type, and assigns it an impossible pointer not in its tracked range, which may or may not be zero.

In other words, ((void *)0) (or pointer to zero) is tracked and converted in a sophisticated manner by the compiler to comply with the ANSI C requirement that the "Null pointer" be GUARANTEED to be unique for all pointers used in the application.

On a final note, the NULL macro must always be 0. Read the references below.

http://c-faq.com/null/macro.html
http://c-faq.com/null/machnon0.html
http://c-faq.com/null/macsochange.html

And recasting a NULL is good for better portability, as referenced here:

http://c-faq.com/null/nullreq.html

And for those, like me a few hours ago, confused about the terms behind NULL and "Null Pointer", here is a run-down:

http://c-faq.com/null/varieties.html

And some final words to live by:

http://c-faq.com/null/confusion.html

---
P.S.

> I am right. You're just too stubborn to imagine that you're wrong

There exists a phenomenon whereby two intelligent parties who are experts at a specific subject can have different "facts" for the same ideas, and when those fact elements are broken down into their primary elements and analysed by a third party, it is likely that both of them have elements of their debate that are erroneous, either due to a lack of details which invalidates a concept, or due to an error in the factualness of that point, or even that the definition of key words have different meanings between the two parties. In either case, without compatible communication, there is no harm believing you are right unless you are proven wrong, because what is knowledge if it isn't a compilation of memories of things past, and what isn't wisdom if it isn't a judgement of those memories, erroneous or not... and what is life without some level of wisdom, instinctual or otherwise.