English Amiga Board


Go Back   English Amiga Board > Coders > Coders. System

 
 
Thread Tools
Old 06 December 2017, 23:03   #1
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 42
Posts: 450
Question 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?

Last edited by AGS; 06 December 2017 at 23:08.
AGS is offline  
AdSense AdSense  
Old 06 December 2017, 23:10   #2
Samurai_Crow
Total Chaos forever!

Samurai_Crow's Avatar
 
Join Date: Aug 2007
Location: Ft. Collins, CO USA
Age: 43
Posts: 920
Send a message via Yahoo to Samurai_Crow
TailPred is the NULL pointer. Tail is the last element in the doubly linked list. Does that help?
Samurai_Crow is offline  
Old 06 December 2017, 23:19   #3
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 42
Posts: 450
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

Last edited by AGS; 06 December 2017 at 23:34.
AGS is offline  
Old 07 December 2017, 02:37   #4
PeterK
Registered User
 
Join Date: Apr 2005
Location: Hangover
Posts: 1,736
Quote:
Originally Posted by Samurai_Crow View Post
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

Last edited by PeterK; 07 December 2017 at 07:02.
PeterK is offline  
Old 07 December 2017, 11:48   #5
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 42
Posts: 450
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
AGS is offline  
Old 07 December 2017, 11:55   #6
Samurai_Crow
Total Chaos forever!

Samurai_Crow's Avatar
 
Join Date: Aug 2007
Location: Ft. Collins, CO USA
Age: 43
Posts: 920
Send a message via Yahoo to 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.
Samurai_Crow is offline  
Old 07 December 2017, 20:24   #7
PeterK
Registered User
 
Join Date: Apr 2005
Location: Hangover
Posts: 1,736
Quote:
Originally Posted by Samurai_Crow View Post
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.
PeterK is offline  
Old 07 December 2017, 22:43   #8
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 42
Posts: 450
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
AGS is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
where can I find a top 100 demos list? turrican9 support.Demos 11 15 December 2016 15:18
Where to find a good list of games with copylocks? MethodGit Amiga scene 7 30 October 2010 23:05
Amiga Christmas Tree Cammy Amiga scene 47 30 December 2008 16:33
Weirdly shaped game boxes Bad Mr Frosty Nostalgia & memories 11 27 February 2004 17:12
Source tree silk support.WinUAE 1 21 January 2003 02:51

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 17:06.


Powered by vBulletin® Version 3.8.8 Beta 1
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Page generated in 0.12848 seconds with 13 queries