Dynamic array of long integers module

[franchsesko]

Hi,

I recently wrote this module to be able to have dynamic arrays of long integers (PB Long type) in structures.
Its a kind of stack to which you give an initial size (DALCreate()) and that automatically grows when pushing Longs (DALPushLong()).
Longs can be set/retrieved (DALSetLong()/DALGetLong()) with a direct index (0..size-1).

I'm not at ease with macros, so its a "code only" solution.
Also I guess my TLongArrayData is not used in this version, except to type the pointer.
I thought I would share it as it is one of my early works in PB (meaning done in 2018 ), so I'll appreciate any comments or feedback.
Sorry I left my "OutputDebugString_" lying around...

(Short) Sample use:

Code: Select all

UseModule MDynArray

Procedure Test()
  Protected.TLongDynArray tArray
  Protected.w wRet
  Protected.l lValue
  wRet = DALCreate(@tArray, 5, 5)
  wRet = DALPushLong(@tArray, 101)
  DALPopLong(@tArray, @lValue)
  OutputDebugString_("pop="+ Str(lValue)) ; outputs pop=101
  DALDelete(@tArray)
EndProcedure

And the module:

Code: Select all

EnableExplicit

DeclareModule MDynArray
  Structure TLongArrayData
    aData.l[0]
  EndStructure
  
  Structure TLongDynArray
    iCount.i
    iSize.i
    iGrowSize.i
    *pData.TLongArrayData
  EndStructure
  
  ; DAL - Dynamic Array of Longs
  Declare.w DALCreate(*ptArray.TLongDynArray, piInitialSize.i, piGrowSize.i = 100)
  Declare   DALClear(*ptArray.TLongDynArray)
  Declare   DALDelete(*ptArray.TLongDynArray)
  Declare.i DALGetCount(*ptArray.TLongDynArray)
  Declare.i DALGetSize(*ptArray.TLongDynArray)
  Declare   DALGetLong(*ptArray.TLongDynArray, piIndex.i, *plRetLong)
  Declare   DALSetLong(*ptArray.TLongDynArray, piIndex.i, plValue.l)
  Declare.i DALPushLong(*ptArray.TLongDynArray, plValue.l)
  Declare.w DALPopLong(*ptArray.TLongDynArray, *plRetLong)
  Declare.w DALRemoveFirst(*ptArray.TLongDynArray, plValue.l)
  Declare.i DALFindFirst(*ptArray.TLongDynArray, plValue.l)
EndDeclareModule

Module MDynArray ; 0 (zero) based arrays
  EnableExplicit
  
  ; this will return 0 if problem or 1 if ok
  Procedure.w DALCreate(*ptArray.TLongDynArray, piInitialSize.i, piGrowSize.i = 100)
    *ptArray\iCount = 0
    *ptArray\iSize = 0
    *ptArray\iGrowSize = piGrowSize
    If piInitialSize <=0 ; defensive
;       OutputDebugString_("DALCreate(): initial size <= 0") ; /**/
      ProcedureReturn 0
    EndIf
;     OutputDebugString_("DALCreate(): requesting memory size: " + Str( SizeOf(Long) * piInitialSize ))
    *ptArray\pData = AllocateMemory(SizeOf(Long) * piInitialSize)
    If *ptArray\pData = 0
;       OutputDebugString_("DALCreate(): failed to allocate memory") ; /**/
      ProcedureReturn 0
    EndIf
    *ptArray\iSize = piInitialSize
;     OutputDebugString_("DynArray Size=" + Str(piInitialSize) + " (" + MemorySize(*ptArray\pData) + " bytes), GrowSize=" +Str(piGrowSize) + ") created.") ; /**/
    ProcedureReturn 1
  EndProcedure
  
  Procedure DALClear(*ptArray.TLongDynArray)
    *ptArray\iCount = 0
  EndProcedure
  
  Procedure DALDelete(*ptArray.TLongDynArray)
    *ptArray\iCount = 0
    FreeMemory(*ptArray\pData)
  EndProcedure
  
  ; PRIVATE. returns new array size, or 0 if problem
  Procedure.i DALGrow(*ptArray.TLongDynArray)
    Protected *pNewAlloc

    *pNewAlloc = ReAllocateMemory( *ptArray\pData, 
                                   SizeOf(Long) * (*ptArray\iSize + *ptArray\iGrowSize) )
    If *pNewAlloc = 0
;       OutputDebugString_("DALGrow(): Failed to allocate memory")
      ProcedureReturn 0
    EndIf
    *ptArray\pData = *pNewAlloc
    *ptArray\iSize + *ptArray\iGrowSize
;     OutputDebugString_("DynArray Size=" + Str(*ptArray\iSize) + " (" + MemorySize(*ptArray\pData) + " bytes), GrowSize=" +Str(*ptArray\iGrowSize) + ") Resized.") ; /**/
    ProcedureReturn *ptArray\iSize
  EndProcedure
  
  Procedure.i DALGetCount(*ptArray.TLongDynArray)
    ProcedureReturn *ptArray\iCount
  EndProcedure
  
  Procedure.i DALGetSize(*ptArray.TLongDynArray)
    ProcedureReturn *ptArray\iSize
  EndProcedure
  
  ; piIndex [0..count-1]
  Procedure DALGetLong(*ptArray.TLongDynArray, piIndex.i, *plRetLong)
    If (piIndex>=0) And (piIndex < *ptArray\iCount)
      PokeL(*plRetLong, *ptArray\pData\aData[piIndex])
    Else
;       OutputDebugString_("DALGetLong() invalid index requested #" + Str(piIndex) + " (Size=" + Str(*ptArray\iSize) + ", Count=" + Str(*ptArray\iCount) + ")") ; /**/
    EndIf
  EndProcedure
  
  Procedure DALSetLong(*ptArray.TLongDynArray, piIndex.i, plValue.l)
    With *ptArray
      If (piIndex < \iSize)
        If (piIndex < \iCount)
          PokeL(*ptArray\pData + SizeOf(Long)*piIndex, plValue)
        Else
          If (piIndex < \iSize)
            PokeL(*ptArray\pData + SizeOf(Long)*piIndex, plValue)
            \iCount = piIndex+1
          Else
;             OutputDebugString_("DALSetLong() index out of bounds #" + Str(piIndex) + " (Size=" + Str(*ptArray\iSize) + ", Count=" + Str(*ptArray\iCount) + ")") ; /**/
          EndIf
        EndIf
      Else
;         OutputDebugString_("DALSetLong() index out of bounds #" + Str(piIndex) + " (Size=" + Str(*ptArray\iSize) + ", Count=" + Str(*ptArray\iCount) + ")") ; /**/
      EndIf
    EndWith    
  EndProcedure
  
  ;Push will return the element index (0 based), or -1 if problem
  Procedure.i DALPushLong(*ptArray.TLongDynArray, plValue.l)
    Protected.i iNewSize
    With *ptArray
      If \iCount = \iSize
        iNewSize = DALGrow(*ptArray)
        If iNewSize = 0
;           OutputDebugString_("DALPushLong() failed to grow array") ; /**/
          ProcedureReturn -1 ; toast
        EndIf
      EndIf
      PokeL(*ptArray\pData + SizeOf(Long) * \iCount, plValue)
      \iCount + 1
      ProcedureReturn \iCount
    EndWith 
    
    ProcedureReturn -1 ; should be unreachable
  EndProcedure
  
  ; returns 1 if ok, 0 if error (pop on empty array)
  Procedure.w DALPopLong(*ptArray.TLongDynArray, *plRetLong)
    Protected iCount.i
    iCount = *ptArray\iCount
;     OutputDebugString_("DALPopLong(), iCount=" + Str(*ptArray\iCount)); /**/
    If iCount = 0
;       OutputDebugString_("DALPopLong() pop on empty stack (Size=" + Str(*ptArray\iSize) + ", Count=" + Str(*ptArray\iCount) + ")") ; /**/
      ProcedureReturn 0
    EndIf
    *ptArray\iCount = iCount - 1
;     OutputDebugString_("DALPopLong(), base=" + StrU(*ptArray\pData) + 
;                        ", addr at pos #" + iCount + 
;                        "=" + StrU(*ptArray\pData + SizeOf(Long) * (iCount-1)) +
;                        "=" + Str(*ptArray\pData\aData[iCount-1])) ; /**/
    PokeL(*plRetLong, PeekL(*ptArray\pData + SizeOf(Long) * (iCount-1)))
    ProcedureReturn 1
  EndProcedure
  
  ; Returns 1 if a long was found and removed from the array, 0 else
  Procedure.w DALRemoveFirst(*ptArray.TLongDynArray, plValue.l)
    Protected.i iRemove
    iRemove = DALFindFirst(*ptArray, plValue)
    If iRemove >= 0
      ; If not last one of the array, need to move memory
      With *ptArray
        If iRemove < (\iCount - 1)
          MoveMemory(\pData + SizeOf(Long) * (iRemove+1), 
                     \pData + SizeOf(Long) * iRemove, 
                     SizeOf(Long) * (\iCount - (iRemove+1)))
        EndIf
        \iCount = \iCount - 1
      EndWith
    EndIf
    ;MoveMemory
    ProcedureReturn 0
  EndProcedure
  
  ; Find a long value stored in DAL and return index
  ; index are zero based, so we return -1 if NOT found
  Procedure.i DALFindFirst(*ptArray.TLongDynArray, plValue.l)
    Protected.i iCount, i
    iCount = *ptArray\iCount
    If iCount > 0
      For i=0 To iCount - 1
        If PeekL(*ptArray\pData + SizeOf(Long) * i) = plValue
          ProcedureReturn i
        EndIf
      Next i
    EndIf
    ProcedureReturn -1
  EndProcedure
  
EndModule

[Kwai chang caine]

Thanks for sharing

[NicTheQuick]

To get an amortized complexity of O(1) you should always double the size of you array instead of growing it by a specific amount.
See also here: https://www.interviewcake.com/concept/j ... d-analysis

[franchsesko]

Hi NickTheQuick,

Very good point indeed, and thanks for the link.

I'm working with relatively small arrays (handles/entries indices in another dynamic array), so I've bet on a relatively safe initial size and then an expansion that should remain exceptional and moderate.

I think I'm convinced by the article. I'll revise that for my next version and go for the doubling (event. allow to choose which strategy, like specifying a grow size of zero does doubling by default).

Although, these dynamic arrays are useful inside structures.
And I got a lot of entries in these structure arrays, some containing more than one dynamic array, so I guess that, as a downside here, there may be a risk of over using memory by doubling each dynamic array just for statistically accommodating a few more entries per array.

Anyway, both choices would ensure upward compatibility for me, so very nice