#macro DynamicUserStackTypeCreate(typename, datatype)
Type typename
Public:
Declare Constructor () '' pre-allocating user stack memory for one element
Declare Property push (Byval i As datatype) '' pushing on the user stack
Declare Property pop () As datatype '' popping from the user stack
Declare Property used () As Integer '' outputting number of used elements in the user stack
Declare Property allocated () As Integer '' outputting number of allocated elements in the user stack
Declare Destructor () '' deallocating use stack memory
Private:
Dim As datatype Ptr pae '' pointer to allocated elements
Dim As Integer nue '' number of used elements
Dim As Integer nae '' number of allocated elements
End Type
Constructor typename ()
This.nue = 0
This.nae = 1
This.pae = Reallocate(This.pae, Sizeof(*This.pae)) '' pre-allocating user stack memory for one element
End constructor
Property typename.push (Byval i As datatype) '' pushing on the user stack
This.nue += 1
If This.nae < This.nue * 2 Then
This.nae *= 2
This.pae = Reallocate(This.pae, This.nae * Sizeof(*This.pae)) '' allocating user stack memory for double used elements at least
End If
This.pae[This.nue - 1] = i
End Property
Property typename.pop () As datatype '' popping from the user stack
If This.nue > 0 Then
Property = This.pae[This.nue - 1]
This.nue -= 1
If This.nae > This.nue * 2 Then
This.nae \= 2
This.pae = Reallocate(This.pae, This.nae * Sizeof(*This.pae)) '' allocating user stack memory for double used elements at more
End If
Else
Property = 0
Assertwarn(This.nue > 0) '' warning if popping while empty user stack and debug mode (-g compiler option)
End If
End Property
Property typename.used () As Integer '' outputting number of used elements in the user stack
Property = This.nue
End property
Property typename.allocated () As Integer '' outputting number of allocated elements in the user stack
Property = This.nae
End property
Destructor typename '' deallocating user stack memory
This.nue = 0
This.nae = 0
This.pae = Reallocate(This.pae, 0) '' deallocating user stack memory
End destructor
#endmacro
'----------------------------------------------------------------------------------------------------------------------------------------
DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)
Dim As DynamicUserStackTypeForInteger Ptr pdusi = New DynamicUserStackTypeForInteger
Screen 0
Width 80, 50
Print "DYNAMIC USER STACK ELEMENTS (Integers) PUSHING:"
Print "Value", "Nb of used", "Nb of allocated"
Print , pdusi->used, pdusi->allocated
For I As Integer = 1 To 20
pdusi->push = 100 + I
Print 100 + I, pdusi->used, pdusi->allocated
Next I
Print
Print "DYNAMIC USER STACK ELEMENTS (Integers) POPPING:"
Print "Value", "Nb of used", "Nb of allocated"
Print , pdusi->used, pdusi->allocated
For I As Integer = 1 To 20
Print pdusi->pop, pdusi->used, pdusi->allocated
Next I
Delete pdusi
Print
Sleep
Version using dynamic array, but working for any Type of data (using typed dynamic array simplifies the code compared to manage explicitly the construction/destruction of elements in memory):
#macro DynamicUserStackTypeCreate(typename, datatype)
Type typename
Public:
Declare Constructor () '' pre-allocating user stack memory for one element
Declare Property push (Byval i As datatype) '' pushing on the user stack
Declare Property pop () As datatype '' popping from the user stack
Declare Property used () As Integer '' outputting number of used elements in the user stack
Declare Property allocated () As Integer '' outputting number of allocated elements in the user stack
Declare Destructor () '' deallocating use stack memory
Private:
Dim As datatype ae (Any) '' array of elements
Dim As Integer nue '' number of used elements
Dim As Integer nae '' number of allocated elements
End Type
Constructor typename ()
This.nue = 0
This.nae = 1
Redim This.ae(This.nae - 1) '' pre-allocating user stack memory for one element
End constructor
Property typename.push (Byval i As datatype) '' pushing on the user stack
This.nue += 1
If This.nae < This.nue * 2 Then
This.nae *= 2
Redim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at least
End If
This.ae(This.nue - 1) = i
End Property
Property typename.pop () As datatype '' popping from the user stack
If This.nue > 0 Then
Property = This.ae(This.nue - 1)
This.nue -= 1
If This.nae > This.nue * 2 Then
This.nae \= 2
Redim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at more
End If
Else
Dim As datatype d
Property = d
Assertwarn(This.nue > 0) '' warning if popping while empty user stack and debug mode (-g compiler option)
End If
End Property
Property typename.used () As Integer '' outputting number of used elements in the user stack
Property = This.nue
End property
Property typename.allocated () As Integer '' outputting number of allocated elements in the user stack
Property = This.nae
End property
Destructor typename '' deallocating user stack memory
This.nue = 0
This.nae = 0
Erase This.ae '' deallocating user stack memory
End destructor
#endmacro
'----------------------------------------------------------------------------------------------------------------------------------------
Type UDT
Dim As Integer I
End Type
DynamicUserStackTypeCreate(DynamicUserStackTypeForUDT, UDT)
Dim As DynamicUserStackTypeForUDT Ptr pdusu = New DynamicUserStackTypeForUDT
Screen 0
Width 80, 50
Print "DYNAMIC USER STACK ELEMENTS (UDTs) PUSHING:"
Print "Value", "Nb of used", "Nb of allocated"
Print , pdusu->used, pdusu->allocated
For I As Integer = 1 To 20
pdusu->push = Type(100 + I)
Print 100 + I, pdusu->used, pdusu->allocated
Next I
Print
Print "DYNAMIC USER STACK ELEMENTS (UDTs) POPPING:"
Print "Value", "Nb of used", "Nb of allocated"
Print , pdusu->used, pdusu->allocated
For I As Integer = 1 To 20
Print pdusu->pop.I, pdusu->used, pdusu->allocated
Next I
Delete pdusu
Print
Sleep
Last edited by fxm on Nov 10, 2017 15:18, edited 1 time in total.
MrSwiss wrote:can you state, a mandatory use case, for "dynamic stack"?
(since total amount of stack is given (compiler settings), anyway)
You're mixing two different meanings of "stack": the implementation here refers to "stack" as common data type/structure in general. You are referring to "stack" as the memory area, that is reserved by the application loader e.g. to store local variables and arguments/return addresses related to function calls. That is also a stack, but quite a specific one. The stack is a common data type used in a lot of algorithms. See also https://en.wikipedia.org/wiki/Stack_(ab ... data_type)
Last edited by St_W on Nov 10, 2017 17:02, edited 1 time in total.
MrSwiss wrote:can you state, a mandatory use case, for "dynamic stack"?
(since total amount of stack is given (compiler settings), anyway)
You're mixing two different meanings of "stack": the implementation here refers to "stack" as common data type/structure in general. You are referring to "stack" as the memory area, that is reserved by the application loader e.g. to store local variables and arguments/return addresses related to function calls. That is also a stack, but quite a specific one. The stack is a common data type used in a lot of algorithms. See also https://en.wikipedia.org/wiki/Stack_(ab ... data_type)
Redim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at least
So is the objective here to make access to the stack a little faster by only resizing the array when it gets too large?
Is this a standard stack strategy or is this your own idea?
When resizing a dynamically allocated memory (with Reallocate, Redim), the memory location (address of the first item) may change (especially when the memory size is enlarged).
In this latter case, if the values in memory must be preserved (Redim Preserve), all of them must be copied to the new memory location. For large memory, this is a lot of time spent.
One solution is to resize the memory less often, but for this with a reserve of available memory (in addition to the size of the memory required at the time of resizing), in order to reduce the occurrence number of necessary resizing.
This principle of dynamic allocation with a reserve is already used by the compiler for the predefined type "String".
Macro version for dynamic user stack type, using dynamic array, working for any Type of data, and optimized for execution time (memory allocation with a dynamic reserve of memory and a minimum size of at least 1 MB):
#macro DynamicUserStackTypeCreate(typename, datatype)
Type typename
Public:
Declare Constructor () '' pre-allocating user stack memory
Declare Property push (Byref i As datatype) '' pushing on the user stack
Declare Property pop () Byref As datatype '' popping from the user stack
Declare Property used () As Integer '' outputting number of used elements in the user stack
Declare Property allocated () As Integer '' outputting number of allocated elements in the user stack
Declare Destructor () '' deallocating user stack memory
Private:
Dim As datatype ae (Any) '' array of elements
Dim As Integer nue '' number of used elements
Dim As Integer nae '' number of allocated elements
Dim As Integer nae0 '' minimum number of allocated elements
End Type
Constructor typename ()
This.nae0 = 2^Int(Log(1024 * 1024 / Sizeof(datatype)) / Log(2) + 1) '' only a power of 2 (1 MB < stack memory < 2 MB here)
This.nue = 0
This.nae = This.nae0
Redim This.ae(This.nae - 1) '' pre-allocating user stack memory
End constructor
Property typename.push (Byref i As datatype) '' pushing on the user stack
This.nue += 1
If This.nue > This.nae0 And This.nae < This.nue * 2 Then
This.nae *= 2
Redim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at least
End If
This.ae(This.nue - 1) = i
End Property
Property typename.pop () Byref As datatype '' popping from the user stack
If This.nue > 0 Then
Property = This.ae(This.nue - 1)
This.nue -= 1
If This.nue > This.nae0 And This.nae > This.nue * 2 Then
This.nae \= 2
Redim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at more
End If
Else
Static As datatype d
dim As datatype d0
d = d0
Property = d
Assertwarn(This.nue > 0) '' warning if popping while empty user stack and debug mode (-g compiler option)
End If
End Property
Property typename.used () As Integer '' outputting number of used elements in the user stack
Property = This.nue
End property
Property typename.allocated () As Integer '' outputting number of allocated elements in the user stack
Property = This.nae
End property
Destructor typename '' deallocating user stack memory
This.nue = 0
This.nae = 0
Erase This.ae '' deallocating user stack memory
End destructor
#endmacro