Author Topic: Sentinel Double Linked List "extra" macros  (Read 1429 times)

HSE

  • Member
  • *****
  • Posts: 1618
  • <AMD>< 7-32>
Sentinel Double Linked List "extra" macros
« on: February 01, 2020, 01:29:32 AM »
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:
Code: [Select]
; ——————————————————————————————————————————————————————————————————————————————————————————————————
; 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 :
Code: [Select]
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

daydreamer

  • Member
  • *****
  • Posts: 1553
  • building nextdoor
Re: Sentinel Double Linked List "extra" macros
« Reply #1 on: February 01, 2020, 08:13:28 PM »
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
SIMD fan and macro fan
Happy new year 2021 that can only turn out to become better than worse 2020 :)

daydreamer

  • Member
  • *****
  • Posts: 1553
  • building nextdoor
Re: Sentinel Double Linked List "extra" macros
« Reply #2 on: October 28, 2020, 02:39:16 AM »
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?
SIMD fan and macro fan
Happy new year 2021 that can only turn out to become better than worse 2020 :)

HSE

  • Member
  • *****
  • Posts: 1618
  • <AMD>< 7-32>
Re: Sentinel Double Linked List "extra" macros
« Reply #3 on: October 28, 2020, 03:27:19 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?

daydreamer

  • Member
  • *****
  • Posts: 1553
  • building nextdoor
Re: Sentinel Double Linked List "extra" macros
« Reply #4 on: October 28, 2020, 04:16:42 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/
SIMD fan and macro fan
Happy new year 2021 that can only turn out to become better than worse 2020 :)

HSE

  • Member
  • *****
  • Posts: 1618
  • <AMD>< 7-32>
Re: Sentinel Double Linked List "extra" macros
« Reply #5 on: October 28, 2020, 05:50:09 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:

daydreamer

  • Member
  • *****
  • Posts: 1553
  • building nextdoor
Re: Sentinel Double Linked List "extra" macros
« Reply #6 on: October 29, 2020, 01:30:05 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
SIMD fan and macro fan
Happy new year 2021 that can only turn out to become better than worse 2020 :)

HSE

  • Member
  • *****
  • Posts: 1618
  • <AMD>< 7-32>
Re: Sentinel Double Linked List "extra" macros
« Reply #7 on: October 29, 2020, 03:17:36 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: