find object in a tree shaped list

[AGS]

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:

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

        ; 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]

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

[AGS]

No, see:

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.

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]

Originally Posted by Samurai_Crow

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.

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

[AGS]

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?

		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]

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]

Originally Posted by Samurai_Crow

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]

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)

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