How does a HEAD pointer end up pointing to the first node in a linked list?

[A “Ashvin”]

The following code is snippet from a FIFO write/read model. The code works. I am only showing the write procedure. My questions are noted after the code snippet.


type Item; --Incomplete declaration
type Ptr is access Item;
type Item is record
NextItem : Ptr;
Data : integer;
end record;
variable Head : Ptr;
procedure FIFO_WRITE(Data : in integer) is
variable NewItem : Ptr;
variable Node : Ptr;
begin
NewItem := new Item'(NextItem => Null, Data => Data);
--allocate memory - point to where the Item is stored.
if Head = null then --if the list is empty
Head := NewItem; --claim the memory and initialise Root/Head to the claimed memory.
else
Node := Head; --start with Root node at the beginning of the list
while Node.NextItem /= null loop --Go through linked list and search for
--last/tail node.
Node := Node.NextItem;
end loop;
Node.NextItem := NewItem; --store NewItem(Item) at the tail end of the list.
end if;
end;


I have a fundamental question. I have declared the variable HEAD to be of type Ptr. Then I check to see if HEAD = NULL. So, all I have done is declare the variable HEAD. How does that end up pointing to the first node in the list? How does the HEAD = NULL work? Is it that when you declare HEAD, that the NextItem of 'record' Item end up pointing to NULL by default? I haven't allocated memory to HEAD. Nothing. Just the declaration causes it to point to the first node in the list? Don't understand that.

Thanks.

[gnuarm.del...@gmail.com]

It's been a long time since I've used pointers in VHDL. But I believe NULL is used to indicate a pointer has no valid value. I don't think it is pointing anywhere. In your case, it indicates it has not been assigned a value. No?

https://www.hdlworks.com/hdl_corner/vhdl_ref/VHDLContents/Null.htm

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209

[A “Ashvin”]

Rick, Thanks. I understand what assignment to NULL means. My question is how does HEAD pointer work? All we have done is declare HEAD as a variable. How does it end up pointing to the first node in the list? We haven't allocated any memory to HEAD (i.e. we haven't made the assignment HEAD := new item'(Nextitem => NULL, data=data);). So, how does HEAD know where to point to?

[gnuarm.del...@gmail.com]

Maybe here?

Head := NewItem; --claim the memory and initialise Root/Head to the claimed memory.

--

Rick C.

+ Get 1,000 miles of free Supercharging
+ Tesla referral code - https://ts.la/richard11209

[A “Ashvin”]

Thanks Rick. But I am doing "if Head = NULL" first and -then- assigning Head := NewItem. So the question is how do we know that Head is pointing to a node and that the node is null -before- assigning it new memory? To simplify the question "where does Head point to when it is first delcared as "variable Head : Ptr".

[gnuarm.del...@gmail.com]

Sorry, there's still a miscommunication somewhere. From the web site I sent you a link for...

"The default value of an access type is null."

https://www.hdlworks.com/hdl_corner/vhdl_ref/VHDLContents/AccessType.htm

I think they are saying it is set to NULL when created. Look at some code and it is clear that is how it works.

This example seems to be for a stack, which is very similar to your FIFO list. The only difference is, that your code would add nodes to one end of the list, and remove them from the other (or copy the data through the list) while the FIFO would add and remove the data from the same end. Oddly enough, this author decided to use the far end of the list as the working end. I have no idea what impact that would have on operation. Are pointers and allocated structures synthesized?

https://vhdlwhiz.com/linked-list/

I don't think I've ever had a need to use pointers other than for strings which were used in simulation to report info to the user or a file. I believe a string is a pointer type, no?

--

Rick C.

-- Get 1,000 miles of free Supercharging
-- Tesla referral code - https://ts.la/richard11209

[KJ]

The short answer to "where does Head point to when it is first delcared as "variable Head : Ptr" is that it points to nothing at all. For the somewhat longer answer, read on.

When you first declare a variable that is of type access (i.e. your statement "variable Head : Ptr;"), VHDL assigns the variable the 'value' null but it is not pointing to anything at that time. This would be different than in C/C++. For example, in C/C++ you can declare a pointer with "char *MyPtr;". In this situation, MyPtr is not guaranteed to be pointing to anything in particular. It is also not guaranteed to even be NULL. However, VHDL does guarantee that a declared but not explicitly initialized variable (or signal) will always have an initial value. For access type variables, this is defined in section 5.4.1 of the VHDL standard (Access types - General).

> For each access type, there is a literal null that has a null access value designating no object at all. The null value of an access type is the default initial value of the type

Thus the VHDL standard's answer to your question is, as I stated, "designating no object at all" meaning it doesn't 'point' to anything.

Following that the standard goes into the other values that an access type variable can take on. In the following sentence, an 'allocator' is something that allocates memory, much like 'new' or 'malloc' in C/C++.

> Other values of an access type are obtained by evaluation of a special operation of the type, called an allocator. Each such access value designates an object of the subtype defined by the subtype indication of the access type definition.

Kevin Jennings

[gnuarm.del...@gmail.com]

So is that the same as having the value NULL? Isn't NULL the indication of pointing to nothing?

If it were uninitialized, it could have any value at all. You've not said it is unitialized, and you have not said it contains NULL. "Pointing to nothing" is not clear unless you mean it contains a NULL. You even say "VHDL assigns the variable the 'value' null". So isn't that an adequate explanation rather than the much more wordy statement, "pointing to nothing"? That's the point of "null", it points to nothing.

--

Rick C.

-+ Get 1,000 miles of free Supercharging
-+ Tesla referral code - https://ts.la/richard11209

[KJ]

On Friday, January 27, 2023 at 9:08:16 AM UTC-5, gnuarm.del...@gmail.com wrote:
> On Friday, January 27, 2023 at 9:13:19 AM UTC-4, KJ wrote:
> > On Thursday, January 26, 2023 at 12:24:16 PM UTC-5, ashokm...@gmail.com wrote:
> > > On Wednesday, January 25, 2023 at 7:25:18 PM UTC-8, gnuarm.del...@gmail.com wrote:
> > > > On Wednesday, January 25, 2023 at 1:36:29 PM UTC-4, ashokm...@gmail.com wrote:
> > > > > On Tuesday, January 24, 2023 at 11:48:22 AM UTC-8, gnuarm.del...@gmail.com wrote:
> > > > > > On Tuesday, January 24, 2023 at 2:34:22 PM UTC-5, ashokm...@gmail.com wrote:

> So is that the same as having the value NULL? Isn't NULL the indication of pointing to nothing?
>

For your first question: The VHDL variable is an access type (similar to but not the same as a C/C++ pointer). That variable will have a value which can be the literal null per the standard. If the value of the variable is null, then the standard is saying that you can't access anything with the variable because there is no object to access (per standard "access value designating no object at all."). The ability (or inability) to access something in VHDL is not the same thing as being able to dereference a pointer in software.

For your second question: Yes.

> If it were uninitialized, it could have any value at all.

Not sure what "it" is that you are referring to but a VHDL variable will never have "any value at all". The OP's declaration of variable 'Head', because this is VHDL, means that the compiler will assign the value of null in the OP's code. The same would not be true for a similarly declared pointer in C/C++. In that situation, the C/C++ variable could have 'any value at all' and would be pointing to who knows what.

> You've not said it is unitialized, and you have not said it contains NULL.

The access type variable's value is the literal null (not the literal 0 or anything but 'null').

> "Pointing to nothing" is not clear unless you mean it contains a NULL.

I quoted the standard and then applied the interpretation that I thought would help the OP understand. What I said was

> "designating no object at all" meaning it doesn't 'point' to anything

> You even say "VHDL assigns the variable the 'value' null". So isn't that an adequate explanation rather than the much more wordy statement, "pointing to nothing"? That's the point of "null", it points to nothing.

Well if you didn't like the longer answer, you should have stopped at the short answer that I gave.

You and the OP have been going back and forth for a bit but the OP was still confused about "where does Head point to when it is first declared", so I was just suggesting an alternative explanation and quoting from the standard as the reference. Maybe it helps the OP understand, maybe not.

Kevin Jennings

[gnuarm.del...@gmail.com]

"it points to nothing at all" was your short answer. The rest of that post was the long answer. Neither were great answers. I believe a more useful answer would be that when created, the declaration

variable Head : Ptr;

Gives Head the value NULL.

If you had said this, instead of the less informative answer, "it points to nothing at all", (which may be perfectly accurate, but not so useful) I think that would have been the end of the conversation.

Have I misstated the nature of the ptr declaration?

--

Rick C.

+- Get 1,000 miles of free Supercharging
+- Tesla referral code - https://ts.la/richard11209

[KJ]

On Friday, January 27, 2023 at 11:25:19 AM UTC-5, gnuarm.del...@gmail.com wrote:
> On Friday, January 27, 2023 at 11:21:02 AM UTC-4, KJ wrote:
> > On Friday, January 27, 2023 at 9:08:16 AM UTC-5, gnuarm.del...@gmail.com wrote:
> > > On Friday, January 27, 2023 at 9:13:19 AM UTC-4, KJ wrote:
> > > > On Thursday, January 26, 2023 at 12:24:16 PM UTC-5, ashokm...@gmail.com wrote:
> > > > > On Wednesday, January 25, 2023 at 7:25:18 PM UTC-8, gnuarm.del...@gmail.com wrote:
> > > > > > On Wednesday, January 25, 2023 at 1:36:29 PM UTC-4, ashokm...@gmail.com wrote:
> > > > > > > On Tuesday, January 24, 2023 at 11:48:22 AM UTC-8, gnuarm.del...@gmail.com wrote:
> > > > > > > > On Tuesday, January 24, 2023 at 2:34:22 PM UTC-5, ashokm...@gmail.com wrote:

> "it points to nothing at all" was your short answer. The rest of that post was the long answer. Neither were great answers.

You left out the question that the OP asked which was "how do we know that Head is pointing to a node and that the node is null -before- assigning it new memory" and me saying that it points to nothing at all and that it is set to null seems pretty clear to me.

If you don't think my response is adequate, OK, but I wasn't responding to you, I was responding to the OP. When you had your chance with the OP your responses didn't clarify since he/she had the same question which resulted in the back and forth that the two of you had. Before criticizing my response, perhaps consider your own.

Kevin Jennings

[gnuarm.del...@gmail.com]

Don't be sensitive now. You pointed out that you didn't think I got to the point. I simply explained that you also missed the point in your very short reply, then went way far overboard with the subsequent exquisitely detailed full reply.

Just trying to help by pointing out that too much information is just as bad as too little.

Enjoy your weekend.

--

Rick C.

++ Get 1,000 miles of free Supercharging
++ Tesla referral code - https://ts.la/richard11209