English Amiga Board

English Amiga Board (http://eab.abime.net/index.php)
-   Coders. System (http://eab.abime.net/forumdisplay.php?f=113)
-   -   find object in a tree shaped list (http://eab.abime.net/showthread.php?t=89722)

AGS 06 December 2017 22:03

find object in a tree shaped exec list
 
I have a tree of elements, where any element is a listnode and contains a listheader. in addition any element points to it's listheader as its parent. with the following code i am able to find the next marked element from any marked element. this works forward. now I would need the same backward, but what I tried, crashes.

forward:

Code:

        ; starting from a marked object in a0
       
.down
        lea    oxO_list(a0),a1
        move.l    MLN_HEAD(a1),a1
        tst.l    (a1)
        bne    .if_chained

.succ
        move.l    oxO_node+MLN_SUCC(a0),a1
        tst.l    (a1)
        bne    .if_chained

        move.l    oxO_parent(a0),d0
        beq    .down

        move.l    d0,a0
        bra    .succ

.if_chained
        move.l    a1,a0
        move.l    oxO_class(a0),a1
        btst    #oxCB_AUTOCHAIN,oxC_flags(a1)
        beq    .down

; marked object found here

backward try:

Code:

        ; find previous chaineable element

        bra    .pred

.downb
        lea    oxO_list(a0),a1
        move.l    MLN_TAILPRED(a1),a1
        tst.l    (a1)
        bne    .if_chain

.pred
        move.l    oxO_node+MLN_PRED(a0),a1
        tst.l    (a1)
        bne    .if_chain

        move.l    oxO_parent(a0),d0
        beq    .downb

        move.l    d0,a0
        bra    .pred

.if_chain
        move.l    a1,a0
        move.l    oxO_class(a0),a1
        btst    #oxCB_AUTOCHAIN,oxC_flags(a1)
        beq    .downb

Any ideas?

Samurai_Crow 06 December 2017 22:10

TailPred is the NULL pointer. Tail is the last element in the doubly linked list. Does that help?

AGS 06 December 2017 22:19

No, see:

Code:

NEWLIST    MACRO  ; list
            MOVE.L  \1,LH_TAILPRED(\1)
            ADDQ.L  #4,\1        ;Get address of LH_TAIL
            CLR.L  (\1)        ;Clear LH_TAIL
            MOVE.L  \1,-(\1)        ;Address of LH_TAIL to LH_HEAD
            ENDM

TAILPRED points to the list header in an empty list. What happens in ADDTAIL is to complicated to me.

Code:

ADDTAIL    MACRO  ; A0-list(destroyed) A1-node D0-(destroyed)
            ADDQ.L  #LH_TAIL,A0
            MOVE.L  LN_PRED(A0),D0
            MOVE.L  A1,LN_PRED(A0)
            EXG    D0,A0
            MOVEM.L D0/A0,(A1)
            MOVE.L  A1,(A0)
            ENDM


PeterK 07 December 2017 01:37

Quote:

Originally Posted by Samurai_Crow (Post 1204387)
TailPred is the NULL pointer. Tail is the last element in the doubly linked list. Does that help?

No, lh_Tail = Null and lh_TailPred points to the last node of a list.

Code:

ADDTAIL MACRO ; A0-list(destroyed) A1-node D0-(destroyed)
        MOVE.L LH_TAILPRED(A0),D0  ; the old last node
        MOVE.L A1,LH_TAILPRED(A0)  ; lh_TailPred = new node
        ADDQ.L #LH_TAIL,A0        ; point to lh_Tail now
        EXG D0,A0
        MOVEM.L D0/A0,(A1)        ; store lh_Tail and old last node in new node
        MOVE.L A1,(A0)            ; store new node as ln_Succ in old last node
        ENDM

The code from the includes was correct but very confusing because they used ln_Pred=4 in a list header instead of lh_TailPred=8 :banghead

AGS 07 December 2017 10:48

I brought it close to the goal. Still some problem when going beyond the first marked object. Actually then the last one should be found but it ends in an endless loop somewhere. So how to find the most far marked object?

Code:

                bra        .pred
               
.downb
                lea        oxO_list(a0),a1
                move.l        8(a1),a1
                tst.l        4(a1)
                bne        .if_chain

.pred
                move.l        oxO_node+MLN_PRED(a0),a1
                tst.l        4(a1)
                bne        .if_chain

                move.l        oxO_parent(a0),d0
                beq        .downb

                move.l        d0,a0
                bra        .pred

.if_chain
                move.l        a1,a0
                move.l        oxO_class(a0),a1
                btst        #oxCB_AUTOCHAIN,oxC_flags(a1)
                beq        .downb


Samurai_Crow 07 December 2017 10:55

Well, whichever one is NULL, it's a circular linked list with the NULL pointer stored in the dummy node between the first item pointer and the last item pointer. If this terminology doesn't ring a bell, Google "circular linked list" and come back. There should be a good diagram on the internet somewhere.

PeterK 07 December 2017 19:24

Quote:

Originally Posted by Samurai_Crow (Post 1204469)
Google "circular linked list" and come back.

From what I've seen in Google's examples these "circular linked lists" are clearly different to the AmigaOS list structures.

1.) In an Amiga list the last node is never directly forward linked to the first node, but always to lh_Tail, the Null pointer in the list header.

2.) The backward link of the first node is never pointing to the last node, but always to lh_Head.

3.) The Amiga list header contains no node structure and no application data.

Amiga lists are not "circular" like the lists in Google's examples. You always have to walk through the list header, which has a different structure than a node. All the nice procedures to manage these "circular linked lists" will fail or destroy the Amiga list structures.

AGS 07 December 2017 21:43

To step from the first marked object to the last in the tree I need to seek for the last. the current solution does not do it though: (d0 is supposed to carry the last marked element (autochain bit set) but doesnt)

Code:

find_last        ; a0 pointer to root (not tested itself)

.childs                lea        oxO_list(a0),a0

.next_member        move.l        (a0),a0
                tst.l        (a0)
                beq.b        .rts

                move.l        oxO_class(a0),a1
                btst        #oxCB_AUTOCHAIN,oxC_flags(a1)
                beq        .down

                move.l        a0,d0

.down                push        a0
                bsr        .childs
                pop        a0

                bra        .next_member

.rts                rts



All times are GMT +2. The time now is 11:10.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.

Page generated in 0.06406 seconds with 11 queries