Generic Macro for Dynamic User Stack Type

[fxm]

Only for any standard numeric datatype:

Code: Select all

#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

[fxm]

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):

Code: Select all

#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

[fxm]

When submitting the above post, freebasic.net just asked me to confirm that I am not a robot!
This is the first time this has happened on the website.

[MrSwiss]

@fxm,

can you state, a mandatory use case, for "dynamic stack"?
(since total amount of stack is given (compiler settings), anyway)

[St_W]

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)

[fxm]

My user stack does not use the program stack.
My user stack is allocated at runtime in the heap (memory for dynamic allocation).

[MrSwiss]

My user stack does not use the program stack. My user stack is allocated at runtime in the heap...

Thanks, that clears it.

[fxm]

With a working link:

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)

[sancho3]

Code: Select all

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?

[fxm]

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".

[fxm]

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):

Code: Select all

#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