INCLUDE 'exec/types.i'
        INCLUDE 'macros.i'

        INCLUDE 'exec/memory.i'

        INCLUDE 'utility/hooks.i'

        INCLUDE 'lvo/exec_lib.i'

        SECTION code,CODE

        NEAR    A4

        XREF    _SysBase

;***** #c
;***** =hil.lib

;***** QSort
;* =    performs a quicksort operation.
;* i    array, A0, APTR * = Array to be sorted
;* i    items, D0, ULONG = Number of elements in array
;* i    cmpfunc, A1, struct Hook * = Hook to be used for comparison.
;*      The hook will be called with the following arguments: 
;*       A0 struct Hook* - pointer to the hook itself
;*       A1 APTR - first pointer in the array for comparison
;*       A2 APTR - second pointer in the array for comparison
;* r    success, D0, BOOL = success/failure indicator.
;* f    This function sorts the given array using an interactive
;*      quicksort algorythm, no stack problems will occur.
;*      A buffer will be allocated to hold the
;*      stack information. If this allocation fails, this function will
;*      fail. The hook will be used for comparison, and should return
;*      something like this: 
;*       <0  e1 <  e2
;*        0  e1 == e2
;*       >0  e1 >  e2
;* e    Hook function for strings:
;*       LONG __saveds __asm cmpfunc(
;*        register __a0 struct Hook *hook,
;*        register __a1 STRPTR e1,
;*        register __a2 STRPTR e2)
;*          {
;*          return strcmp(e1, e2);
;*          }
;*****
        XDEF    _QSort
_QSort

                RSRESET
.stack          RS.L    1
.stackpt        RS.L    1
.array          RS.L    1
.elements       RS.L    1
.x              RS.L    1
.hook           RS.L    1
.vars           RS.L    0

        pushm.L A3/A6
        lea     (-.vars,SP),SP

        move.L  A1,(.hook,SP)
        movem.L A0/D0,(.array,SP)
        movea.L (_SysBase,A4),A6
        asl.L   #3,D0
        moveq   #MEMF_ANY,D1
        call    AllocVec
        tst.L   D0
        beq.S   .nomemerr
        movea.L D0,A3
        move.L  D0,(.stack,SP)

        movem.L (.array,SP),A0/D0
        move.L  A0,(A3)+
        add.L   D0,D0
        add.L   D0,D0
        lea     (A0,D0.L),A0
        move.L  A0,(A3)+

.lpA    cmpa.L  (.stack,SP),A3
        beq.W   .endsort
        movea.L -(A3),A2
        movea.L -(A3),A1
        subq.L  #4,A2
        move.L  A3,(.stackpt,SP)

; A1 = a
; A2 = b

        move.L  A2,D0
        sub.L   A1,D0
        cmp.L   #2,D0
        blt.S   .lpA    ; nothing to sort
        move.L  (A1),(.x,SP)

.lp0    cmpa.L  A1,A2
        bls.S   .ok2

.lp1    cmpa.L  A1,A2
        bls.S   .end1
        pushm.L A1-A2
        movea.L (.hook+8,SP),A0
        movea.L (.x+8,SP),A1
        movea.L (A2),A2
        move.L  (h_Entry,A0),A3
        jsr     (A3)
        popm.L  A1-A2
        neg.L   D0
        bmi.S   .end1
        subq.L  #4,A2
        bra.S   .lp1

.end1   cmpa.L  A1,A2
        bls.S   .lp2
        move.L  (A2),(A1)++

.lp2    cmpa.L  A1,A2
        bls.S   .end2
        pushm.L A1-A2
        movea.L (.hook+8,SP),A0
        movea.L (A1),A1
        movea.L (.x+8,SP),A2
        move.L  (h_Entry,A0),A3
        jsr     (A3)
        popm.L  A1-A2
        neg.L   D0
        bmi.S   .end2
        addq.L  #4,A1
        bra.S   .lp2

.end2   cmpa.L  A1,A2
        bls.S   .lp0
        move.L  (A1),(A2)
        subq.L  #4,A2
        bra.S   .lp0

.ok2    move.L  (.x,SP),(A1)

        movea.L (.stackpt,SP),A3
        addq.L  #4,A3
        move.L  (A3),D0
        move.L  A1,(A3)+
        addq.L  #4,A1
        move.L  A1,(A3)+
        move.L  D0,(A3)+

        bra.W   .lpA

.endsort
        movea.L (.stack,SP),A1
        call    FreeVec
        moveq   #1,D0
.nomemerr
        lea     (.vars,SP),SP
        popm.L  A3/A6
        rts