; ; llistMan.s ; ; Linked List Management (TMA) ; ; © 1994-1998 Straylight ; ;----- Licensing note ------------------------------------------------------- ; ; This file is part of Straylight's Sapphire library. ; ; Sapphire is free software; you can redistribute it and/or modify ; it under the terms of the GNU General Public License as published by ; the Free Software Foundation; either version 2, or (at your option) ; any later version. ; ; Sapphire is distributed in the hope that it will be useful, ; but WITHOUT ANY WARRANTY; without even the implied warranty of ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ; GNU General Public License for more details. ; ; You should have received a copy of the GNU General Public License ; along with Sapphire. If not, write to the Free Software Foundation, ; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ;----- Standard header ------------------------------------------------------ GET libs:header GET libs:swis ;----- External dependencies ------------------------------------------------ GET sapphire:alloc GET sapphire:fastMove GET sapphire:sapphire ;----- Main code ------------------------------------------------------------ AREA |Sapphire$$Code|,CODE,READONLY ; --- llist_create --- ; ; On entry: R0 == pointer to 12 byte list head to fill in ; R1 == sort routine to use (0 for none) ; ; On exit: List head filled in appropriately ; ; Use: This call set up list. It must be made just once, before ; and other list alls are made. On entry, R0 must point to ; 12 bytes in memory, which is filled in by this call. ; Example code may look like: ; ; ADR R0,myList ; LDR R1,=myStrCmp ; BL llist_create ; ; . ; . ; . ; ; mylist DCD 0,0 EXPORT llist_create llist_create ROUT STMFD R13!,{R12,R14} ;Stack some registers WSPACE llist__wSpace ;Locate my workspace ADR R14,ws__z ;Point to list terminator STR R14,[R0,#ll__first] ;Store in the list head STR R1,[R0,#ll__sort] ;The sort routine MOV R14,#0 ;Number of items so far STR R14,[R0,#ll__items] ;Stor that in the block LDMFD R13!,{R12,PC}^ ;Return to caller LTORG ; --- llist_destroy --- ; ; On entry: R0 == pointer to list head ; ; On exit: R0 corrupted ; ; Use: Destroys the given list. EXPORT llist_destroy llist_destroy ROUT STMFD R13!,{R1,R2,R12,R14} ;Stack registers WSPACE llist__wSpace ;Locate my workspace ADR R1,ws__z ;Point to terminator LDR R0,[R0,#ll__first] ;Get the first item 00llist_destroy LDR R2,[R0,#ll__next] ;Get the next item CMP R0,R1 ;Are we at the end? BLNE free ;No -- free item MOVNE R0,R2 ;Get the next item BNE %00llist_destroy ;And destroy that too LDMFD R13!,{R1,R2,R12,PC}^ ;Return to caller LTORG ; --- llist__insert --- ; ; On entry: R0 == pointer to the list head ; R1 == pointer to the item (user data) ; ; On exit: -- ; ; Use: Insert the given item into the list, assuming that the list ; is already sorted. llist__insert ROUT STMFD R13!,{R0-R5,R12,R14} ;Stack some registers WSPACE llist__wSpace ;Find workspace ADR R2,ws__z ;The list terminator LDR R5,[R0,#ll__sort] ;The sort routine MOV R3,R0 ;The previous item ; --- Scan through the items, until comparison is GT --- 00llist__insert MOV R4,R3 ;The previous item LDR R3,[R3,#ll__next] ;Get the next item CMP R3,R2 ;Is there one? BEQ %20llist__insert ;No -- insert at end ADD R0,R3,#ll__blockSize ;Point to user data CMP R5,#0 ;Is there a sort routine? CMPEQ R0,R0 ;No -- make LE condition MOVNE R14,PC ;Yes -- set up return address MOVNE PC,R5 ;...and branch to sort routn BLE %00llist__insert ;Keep looking ; --- Insert the item --- 20llist__insert SUB R1,R1,#ll__blockSize ;Point to full item desc STR R1,[R4,#ll__next] ;Store in previous next ^ STR R3,[R1,#ll__next] ;Update this next pointer STR R1,[R3,#ll__prev] ;Update next previous pointer STR R4,[R1,#ll__prev] ;Update this previous pointer ; --- Return to the caller --- 99llist__insert LDMFD R13!,{R0-R5,R12,PC}^ ;Return LTORG ; --- llist_addItem --- ; ; On entry: R0 == pointer to list head ; R1 == pointer to user data (or 0 if none to copy) ; R2 == size of user data ; ; On exit: R0 preserved ; R1 == pointer to the new user data ; May return an error ; ; Use: This call will add an item to a list. Notice that the ; item is entirely allocated by the list manager, it does not ; point to the data that you supply it, instead it ; copies the data into the newly created item. For this reason ; if 0 is supplied as the user data, nothing is copied. ; It is the returned user data pointer, that must be ; used to reference the item in other llist calls. EXPORT llist_addItem llist_addItem ROUT BIC R14,R14,#V_flag ;No error yet STMFD R13!,{R0,R2,R3,R12,R14} ;Stack some registers WSPACE llist__wSpace ;Locate workspace MOV R3,R2 ;Size of user data ADD R2,R2,#ll__blockSize+3 ;The blocksize required BIC R2,R2,#3 ;Word align MOV R0,R2 ;Allocate this much BL alloc ;Try to allocate the block BCS alloc_error ;No memory? Get message BVS %99llist_addItem ;And return with error STR R2,[R0,#ll__size] ;Store the item size MOV R2,R3 ;Just copy this much MOV R3,R0 ;Remember this pointer ADD R0,R0,#ll__blockSize ;Point to user data CMP R1,#0 ;Any data supplied? BLNE fastMove ;Yes -- copy it over MOV R2,#0 ;The flags word STR R2,[R3,#ll__flags] ;Store them nicely BEQ %10llist_addItem ;...and insert at beginning MOV R1,R0 ;Point to the list item block LDMIA R13,{R0} ;Get list head back BL llist__insert ;Insert the item in the list LDR R2,[R0,#ll__items] ;Get the item count ADD R2,R2,#1 ;Increment it STR R2,[R0,#ll__items] ;Store it back again B %99llist_addItem ;Return to caller ; --- Just insert at the beginning --- 10llist_addItem MOV R1,R0 ;Point to the item data SUB R0,R0,#ll__blockSize ;Point to full item desc LDMIA R13,{R2} ;Get list head back STR R2,[R0,#ll__prev] ;Store head in item LDR R14,[R2,#ll__first] ;Get the first item STR R14,[R0,#ll__next] ;Store this as second item STR R0,[R2,#ll__first] ;Store this as first item STR R0,[R14,#ll__prev] ;Finish off the insertion LDR R14,[R2,#ll__items] ;Get the item count ADD R14,R14,#1 ;Increment it STR R14,[R2,#ll__items] ;Store it back again 99llist_addItem LDMFD R13!,{R0,R2,R3,R12,R14} ;Get registers back ORRVSS PC,R14,#V_flag ;Return either with... BICVCS PC,R14,#V_flag ;...or without error LTORG ; --- llist__removeItem --- ; ; On entry: R1 == pointer to item to remove (as returned by addItem) ; ; On exit: -- ; ; Use: This call removes the item from the given list. The ; item in question is not freed. llist__removeItem ROUT STMFD R13!,{R1,R2,R14} ;Stack some registers SUB R1,R1,#ll__blockSize ;Point to the real item block LDR R2,[R1,#ll__next] ;Get next item in list LDR R14,[R1,#ll__prev] ;And the previous item STR R2,[R14,#ll__next] ;Update previous next pointer STR R14,[R2,#ll__prev] ;Update next previous pointer LDMFD R13!,{R1,R2,PC}^ ;Return to caller LTORG ; --- llist_removeItem --- ; ; On entry: R0 == list head pointer ; R1 == pointer to item to remove (as returned by addItem) ; ; On exit: -- ; ; Use: This call removes the item from the given list. All ; memory taken up by the item is freed. If the value ; passed in R1 is not an item in the list, then all hell is ; likely to break loose, so I don't advise making this mistake. EXPORT llist_removeItem llist_removeItem ROUT STMFD R13!,{R0,R1,R14} ;Stack some registers BL llist__removeItem ;Remove the item LDR R14,[R0,#ll__items] ;Get the item count SUB R14,R14,#1 ;Reduce it STR R14,[R0,#ll__items] ;Store it back again SUB R1,R1,#ll__blockSize ;Point to the allocated block MOV R0,R1 ;Point to item to remove BL free ;Free it nicely LDMFD R13!,{R0,R1,PC}^ ;Return to caller LTORG ; --- llist_reinsert --- ; ; On entry: R0 == pointer to list head ; R1 == item to reinsert ; ; On exit: -- ; ; Use: Reinserts the given item into the list. This call is ; used if the item is updated in such a way that its ; position in the list may change. EXPORT llist_reinsert llist_reinsert ROUT STMFD R13!,{R14} ;Stack the link register BL llist__removeItem ;Remove the item from list BL llist__insert ;Insert it into the list LDMFD R13!,{PC}^ ;Return to caller LTORG ; --- llist_setFlags --- ; ; On entry: R1 == pointer to list item ; R2 == BIC word ; R3 == EOR word ; ; On exit: R2 == the new flags word ; ; Use: Sets the flags associated with the given item. If you ; just wish to read them, set R2 and R3 to 0. EXPORT llist_setFlags llist_setFlags ROUT STMFD R13!,{R0,R14} ;Stack registers SUB R0,R1,#ll__blockSize ;Point to real item LDR R14,[R0,#ll__flags] ;Get the flags word BIC R14,R14,R2 ;Do the BIC operation EOR R14,R14,R3 ;Now the EOR op STR R14,[R0,#ll__flags] ;Set the flags word MOV R2,R14 ;Return these flags LDMFD R13!,{R0,PC}^ ;Return to caller LTORG ; --- llist_items --- ; ; On entry: R0 == pointer to list head ; ; On exit: R1 == number of items in list ; ; Use: Returns the number of items in the list given. This is ; a cached value, and so is very fast. EXPORT llist_items llist_items ROUT LDR R1,[R0,#ll__items] ;Get the number of items MOVS PC,R14 ;And return ; --- llist_enumerate --- ; ; On entry: R0 == pointer to list head ; R1 == pointer to item (0 for first) ; R2 == mask word ; R3 == test word ; ; On exit: CS and R1 == next item that matches ; CC and R1 corrupted if no more items ; ; Use: This calls return each item in the list, one at a time, ; as long as the item matches the pattern given. EXPORT llist_enumerate llist_enumerate ROUT STMFD R13!,{R4,R12,R14} ;Stack some registers WSPACE llist__wSpace ;Locate my workspace ADR R4,ws__z ;The last item in list ; --- Find first item to search from --- CMP R1,#0 ;Is this the first call? LDREQ R1,[R0,#ll__first] ;Yes -- get first item LDRNE R1,[R1,#ll__next-ll__blockSize] ;No -- get the next ; --- Keep looking for an item that matches --- 00 CMP R1,R4 ;Are we at the end BEQ %95llist_enumerate ;Yes -- return failure LDR R14,[R1,#ll__flags] ;Get the flags word AND R14,R14,R2 ;Clear un-interesting bits CMP R14,R3 ;Is this a match? BEQ %90llist_enumerate ;Yes -- return it then LDR R1,[R1,#ll__next] ;Get the next item in list B %00llist_enumerate ;No -- test it then ;--- We have found an item which matches --- 90 ADD R1,R1,#ll__blockSize ;Point to user data LDMFD R13!,{R4,R12,R14} ;Get registers back ORRS PC,R14,#C_flag ;Return with carry set ; --- There are no more matching items --- 95 LDMFD R13!,{R4,R12,R14} ;Get registers back BICS PC,R14,#C_flag ;Return with carry clear LTORG ; --- llist_itemToIndex --- ; ; On entry: R0 == pointer to list head ; R1 == point to the item ; ; On exit: R1 == index of the item, -1 if it's not there ; ; Use: Returns the index of the item given, indexed from 0. EXPORT llist_itemToIndex llist_itemToIndex ROUT STMFD R13!,{R2,R3,R12,R14} ;Stack some registers WSPACE llist__wSpace ;Find my workspace ADR R14,ws__z ;Terminator -- (I'll be back) SUB R2,R1,#ll__blockSize ;Point to real item MOV R1,#0 ;Index so far MOV R3,R0 ;Start from here 00 LDR R3,[R3,#ll__next] ;The next item in the list CMP R3,R2 ;Is this the one we want? BEQ %99llist_itemToIndex ;Yes -- return CMP R3,R14 ;Are we at the end? MOVEQ R1,#-1 ;Yes -- no valid index then BEQ %99llist_itemToIndex ;...and return ADD R1,R1,#1 ;Increment index B %00llist_itemToIndex ;Keep on looking 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller LTORG ; --- llist_indexToItem --- ; ; On entry: R0 == pointer to list head ; R1 == point to the index (indexed from 0) ; ; On exit: R1 == the item itself, or 0 if index doesn't exist ; ; Use: Returns the index of the item given, indexed from 0. EXPORT llist_indexToItem llist_indexToItem ROUT STMFD R13!,{R2,R3,R12,R14} ;Stack some registers LDR R2,[R0,#ll__items] ;The number ot items in list CMP R1,R2 ;How do they compare? MOVGE R1,#0 ;No such index -- return 0 BGE %99llist_indexToItem ;And actually return MOV R2,R1 ;Get the index in R2 LDR R1,[R0,#ll__first] ;The first item CMP R2,#0 ;Is this the one we want? BEQ %98llist_indexToItem ;Yes -- return 00 LDR R1,[R1,#ll__next] ;Get the next in the list SUBS R2,R2,#1 ;Decrement the index BNE %00llist_indexToItem ;And keep looking 98 ADD R1,R1,#ll__blockSize 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller LTORG ; --- llist__merge --- ; ; On entry: R1 == sort routine ; R2 == list a ; R3 == list b ; R8 == z ; R9 == list c ; ; On exit: c^.next = merge of a and b ; R9 == last item in list ; ; Use: Used in the mergesort routine to merge two lists. llist__merge ROUT STMFD R13!,{R0-R5,R14} ;Stack some registers MOV R5,R1 ;Keep pointer to sort routine MOV R4,R8 ;c:=z ; --- The main loop --- 00llist__merge ADD R0,R2,#ll__blockSize ;Point to user data for a ADD R1,R3,#ll__blockSize ;Point to user data for b CMP R5,#0 ;Is there a sort routine? CMPEQ R0,R0 ;No -- make LE condition MOVNE R14,PC ;Yes -- set up return address MOVNE PC,R5 ;...and branch to sort routn BGT %10llist__merge ;If a^.key>b^.key STR R2,[R4,#ll__next] ;c^.next=a STR R4,[R2,#ll__prev] ;a^.prev=c MOV R4,R2 ;c:=a LDR R2,[R2,#ll__next] ;a:=a^.next B %20llist__merge ;Jump ahead 10llist__merge STR R3,[R4,#ll__next] ;c^.next=b STR R4,[R3,#ll__prev] ;b^.prev=c MOV R4,R3 ;c:=b LDR R3,[R3,#ll__next] ;b:=b^.next 20llist__merge CMP R4,R8 ;c=z? BNE %00llist__merge ;No -- keep looping LDR R14,[R8,#ll__next] ;z^.next STR R14,[R9,#ll__next] ;Update next for 'entry c' LDR R9,[R4,#ll__prev] ;Return last item STR R8,[R8,#ll__next] ;z^.next:=z LDMFD R13!,{R0-R5,PC}^ ;Return to caller LTORG ; --- llist__mergeSort --- ; ; On entry: R0 == pointer to list head ; R1 == pointer to sort routine ; ; On exit: -- ; ; Use: Sort the given list very quickly. Ref Sedgewick P.170 llist__mergeSort ROUT STMFD R13!,{R0-R10,R12,R14} ;Stack some registers WSPACE llist__wSpace ;Find my workspace ; --- Initialise some variables --- ADR R8,ws__z ;The terminator MOV R7,#1 ;N:=1 ; --- The outer loop --- 00 LDR R5,[R0,#ll__next] ;todo:=head^.next MOV R9,R0 ;c:=head ; --- The inner loop --- 10 MOV R4,R5 ;t:=todo MOV R2,R4 ;a:=t SUB R10,R7,#1 ;R10=N-1 MOV R6,#1 ;i:=1 15 CMP R6,R10 ;Do an iteration? LDRLE R4,[R4,#ll__next] ;Yes -- t:=t^.next ADDLE R6,R6,#1 ;...i:=i+1 BLE %15llist__mergeSort ;...continue the loop LDR R3,[R4,#ll__next] ;b:=t^.next STR R8,[R4,#ll__next] ;t^.next=z MOV R4,R3 ;t:=b MOV R6,#1 ;i:=1 20 CMP R6,R10 ;Do an iteration? LDRLE R4,[R4,#ll__next] ;Yes -- t:=t^.next ADDLE R6,R6,#1 ;...i:=i+1 BLE %20llist__mergeSort ;...continue the loop LDR R5,[R4,#ll__next] ;todo:=t^.next STR R8,[R4,#ll__next] ;t^.next=z BL llist__merge ;c^.next:=merge(a,b) ;c points to last item CMP R5,R8 ;todo=z? BNE %10llist__mergeSort ;No -- keep looping ADD R7,R7,R7 ;N:=N+N LDR R14,[R0,#ll__next] ;head^.next CMP R14,R2 ;a=head^.next? BNE %00llist__mergeSort ;No -- keep looping LDMFD R13!,{R0-R10,R12,PC}^ ;Return to caller LTORG ; --- llist_registerSort --- ; ; On entry: R0 == pointer to list head ; R1 == pointer to new sort routine ; ; On exit: -- ; ; Use: Registers a new sort routine to be used on the given ; list. This call will also cause a complete resort ; of the given list using a mergesort algorithm -- O(n log n). EXPORT llist_registerSort llist_registerSort ROUT STMFD R13!,{R12,R14} ;Stack registers WSPACE llist__wSpace ;Locate my workspace STR R1,[R0,#ll__sort] ;Store the sort routine CMP R1,#0 ;Is there one now? LDMEQFD R13!,{R12,PC}^ ;No -- return LDR R14,[R0,#ll__items] ;Get number of items in list CMP R14,#2 ;2 or more items? BLGE llist__mergeSort ;Yes -- do the merge sort LDMFD R13!,{R12,PC}^ ;Return to caller LTORG ; --- llist_init --- ; ; On entry: -- ; ; On exit: -- ; ; Use: Initialises the llistMan unit. EXPORT llist_init llist_init ROUT STMFD R13!,{R12,R14} ;Stack some registers WSPACE llist__wSpace ;Locate my workspace ; --- Ensure that we are not already initialised --- LDR R14,ws__flags ;Get the flags word TST R14,#wsFlag__inited ;Are we initialised? BNE %99llist_init ;Yes -- return ORR R14,R14,#wsFlag__inited ;We are initialised now STR R14,ws__flags ;Store back modified flags ; --- Set up the workspace --- ADR R14,ws__z ;Point to terminating item STR R14,[R14,#ll__next] ;Set up the next field ; --- Return to caller --- 99llist_init LDMFD R13!,{R12,PC}^ ;Return to caller LTORG llist__wSpace DCD 0 ;----- Workspace layout ----------------------------------------------------- ; --- The list head description --- ^ 0 ll__first # 4 ;The first item ll__sort # 4 ;The sort routine ll__items # 4 ;The number of items ; --- The list item description --- ^ 0 ll__next # 4 ;The next item in the list ll__prev # 4 ;The previous item in list ll__flags # 4 ;Various item flags ll__size # 4 ;Total size of this item ll__blockSize # 0 ;Size without user data ll__userData # 4 ;The user data itself ; --- The workspace --- ^ 0,R12 ws__start # 0 ;Workspace start ws__flags # 4 ;The flags word ws__z # 8 ;The end node of a list ws__size EQU {VAR}-ws__start ;The workspace size wsFlag__inited EQU (1<<0) ;We have been initialised AREA |Sapphire$$LibData|,CODE,READONLY DCD ws__size DCD llist__wSpace DCD 0 DCD llist_init ;----- That's all, folks ---------------------------------------------------- END