opt l+,o+,ow- * * qsort.s version 7.6 - © Copyright 1990 Jaba Development * * Author : Jan van den Baard * Assembler : Devpac vesion 2.14 * incdir 'sys:devpac_inc/' include 'mymacros.i' include 'tool.i' include 'exec/exec_lib.i' xdef InitMemoryChain xdef AllocItem xdef FreeItem xdef FreeMemoryChain InitMemoryChain: move.l a0,a1 ; chain to a1 lea.l mc_Blocks(a1),a0 NEWLIST a0 ; initialize block list lea.l mc_Items(a1),a0 NEWLIST a0 ; initialize item list LONGALLIGN d0 ; allign the block size move.l d0,mc_BlockSize(a1) ; put it in the structure rts FreeBlock: movem.l a2-a3/a5-a6,-(sp) move.l a0,a2 ; chain to a2 move.l a1,a3 ; block to a3 lea.l mc_Items(a2),a5 move.l il_First(a5),a5 ; first item in a5 FBLoop: tst.l mit_Next(a5) ; is there a next item ? beq.s FBDone ; no.. done cmp.l mit_Block(a5),a3 ; item in the block ? bne.s FBNotSame ; no.. get next item move.l a5,a1 REMOVE ; remove item from the list lea.l mc_Items(a2),a5 move.l il_First(a5),a5 bra.s FBLoop ; start from the begin FBNotSame: move.l mit_Next(a5),a5 bra.s FBLoop ; try the next item FBDone: move.l a3,a1 REMOVE ; remove block from the list move.l (_SysBase).w,a6 move.l a3,a1 move.l mc_BlockSize(a2),d0 add.l #mb_SIZEOF,d0 libcall FreeMem ; free the block's memory movem.l (sp)+,a2-a3/a5-a6 rts AllocBlock: movem.l d2/a2-a3/a5-a6,-(sp) move.l a0,a2 ; chain to a2 move.l d0,d2 ; reqs to d2 move.l d2,d1 move.l mc_BlockSize(a2),d0 add.l #mb_SIZEOF,d0 move.l (_SysBase).w,a6 libcall AllocMem ; allocate the memory move.l d0,a3 ; put it in a3 beq.s ABNoMem move.l d2,mb_Requirements(a3) ; set block reqs clr.l mb_BytesUsed(a3) ; clear bytes used counter lea.l mc_Blocks(a2),a0 move.l a3,a1 ADDHEAD ; add block in the list move.l a3,a5 add.l #mb_SIZEOF,a5 ; get first item in a5 move.l a3,mit_Block(a5) ; set it's block move.l mc_BlockSize(a2),mit_Size(a5) ; set it's size lea.l mc_Items(a2),a0 move.l a5,a1 ADDHEAD ; add item in the list move.l a3,d0 ; return the block ABEnd: movem.l (sp)+,d2/a2-a3/a5-a6 rts ABNoMem: cldat d0 ; alloc failed.. return 0 bra.s ABEnd OptimizeBlock: link a6,#-il_SIZEOF ; create stack space movem.l d2/a2-a6,-(sp) move.l a0,a2 ; chain to a2 move.l a1,a3 ; block to a3 lea.l -il_SIZEOF(a6),a0 NEWLIST a0 ; init buffer list lea.l mc_Items(a2),a4 move.l il_First(a4),a4 ; first item to a4 OBLoop1: tst.l mit_Next(a4) ; is there a next item ? beq.s OBDone1 ; no.. done cmp.l mit_Block(a4),a3 ; item in the block ? bne.s OBNotSame1 ; no.. skip it move.l a4,a1 REMOVE ; remove item lea.l -il_SIZEOF(a6),a0 move.l a4,a1 ADDTAIL ; put item in buffer list lea.l mc_Items(a2),a4 move.l il_First(a4),a4 bra.s OBLoop1 ; start from the begin OBNotSame1: move.l mit_Next(a4),a4 bra.s OBLoop1 ; try the next item OBDone1: lea.l -il_SIZEOF(a6),a0 move.l il_First(a0),a4 ; first buffer item in a4 OBLoop2: tst.l mit_Next(a4) ; is there a next item ? beq.s OBDone2 ; no.. done move.l a4,d2 add.l mit_Size(a4),d2 ; addres behind item to d2 move.l a4,a5 OBLoop3: tst.l mit_Next(a5) ; is there a next item ? beq.s OBDone3 ; no.. done cmp.l d2,a5 ; d2 is a5 ? bne.s OBNotSame2 ; no.. skip it move.l mit_Size(a5),d0 add.l d0,mit_Size(a4) ; join a4 with a5 add.l d0,d2 move.l a5,a1 REMOVE ; remove a5 from the list lea.l -il_SIZEOF(a6),a0 move.l il_First(a0),a5 bra.s OBLoop3 ; start from the begin OBNotSame2: move.l mit_Next(a5),a5 bra.s OBLoop3 ; try the next item OBDone3: move.l mit_Next(a4),a4 bra.s OBLoop2 ; try the next item OBDone2: lea.l -il_SIZEOF(a6),a0 REMHEAD ; remove item from the buffer tst.l d0 ; is it 0 ? beq.s NoMore ; yes.. all done move.l d0,a1 lea.l mc_Items(a2),a0 ADDHEAD ; add it to the list bra.s OBDone2 NoMore: movem.l (sp)+,d2/a2-a6 unlk a6 rts OptimizeChain: movem.l a2-a3,-(sp) move.l a0,a2 ; chain to a2 lea.l mc_Blocks(a2),a3 move.l bl_First(a3),a3 ; first block in a2 OCLoop: tst.l mb_Next(a3) ; is there a next block ? beq.s OCDone ; no.. done move.l a2,a0 move.l a3,a1 bsr OptimizeBlock ; optimize it move.l mb_Next(a3),a3 ; next patient please.. bra.s OCLoop OCDone: movem.l (sp)+,a2-a3 rts FindSpace: movem.l d2-d3/a2-a3,-(sp) move.l a0,a2 ; chain to a2 move.l d0,d2 ; size to d2 move.l d1,d3 ; reqs to d3 lea.l mc_Items(a2),a3 move.l il_First(a3),a3 ; first item to a3 FSLoop: tst.l mit_Next(a3) ; is there a next item ? beq.s FSDone ; no.. done move.l mit_Block(a3),a0 cmp.l mb_Requirements(a0),d3 ; requirements OK ? bne.s FSNotSame ; no.. skip it cmp.l mit_Size(a3),d2 ; size OK ? bhi.s FSNotSame ; no.. skip it move.l a3,d0 ; return the item bra.s FSEnd FSNotSame: move.l mit_Next(a3),a3 bra.s FSLoop ; try the next item FSDone: cldat d0 ; no item found FSEnd: movem.l (sp)+,d2-d3/a2-a3 rts AllocItem: movem.l d2-d4/a2-a5,-(sp) move.l a0,a2 ; chain to a2 move.l d0,d2 ; size to d2 move.l d1,d3 ; reqs to d3 bclr.l #16,d3 ; clear MEMF_CLEAR bit bclr.l #17,d3 ; clear MEMF_LARGEST bit cmp.l #mit_SIZEOF,d2 ; size > mit_SIZEOF ? bhi.s ASOK ; yes.. ok move.l #mit_SIZEOF,d2 ; else make it that big ASOK: LONGALLIGN d2 ; allign the size move.l d3,d1 move.l d2,d0 move.l a2,a0 bsr FindSpace ; find a suitable item move.l d0,a4 ; put it in a4 bne.s HaveSpace ; found one.. move.l d3,d0 move.l a2,a0 bsr AllocBlock ; allocate a block move.l d0,a4 ; put it in a4 beq NoMem ; no more memory (wheeee) add.l #mb_SIZEOF,a4 ; get first item HaveSpace: move.l mit_Block(a4),a3 ; get block in a3 cmp.l mit_Size(a4),d2 ; size equals item size ? beq.s NoSplit ; yes.. don't split it move.l mit_Size(a4),d4 sub.l d2,d4 cmp.l #mit_SIZEOF,d4 ; size left < mit_SIZEOF ? bcs.s NoSplit ; yes.. don't split it move.l a4,a5 add.l d2,a5 ; new item in a5 move.l d4,mit_Size(a5) ; set new item size move.l a3,mit_Block(a5) ; set new item block lea.l mc_Items(a2),a0 move.l a5,a1 ADDHEAD ; add it in the list NoSplit: move.l a4,a1 REMOVE ; remove it from the list move.l a4,a0 move.l d2,d0 bsr ClearAlloc ; clear memory add.l d2,mb_BytesUsed(a3) ; increase bytes used counter move.l a4,d0 ; return the pointer AIEnd: movem.l (sp)+,d2-d4/a2-a5 rts NoMem: cldat d0 ; no memory.. return 0 bra.s AIEnd FreeItem: movem.l d2/a2-a4,-(sp) move.l a0,a2 ; chain to a2 move.l a1,a3 ; memptr to a3 move.l d0,d2 ; size to d2 cmp.l #mit_SIZEOF,d2 ; size > mit_SIZEOF ? bhi.s FSOK ; yes.. ok move.l #mit_SIZEOF,d2 ; else make it that big FSOK: LONGALLIGN d2 ; allign the size bsr FindBlock ; find it's block move.l d0,a4 ; and put it in a4 beq FRDone ; block 0.. don't free move.l a4,mit_Block(a3) ; set item block move.l d2,mit_Size(a3) ; set item size sub.l d2,mb_BytesUsed(a4) ; decrease bytes used count move.l a3,a1 lea.l mc_Items(a2),a0 ADDHEAD ; add item in the list tst.l mb_BytesUsed(a4) bne.s FROpt ; block not free move.l mit_Block(a3),a1 move.l a2,a0 bsr FreeBlock ; free the block FROpt: move.l a2,a0 bsr OptimizeChain ; optimize the chain FRDone: movem.l (sp)+,d2/a2-a4 rts FindBlock: move.l a2,-(sp) lea.l mc_Blocks(a0),a2 move.l bl_First(a2),a2 ; first block to a2 FBBLoop: tst.l mb_Next(a2) ; is there a next block ? beq.s FBBDone ; no.. done move.l a2,d0 cmp.l d0,a1 ; memptr < block start ? bmi.s FBBNotSame ; yes.. skip it add.l #mb_SIZEOF,d0 add.l mc_BlockSize(a0),d0 cmp.l d0,a1 ; memptr > block end ? bhi.s FBBNotSame ; yes.. skip it move.l a2,d0 ; return block bra.s EndFBB FBBNotSame: move.l mb_Next(a2),a2 bra.s FBBLoop ; try the next block FBBDone: cldat d0 ; block not found.. return 0 EndFBB: move.l (sp)+,a2 rts FreeMemoryChain: movem.l a2-a3/a6,-(sp) move.l a0,a2 ; chain to a2 move.l (_SysBase).w,a6 FMCLoop: lea.l mc_Blocks(a2),a0 REMHEAD ; remove a block move.l d0,a1 ; put it in a1 beq.s AllDone ; block 0 then done move.l mc_BlockSize(a2),d0 add.l #mb_SIZEOF,d0 libcall FreeMem ; free it's memory bra.s FMCLoop AllDone: move.l mc_BlockSize(a2),d0 move.l a2,a0 bsr InitMemoryChain ; re-initialize the chain movem.l (sp)+,a2-a3/a6 rts ClearAlloc: lsr.l #2,d0 ; size / 2 dec.l d0 Loop: clr.l (a0)+ ; clear a long word dbra d0,Loop rts