4 ; Linked List Management (TMA)
6 ; © 1994-1998 Straylight
9 ;----- Licensing note -------------------------------------------------------
11 ; This file is part of Straylight's Sapphire library.
13 ; Sapphire is free software; you can redistribute it and/or modify
14 ; it under the terms of the GNU General Public License as published by
15 ; the Free Software Foundation; either version 2, or (at your option)
18 ; Sapphire is distributed in the hope that it will be useful,
19 ; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ; GNU General Public License for more details.
23 ; You should have received a copy of the GNU General Public License
24 ; along with Sapphire. If not, write to the Free Software Foundation,
25 ; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 ;----- Standard header ------------------------------------------------------
32 ;----- External dependencies ------------------------------------------------
38 ;----- Main code ------------------------------------------------------------
40 AREA |Sapphire$$Code|,CODE,READONLY
42 ; --- llist_create ---
44 ; On entry: R0 == pointer to 12 byte list head to fill in
45 ; R1 == sort routine to use (0 for none)
47 ; On exit: List head filled in appropriately
49 ; Use: This call set up list. It must be made just once, before
50 ; and other list alls are made. On entry, R0 must point to
51 ; 12 bytes in memory, which is filled in by this call.
52 ; Example code may look like:
67 STMFD R13!,{R12,R14} ;Stack some registers
68 WSPACE llist__wSpace ;Locate my workspace
70 ADR R14,ws__z ;Point to list terminator
71 STR R14,[R0,#ll__first] ;Store in the list head
72 STR R1,[R0,#ll__sort] ;The sort routine
73 MOV R14,#0 ;Number of items so far
74 STR R14,[R0,#ll__items] ;Stor that in the block
76 LDMFD R13!,{R12,PC}^ ;Return to caller
80 ; --- llist_destroy ---
82 ; On entry: R0 == pointer to list head
84 ; On exit: R0 corrupted
86 ; Use: Destroys the given list.
91 STMFD R13!,{R1,R2,R12,R14} ;Stack registers
92 WSPACE llist__wSpace ;Locate my workspace
93 ADR R1,ws__z ;Point to terminator
95 LDR R0,[R0,#ll__first] ;Get the first item
96 00llist_destroy LDR R2,[R0,#ll__next] ;Get the next item
97 CMP R0,R1 ;Are we at the end?
98 BLNE free ;No -- free item
99 MOVNE R0,R2 ;Get the next item
100 BNE %00llist_destroy ;And destroy that too
102 LDMFD R13!,{R1,R2,R12,PC}^ ;Return to caller
106 ; --- llist__insert ---
108 ; On entry: R0 == pointer to the list head
109 ; R1 == pointer to the item (user data)
113 ; Use: Insert the given item into the list, assuming that the list
118 STMFD R13!,{R0-R5,R12,R14} ;Stack some registers
119 WSPACE llist__wSpace ;Find workspace
120 ADR R2,ws__z ;The list terminator
122 LDR R5,[R0,#ll__sort] ;The sort routine
123 MOV R3,R0 ;The previous item
125 ; --- Scan through the items, until comparison is GT ---
127 00llist__insert MOV R4,R3 ;The previous item
128 LDR R3,[R3,#ll__next] ;Get the next item
129 CMP R3,R2 ;Is there one?
130 BEQ %20llist__insert ;No -- insert at end
131 ADD R0,R3,#ll__blockSize ;Point to user data
132 CMP R5,#0 ;Is there a sort routine?
133 CMPEQ R0,R0 ;No -- make LE condition
134 MOVNE R14,PC ;Yes -- set up return address
135 MOVNE PC,R5 ;...and branch to sort routn
136 BLE %00llist__insert ;Keep looking
138 ; --- Insert the item ---
140 20llist__insert SUB R1,R1,#ll__blockSize ;Point to full item desc
141 STR R1,[R4,#ll__next] ;Store in previous next ^
142 STR R3,[R1,#ll__next] ;Update this next pointer
143 STR R1,[R3,#ll__prev] ;Update next previous pointer
144 STR R4,[R1,#ll__prev] ;Update this previous pointer
146 ; --- Return to the caller ---
148 99llist__insert LDMFD R13!,{R0-R5,R12,PC}^ ;Return
152 ; --- llist_addItem ---
154 ; On entry: R0 == pointer to list head
155 ; R1 == pointer to user data (or 0 if none to copy)
156 ; R2 == size of user data
158 ; On exit: R0 preserved
159 ; R1 == pointer to the new user data
160 ; May return an error
162 ; Use: This call will add an item to a list. Notice that the
163 ; item is entirely allocated by the list manager, it does not
164 ; point to the data that you supply it, instead it
165 ; copies the data into the newly created item. For this reason
166 ; if 0 is supplied as the user data, nothing is copied.
167 ; It is the returned user data pointer, that must be
168 ; used to reference the item in other llist calls.
173 BIC R14,R14,#V_flag ;No error yet
174 STMFD R13!,{R0,R2,R3,R12,R14} ;Stack some registers
175 WSPACE llist__wSpace ;Locate workspace
177 MOV R3,R2 ;Size of user data
178 ADD R2,R2,#ll__blockSize+3 ;The blocksize required
179 BIC R2,R2,#3 ;Word align
180 MOV R0,R2 ;Allocate this much
181 BL alloc ;Try to allocate the block
182 BCS alloc_error ;No memory? Get message
183 BVS %99llist_addItem ;And return with error
185 STR R2,[R0,#ll__size] ;Store the item size
186 MOV R2,R3 ;Just copy this much
187 MOV R3,R0 ;Remember this pointer
188 ADD R0,R0,#ll__blockSize ;Point to user data
189 CMP R1,#0 ;Any data supplied?
190 BLNE fastMove ;Yes -- copy it over
191 MOV R2,#0 ;The flags word
192 STR R2,[R3,#ll__flags] ;Store them nicely
193 BEQ %10llist_addItem ;...and insert at beginning
194 MOV R1,R0 ;Point to the list item block
195 LDMIA R13,{R0} ;Get list head back
196 BL llist__insert ;Insert the item in the list
197 LDR R2,[R0,#ll__items] ;Get the item count
198 ADD R2,R2,#1 ;Increment it
199 STR R2,[R0,#ll__items] ;Store it back again
200 B %99llist_addItem ;Return to caller
202 ; --- Just insert at the beginning ---
204 10llist_addItem MOV R1,R0 ;Point to the item data
205 SUB R0,R0,#ll__blockSize ;Point to full item desc
206 LDMIA R13,{R2} ;Get list head back
207 STR R2,[R0,#ll__prev] ;Store head in item
208 LDR R14,[R2,#ll__first] ;Get the first item
209 STR R14,[R0,#ll__next] ;Store this as second item
210 STR R0,[R2,#ll__first] ;Store this as first item
211 STR R0,[R14,#ll__prev] ;Finish off the insertion
212 LDR R14,[R2,#ll__items] ;Get the item count
213 ADD R14,R14,#1 ;Increment it
214 STR R14,[R2,#ll__items] ;Store it back again
216 99llist_addItem LDMFD R13!,{R0,R2,R3,R12,R14} ;Get registers back
217 ORRVSS PC,R14,#V_flag ;Return either with...
218 BICVCS PC,R14,#V_flag ;...or without error
222 ; --- llist__removeItem ---
224 ; On entry: R1 == pointer to item to remove (as returned by addItem)
228 ; Use: This call removes the item from the given list. The
229 ; item in question is not freed.
231 llist__removeItem ROUT
233 STMFD R13!,{R1,R2,R14} ;Stack some registers
235 SUB R1,R1,#ll__blockSize ;Point to the real item block
236 LDR R2,[R1,#ll__next] ;Get next item in list
237 LDR R14,[R1,#ll__prev] ;And the previous item
238 STR R2,[R14,#ll__next] ;Update previous next pointer
239 STR R14,[R2,#ll__prev] ;Update next previous pointer
241 LDMFD R13!,{R1,R2,PC}^ ;Return to caller
245 ; --- llist_removeItem ---
247 ; On entry: R0 == list head pointer
248 ; R1 == pointer to item to remove (as returned by addItem)
252 ; Use: This call removes the item from the given list. All
253 ; memory taken up by the item is freed. If the value
254 ; passed in R1 is not an item in the list, then all hell is
255 ; likely to break loose, so I don't advise making this mistake.
257 EXPORT llist_removeItem
258 llist_removeItem ROUT
260 STMFD R13!,{R0,R1,R14} ;Stack some registers
262 BL llist__removeItem ;Remove the item
263 LDR R14,[R0,#ll__items] ;Get the item count
264 SUB R14,R14,#1 ;Reduce it
265 STR R14,[R0,#ll__items] ;Store it back again
266 SUB R1,R1,#ll__blockSize ;Point to the allocated block
267 MOV R0,R1 ;Point to item to remove
268 BL free ;Free it nicely
270 LDMFD R13!,{R0,R1,PC}^ ;Return to caller
274 ; --- llist_reinsert ---
276 ; On entry: R0 == pointer to list head
277 ; R1 == item to reinsert
281 ; Use: Reinserts the given item into the list. This call is
282 ; used if the item is updated in such a way that its
283 ; position in the list may change.
285 EXPORT llist_reinsert
288 STMFD R13!,{R14} ;Stack the link register
289 BL llist__removeItem ;Remove the item from list
290 BL llist__insert ;Insert it into the list
291 LDMFD R13!,{PC}^ ;Return to caller
295 ; --- llist_setFlags ---
297 ; On entry: R1 == pointer to list item
301 ; On exit: R2 == the new flags word
303 ; Use: Sets the flags associated with the given item. If you
304 ; just wish to read them, set R2 and R3 to 0.
306 EXPORT llist_setFlags
309 STMFD R13!,{R0,R14} ;Stack registers
310 SUB R0,R1,#ll__blockSize ;Point to real item
311 LDR R14,[R0,#ll__flags] ;Get the flags word
312 BIC R14,R14,R2 ;Do the BIC operation
313 EOR R14,R14,R3 ;Now the EOR op
314 STR R14,[R0,#ll__flags] ;Set the flags word
315 MOV R2,R14 ;Return these flags
316 LDMFD R13!,{R0,PC}^ ;Return to caller
320 ; --- llist_items ---
322 ; On entry: R0 == pointer to list head
324 ; On exit: R1 == number of items in list
326 ; Use: Returns the number of items in the list given. This is
327 ; a cached value, and so is very fast.
332 LDR R1,[R0,#ll__items] ;Get the number of items
333 MOVS PC,R14 ;And return
335 ; --- llist_enumerate ---
337 ; On entry: R0 == pointer to list head
338 ; R1 == pointer to item (0 for first)
342 ; On exit: CS and R1 == next item that matches
343 ; CC and R1 corrupted if no more items
345 ; Use: This calls return each item in the list, one at a time,
346 ; as long as the item matches the pattern given.
348 EXPORT llist_enumerate
351 STMFD R13!,{R4,R12,R14} ;Stack some registers
352 WSPACE llist__wSpace ;Locate my workspace
353 ADR R4,ws__z ;The last item in list
355 ; --- Find first item to search from ---
357 CMP R1,#0 ;Is this the first call?
358 LDREQ R1,[R0,#ll__first] ;Yes -- get first item
359 LDRNE R1,[R1,#ll__next-ll__blockSize] ;No -- get the next
361 ; --- Keep looking for an item that matches ---
363 00 CMP R1,R4 ;Are we at the end
364 BEQ %95llist_enumerate ;Yes -- return failure
365 LDR R14,[R1,#ll__flags] ;Get the flags word
366 AND R14,R14,R2 ;Clear un-interesting bits
367 CMP R14,R3 ;Is this a match?
368 BEQ %90llist_enumerate ;Yes -- return it then
369 LDR R1,[R1,#ll__next] ;Get the next item in list
370 B %00llist_enumerate ;No -- test it then
372 ;--- We have found an item which matches ---
374 90 ADD R1,R1,#ll__blockSize ;Point to user data
375 LDMFD R13!,{R4,R12,R14} ;Get registers back
376 ORRS PC,R14,#C_flag ;Return with carry set
378 ; --- There are no more matching items ---
380 95 LDMFD R13!,{R4,R12,R14} ;Get registers back
381 BICS PC,R14,#C_flag ;Return with carry clear
385 ; --- llist_itemToIndex ---
387 ; On entry: R0 == pointer to list head
388 ; R1 == point to the item
390 ; On exit: R1 == index of the item, -1 if it's not there
392 ; Use: Returns the index of the item given, indexed from 0.
394 EXPORT llist_itemToIndex
395 llist_itemToIndex ROUT
397 STMFD R13!,{R2,R3,R12,R14} ;Stack some registers
398 WSPACE llist__wSpace ;Find my workspace
399 ADR R14,ws__z ;Terminator -- (I'll be back)
401 SUB R2,R1,#ll__blockSize ;Point to real item
402 MOV R1,#0 ;Index so far
403 MOV R3,R0 ;Start from here
404 00 LDR R3,[R3,#ll__next] ;The next item in the list
405 CMP R3,R2 ;Is this the one we want?
406 BEQ %99llist_itemToIndex ;Yes -- return
407 CMP R3,R14 ;Are we at the end?
408 MOVEQ R1,#-1 ;Yes -- no valid index then
409 BEQ %99llist_itemToIndex ;...and return
410 ADD R1,R1,#1 ;Increment index
411 B %00llist_itemToIndex ;Keep on looking
413 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller
417 ; --- llist_indexToItem ---
419 ; On entry: R0 == pointer to list head
420 ; R1 == point to the index (indexed from 0)
422 ; On exit: R1 == the item itself, or 0 if index doesn't exist
424 ; Use: Returns the index of the item given, indexed from 0.
426 EXPORT llist_indexToItem
427 llist_indexToItem ROUT
429 STMFD R13!,{R2,R3,R12,R14} ;Stack some registers
431 LDR R2,[R0,#ll__items] ;The number ot items in list
432 CMP R1,R2 ;How do they compare?
433 MOVGE R1,#0 ;No such index -- return 0
434 BGE %99llist_indexToItem ;And actually return
436 MOV R2,R1 ;Get the index in R2
437 LDR R1,[R0,#ll__first] ;The first item
438 CMP R2,#0 ;Is this the one we want?
439 BEQ %98llist_indexToItem ;Yes -- return
440 00 LDR R1,[R1,#ll__next] ;Get the next in the list
441 SUBS R2,R2,#1 ;Decrement the index
442 BNE %00llist_indexToItem ;And keep looking
444 98 ADD R1,R1,#ll__blockSize
445 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller
449 ; --- llist__merge ---
451 ; On entry: R1 == sort routine
457 ; On exit: c^.next = merge of a and b
458 ; R9 == last item in list
460 ; Use: Used in the mergesort routine to merge two lists.
464 STMFD R13!,{R0-R5,R14} ;Stack some registers
466 MOV R5,R1 ;Keep pointer to sort routine
469 ; --- The main loop ---
471 00llist__merge ADD R0,R2,#ll__blockSize ;Point to user data for a
472 ADD R1,R3,#ll__blockSize ;Point to user data for b
473 CMP R5,#0 ;Is there a sort routine?
474 CMPEQ R0,R0 ;No -- make LE condition
475 MOVNE R14,PC ;Yes -- set up return address
476 MOVNE PC,R5 ;...and branch to sort routn
477 BGT %10llist__merge ;If a^.key>b^.key
479 STR R2,[R4,#ll__next] ;c^.next=a
480 STR R4,[R2,#ll__prev] ;a^.prev=c
482 LDR R2,[R2,#ll__next] ;a:=a^.next
483 B %20llist__merge ;Jump ahead
485 10llist__merge STR R3,[R4,#ll__next] ;c^.next=b
486 STR R4,[R3,#ll__prev] ;b^.prev=c
488 LDR R3,[R3,#ll__next] ;b:=b^.next
490 20llist__merge CMP R4,R8 ;c=z?
491 BNE %00llist__merge ;No -- keep looping
493 LDR R14,[R8,#ll__next] ;z^.next
494 STR R14,[R9,#ll__next] ;Update next for 'entry c'
495 LDR R9,[R4,#ll__prev] ;Return last item
496 STR R8,[R8,#ll__next] ;z^.next:=z
498 LDMFD R13!,{R0-R5,PC}^ ;Return to caller
502 ; --- llist__mergeSort ---
504 ; On entry: R0 == pointer to list head
505 ; R1 == pointer to sort routine
509 ; Use: Sort the given list very quickly. Ref Sedgewick P.170
511 llist__mergeSort ROUT
513 STMFD R13!,{R0-R10,R12,R14} ;Stack some registers
514 WSPACE llist__wSpace ;Find my workspace
516 ; --- Initialise some variables ---
518 ADR R8,ws__z ;The terminator
521 ; --- The outer loop ---
523 00 LDR R5,[R0,#ll__next] ;todo:=head^.next
526 ; --- The inner loop ---
528 10 MOV R4,R5 ;t:=todo
530 SUB R10,R7,#1 ;R10=N-1
533 15 CMP R6,R10 ;Do an iteration?
534 LDRLE R4,[R4,#ll__next] ;Yes -- t:=t^.next
535 ADDLE R6,R6,#1 ;...i:=i+1
536 BLE %15llist__mergeSort ;...continue the loop
538 LDR R3,[R4,#ll__next] ;b:=t^.next
539 STR R8,[R4,#ll__next] ;t^.next=z
543 20 CMP R6,R10 ;Do an iteration?
544 LDRLE R4,[R4,#ll__next] ;Yes -- t:=t^.next
545 ADDLE R6,R6,#1 ;...i:=i+1
546 BLE %20llist__mergeSort ;...continue the loop
548 LDR R5,[R4,#ll__next] ;todo:=t^.next
549 STR R8,[R4,#ll__next] ;t^.next=z
551 BL llist__merge ;c^.next:=merge(a,b)
552 ;c points to last item
555 BNE %10llist__mergeSort ;No -- keep looping
559 LDR R14,[R0,#ll__next] ;head^.next
560 CMP R14,R2 ;a=head^.next?
561 BNE %00llist__mergeSort ;No -- keep looping
563 LDMFD R13!,{R0-R10,R12,PC}^ ;Return to caller
567 ; --- llist_registerSort ---
569 ; On entry: R0 == pointer to list head
570 ; R1 == pointer to new sort routine
574 ; Use: Registers a new sort routine to be used on the given
575 ; list. This call will also cause a complete resort
576 ; of the given list using a mergesort algorithm -- O(n log n).
578 EXPORT llist_registerSort
579 llist_registerSort ROUT
581 STMFD R13!,{R12,R14} ;Stack registers
582 WSPACE llist__wSpace ;Locate my workspace
584 STR R1,[R0,#ll__sort] ;Store the sort routine
585 CMP R1,#0 ;Is there one now?
586 LDMEQFD R13!,{R12,PC}^ ;No -- return
587 LDR R14,[R0,#ll__items] ;Get number of items in list
588 CMP R14,#2 ;2 or more items?
589 BLGE llist__mergeSort ;Yes -- do the merge sort
591 LDMFD R13!,{R12,PC}^ ;Return to caller
601 ; Use: Initialises the llistMan unit.
606 STMFD R13!,{R12,R14} ;Stack some registers
607 WSPACE llist__wSpace ;Locate my workspace
609 ; --- Ensure that we are not already initialised ---
611 LDR R14,ws__flags ;Get the flags word
612 TST R14,#wsFlag__inited ;Are we initialised?
613 BNE %99llist_init ;Yes -- return
614 ORR R14,R14,#wsFlag__inited ;We are initialised now
615 STR R14,ws__flags ;Store back modified flags
617 ; --- Set up the workspace ---
619 ADR R14,ws__z ;Point to terminating item
620 STR R14,[R14,#ll__next] ;Set up the next field
622 ; --- Return to caller ---
624 99llist_init LDMFD R13!,{R12,PC}^ ;Return to caller
630 ;----- Workspace layout -----------------------------------------------------
632 ; --- The list head description ---
636 ll__first # 4 ;The first item
637 ll__sort # 4 ;The sort routine
638 ll__items # 4 ;The number of items
640 ; --- The list item description ---
644 ll__next # 4 ;The next item in the list
645 ll__prev # 4 ;The previous item in list
646 ll__flags # 4 ;Various item flags
647 ll__size # 4 ;Total size of this item
648 ll__blockSize # 0 ;Size without user data
649 ll__userData # 4 ;The user data itself
651 ; --- The workspace ---
655 ws__start # 0 ;Workspace start
657 ws__flags # 4 ;The flags word
658 ws__z # 8 ;The end node of a list
660 ws__size EQU {VAR}-ws__start ;The workspace size
662 wsFlag__inited EQU (1<<0) ;We have been initialised
664 AREA |Sapphire$$LibData|,CODE,READONLY
671 ;----- That's all, folks ----------------------------------------------------