Dynamic ArrayList (with circular doubly linked list under the hood)

[fxm]

About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)

Using this new destruction member method, compared to a user destruction loop (user data destruction + element destruction in a same loop), allows to gain a factor of about 30% on the destruction time.
Should we then validate this idea?

Test code with the file to include modified accordingly:

Code: Select all

' DynamicArrayList.bi modified

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    ' Allocates memory for new node
    Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
    If newNodePtr = 0 Then Return 0
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    ' Deallocates memory for the node
    Deallocate(searchNodePtr)
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        ' Allocates memory for new node
        Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return This.nbrUserNode
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            Deallocate(nodePtr->prevNodePtr)
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            Deallocate(nodePtr->prevNodePtr)
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one  by transverse access
    This.DestroyAllNthPosition()
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   ";
    For I As Integer = 1 To 5
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print " .....";
    For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print
End Sub

Sub destroy(ByVal p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Integer position
    
    Dim As DynamicArrayList dal1
    Dim As DynamicArrayList dal2
    Print "Two Dynamic ArrayLists pointing to """ & N & """ dynamic integers :"
    For I As Integer = 1 To N
        dal1.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal1)
    For I As Integer = 1 To N
        dal2.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal2)
    Print
    Print "   Time to destroy all elements + the dynamic user data :"
    Print "      - by using a user loop for the first Dynamic ArrayList :"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal1.SuppressTheNthPosition(1))
    Next i
    Print "         " & Timer - t & " s"
    Print "      - by using the member method for the second Dynamic ArrayList :"
    t = Timer
    dal2.DestroyAllNthPosition(@destroy)
    Print "         " & Timer - t & " s"
End Sub

Test(1000000)
Print "--------------------------------------------------------------------"
Test(3000000)
Print "--------------------------------------------------------------------"
Test(5000000)
Print "--------------------------------------------------------------------"
Test(7000000)
Print "--------------------------------------------------------------------"
Test(9000000)

Sleep

• Output example:

  Code: Select all

  Two Dynamic ArrayLists pointing to "1000000" dynamic integers :
      1 2 3 4 5 ..... 999996 999997 999998 999999 1000000
      1 2 3 4 5 ..... 999996 999997 999998 999999 1000000
  
     Time to destroy all elements + the dynamic user data :
        - by using a user loop for the first Dynamic ArrayList :
           0.1290565999519799 s
        - by using the member method for the second Dynamic ArrayList :
           0.08200879994598154 s
  --------------------------------------------------------------------
  Two Dynamic ArrayLists pointing to "3000000" dynamic integers :
      1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000
      1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000
  
     Time to destroy all elements + the dynamic user data :
        - by using a user loop for the first Dynamic ArrayList :
           0.3774869000394574 s
        - by using the member method for the second Dynamic ArrayList :
           0.2655347000473967 s
  --------------------------------------------------------------------
  Two Dynamic ArrayLists pointing to "5000000" dynamic integers :
      1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000
      1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000
  
     Time to destroy all elements + the dynamic user data :
        - by using a user loop for the first Dynamic ArrayList :
           0.6417374999850267 s
        - by using the member method for the second Dynamic ArrayList :
           0.4314474999961249 s
  --------------------------------------------------------------------
  Two Dynamic ArrayLists pointing to "7000000" dynamic integers :
      1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000
      1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000
  
     Time to destroy all elements + the dynamic user data :
        - by using a user loop for the first Dynamic ArrayList :
           0.8864024000415611 s
        - by using the member method for the second Dynamic ArrayList :
           0.6022076999993828 s
  --------------------------------------------------------------------
  Two Dynamic ArrayLists pointing to "9000000" dynamic integers :
      1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
      1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
  
     Time to destroy all elements + the dynamic user data :
        - by using a user loop for the first Dynamic ArrayList :
           1.11212479997738 s
        - by using the member method for the second Dynamic ArrayList :
           0.7666473000202814 s
  

I would prefer to add this member method to the DynamicArrayList structure, which makes it easier for the user to manually destroy the list elements and its associated data if necessary.

[fxm]

About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)

Added the member method 'Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)' in the 'DynamicArrayList' type:
- To destroy in one shoot all elements of the list, the user can call this member procedure, passing as optional argument a user procedure (callback) to also destroy (if necessary) from the member procedure internal loop his own dynamic data at the same time than the list elements.

These 3 posts have been updated.

[fxm]

- For a preserved dynamic array, inserting (or deleting) an element at the end of the array is the best case in terms of execution time, otherwise it can be much worse when the insertion (or deletion) position is far from the end because all elements from the insertion position (or after the deletion position) have additionally to be shifted.
- For the Dynamic ArrayList, the insertion (or deletion) position has almost no effect on the execution time.

Test code:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintArray(array() As Integer)
    Print "            array:";
    If (Ubound(array) + 1) = 0 Then
        Print " empty";
    Elseif (Ubound(array) + 1) <= 10 Then
        For I As Integer = 0 To Ubound(array)
            Print array(I);
        Next I
    Else
        For I As Integer = 1 To 5
            Print array(I - 1);
        Next I
        Print " .....";
        For I As Integer = Ubound(array) - 4 To Ubound(array)
            Print array(I);
        Next I
    End If
    Print
End Sub

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Long array()
    Dim As DynamicArrayList dal
    
    Print
    Print "Preserved dynamic array of integers:"
    Print "   By acting only from the end of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        Redim Preserve array(Ubound(array) + 1)
        array(Ubound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "   By acting only from the beginning of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    Redim Preserve array(Ubound(array) + 1)
    array(Lbound(array)) = 1
    For I As Integer = 2 To N
        Redim Preserve array(Ubound(array) + 1)
        FB_Memmove(array(Lbound(array) + 1), array(Lbound(array)), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        array(Lbound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        FB_Memmove(array(Lbound(array)), array(Lbound(array) + 1), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print
    
    Print "Dynamic ArrayList pointing to dynamic integers:"
    Print "   By acting only from the end of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "   By acting only from the beginning of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 1)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print
End Sub

Test(5000)
Print "--------------------------------------------------------------------"
Test(10000)
Print "--------------------------------------------------------------------"
Test(30000)
Print "--------------------------------------------------------------------"
Test(60000)

Sleep

• Output example:

  Code: Select all

  Preserved dynamic array of integers:
     By acting only from the end of the array:
        Time to increase the array step by step up to 5000 elements:
           0.0006975000759439354 s
              array: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
        Time to decrease the array step by step up to 0 element:
           0.0004722000704759921 s
              array: empty
     By acting only from the beginning of the array:
        Time to increase the array step by step up to 5000 elements:
           0.006149299884668835 s
              array: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
        Time to decrease the array step by step up to 0 element:
           0.005664100097419578 s
              array: empty
  
  Dynamic ArrayList pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 5000 elements:
           0.001034800063621333 s
              list: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
        Time to decrease the list step by step, up to 0 element:
           0.000546199929544855 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 5000 elements:
           0.001758899901801669 s
              list: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
        Time to decrease the list step by step, up to 0 element:
           0.0006361998839565786 s
              list: empty
  
  --------------------------------------------------------------------
  
  Preserved dynamic array of integers:
     By acting only from the end of the array:
        Time to increase the array step by step up to 10000 elements:
           0.001257399970768347 s
              array: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
        Time to decrease the array step by step up to 0 element:
           0.001068000088025656 s
              array: empty
     By acting only from the beginning of the array:
        Time to increase the array step by step up to 10000 elements:
           0.0219928001037033 s
              array: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
        Time to decrease the array step by step up to 0 element:
           0.02092620003111278 s
              array: empty
  
  Dynamic ArrayList pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 10000 elements:
           0.002987899914046466 s
              list: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
        Time to decrease the list step by step, up to 0 element:
           0.001579099906393822 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 10000 elements:
           0.00231859990446992 s
              list: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
        Time to decrease the list step by step, up to 0 element:
           0.001407299953825714 s
              list: empty
  
  --------------------------------------------------------------------
  
  Preserved dynamic array of integers:
     By acting only from the end of the array:
        Time to increase the array step by step up to 30000 elements:
           0.003644799999847237 s
              array: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
        Time to decrease the array step by step up to 0 element:
           0.002756000055342156 s
              array: empty
     By acting only from the beginning of the array:
        Time to increase the array step by step up to 30000 elements:
           0.2054611000864952 s
              array: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
        Time to decrease the array step by step up to 0 element:
           0.2067085000668385 s
              array: empty
  
  Dynamic ArrayList pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 30000 elements:
           0.007203299971251909 s
              list: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
        Time to decrease the list step by step, up to 0 element:
           0.006684799898835081 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 30000 elements:
           0.00683309997282322 s
              list: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
        Time to decrease the list step by step, up to 0 element:
           0.005087799908778834 s
              list: empty
  
  --------------------------------------------------------------------
  
  Preserved dynamic array of integers:
     By acting only from the end of the array:
        Time to increase the array step by step up to 60000 elements:
           0.009835400026190655 s
              array: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
        Time to decrease the array step by step up to 0 element:
           0.007979600000567189 s
              array: empty
     By acting only from the beginning of the array:
        Time to increase the array step by step up to 60000 elements:
           0.7594995999510274 s
              array: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
        Time to decrease the array step by step up to 0 element:
           0.7474576999555893 s
              array: empty
  
  Dynamic ArrayList pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 60000 elements:
           0.01554709993968117 s
              list: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
        Time to decrease the list step by step, up to 0 element:
           0.01119940009459697 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 60000 elements:
           0.01170210008638151 s
              list: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
        Time to decrease the list step by step, up to 0 element:
           0.008671499908473379 s
              list: empty
  

  In the above results, for inserting/suppressing elements:
  - When using a preserve array, acting from the array beginning compared to acting from the array end increases the exécution time by a factor 10 to 100 depending on array size.
  - When using the Dynamic ArrayList, there is not notable difference in execution time between acting from the list beginning and acting from the list end, and this whatever the list size.

[fxm]

Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.

Only this post has been updated.

[shadow008]

Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.

I had done this test myself in the past on personal projects, but this was on allocations of 100s to 10,000s of items only. The resulting segment allocations were usually <10KB in size, and I had seen barely measurable performance difference. I had came to the conclusion:

1. Callocate effectively loaded the entire memory segment into cache as part of zeroing out the segment
2. The segments usually fit into L1 cache
3. Therefore, the only difference between Allocate + fill and Callocate + fill was the additional iteration over the callocated segment, which was entirely in low level cache, and thus did not make any considerable performance difference.

At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?

[fxm]

At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?

Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).

[fxm]

At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?

Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).

Simple example with only the 'CAllocate' / 'Allocate' time taken into account:

Code: Select all

#define allocNbr 10000000

Dim As Double t
Redim As Any Ptr parray(1 To allocNbr)

For N As Integer = 1 To 5
    Print "Time for " & allocNbr & " 'Callocate' of 3 pointers each : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, 3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I

    Print "Time for " & allocNbr & " 'Allocate' of 3 pointers each  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    Print
Next N

Erase parray
Sleep

• Output example:

  Code: Select all

  Time for 10000000 'Callocate' of 3 pointers each : 0.7727757000153872 s
  Time for 10000000 'Allocate' of 3 pointers each  : 0.5569001999748195 s
  
  Time for 10000000 'Callocate' of 3 pointers each : 0.7536964999775364 s
  Time for 10000000 'Allocate' of 3 pointers each  : 0.5533465999784255 s
  
  Time for 10000000 'Callocate' of 3 pointers each : 0.7513144000059526 s
  Time for 10000000 'Allocate' of 3 pointers each  : 0.560658500011499 s
  
  Time for 10000000 'Callocate' of 3 pointers each : 0.7622070999868811 s
  Time for 10000000 'Allocate' of 3 pointers each  : 0.5542497999804255 s
  
  Time for 10000000 'Callocate' of 3 pointers each : 0.7434600999982592 s
  Time for 10000000 'Allocate' of 3 pointers each  : 0.5390733000285479 s
  

  Speedup of about 25% here.

Note: it is surprising when using 'New', we find an execution time comparable to that of 'Allocate' (better than 'CAllocate'), while the memory is set to 0.
Example with an UDT of 3 pointers to be compatible with 'New':

Code: Select all

#define allocNbr 10000000

Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type

Dim As Double t
Redim As DoublyLinkedNode Ptr parray(1 To allocNbr)

For N As Integer = 1 To 3
    Print "Time for " & allocNbr & " 'Callocate' of UDT (3 pointers) : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'Allocate' of UDT (3 pointers)  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'New' of UDT (3 pointers)       : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = New DoublyLinkedNode
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Delete'     : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Delete(parray(I))
    Next I
    t = Timer - t
    Print t & " s"
    Print
Next N

Erase parray
Sleep

• Output example:

  Code: Select all

  Time for 10000000 'Callocate' of UDT (3 pointers) : 0.9042052000002663 s
     Time for 10000000 'Deallocate' : 0.3417718000007319 s
  Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6365616000034109 s
     Time for 10000000 'Deallocate' : 0.3315588000019929 s
  Time for 10000000 'New' of UDT (3 pointers)       : 0.6527570999982508 s
     Time for 10000000 'Delete'     : 0.4361705000013423 s
  
  Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7977705999997653 s
     Time for 10000000 'Deallocate' : 0.3519302000023714 s
  Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6200587000020903 s
     Time for 10000000 'Deallocate' : 0.341211499998618 s
  Time for 10000000 'New' of UDT (3 pointers)       : 0.6394830000023006 s
     Time for 10000000 'Delete'     : 0.4483076000033428 s
  
  Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7915781999985043 s
     Time for 10000000 'Deallocate' : 0.3403417999994574 s
  Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6272025000029693 s
     Time for 10000000 'Deallocate' : 0.3491629999966825 s
  Time for 10000000 'New' of UDT (3 pointers)       : 0.6726065999964668 s
     Time for 10000000 'Delete'     : 0.4498922999965451 s
  

[fxm]

Dynamic ArrayList: Pre-allocating memory for nodes ('DynamicArrayListWithPreAlloc.bi')

I tested the possibility of using pre-allocated memory for the nodes, in order to improve the execution time for inserting and suppressing positions in the list.
The user can set the number of pre-allocated nodes using an optional parameter at construction time.

Only a rudimentary pre-allocation of nodes can be used to obtain speed up of performance:
- individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated (no time to scan the allocated memory to find a free node),
- if all pre-allocated nodes are freed, the full pre-allocation memory becomes back available,
- pre-allocated memory block cannot be resized (no time to readjust the pointers of all used nodes in allocated memory block),
- once that the end of the pre-allocated memory for nodes is reached, the next nodes are allocated individually.

Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

- DynamicArrayListWithPreAlloc.bi:

Code: Select all

' DynamicArrayListWithPreAlloc.bi

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(Byval nbrPreAlloc As Integer)
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        If This.nbrPreAllocUsed = 0 Then This.preAllocNbr = 0
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(Byval nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor

- Test code:

Code: Select all

#include "DynamicArrayListWithPreAlloc.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub destroy(Byval p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    
    Scope
        Print "Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal
        For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope

    Scope
        Print "Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal = DynamicArrayList(N)
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope
End Sub

Test(9000000)

Sleep

• Output example:

  Code: Select all

  Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 9000000 elements:
           1.498154600001138 s
              list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
        Time to decrease the list step by step, up to 0 element:
           1.025472899999013 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 9000000 elements:
           1.406190900000343 s
              list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
        Time to destroy the list in one shoot:
           0.7894261999986991 s
              list: empty
  
  Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:
     By acting only from the end of the list:
        Time to increase the list step by step, up to 9000000 elements:
           0.9478515000013648 s
              list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
        Time to decrease the list step by step, up to 0 element:
           0.7321279999994452 s
              list: empty
     By acting only from the beginning of the list:
        Time to increase the list step by step, up to 9000000 elements:
           0.9181955000000759 s
              list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
        Time to destroy the list in one shoot:
           0.5359600999990555 s
              list: empty