home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 177.lha / DRes_v1.3 / src / lists.asm < prev    next >
Encoding:
Assembly Source File  |  1988-04-28  |  7.5 KB  |  275 lines
  1.  
  2.         ;   EXTENDED LIST/NODE HANDLING
  3.         ;
  4.         ;   (C)CopyRight May 1988, Matthew Dillon, All Rights Reserved
  5.         ;
  6.  
  7.  
  8.         ;NOTE:    These routines accomodate structures where the
  9.         ;    NODE used to traverse the list is not necessarily
  10.         ;    at the beginning of the structure.  This, 'sptr'
  11.         ;    refers to the structure pointer (not the node
  12.         ;    pointer, unless the node is at the beginning), and
  13.         ;    'off' offset refers to the offset into the structure
  14.         ;    where the NODE resides.
  15.  
  16.         public    _lGetHead         ; node = GetHead(list)
  17.         public    _lGetTail         ; node = GetTail(list)
  18.         public    _lGetSucc         ; node = GetSucc(node)
  19.         public    _lGetPred         ; node = GetPred(node)
  20.         public    _lGetHeadOff         ; sptr = GetHeadOff(list, off)
  21.         public    _lGetTailOff         ; sptr = GetTailOff(list, off)
  22.         public    _lGetSuccOff         ; sptr = GetSuccOff(sptr, off)
  23.         public    _lGetPredOff         ; sptr = GetPredOff(sptr, off)
  24.         public    _lEnqueueLong         ; (void)EnqueueLong(list, start, sptr, valoff)
  25.         public    _lEnqueueOffLong     ; (void)EnqueueOffLong(list, start, sptr, off, valoff)
  26.         public    _lSearchFwdNode      ; ret  = SearchFwdNode(sptr, func, arg)      ->  func(somesptr,arg)
  27.         public    _lSearchRvsNode      ; ret  = SearchRvsNode(sptr, func, arg)             (ditto)
  28.         public    _lSearchFwdList      ; ret  = SearchFwdList(list, func, arg)             (ditto)
  29.         public    _lSearchRvsList      ; ret  = SearchRvsList(list, func, arg)             (ditto)
  30.         public    _lSearchFwdNodeOff   ; ret  = SearchFwdNode(sptr, func, off, arg) ->  func(somesptr,arg)
  31.         public    _lSearchRvsNodeOff   ; ret  = SearchRvsNode(sptr, func, off, arg)        (ditto)
  32.         public    _lSearchFwdListOff   ; ret  = SearchFwdList(list, func, off, arg)        (ditto)
  33.         public    _lSearchRvsListOff   ; ret  = SearchRvsList(list, func, off, arg)        (ditto)
  34.  
  35.         ;   GETHEAD(list:A0)
  36.         ;   GETSUCC(node:A0)
  37. _lGetSucc:
  38. _lGetHead:    move.l    (A0),A0
  39.         tst.l    (A0)
  40.         beq    .gh0
  41.         move.l    A0,D0
  42.         rts
  43.  
  44.         ;   GETTAIL(list:A0)
  45.  
  46. _lGetTail:    move.l    8(A0),A0
  47.         tst.l    4(A0)
  48.         beq    .gh0
  49.         move.l    A0,D0
  50.         rts
  51.  
  52.         ;   GETPRED(node:A0)
  53.  
  54. _lGetPred:    move.l    4(A0),A0
  55.         tst.l    4(A0)
  56.         beq    .gh0
  57.         move.l    A0,D0
  58.         rts
  59.  
  60. .gh0        moveq.l #0,D0
  61.         rts
  62.  
  63.         ;   GETHEADOFF(list:D0, offset:D1)
  64.  
  65. _lGetHeadOff:    move.l    D0,A0
  66.         move.l    (A0),A0
  67.         tst.l    (A0)
  68.         beq    .gh0
  69.         sub.l    D1,A0
  70.         move.l    A0,D0
  71.         rts
  72.  
  73.         ;   GETTAILOFF(list:D0, offset:D1)
  74.  
  75. _lGetTailOff:    move.l    D0,A0
  76.         move.l    8(A0),A0
  77.         tst.l    4(A0)
  78.         beq    .gh0
  79.         sub.l    D1,A0
  80.         move.l    A0,D0
  81.         rts
  82.  
  83.         ;   SPTR is a structure pointer, where the node is offset
  84.         ;   OFFSET from the base of the structure.
  85.  
  86.         ;   GETSUCCOFF(sptr:D0, offset:D1)
  87.  
  88. _lGetSuccOff:    move.l    D0,A0
  89.         move.l    (A0,D1.L),A0
  90.         tst.l    (A0)
  91.         beq    .gh0
  92.         suba.l    D1,A0
  93.         move.l    A0,D0
  94.         rts
  95.  
  96.         ;   GETPREDOFF(sptr:D0, offset:D1)
  97.  
  98. _lGetPredOff:    move.l    D0,A0
  99.         move.l    4(A0,D1.L),A0
  100.         tst.l    4(A0)
  101.         beq    .gh0
  102.         suba.l    D1,A0
  103.         move.l    A0,D0
  104.         rts
  105.  
  106.         ;   ENQUEUELONG(list:D0, start:D1, sptr:D2, valoff:D4)
  107.         ;   ENQUEUEOFFLONG(list:D0, start:D1, sptr:D2, off:D3, valoff:D4)
  108.         ;
  109.         ;   list:    list to queue the object in
  110.         ;   start:    sptr to start search at (NULL=beginning of list)
  111.         ;   sptr:    pointer to the structure to queue, where
  112.         ;   off:    offset into the structure where the embedded Node is
  113.         ;   valoff:    offset into structure where the longword holding
  114.         ;        the sorting priority of the object is.
  115.         ;
  116.         ;   The list is already assumed to be sorted.  The search
  117.         ;   progresses either forward or reverse along the list until
  118.         ;   the proper place is found, then the object is inserted into
  119.         ;   the list.  The object is placed AFTER any objects of equal
  120.         ;   priority (whether the list is searched forward or backwards).
  121.  
  122. _lEnqueueLong:
  123.         movem.l D3/A2/A3,-(sp)
  124.         moveq.l #0,D3
  125.         bra    .eol1
  126. _lEnqueueOffLong:
  127.         movem.l D3/A2/A3,-(sp)
  128. .eol1        move.l    D2,A3        ; A3 = structure to add
  129.         move.l    D1,A2        ; A2 = roving structure in search
  130.         tst.l    D1
  131.         bne    .eol2
  132.         move.l    D0,A2        ; use list head instead
  133.         move.l    (A2),A1
  134.         tst.l    (A1)
  135.         beq    .eol100     ; add structure to empty list
  136.         move.l    A1,A2
  137.         sub.l    D3,A2        ; retrieve structure pointer
  138.  
  139.         ;   D0 = D4(A3)
  140.         ;   D3 = offset into A2/A3 of node
  141.         ;   D4 = offset into A2/A3 of longword value
  142.         ;   A2 = roving structure ptr
  143.         ;   A3 = structure to add
  144.         ;
  145.         ;   Sequence:    if D4(A3) > D4(A2), forward search
  146.         ;        if D4(A3) < D4(A2), reverse search
  147.  
  148. .eol2        move.l    (A3,D4.L),D0    ; Search forwards or backwards?
  149.         cmp.l    (A2,D4.L),D0
  150.         blt    .eol50
  151. .eol10        move.l    (A2,D3.L),A2    ; SEARCH FORWARDS (A2 = next node)
  152.         tst.l    (A2)            ; reached list tail
  153.         beq    .eol30        ; Add to tail
  154.         sub.l    D3,A2        ; A2 = structure
  155.         cmp.l    (A2,D4.L),D0
  156.         bge    .eol10        ; loop while value > roving_value
  157.         add.l    D3,A2        ; ADDBEFORE current node, A2 = listnode
  158.         add.l    D3,A3        ; A3 = node to add
  159.  
  160.         move.l    A2,(A3)         ; INSERT BEFORE (listnode:A2, node:A3)
  161.         move.l    4(A2),A0        ; A0 is node before A2  (seq A0-A3-A2)
  162.         move.l    A0,4(A3)
  163.         move.l    A3,4(A2)
  164.         move.l    A3,(A0)
  165.         bra    .eolend
  166.                     ; (A2 points to lh_Tail here)
  167. .eol30        move.l    4(A2),A2        ; ADDTOEND, A2 = tail element
  168.         bra    .eol100
  169. .eol50        move.l    4(A2,D3.L),A2   ;SEARCH BACKWARDS (A2 = prev. node)
  170.         tst.l    4(A2)           ;reached list head .. AddHead()
  171.         beq    .eol100
  172.         sub.l    D3,A2        ;A2 = structure pointer
  173.         cmp.l    (A2,D4.L),D0    ;loop while value < roving_value
  174.         blt    .eol50
  175.         add.l    D3,A2        ;add after NODE A2
  176. .eol100     add.l    D3,A3        ;INSERT AFTER(list/node:A2, structure:A3)
  177.         move.l    (A2),A0
  178.         move.l    A0,(A3)
  179.         move.l    4(A0),4(A3)
  180.         move.l    A3,(A2)
  181.         move.l    A3,4(A0)
  182. .eolend     movem.l (sp)+,D3/A2/A3
  183.         rts
  184.  
  185.         ;   SEARCHFWDLIST[OFF](list:D0, func:D1, [offset:A0,] funcarg:A1)
  186.         ;   SEARCHRVSLIST[OFF](list:D0, func:D1, [offset:A0,] funcarg:A1)
  187.         ;
  188.         ;    Get head/tail of list then call Search???Node
  189.  
  190. _lSearchFwdList:
  191.         sub.l    A0,A0
  192. _lSearchFwdListOff:
  193.         movem.l D2-D5/A2/A3/A6,-(sp)
  194.         move.l    D0,A2
  195.         move.l    (A2),A2             ; get head of list
  196.         tst.l    (A2)                ; empty list?
  197.         bne    SFN
  198.         bra    .sfn0
  199.  
  200. _lSearchRvsList:
  201.         sub.l    A0,A0
  202. _lSearchRvsListOff:
  203.         movem.l D2-D5/A2/A3/A6,-(sp)
  204.         move.l    D0,A2
  205.         move.l    8(A2),A2            ; get tail of list
  206.         tst.l    4(A2)               ; empty list?
  207.         bne    SRN
  208.         bra    .sfr0
  209.  
  210.         ;   For compatibility with various C compilers, neither
  211.         ;   A4 or A5 is touched.  D2,D3, and A6 are also assumed
  212.         ;   to be destroyed by the function.
  213.         ;
  214.         ;   The search ends when the function returns a non-NULL
  215.         ;   value or the list is exhausted (NULL is returned)
  216.         ;
  217.         ;   SEARCHFWDNODE(sptr:D0, func:D1, offset:A0, funcarg:A1)
  218.  
  219.  
  220. _lSearchFwdNode:
  221.         sub.l    A0,A0
  222. _lSearchFwdNodeOff:
  223.         movem.l D2-D5/A2/A3/A6,-(sp)
  224.         move.l    D0,A2
  225. SFN:        move.l    D1,A3
  226.         move.l    A0,D4
  227.         move.l    A1,D5
  228.         move.l    A2,D0            ; test for initial NULL
  229.         beq    .sfndone
  230.         adda.l    D4,A2
  231. .sfnloop    suba.l    D4,A2
  232.         move.l    D5,-(sp)            ; call function(sptr, funcarg)
  233.         move.l    A2,-(sp)
  234.         jsr    (A3)
  235.         addq.l    #8,sp
  236.         tst.l    D0            ; non-zero ret. value
  237.         bne    .sfndone
  238.         adda.l    D4,A2            ; GetSuccOff()
  239.         move.l    (A2),A2
  240.         tst.l    (A2)
  241.         bne    .sfnloop
  242. .sfn0        moveq.l #0,D0
  243. .sfndone    movem.l (sp)+,D2-D5/A2/A3/A6
  244.         rts
  245.  
  246.         ;   SEARCHRVSNODE(node:D0, func:D1, offset:A0, funcarg:A1)
  247.  
  248. _lSearchRvsNode:
  249.         sub.l    A0,A0
  250.  
  251. _lSearchRvsNodeOff:
  252.         movem.l D2-D5/A2/A3/A6,-(sp)
  253.         move.l    D0,A2
  254. SRN:        move.l    D1,A3
  255.         move.l    A0,D4
  256.         move.l    A1,D5
  257.         move.l    A2,D0            ; test for initial NULL
  258.         beq    .sfrdone
  259.         adda.l    D4,A2
  260. .sfrloop    suba.l    D4,A2
  261.         move.l    D5,-(sp)            ; call function(sptr, funcarg)
  262.         move.l    A2,-(sp)            ; args also in A2 and D5
  263.         jsr    (A3)
  264.         addq.l    #8,sp
  265.         tst.l    D0            ; non-zero ret. value
  266.         bne    .sfrdone
  267.         adda.l    D4,A2            ; GetPredOff()
  268.         move.l    4(A2),A2
  269.         tst.l    4(A2)
  270.         bne    .sfrloop
  271. .sfr0        moveq.l #0,D0
  272. .sfrdone    movem.l (sp)+,D2-D5/A2/A3/A6
  273.         rts
  274.  
  275.