News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests

Main Menu

Sentinel Double Linked List "extra" macros

Started by HSE, February 01, 2020, 01:29:32 AM

Previous topic - Next topic

HSE

Hi all!

From almost 5 years ago I'm trying to replace LinkedList object with SDLL.

Here are some additional macros that are evolving with time:; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SENTINEL_P
; Purpose:    Insert a new Sentinel structure.
; Arguments:  Arg1: Name -> Reference to sentinel structure.

; Example:
;             Object PrentObject,, Primer
;                 SENTINEL_P Items
;                 DefineR8_ observado
;                 DefineR8_ calculado
;             ObjectEnd

; in parent
; -------------------------------------------------
;   DefineVariable Items, SDLL_SENTINEL,  {}
; ------------------------------------------------
; ==================================================================================================
       SENTINEL_P macro name:=<Items>
        DefineVariable &name, SDLL_SENTINEL,  {}
       endm

; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SENTINEL_I
; Purpose:    Insert a new Item structure.
; Arguments:  Arg1: Name -> Reference to item structure.

; Example
;
; Object ChildObject,, Primer
; SENTINEL_I
; DefineR8_ x
; DefineR8_ y
; ObjectEnd

; in child
; -------------------------------------------------------------
;   DefineVariable cadena, SDLL_ITEM , {NULL, NULL}        ;Item linkage
; ------------------------------------------------------------
       SENTINEL_I macro name:=<cadena>
        DefineVariable &name, SDLL_ITEM , {NULL, NULL}
       endm

; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SDLL_InsertLastt
; Purpose:    Insert a new member to the end of the Linked List.
; Arguments:  Arg1: Register -> Reference item.
;             Arg2: Name -> Sentinel structure.
;             Arg3: Name -> Child object.
;             Arg4: Register -> Child.object
;             Arg5: Name -> item structure
;             Arg6; Register -> Auxiliar register

; Example:    SDLL_InsertLastt esi, Items, &child, eax, cadena, ebx

SDLL_InsertLastt macro ParentReg:req, Sentinel:req, ChildObj:req, ChildReg:req, Chain:req, AuxReg:req

.if [ParentReg].&Sentinel.SDLL_SENTINEL.pFirstItem == NULL
mov [ParentReg].&Sentinel.SDLL_SENTINEL.pFirstItem, ChildReg
    mov [ParentReg].&Sentinel.SDLL_SENTINEL.pLastItem, ChildReg
.else
      SetObject AuxReg, ChildObj,[ParentReg].&Sentinel.SDLL_SENTINEL.pLastItem
  mov [AuxReg].&Chain.SDLL_ITEM.pNextItem , ChildReg
SetObject ChildReg, ChildObj, ChildReg
mov [ChildReg].&Chain.SDLL_ITEM.pPrevItem, AuxReg
mov [ParentReg].&Sentinel.SDLL_SENTINEL.pLastItem, ChildReg
    .endif
endm

; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SDLL_InsertLast_tot
; Purpose:    Insert a new member to the end of the Linked List.
; Arguments:  Arg1: Register -> Reference item.
;             Arg2: Name -> Child object.
;             Arg3: Register -> Child.object
;             Arg4: Name -> item structure
;             Arg5; Register -> Auxiliar register
; Note:       Used specially when parent object contain an array of sentinel structures

; Example:
;   lea ecx, [esi].RItems0      ; is structure in parent object
;             SDLL_InsertLast_tot ecx, punto, eax, cadena, ebx

SDLL_InsertLast_tot macro ParentReg:req, ChildObj:req, ChildReg:req, Chain:req, AuxReg:req
.if [ParentReg].SDLL_SENTINEL.pFirstItem == NULL
mov [ParentReg].SDLL_SENTINEL.pFirstItem, ChildReg
    mov [ParentReg].SDLL_SENTINEL.pLastItem, ChildReg
.else
      push ChildReg
      SetObject AuxReg, ChildObj, [ParentReg].SDLL_SENTINEL.pLastItem
  mov [AuxReg].&Chain.SDLL_ITEM.pNextItem, ChildReg
SetObject ChildReg, ChildObj, ChildReg
mov [ChildReg].&Chain.SDLL_ITEM.pPrevItem, AuxReg
pop ChildReg
mov [ParentReg].SDLL_SENTINEL.pLastItem, ChildReg
    .endif
endm
SDLL_InsertLast_if macro ParentReg:req, ChildObj:req, ChildReg:req, Chain:req, AuxReg:req
.if [ParentReg].SDLL_SENTINEL.pFirstItem == NULL
mov [ParentReg].SDLL_SENTINEL.pFirstItem, ChildReg
    mov [ParentReg].SDLL_SENTINEL.pLastItem, ChildReg
endm   
SDLL_InsertLast_else macro ParentReg:req, ChildObj:req, ChildReg:req, Chain:req, AuxReg:req
.else
      push ChildReg
      SetObject AuxReg, ChildObj, [ParentReg].SDLL_SENTINEL.pLastItem
  mov [AuxReg].&Chain.SDLL_ITEM.pNextItem, ChildReg
SetObject ChildReg, ChildObj, ChildReg
mov [ChildReg].&Chain.SDLL_ITEM.pPrevItem, AuxReg
pop ChildReg
mov [ParentReg].SDLL_SENTINEL.pLastItem, ChildReg
endm
SDLL_InsertLast_endif macro ParentReg:req, ChildObj:req, ChildReg:req, Chain:req, AuxReg:req
    .endif
endm


; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SDLL_Done
; Purpose:    Remove all members, calling IDone before.
; Arguments:  Arg1: Register -> Parent pointer.
;             Arg2: Name -> Sentinel structure (in parent).
;             Arg3: ChilObject -> Linked Object Name
;   Arg4: Register -> willbe used as pointer
;   Arg5: Name - > Linked structure (in child),

; Example:    SDLL_Done esi, Items, punto, eax, cadena

SDLL_Done macro ParentReg:req, Sentinel:req, ChildObj:req, ChildReg:req, Chain:req;, AuxReg:req
push ParentReg
mov ChildReg, [ParentReg].&Sentinel.SDLL_SENTINEL.pFirstItem
.while ChildReg != NULL
  assume ChildReg: ptr &ChildObj
push [ChildReg].&Chain.SDLL_ITEM.pNextItem   ;Preserve address of next node
  assume ChildReg: nothing
  push ChildReg
  OCall ChildReg::&ChildObj.Done
  pop ChildReg
  MemFree ChildReg ;Free the linked node
  pop ChildReg ;Restore address of next node
.endw
pop ParentReg
endm

; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      SDLL_Clean
; Purpose:    Insert a new member to the end of the Linked List.
; Arguments:  Arg1: Register -> Parent pointer.
;             Arg2: Name -> Sentinel structure.
;             Arg3: ChilObject -> Linked Object Name
;   Arg4: Register -> willbe used as pointer
;   Arg5: Name - > Linked structure

; Example:    SDLL_Clean esi, Items, punto, eax, cadena

SDLL_Clean macro ParentReg:req, Sentinel:req, ChildObj:req, ChildReg:req, Chain:req;, AuxReg:req
push ParentReg
mov ChildReg, [ParentReg].&Sentinel.SDLL_SENTINEL.pFirstItem
.while ChildReg != NULL
  assume ChildReg: ptr &ChildObj
push [ChildReg].&Chain.SDLL_ITEM.pNextItem   ;Preserve address of next node
  assume ChildReg: nothing
  MemFree ChildReg ;Free the linked node
  pop ChildReg ;Restore address of next node
.endw
pop ParentReg
mov [ParentReg].&Sentinel.SDLL_SENTINEL.pFirstItem, NULL
mov [ParentReg].&Sentinel.SDLL_SENTINEL.pLastItem, NULL
endm


They are a little exaggerated :biggrin:, but allow me to follow code more easily :Method Statics.CargaPar, uses esi, nvar:dword, robservado:REAL8, rcalculado:REAL8

local fSlvTLS(CargaPar,)

SetObject esi

New pareados

f2f [eax].pareados.R8_observado, robservado
f2f [eax].pareados.R8_calculado, rcalculado

mov edx, nvar
dec edx
mov ecx, [esi].ItemsOf[edx*4]     ; array of sentinel structures offsets

SDLL_InsertLast_if ecx, pareados, eax, cadena, ebx

    f2f [esi].R8_minimo[edx*8], robservado
    f2f [esi].R8_maximo[edx*8], robservado
    .if fLT(rcalculado,[esi].R8_minimo[edx*8])
    f2f [esi].R8_minimo[edx*8], rcalculado
    .endif
    .if fGT(rcalculado,[esi].R8_maximo[edx*8])
    f2f [esi].R8_maximo[edx*8], rcalculado
    .endif

SDLL_InsertLast_else ecx, pareados, eax, cadena, ebx

mov edx, nvar
dec edx
    .if fLT(robservado,[esi].R8_minimo[edx*8])
    f2f [esi].R8_minimo[edx*8], robservado
    .endif
    .if fGT(robservado,[esi].R8_maximo[edx*8])
    f2f [esi].R8_maximo[edx*8], robservado
    .endif
    .if fLT(rcalculado,[esi].R8_minimo[edx*8])
    f2f [esi].R8_minimo[edx*8], rcalculado
    .endif
    .if fGT(rcalculado,[esi].R8_maximo[edx*8])
    f2f [esi].R8_maximo[edx*8], rcalculado
    .endif

SDLL_InsertLast_endif ecx, pareados, eax, cadena, ebx

MethodEnd


Regards. HSE
Equations in Assembly: SmplMath

daydreamer

nice to see you can also make linked lists in asm
its a common exercise for C programmers
BSP and oct-tree are useful in game programming
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

daydreamer

Hi HSE
maybe you could help me with example openlist,closedlist used in 2d pathfinding algo?
LOCAL arrays in a PROC is stored on stack,so maybe use real push/pop?
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

HSE

Quote from: daydreamer on October 28, 2020, 02:39:16 AM
maybe you could help me with example openlist,closedlist used in 2d pathfinding algo?
LOCAL arrays in a PROC is stored on stack,so maybe use real push/pop?
Where is algo?
Equations in Assembly: SmplMath

daydreamer

Quote from: HSE on October 28, 2020, 03:27:19 AM
Quote from: daydreamer on October 28, 2020, 02:39:16 AM
maybe you could help me with example openlist,closedlist used in 2d pathfinding algo?
LOCAL arrays in a PROC is stored on stack,so maybe use real push/pop?
Where is algo?

https://www.geeksforgeeks.org/a-search-algorithm/
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

HSE

Quote from: daydreamer on October 28, 2020, 04:16:42 AM
https://www.geeksforgeeks.org/a-search-algorithm/

openList is a container or collection (like in ObjAsm  :biggrin:)

closedList is an array in memory.

None of them is a list.

In tracePath procedure is used an object named stack. You can replace that with the real stack, but you have to count pushs and pops, because there is no empty() in real stack, just crash()  :biggrin: :biggrin: :biggrin:
Equations in Assembly: SmplMath

daydreamer

Quote from: HSE on October 28, 2020, 05:50:09 AM
Quote from: daydreamer on October 28, 2020, 04:16:42 AM
https://www.geeksforgeeks.org/a-search-algorithm/

openList is a container or collection (like in ObjAsm  :biggrin:)

closedList is an array in memory.

None of them is a list.

In tracePath procedure is used an object named stack. You can replace that with the real stack, but you have to count pushs and pops, because there is no empty() in real stack, just crash()  :biggrin: :biggrin: :biggrin:
thanks
I have earlier made some SSE macros for push/pop XMM regs,simulating a stack
I could try save esp somewhere before use it for LOCAL array and restore right before ret /ENDP
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

HSE

Quote from: daydreamer on October 29, 2020, 01:30:05 AM
I could try save esp somewhere before use it for LOCAL array and restore right before ret /ENDP
There is no purpose to make array local. The algorithm need to know number of pushes to make same number of pops, balance is mandatory.

We are waiting your code  :thumbsup:
Equations in Assembly: SmplMath