Initial revision
[ssr] / StraySrc / Libraries / Sapphire / s / llistMan
1 ;
2 ; llistMan.s
3 ;
4 ; Linked List Management (TMA)
5 ;
6 ; © 1994-1998 Straylight
7 ;
8
9 ;----- Licensing note -------------------------------------------------------
10 ;
11 ; This file is part of Straylight's Sapphire library.
12 ;
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)
16 ; any later version.
17 ;
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.
22 ;
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.
26
27 ;----- Standard header ------------------------------------------------------
28
29 GET libs:header
30 GET libs:swis
31
32 ;----- External dependencies ------------------------------------------------
33
34 GET sapphire:alloc
35 GET sapphire:fastMove
36 GET sapphire:sapphire
37
38 ;----- Main code ------------------------------------------------------------
39
40 AREA |Sapphire$$Code|,CODE,READONLY
41
42 ; --- llist_create ---
43 ;
44 ; On entry: R0 == pointer to 12 byte list head to fill in
45 ; R1 == sort routine to use (0 for none)
46 ;
47 ; On exit: List head filled in appropriately
48 ;
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:
53 ;
54 ; ADR R0,myList
55 ; LDR R1,=myStrCmp
56 ; BL llist_create
57 ;
58 ; .
59 ; .
60 ; .
61 ;
62 ; mylist DCD 0,0
63
64 EXPORT llist_create
65 llist_create ROUT
66
67 STMFD R13!,{R12,R14} ;Stack some registers
68 WSPACE llist__wSpace ;Locate my workspace
69
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
75
76 LDMFD R13!,{R12,PC}^ ;Return to caller
77
78 LTORG
79
80 ; --- llist_destroy ---
81 ;
82 ; On entry: R0 == pointer to list head
83 ;
84 ; On exit: R0 corrupted
85 ;
86 ; Use: Destroys the given list.
87
88 EXPORT llist_destroy
89 llist_destroy ROUT
90
91 STMFD R13!,{R1,R2,R12,R14} ;Stack registers
92 WSPACE llist__wSpace ;Locate my workspace
93 ADR R1,ws__z ;Point to terminator
94
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
101
102 LDMFD R13!,{R1,R2,R12,PC}^ ;Return to caller
103
104 LTORG
105
106 ; --- llist__insert ---
107 ;
108 ; On entry: R0 == pointer to the list head
109 ; R1 == pointer to the item (user data)
110 ;
111 ; On exit: --
112 ;
113 ; Use: Insert the given item into the list, assuming that the list
114 ; is already sorted.
115
116 llist__insert ROUT
117
118 STMFD R13!,{R0-R5,R12,R14} ;Stack some registers
119 WSPACE llist__wSpace ;Find workspace
120 ADR R2,ws__z ;The list terminator
121
122 LDR R5,[R0,#ll__sort] ;The sort routine
123 MOV R3,R0 ;The previous item
124
125 ; --- Scan through the items, until comparison is GT ---
126
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
137
138 ; --- Insert the item ---
139
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
145
146 ; --- Return to the caller ---
147
148 99llist__insert LDMFD R13!,{R0-R5,R12,PC}^ ;Return
149
150 LTORG
151
152 ; --- llist_addItem ---
153 ;
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
157 ;
158 ; On exit: R0 preserved
159 ; R1 == pointer to the new user data
160 ; May return an error
161 ;
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.
169
170 EXPORT llist_addItem
171 llist_addItem ROUT
172
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
176
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
184
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
201
202 ; --- Just insert at the beginning ---
203
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
215
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
219
220 LTORG
221
222 ; --- llist__removeItem ---
223 ;
224 ; On entry: R1 == pointer to item to remove (as returned by addItem)
225 ;
226 ; On exit: --
227 ;
228 ; Use: This call removes the item from the given list. The
229 ; item in question is not freed.
230
231 llist__removeItem ROUT
232
233 STMFD R13!,{R1,R2,R14} ;Stack some registers
234
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
240
241 LDMFD R13!,{R1,R2,PC}^ ;Return to caller
242
243 LTORG
244
245 ; --- llist_removeItem ---
246 ;
247 ; On entry: R0 == list head pointer
248 ; R1 == pointer to item to remove (as returned by addItem)
249 ;
250 ; On exit: --
251 ;
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.
256
257 EXPORT llist_removeItem
258 llist_removeItem ROUT
259
260 STMFD R13!,{R0,R1,R14} ;Stack some registers
261
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
269
270 LDMFD R13!,{R0,R1,PC}^ ;Return to caller
271
272 LTORG
273
274 ; --- llist_reinsert ---
275 ;
276 ; On entry: R0 == pointer to list head
277 ; R1 == item to reinsert
278 ;
279 ; On exit: --
280 ;
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.
284
285 EXPORT llist_reinsert
286 llist_reinsert ROUT
287
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
292
293 LTORG
294
295 ; --- llist_setFlags ---
296 ;
297 ; On entry: R1 == pointer to list item
298 ; R2 == BIC word
299 ; R3 == EOR word
300 ;
301 ; On exit: R2 == the new flags word
302 ;
303 ; Use: Sets the flags associated with the given item. If you
304 ; just wish to read them, set R2 and R3 to 0.
305
306 EXPORT llist_setFlags
307 llist_setFlags ROUT
308
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
317
318 LTORG
319
320 ; --- llist_items ---
321 ;
322 ; On entry: R0 == pointer to list head
323 ;
324 ; On exit: R1 == number of items in list
325 ;
326 ; Use: Returns the number of items in the list given. This is
327 ; a cached value, and so is very fast.
328
329 EXPORT llist_items
330 llist_items ROUT
331
332 LDR R1,[R0,#ll__items] ;Get the number of items
333 MOVS PC,R14 ;And return
334
335 ; --- llist_enumerate ---
336 ;
337 ; On entry: R0 == pointer to list head
338 ; R1 == pointer to item (0 for first)
339 ; R2 == mask word
340 ; R3 == test word
341 ;
342 ; On exit: CS and R1 == next item that matches
343 ; CC and R1 corrupted if no more items
344 ;
345 ; Use: This calls return each item in the list, one at a time,
346 ; as long as the item matches the pattern given.
347
348 EXPORT llist_enumerate
349 llist_enumerate ROUT
350
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
354
355 ; --- Find first item to search from ---
356
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
360
361 ; --- Keep looking for an item that matches ---
362
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
371
372 ;--- We have found an item which matches ---
373
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
377
378 ; --- There are no more matching items ---
379
380 95 LDMFD R13!,{R4,R12,R14} ;Get registers back
381 BICS PC,R14,#C_flag ;Return with carry clear
382
383 LTORG
384
385 ; --- llist_itemToIndex ---
386 ;
387 ; On entry: R0 == pointer to list head
388 ; R1 == point to the item
389 ;
390 ; On exit: R1 == index of the item, -1 if it's not there
391 ;
392 ; Use: Returns the index of the item given, indexed from 0.
393
394 EXPORT llist_itemToIndex
395 llist_itemToIndex ROUT
396
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)
400
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
412
413 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller
414
415 LTORG
416
417 ; --- llist_indexToItem ---
418 ;
419 ; On entry: R0 == pointer to list head
420 ; R1 == point to the index (indexed from 0)
421 ;
422 ; On exit: R1 == the item itself, or 0 if index doesn't exist
423 ;
424 ; Use: Returns the index of the item given, indexed from 0.
425
426 EXPORT llist_indexToItem
427 llist_indexToItem ROUT
428
429 STMFD R13!,{R2,R3,R12,R14} ;Stack some registers
430
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
435
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
443
444 98 ADD R1,R1,#ll__blockSize
445 99 LDMFD R13!,{R2,R3,R12,PC}^ ;Return to caller
446
447 LTORG
448
449 ; --- llist__merge ---
450 ;
451 ; On entry: R1 == sort routine
452 ; R2 == list a
453 ; R3 == list b
454 ; R8 == z
455 ; R9 == list c
456 ;
457 ; On exit: c^.next = merge of a and b
458 ; R9 == last item in list
459 ;
460 ; Use: Used in the mergesort routine to merge two lists.
461
462 llist__merge ROUT
463
464 STMFD R13!,{R0-R5,R14} ;Stack some registers
465
466 MOV R5,R1 ;Keep pointer to sort routine
467 MOV R4,R8 ;c:=z
468
469 ; --- The main loop ---
470
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
478
479 STR R2,[R4,#ll__next] ;c^.next=a
480 STR R4,[R2,#ll__prev] ;a^.prev=c
481 MOV R4,R2 ;c:=a
482 LDR R2,[R2,#ll__next] ;a:=a^.next
483 B %20llist__merge ;Jump ahead
484
485 10llist__merge STR R3,[R4,#ll__next] ;c^.next=b
486 STR R4,[R3,#ll__prev] ;b^.prev=c
487 MOV R4,R3 ;c:=b
488 LDR R3,[R3,#ll__next] ;b:=b^.next
489
490 20llist__merge CMP R4,R8 ;c=z?
491 BNE %00llist__merge ;No -- keep looping
492
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
497
498 LDMFD R13!,{R0-R5,PC}^ ;Return to caller
499
500 LTORG
501
502 ; --- llist__mergeSort ---
503 ;
504 ; On entry: R0 == pointer to list head
505 ; R1 == pointer to sort routine
506 ;
507 ; On exit: --
508 ;
509 ; Use: Sort the given list very quickly. Ref Sedgewick P.170
510
511 llist__mergeSort ROUT
512
513 STMFD R13!,{R0-R10,R12,R14} ;Stack some registers
514 WSPACE llist__wSpace ;Find my workspace
515
516 ; --- Initialise some variables ---
517
518 ADR R8,ws__z ;The terminator
519 MOV R7,#1 ;N:=1
520
521 ; --- The outer loop ---
522
523 00 LDR R5,[R0,#ll__next] ;todo:=head^.next
524 MOV R9,R0 ;c:=head
525
526 ; --- The inner loop ---
527
528 10 MOV R4,R5 ;t:=todo
529 MOV R2,R4 ;a:=t
530 SUB R10,R7,#1 ;R10=N-1
531
532 MOV R6,#1 ;i:=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
537
538 LDR R3,[R4,#ll__next] ;b:=t^.next
539 STR R8,[R4,#ll__next] ;t^.next=z
540 MOV R4,R3 ;t:=b
541
542 MOV R6,#1 ;i:=1
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
547
548 LDR R5,[R4,#ll__next] ;todo:=t^.next
549 STR R8,[R4,#ll__next] ;t^.next=z
550
551 BL llist__merge ;c^.next:=merge(a,b)
552 ;c points to last item
553
554 CMP R5,R8 ;todo=z?
555 BNE %10llist__mergeSort ;No -- keep looping
556
557 ADD R7,R7,R7 ;N:=N+N
558
559 LDR R14,[R0,#ll__next] ;head^.next
560 CMP R14,R2 ;a=head^.next?
561 BNE %00llist__mergeSort ;No -- keep looping
562
563 LDMFD R13!,{R0-R10,R12,PC}^ ;Return to caller
564
565 LTORG
566
567 ; --- llist_registerSort ---
568 ;
569 ; On entry: R0 == pointer to list head
570 ; R1 == pointer to new sort routine
571 ;
572 ; On exit: --
573 ;
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).
577
578 EXPORT llist_registerSort
579 llist_registerSort ROUT
580
581 STMFD R13!,{R12,R14} ;Stack registers
582 WSPACE llist__wSpace ;Locate my workspace
583
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
590
591 LDMFD R13!,{R12,PC}^ ;Return to caller
592
593 LTORG
594
595 ; --- llist_init ---
596 ;
597 ; On entry: --
598 ;
599 ; On exit: --
600 ;
601 ; Use: Initialises the llistMan unit.
602
603 EXPORT llist_init
604 llist_init ROUT
605
606 STMFD R13!,{R12,R14} ;Stack some registers
607 WSPACE llist__wSpace ;Locate my workspace
608
609 ; --- Ensure that we are not already initialised ---
610
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
616
617 ; --- Set up the workspace ---
618
619 ADR R14,ws__z ;Point to terminating item
620 STR R14,[R14,#ll__next] ;Set up the next field
621
622 ; --- Return to caller ---
623
624 99llist_init LDMFD R13!,{R12,PC}^ ;Return to caller
625
626 LTORG
627
628 llist__wSpace DCD 0
629
630 ;----- Workspace layout -----------------------------------------------------
631
632 ; --- The list head description ---
633
634 ^ 0
635
636 ll__first # 4 ;The first item
637 ll__sort # 4 ;The sort routine
638 ll__items # 4 ;The number of items
639
640 ; --- The list item description ---
641
642 ^ 0
643
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
650
651 ; --- The workspace ---
652
653 ^ 0,R12
654
655 ws__start # 0 ;Workspace start
656
657 ws__flags # 4 ;The flags word
658 ws__z # 8 ;The end node of a list
659
660 ws__size EQU {VAR}-ws__start ;The workspace size
661
662 wsFlag__inited EQU (1<<0) ;We have been initialised
663
664 AREA |Sapphire$$LibData|,CODE,READONLY
665
666 DCD ws__size
667 DCD llist__wSpace
668 DCD 0
669 DCD llist_init
670
671 ;----- That's all, folks ----------------------------------------------------
672
673 END