chiark - git - mdw - ssr/blob - 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