Linked List from the documentation problem

[sancho3]

I have a couple of questions regarding the linked list shown in the docs here
This list works well but I don't understand the extra code in the get previous node function:

Code: Select all

Function ListGetPrev(list As listnode Ptr) As listnode Ptr
    ' can't do anything to a null list
    If (list = 0) Then Return 0
    ' this is needed for below
    If (list->pPrev = 0) Then Return 0		' what is this and the line below for 
    ' since the list starts with a null node (pPrev and pData = 0),
    ' the first should be the one right after the real first.
    If (list->pPrev->pPrev = 0) Then Return 0

    Return list->pPrev
End Function

I understand that this list uses a null node as the base node. From there the first node is added and so on. What are those two extra lines preventing?

I also created an oop version:

Code: Select all

Type TListNode
    As Any Ptr pData
    As TListNode Ptr pNext
    As TListNode Ptr pPrev
End Type
Type TList 
	As TListNode Ptr null_node
	As Integer node_count
	
	Declare Constructor (ByRef node As TListNode Ptr = 0)
	Declare Destructor()
	Declare Function add_item(ByVal item As Any Ptr) As Any Ptr
	Declare Function add_head(ByVal item As Any Ptr) As Any Ptr
	Declare Function get_first_item() As TListNode Ptr
	Declare Function get_last_item() As TListNode Ptr
	Declare Function get_next_item(ByVal node As TListNode Ptr) As TListNode Ptr
	Declare Function get_prev_item(ByVal node As TListNode Ptr) As TListNode Ptr
	Declare Function get_data(ByVal node As TListNode Ptr) As Any Ptr
	Declare Function remove_item(ByVal node As TListNode Ptr, ByVal bDelete As boolean = 0) As TListNode Ptr
	Declare Sub remove_all(ByVal bDelete As boolean = 0)

End Type
Destructor TList()
	'
	Dim As TListNode Ptr node
	
	this.remove_all(TRUE)
	DeAllocate(this.null_node)	
	this.null_node = 0
End Destructor
Function TList.add_head(ByVal item As Any Ptr) As Any Ptr
	Dim As TListNode Ptr pTemp
	
	If (this.null_node = 0) Then Return 0
	
	pTemp = this.null_node->pNext
	this.null_node->pNext = CAllocate(Len(TListNode))
	
	this.null_node->pNext->pPrev = this.null_node
	this.null_node->pNext->pData = item
	this.null_node->pNext->pNext = pTemp
	
	If (pTemp <> 0) Then
	  pTemp->pPrev = this.null_node->pNext
	End If
	
	Return item
End Function
Sub TList.remove_all(ByVal bDelete As boolean = FALSE)
	' does not remove null node
	Dim As TListNode Ptr node, pTemp
	 	
	node = this.get_last_item()
	While node <> 0 And node <> this.null_node
		pTemp = node->pPrev
		If (cbool(node->pData <> 0) = TRUE AndAlso (bDelete = TRUE)) Then 
			DeAllocate node->pData
			node->pData = 0        	
		EndIf
		
		this.remove_item(node)
		node = pTemp
	Wend
End Sub

Function TList.remove_item(ByVal node As TListNode Ptr, ByVal bDelete As boolean = 0) As TListNode Ptr
	Dim As TListNode Ptr pPrev
	Dim As TListNode Ptr pNext
	
	If (node = 0) Then Return 0
	
	pPrev = node->pPrev
	pNext = node->pNext
	
	If (cbool(node->pData <> 0) = TRUE  AndAlso (bDelete = FALSE)) Then 
		Deallocate node->pData
		node->pData = 0				
	EndIf

	
	DeAllocate node
	node = 0
	
	If (pPrev <> 0) Then
	  pPrev->pNext = pNext
	End If
	If (pNext <> 0) Then
	  pNext->pPrev = pPrev
	End If
	
	this.node_count -= 1	
	Return pNext

End Function

Function TList.get_next_item(ByVal node As TListNode Ptr) As TListNode Ptr
    If (node = 0) Then Return 0

    Return node->pNext
End Function

Function TList.get_prev_item(ByVal node As TListNode Ptr) As TListNode Ptr
    ' can't do anything to a null list
    If (node = 0) Then Return 0
    ' this is needed for below
    'If (list->pPrev = 0) Then Return 0
    '' since the list starts with a null node (pPrev and pData = 0),
    '' the first should be the one right after the real first.
    'If (node->pPrev->pPrev = 0) Then Return 0

    Return node->pPrev
End Function
Function TList.get_first_item() As TListNode Ptr
    If (this.null_node = 0) Then Return 0

    Return this.null_node->pNext
End Function
Function TList.get_data(ByVal node As TListNode Ptr) As Any Ptr
    If (this.null_node = 0) Then Return 0

    Return node->pData
End Function
Function TList.get_last_item() As TListNode Ptr
    Dim As TListNode Ptr pTemp

    If (this.null_node = 0) Then Return 0

    pTemp = this.null_node
    While (pTemp->pNext <> 0)
        pTemp = pTemp->pNext
    Wend

    Return pTemp
End Function
Function TList.add_item(ByVal item As Any Ptr) As Any Ptr
	Dim As TListNode Ptr pTemp
	
	If (this.null_node = 0) Then Return 0 	'item
	
	pTemp = this.get_last_item()
	
	pTemp->pNext = CAllocate(Len(TListNode))
	pTemp->pNext->pPrev = pTemp
	pTemp->pNext->pData = item
	
	this.node_count += 1
	Return item
End Function
Constructor TList(ByRef node As TListNode Ptr = 0)
	' this doubles as default constructor
    Dim As TListNode Ptr pTemp
    this.null_node = CAllocate(Len(TListNode))
    node = this.null_node
	'? "ppp";node
End Constructor
'----------------------------------------------------------------------------------------------------------------
'----------------------------------------------------------------------------------------------------------------
Dim As TList list
Dim As String Ptr item ', test
Dim As tlistnode Ptr test
'
item = list.add_item(Callocate(Len(String)))
*item = "hello"
item = list.add_item(Callocate(Len(String)))
*item = "world"
item = list.add_item(Callocate(Len(String)))
*item = "moo"
'
test = list.get_first_item()
item = list.get_data(test)
? *item
test = list.get_last_item()
item = list.get_data(test)
? *item
sleep

In my version I comment out the code that I don't understand and it still works.
Is my version flawed?

I also tried another version where I replaced callocate and deallocate with new and delete
But since this is using any ptr as the node type, in the destructor there is no way to determine what type the node data is.
Trying to delete an any ptr gives you a warning (undefined). In my testing I believe that the pointer was in fact not deleted.
This is a very generic list and can contain different types in the same list. Is there a way to use new/delete in this list?
I have seen the macro work around for generic types. Is that the only way?

[grindstone]

I understand that this list uses a null node as the base node. From there the first node is added and so on. What are those two extra lines preventing?

In the examples the parameter name "list" is a little ambiguous. While in ListGetFirst and ListGetLast "list" is the pointer to the null node, in ListGetPrev "list" can point to any node of the list.

In the tutorial's list type neither the null node nor the first node can have a predecessor. So

Code: Select all

If (list->pPrev = 0) Then Return 0

detects you are accessing the null node, and

Code: Select all

If (list->pPrev->pPrev = 0)

detects you are accessing the first node.

I also tried another version where I replaced callocate and deallocate with new and delete
But since this is using any ptr as the node type, in the destructor there is no way to determine what type the node data is.

That isn't right.

Code: Select all

New TListNode

returns a TListNode Ptr. The disadvantage of New compared to Callocate is that the memory isn't zeroed, so I would recommend using Callocate rather than New.

At a first glance your TList Type seems to be OK, but your test program isn't quite correct, although it partially works:

Code: Select all

Dim As TList list
Dim As String item(3) ', test
Dim As tlistnode Ptr test
'
item(1) = "hello"
item(2) = "world"
item(3) = "moo"

list.add_item(StrPtr(item(1)))
list.add_item(StrPtr(item(2)))
list.add_item(StrPtr(item(3)))

test = list.get_first_item()
? *Cast(ZString Ptr, list.get_data(test))
test = list.get_next_item(test)
? *Cast(ZString Ptr, list.get_data(test))
test = list.get_last_item()
? *Cast(ZString Ptr, list.get_data(test))

Sleep

[fxm]

The disadvantage of New compared to Callocate is that the memory isn't zeroed, so I would recommend using Callocate rather than New.

When calling NEW without ANY in the syntax, and neither as initializer for the data fields if it's an object, the corresponding data are initialized by default (zeroed for numeric data), and constructed if it's an object with constructor.

[grindstone]

In this case, using New / Delete shouldn't cause any problems.

@sancho3: I strongly recommend NOT to Delete nor Deallocate pData from inside TList.remove_all because it points to some thing that was created outside of the TList type, and the procedure has no information about what kind of data it points to and thus the amount of memory that should be freed (that's why it is stated "undefined").

[fxm]

@sancho3: I strongly recommend NOT to Delete nor Deallocate pData from inside TList.remove_all because it points to some thing that was created outside of the TList type.

I approve this completely.

[sancho3]

In the examples the parameter name "list" is a little ambiguous.

Yes, I noticed that as well.

IIn the tutorial's list type neither the null node nor the first node can have a predecessor. So

Code: Select all

If (list->pPrev = 0) Then Return 0

detects you are accessing the null node, and

Code: Select all

If (list->pPrev->pPrev = 0)

detects you are accessing the first node.

Ok, I did some tests and found that my version was allowing access to (first node)->previous node and (null node)->previous node. This must be prevented.

I strongly recommend NOT to Delete nor Deallocate pData from inside TList.remove_all because it points to some thing that was created outside of the TList type,

This makes sense. That is what the boolean parameter was for in the tutorial code. I can see that this is not a good design decision.
Since I'm not going to delete the pData pointer in the TList object then that resolves the undefined issue.

Thank you.

[sancho3]

I have a class named TTokenizer that extends the TList class.
I create a token instance using the New keyword and add it to the list via this:

Code: Select all

Function TTokenizer._add_token(ByRef tkn As TToken Ptr, ByRef tl As Const TTokenizer) As ULongInt 
	' this is a static function so I can create a pointer to it in other places (this might change)
	Dim As TToken Ptr t 

	t = tl.add_item(New TToken)
	*t = *tkn
	t->line_number = tl._char_line
	t->token_index = tl.node_count

	Return tl.node_count

End Function 

Now when destroying TTokenizer I loop through all the nodes in the list and use the Delete keyword to delete
the pData data. Then I use the TList.remove_all() function to remove all the items and finally I deallocate
the null node.
I'm worried about the Delete Cast(TToken Ptr, n->pData) statement in the following destructor.
Is this actually working?

Code: Select all

Destructor TTokenizer()
	'
	Dim As TToken Ptr t
	Dim As TListNode Ptr n
	n = this.get_last_item
	While n <> 0 
			
		Delete Cast(TToken Ptr, n->pData)
		n->pData = 0
		n = n->pPrev
	Wend
	
	this.remove_all()
	?
	? "tokenizer destructor called"
End Destructor

[fxm]

To be able to give an opinion on your query, the whole code would be welcome.

[sancho3]

I was hoping I had shown enough info.
The whole code is way to big to post. Its 2000 lines not including the TList I have posted here already.

But the question boils down to this. In the following code is the pointer being deleted?

Code: Select all

dim as integer x = 12
dim as integer ptr n, y

n = new integer
n = @x
?n
y = n
? y

delete y
? *n

I think the pointer is deallocated because the last line leads to abnormal termination.

[fxm]

I was hoping I had shown enough info.

You 'DELETE' a 'TToken' pointer (unknown type).

'DELETE pointer' destroys data referenced by the provided pointer value (the pointer type being the same as the data type to destroy). The pointer itself is not destroyed.
'DELETE' only applies on data created by 'New' (dynamic data).
'DELETE' cannot apply on static data (created by 'DIM').

In your short above code, the 'INTEGER' created by 'NEW' induces memory leak because it is never destroyed (its address is overwritten by the address of 'x') and 'DELETE n' (with ptr n=@x) is irrelevant because 'x' was not created by 'NEW'.

On the other hand, this works:

Code: Select all

dim byref as integer x = *new integer

? @x, x

x = 12
? @x, x

delete @x
? @x, x

[sancho3]

Sadly I gave a poor example.
This is what I was going for:

Code: Select all

Dim As Integer Ptr n = New Integer
Dim As Integer ptr y
*n = 12
y = n
? *n, n, *y, y
Delete y
? *n, n, *y, y
sleep

In this code is Delete y deleting the n pointer data? Is it the same as Delete n?
In looking at your code Delete @x, you are sending the Delete keyword an address. This tells me that in
my code above, the data associated with pointer n is being deleted since y contains the same address as n.

In VB6 if you had a reference to an instance object you would use the following code to delete it.

Code: Select all

set myobject = nothing 

However if you had any other variable pointing to that instance the instance would not be deleted.

Code: Select all

set myobject = new some_object
set another_var = myobject 
set myobject = nothing  ' this would not delete the instance because it is still held in another_var

Although a reference variable in VB is not the same as a pointer in FB, this is why I wonder if the memory
created with New is being released if I am not using Delete on the original variable.

Here is the TToken class. It contains no pointers and allocates no memory. It contains one other object
that is TLocation which is just a pair of integers and overloaded operators:

Code: Select all

Type TLocation
	As ULongInt first_char
	As ULongInt last_char
	Declare Operator Cast () As String
	Declare Operator Let(ByVal i As UByte)
End Type
Operator TLocation.Let(ByVal i As UByte)
	this.first_char = i
	this.last_char = i
End Operator
Operator TLocation.Cast() As String 
	Return Str(first_char) & ", " & Str(last_char)
End Operator
Operator Len(ByRef tl As Const TLocation ) As Integer
	Return tl.last_char - tl.first_char + 1
End Operator
'----------------------------------------------------------------------------------------------------------------------
Type TToken
	As TokenType token_type		' TokenType is an enum 
	As TLocation index
	As ULongInt token_index
	As ULongInt line_number 

	Declare Function get_length() As ULong		
	Declare Constructor
	Declare Constructor(ByVal tk_txt As Any Ptr, ByRef tk_type As Const TokenTYpe, _ 
						 ByRef tk_start As Const ULongInt, ByRef tk_end As Const ULongInt)  

	Declare Constructor(ByRef tk_txt As Const byte, ByRef tk_type As Const TokenTYpe, _ 
						 ByRef tk_start As Const ULongInt, ByRef tk_end As Const ULongInt)  

	Declare Operator Cast() As String
	Declare Operator Let(ByVal i As Double)  
	Declare Operator Let(ByVal tt As TokenType)
End Type
Operator TToken.Let(ByVal tt As TokenType)
	'
	this.token_type = tt
End Operator
Operator TToken.Let(ByVal i As Double)
	'
	With This 
		If i = 0 Then
			.token_type = 0
			.index = 0		
		EndIf
	End With
	
End Operator 

Constructor TToken()
	'
	this.token_type = ttUnknown
End Constructor
Constructor TToken(ByRef tk_txt As Const Byte, ByRef tk_type As Const TokenType, _ 
						 ByRef tk_start As Const ULongInt, ByRef tk_end As Const ULongInt)
	'
	With This
		.token_type = tk_type
		.index = Type<TLocation>(tk_start, tk_end)
	End With

End Constructor
Constructor TToken(ByVal tk_txt As Any Ptr, ByRef tk_type As Const TokenType, _ 
						 ByRef tk_start As Const ULongInt, ByRef tk_end As Const ULongInt)
	'
	 With This
		.token_type = tk_type
		.index = Type<TLocation>(tk_start, tk_end)
	 End With
	 
End Constructor 						   

Function TToken.get_length() As ULong 
	'
	Return this.index.last_char - this.index.first_char + 1
End Function 

[fxm]

In this code is Delete y deleting the n pointer data? Is it the same as Delete n?
In looking at your code Delete @x, you are sending the Delete keyword an address. This tells me that in
my code above, the data associated with pointer n is being deleted since y contains the same address as n.

Yes, you can destroy with 'DELETE' a dynamic object (constructed with 'NEW') by using another pointer than at the creation step as long as it has both the good type and the good value.