chiark - git - mdw - ssr/blob - StraySrc/Libraries/Core/s/heap

   1 ;
   2 ; heap.s
   3 ;
   4 ; A resizing, nonshifting heap (MDW)
   5 ;
   6 ; © 1994-1998 Straylight
   7 ;
   8
   9 ;----- Licensing note -------------------------------------------------------
  10 ;
  11 ; This file is part of Straylight's heap.
  12 ;
  13 ; Heap 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 ; Heap 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 Heap.  If not, write to the Free Software Foundation,
  25 ; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  26
  27 ;----- New unified version --------------------------------------------------
  28 ;
  29 ; I'm finally fed up of maintaining two different versions of this code.
  30 ; From now on, there is only this one.
  31 ;
  32 ; Lots of options are supported:
  33 ;
  34 ; OPT_APCS      Generate an APCS-compatible version
  35 ; OPT_SAPPHIRE  Generate a Sapphire-compatible version
  36 ; OPT_STANDALONE Build a standalone assembler version (default)
  37 ; OPT_DLL       Generate absolute address relocation for DLL code
  38 ;
  39 ;                                                               [mdw]
  40
  41 ;----- Set up some options --------------------------------------------------
  42
  43                 MACRO
  44                 DCLOPT  $var
  45                 [       :DEF:$var
  46 $var            SETL    {TRUE}
  47                 |
  48                 GBLL    $var
  49 $var            SETL    {FALSE}
  50                 ]
  51                 MEND
  52
  53                 DCLOPT  OPT_APCS
  54                 DCLOPT  OPT_SAPPHIRE
  55                 DCLOPT  OPT_STANDALONE
  56                 DCLOPT  OPT_DLL
  57
  58         [ :LNOT:OPT_APCS:LAND::LNOT:OPT_SAPPHIRE:LAND::LNOT:OPT_STANDALONE
  59                 GBLL    OPT_STANDALONE
  60 OPT_STANDALONE  SETL    {TRUE}
  61         ]
  62
  63 ;----- Standard header ------------------------------------------------------
  64
  65                 GET     libs:header
  66                 GET     libs:swis
  67
  68 ;----- External dependencies ------------------------------------------------
  69
  70         [ OPT_SAPPHIRE
  71                 GET     sapphire:alloc
  72                 GET     sapphire:flex
  73                 GET     sapphire:msgs
  74                 GET     sapphire:fastMove
  75                 GET     sapphire:sapphire
  76         |
  77                 IMPORT  fastMove
  78                 IMPORT  flex_init
  79                 IMPORT  flex_alloc
  80                 IMPORT  flex_extend
  81         ]
  82
  83 ;----- Workspace macros -----------------------------------------------------
  84
  85         [ OPT_APCS
  86
  87                 MACRO
  88 $label          WSPACE  $addr,$reg
  89                 LCLS    r
  90                 [       "$reg"=""
  91 r               SETS    "R12"
  92                 |
  93 r               SETS    "$reg"
  94                 ]
  95                 ALIGN
  96 $label
  97                 LDR     $r,$addr
  98                 [       OPT_DLL
  99                 LDR     R14,[R10,#-536]
 100                 ADD     $r,R14,$r
 101                 ]
 102                 MEND
 103
 104         ]
 105
 106 ;----- External routines ----------------------------------------------------
 107
 108         [ OPT_SAPPHIRE
 109                 AREA    |Sapphire$$Code|,CODE,READONLY
 110         ]
 111         [ OPT_APCS
 112                 AREA    |C$$Code|,CODE,READONLY
 113         ]
 114         [ OPT_STANDALONE
 115                 AREA    |Straylight$$Code|,CODE,READONLY
 116         ]
 117
 118 ; --- heap_init ---
 119 ;
 120 ; On entry:     --
 121 ;
 122 ; On exit:      --
 123 ;
 124 ; Use:          Initialises the heap system for use.
 125
 126                 EXPORT  heap_init
 127
 128 heap_init       ROUT
 129
 130                 STMFD   R13!,{R0,R1,R12,R14}    ;Stash some registers
 131                 WSPACE  heap__wSpace            ;Find my workspace
 132
 133         [ OPT_SAPPHIRE
 134                 BL      msgs_init               ;Make sure msgs is going
 135         ]
 136                 BL      flex_init               ;Make sure flex is up
 137
 138         [ :LNOT:OPT_STANDALONE
 139
 140                 ; --- Ensure I'm not already initialised ---
 141
 142                 LDR     R0,heap__flex           ;Get my flex pointer
 143                 CMP     R0,#0                   ;Is it a silly value?
 144                 LDMNEFD R13!,{R0,R1,R12,PC}^    ;Yes -- return now
 145
 146         ]
 147
 148                 ; --- Read the machine chunk size ---
 149
 150                 SWI     OS_ReadMemMapInfo       ;Get page size (in R0)
 151                 STR     R0,heap__chunkSize      ;Store for future reference
 152
 153                 ; --- Allocate the base flex block ---
 154
 155                 SUB     R1,R0,#8                ;Need to allocate memory
 156                 ADR     R0,heap__flex           ;Point to flex anchor
 157                 BL      flex_alloc              ;Hope it worked
 158         [ OPT_APCS
 159                 CMP     R0,#0                   ;Check the result code
 160                 BEQ     %99heap_init            ;If it failed, go ahead
 161         |
 162                 BCS     %99heap_init            ;If it failed, go ahead
 163         ]
 164
 165                 ; --- Initialise the rest of the workspace ---
 166
 167                 MOV     R0,#0
 168                 STR     R0,heap__alloced
 169                 MOV     R0,#-1
 170                 STR     R0,heap__freeList
 171                 LDR     R0,heap__chunkSize
 172                 SUB     R0,R0,#8
 173                 STR     R0,heap__size
 174                 LDMFD   R13!,{R0,R1,R12,PC}^
 175
 176 99heap_init     ADR     R0,heap__nomem          ;Point to the error block
 177         [ OPT_SAPPHIRE
 178                 BL      msgs_error              ;Translate the message
 179         ]
 180                 SWI     OS_GenerateError        ;And really moan about it
 181
 182 heap__nomem     DCD     1
 183         [ OPT_SAPPHIRE
 184                 DCB     "hpNEMI",0
 185         |
 186                 DCB     "Not enough memory to build heap",0
 187         ]
 188                 ALIGN
 189
 190         [ OPT_SAPPHIRE
 191 heap__wSpace    DCD     0
 192         ]
 193
 194         [ OPT_APCS
 195 heap__wSpace    DCD     heap__sSpace
 196         ]
 197
 198                 LTORG
 199
 200         [ OPT_SAPPHIRE
 201
 202 ; --- heap_useHeap ---
 203 ;
 204 ; On entry:     --
 205 ;
 206 ; On exit:      --
 207 ;
 208 ; Use:          Registers the resizing heap as the current allocator.
 209
 210                 EXPORT  heap_useHeap
 211 heap_useHeap    ROUT
 212
 213                 STMFD   R13!,{R0-R2,R14}        ;Save some registers
 214                 ADR     R0,heap_alloc           ;Point to the allocator
 215                 ADR     R1,heap_free            ;And to the freer
 216                 MOV     R2,#0                   ;Don't care about workspace
 217                 BL      alloc_register          ;Make heap the allocator
 218                 LDMFD   R13!,{R0-R2,PC}^        ;Return to caller
 219
 220                 LTORG
 221
 222         ]
 223
 224 ; --- heap_info ---
 225 ;
 226 ; On entry:     R0 == pointer to structure to fill in (APCS)
 227 ;
 228 ; On exit:      R0 == current heap size (Sapphire)
 229 ;               R1 == amount of memory free in the heap (Sapphire)
 230 ;               R2 == size of the largest block free (Sapphire)
 231 ;
 232 ; Use:          Describes the heap's current status.
 233
 234                 EXPORT  heap_info
 235 heap_info       ROUT
 236
 237         [ OPT_APCS
 238                 STMFD   R13!,{R4,R5,R12,R14}
 239                 WSPACE  heap__wSpace
 240                 MOV     R5,R0
 241         |
 242                 STMFD   R13!,{R3,R4,R12,R14}
 243                 WSPACE  heap__wSpace
 244         ]
 245
 246                 ; --- Set up some registers ---
 247
 248                 LDR     R0,heap__size           ;Get size of heap
 249
 250                 LDR     R4,heap__flex           ;Pointer to the heap
 251                 LDR     R14,heap__freeList      ;Offset to first free block
 252                 LDR     R2,heap__alloced        ;Length of allocated region
 253                 SUB     R1,R0,R2                ;This area is free
 254                 MOV     R2,R1                   ;Largest block found yet
 255
 256                 ; --- Now we can proceed through the loop ---
 257
 258 00heap_info     CMP     R14,#-1                 ;Is this the end of the list?
 259                 BEQ     %01heap_info            ;Yes - wrap things up nicely
 260                 ADD     R14,R14,R4              ;Convert to a pointer
 261                 LDR     R3,[R14,#0]             ;Get the length of this block
 262                 ADD     R1,R1,R3                ;Add to free size
 263                 CMP     R3,R2                   ;Is it the biggest one yet?
 264                 MOVGT   R2,R3                   ;Yes - remember it
 265                 LDR     R14,[R14,#4]            ;Get next offset
 266                 B       %00heap_info            ;And loop round again
 267
 268                 ; --- Now return this information ---
 269
 270         [ OPT_APCS
 271 01heap_info     STMIA   R5,{R0-R2}
 272                 LDMFD   R13!,{R4,R5,R12,PC}^
 273         |
 274 01heap_info     LDMFD   R13!,{R3,R4,R12,PC}^    ;Return to caller
 275         ]
 276
 277                 LTORG
 278
 279 ; --- heap_alloc ---
 280 ;
 281 ; On entry:     R0 == size of block wanted
 282 ;
 283 ; On exit:      Sapphire: CC if enough memory, R0 == address; CS if no
 284 ;                       memory, R0 corrupted
 285 ;               APCS: R0 == pointer to memory, or zero if not enough
 286 ;
 287 ; Use:          Allocates a block of at least a given size from a heap.  If
 288 ;               the heap is not big enough, more is claimed from the
 289 ;               operating system.
 290
 291                 EXPORT  heap_alloc
 292 heap_alloc      ROUT
 293
 294                 ; --- Make sure there's something to do ---
 295
 296                 CMP     R0,#0                   ;Is the required size 0?
 297                 MOVEQS  PC,R14                  ;Yes -- return a NULL pointer
 298
 299                 ; --- Start everything up then ---
 300
 301         [ :LNOT:OPT_APCS
 302                 BIC     R14,R14,#C_flag
 303         ]
 304                 STMFD   R13!,{R1-R6,R12,R14}    ;Save a load of registers
 305                 WSPACE  heap__wSpace
 306
 307                 ; --- First, set up parameters ---
 308
 309                 ADD     R0,R0,#11               ;Add overhead and align to
 310                 BIC     R0,R0,#7                ; multiple of 8
 311
 312                 ; --- Initialise for a loop through the free list ---
 313
 314                 LDR     R6,heap__flex           ;Point to heap start
 315                 MOV     R5,#-1                  ;Previous block
 316                 LDR     R4,heap__freeList       ;Point to free list to scan
 317
 318                 ; --- This is the free list scanning loop ---
 319
 320 00heap_alloc    CMP     R4,#-1                  ;Is this the end?
 321                 BEQ     %02heap_alloc           ;Yes - try unallocated region
 322                 ADD     R4,R4,R6                ;Translate offset to address
 323                 LDR     R1,[R4,#0]              ;Get length word
 324                 CMP     R1,R0                   ;Check sizes
 325                 MOVCC   R5,R4                   ;Too small - set up prev ptr
 326                 LDRCC   R4,[R4,#4]              ;Get next pointer
 327                 BCC     %00heap_alloc           ;And try next block
 328
 329                 ; --- If block is right size, remove from the chain ---
 330
 331                 LDREQ   R2,[R4,#4]              ;Get next offset
 332                 ADDEQ   R2,R2,R6                ;Translate to address
 333                 BEQ     %01heap_alloc           ;And branch ahead
 334
 335                 ; --- Now, we try to hack off the bit we need ---
 336
 337                 STR     R0,[R4,#0]              ;Store block's new length
 338                 ADD     R2,R0,R4                ;R2 points to next block
 339                 SUB     R3,R1,R0                ;Space left in this block
 340                 STR     R3,[R2,#0]              ;Store in length field
 341                 LDR     R3,[R4,#4]              ;Now get next pointer
 342                 STR     R3,[R2,#4]              ;Store.
 343
 344                 ; --- Now put in link from previous block and return ---
 345
 346 01heap_alloc    SUB     R2,R2,R6                ;Translate back to an offset
 347                 CMP     R5,#-1                  ;Is there a previous block?
 348                 STRNE   R2,[R5,#4]              ;Store in previous block
 349                 STREQ   R2,heap__freeList       ;No - stick it in the front
 350                 ADD     R0,R4,#4                ;Leave out the length field
 351                 LDMFD   R13!,{R1-R6,R12,PC}^    ;And return to caller
 352
 353                 ; --- Check the free area is big enough for the block ---
 354
 355 02heap_alloc    LDR     R4,heap__alloced        ;Offset to free area
 356                 LDR     R5,heap__size           ;Current size of heap
 357                 ADD     R6,R4,R0                ;How big the area needs to be
 358                 CMP     R5,R6                   ;Is this sufficient?
 359                 BCS     %03heap_alloc           ;Yes - allocate block
 360
 361                 ; --- We need more memory in the heap.  Call flex for it ---
 362
 363                 MOV     R5,R0                   ;Preserve the caller's length
 364                 LDR     R1,heap__chunkSize      ;Units of allocation
 365                 SUB     R1,R1,#1                ;For alignment purposes
 366                 ADD     R6,R6,#8
 367                 ADD     R6,R6,R1                ;First step in alignment
 368                 BIC     R6,R6,R1                ;Second step
 369                 SUB     R6,R6,#8
 370                 ADR     R0,heap__flex           ;Point to anchor
 371                 MOV     R1,R6                   ;New size we want
 372                 BL      flex_extend             ;Try to get memory
 373         [ OPT_APCS
 374                 CMP     R0,#0                   ;If it failed,
 375                 LDMEQFD R13!,{R1-R6,R12,PC}^    ;Return a null pointer
 376         |
 377                 LDMCSFD R13!,{R1-R6,R12,R14}    ;If it failed, return with...
 378                 ORRCSS  PC,R14,#C_flag          ;...carry set
 379         ]
 380                 STR     R6,heap__size           ;Store new heap size
 381                 MOV     R0,R5                   ;Restore the desired length
 382
 383                 ; --- Now allocate a block from the free area properly ---
 384
 385 03heap_alloc    LDR     R1,heap__flex           ;Point to start of heap
 386                 ADD     R2,R4,R1                ;R2 points to new block
 387                 STR     R0,[R2,#0]              ;Store the length
 388                 ADD     R4,R4,R0                ;Get new free offset
 389                 STR     R4,heap__alloced        ;Store permanently
 390                 ADD     R0,R2,#4                ;Point to free part of block
 391                 LDMFD   R13!,{R1-R6,R12,PC}^    ;Return flushed with success
 392
 393                 LTORG
 394
 395 ; --- heap_free ---
 396 ;
 397 ; On entry:     R0 == pointer to a block created with heap_alloc
 398 ;
 399 ; On exit:      --
 400 ;
 401 ; Use:          Frees a block allocated using heap_alloc.  It tries to
 402 ;               shrink the heap as much as possible afterwards.
 403
 404                 EXPORT  heap_free
 405 heap_free       ROUT
 406
 407                 ; --- Make sure the user's not being stupid ---
 408
 409                 CMP     R0,#0
 410                 MOVEQS  PC,R14
 411
 412                 ; --- Proceed as normal ---
 413
 414                 STMFD   R13!,{R0-R8,R12,R14}
 415                 WSPACE  heap__wSpace
 416
 417                 ; --- Scan the free list ---
 418                 ;
 419                 ; Now first we run through the free list trying to find
 420                 ; a free block (a) immediately before the current one and
 421                 ; (b) immediately after the current one.
 422
 423                 SUB     R5,R0,#4                ;Point to real block start
 424                 LDR     R6,[R5,#0]              ;Get length of block
 425                 ADD     R6,R5,R6                ;R6 points off end of block
 426                 MOV     R7,#-1                  ;Haven't found preblock
 427                 MOV     R8,#-1                  ;Haven't found postblock
 428                 LDR     R4,heap__flex           ;Pointer to start of heap
 429                 MOV     R1,#0                   ;Previous block in the chain
 430                 LDR     R0,heap__freeList       ;Scan the free list
 431
 432                 ; --- Now do the scanning loop ---
 433
 434 00heap_free     CMP     R0,#-1                  ;Have we reached the end?
 435                 BEQ     %01heap_free            ;Yes - free the block
 436                 ADD     R0,R0,R4                ;Convert to a pointer
 437                 CMP     R0,R6                   ;Could this be postblock?
 438                 MOVEQ   R8,R1                   ;Yes - remember
 439                 LDR     R2,[R0,#0]              ;Get length
 440                 ADD     R2,R0,R2                ;R2 points past that block
 441                 CMP     R2,R5                   ;Is this preblock?
 442                 MOVEQ   R7,R1                   ;Yes - remember
 443                 MOV     R1,R0                   ;Shift prev block along
 444                 LDR     R0,[R0,#4]              ;And get next block in list
 445                 B       %00heap_free            ;Loop round until finished
 446
 447                 ; --- Now try and coagulate the blocks ---
 448
 449 01heap_free     CMP     R7,#-1                  ;Did we find preblock?
 450                 BEQ     %02heap_free            ;No - try postblock
 451                 CMP     R7,#0                   ;Is it the first block?
 452                 LDREQ   R0,heap__freeList       ;Yes - get offset
 453                 LDRNE   R0,[R7,#4]              ;No - get offset (!)
 454                 ADD     R0,R0,R4                ;Convert to a pointer
 455                 LDR     R1,[R0,#0]              ;Get block length
 456                 LDR     R2,[R5,#0]              ;Get length of block to free
 457                 ADD     R1,R1,R2                ;Add them together
 458                 STR     R1,[R0,#0]              ;Store back in block
 459                 LDR     R1,[R0,#4]              ;Get next block offset
 460                 CMP     R7,#0                   ;Is there a previous block?
 461                 STREQ   R1,heap__freeList       ;No - start the list with it
 462                 STRNE   R1,[R7,#4]              ;Yes - link in as normal
 463                 MOV     R5,R0                   ;This is the block to free
 464
 465                 CMP     R8,R0                   ;Is this prev to postblock?
 466                 MOVEQ   R8,R7                   ;Yes - show we've delinked
 467
 468 02heap_free     CMP     R8,#-1                  ;Did we find postblock?
 469                 BEQ     %03heap_free            ;No - free the block
 470                 CMP     R8,#0                   ;Is it the first block?
 471                 LDREQ   R0,heap__freeList       ;Yes - get offset
 472                 LDRNE   R0,[R8,#4]              ;No - get offset (!)
 473                 ADD     R0,R0,R4                ;Convert to a pointer
 474                 LDR     R1,[R0,#0]              ;Get block length
 475                 LDR     R2,[R5,#0]              ;Get length of block to free
 476                 ADD     R1,R1,R2                ;Add them together
 477                 STR     R1,[R5,#0]              ;Store back in block
 478                 LDR     R1,[R0,#4]              ;Get next block offset
 479                 CMP     R8,#0                   ;Is there a previous block?
 480                 STREQ   R1,heap__freeList       ;No - start the list with it
 481                 STRNE   R1,[R8,#4]              ;Yes - link in as normal
 482
 483                 ; --- Now we try to reduce the allocated area ---
 484
 485 03heap_free     LDR     R0,heap__alloced        ;Find end of allocated area
 486                 ADD     R1,R0,R4                ;Convert to a pointer
 487                 LDR     R2,[R5,#0]              ;Get length of our block
 488                 ADD     R3,R5,R2                ;Find the end of it
 489                 CMP     R3,R1                   ;Are they the same?
 490                 BNE     %04heap_free            ;No - old-fashioned method!
 491                 SUB     R0,R0,R2                ;Reduce the allocated region
 492                 STR     R0,heap__alloced        ;Remember this!
 493                 LDR     R1,heap__chunkSize      ;Get the chunk size
 494                 SUB     R1,R1,#1                ;More useful like this!
 495                 ADD     R0,R0,#8
 496                 ADD     R0,R0,R1                ;Alignment step 1
 497                 BIC     R7,R0,R1                ;Alignment step 2
 498                 SUB     R7,R7,#8
 499                 LDR     R2,heap__size           ;Get current heap size
 500                 CMP     R7,R2                   ;Are they the same?
 501                 LDMGEFD R13!,{R0-R8,R12,PC}^    ;Yes - nothing doing
 502                 ADR     R0,heap__flex           ;Point to flex anchor
 503                 MOV     R1,R7                   ;New size for block
 504                 BL      flex_extend             ;Try and reduce
 505         [ OPT_APCS
 506                 CMP     R0,#0                   ;Did it fail (unlikely!)
 507                 STRNE   R7,heap__size           ;No - remember new size
 508         |
 509                 STRCC   R7,heap__size
 510         ]
 511                 LDMFD   R13!,{R0-R8,R12,PC}^    ;Return to sender
 512
 513                 ; --- Now use the old fashioned method to link the block ---
 514
 515 04heap_free     LDR     R0,heap__freeList       ;Get current first free block
 516                 STR     R0,[R5,#4]              ;Store in our block
 517                 SUB     R5,R5,R4                ;Turn back into an offset
 518                 STR     R5,heap__freeList       ;Store as new first free
 519                 LDMFD   R13!,{R0-R8,R12,PC}^    ;Return to sender
 520
 521                 LTORG
 522
 523 ; --- heap_reAlloc ---
 524 ;
 525 ; On entry:     R0 == pointer to block whose size we want to change
 526 ;               R1 == the new size of the block
 527 ;
 528 ; On exit:      Sapphire: CC and R0 == pointer to block if OK, CS if no mem
 529 ;               APCS: R0 == pointer to block if OK, or null if no mem
 530 ;
 531 ; Use:          Changes the size of a heap block.  If possible, the block's
 532 ;               position is unchanged, but this may not always be the case.
 533 ;
 534 ;               Note that changing a block's size to 0 is permitted.
 535
 536                 EXPORT  heap_reAlloc
 537                 EXPORT  heap_realloc
 538 heap_reAlloc    ROUT
 539 heap_realloc
 540
 541                 ; --- Some ANSI-compatible checks on the parameters ---
 542
 543                 CMP     R0,#0                   ;If the pointer is NULL...
 544                 MOVEQ   R0,R1                   ;This should just do a malloc
 545                 BEQ     heap_alloc
 546
 547         [ :LNOT:OPT_APCS
 548                 BIC     R14,R14,#C_flag         ;Clr carry flag on offchance
 549         ]
 550                 STMFD   R13!,{R1-R8,R12,R14}
 551
 552                 CMP     R1,#0                   ;If new size is NULL
 553                 BLEQ    heap_free               ;This should just free it
 554                 MOVEQ   R0,#0                   ;Return a NULL pointer
 555                 LDMEQDB R13!,{R1-R8,R12,PC}^    ;And return to caller
 556
 557                 ; --- First set things up nicely ---
 558                 ;
 559                 ; Make sure we actually have to do anything.
 560
 561                 WSPACE  heap__wSpace            ;Get global heap data
 562                 ADD     R6,R1,#11               ;Add 4 bytes length and align
 563                 BIC     R6,R6,#7                ;to a multiple of 8
 564                 SUB     R5,R0,#4                ;Point to length word
 565                 LDR     R7,[R5,#0]              ;Get the length word
 566                 CMP     R7,R6                   ;Do we have to do any work?
 567                 LDMEQDB R13!,{R1-R8,R12,PC}^    ;No - don't then!
 568
 569                 ; --- Try for some easy cases ---
 570                 ;
 571                 ; If this block is at the end of the allocated area, we
 572                 ; can just extend this area and the block size.  So check
 573                 ; for this case.
 574
 575                 ADD     R2,R5,R7                ;Find end of the block
 576                 LDR     R8,heap__alloced        ;Offset of free space
 577                 LDR     R4,heap__flex           ;Pointer to start of heap
 578                 ADD     R3,R8,R4                ;Convert offset to pointer
 579                 CMP     R2,R3                   ;Are they the same?
 580                 BNE     %02heap_reAlloc         ;No - deal with other case
 581
 582                 ; --- Just extend the area then ---
 583                 ;
 584                 ; Now we shall need to make sure that the free area is big
 585                 ; enough (or maybe reduce it!)  This may, of course, fail.
 586
 587                 SUB     R8,R8,R7                ;Remove the original length
 588                 ADD     R8,R8,R6                ;And add the new length
 589                 ADD     R4,R8,#8                ;Add on flex's two words
 590                 LDR     R0,heap__chunkSize      ;Get the chunk size
 591                 SUB     R0,R0,#1                ;For aligning purposes
 592                 ADD     R4,R4,R0                ;Alignment step 1
 593                 BIC     R4,R4,R0                ;Alignment step 2
 594                 SUB     R4,R4,#8                ;Remove flex's words again
 595                 LDR     R0,heap__size           ;Find the heap's size
 596                 CMP     R0,R4                   ;How different are they?
 597                 BEQ     %00heap_reAlloc         ;If they're the same, no prob
 598                 ADR     R0,heap__flex           ;Point to block anchor
 599                 MOV     R1,R4                   ;Set up new size
 600                 BL      flex_extend             ;Try and change block size
 601         [ OPT_APCS
 602                 CMP     R0,#0                   ;Did it fail?
 603                 BEQ     %01heap_reAlloc         ;Yes - try some other way
 604         |
 605                 BCS     %01heap_reAlloc         ;Failed - try some other way
 606         ]
 607
 608 00heap_reAlloc  STR     R4,heap__size           ;Remember new size
 609                 STR     R8,heap__alloced        ;And new free offset
 610                 STR     R6,[R5,#0]              ;Store new length
 611                 ADD     R0,R5,#4                ;Set up return pointer
 612                 B       %80heap_reAlloc         ;Return the pointer back
 613
 614                 ; --- Try fiddling around inside the heap block ---
 615                 ;
 616                 ; This sets up all the registers again
 617
 618 01heap_reAlloc  LDR     R2,[R5,#0]              ;Get block length
 619                 ADD     R2,R5,R2                ;Point to end of block
 620                 LDR     R4,heap__flex           ;Point to heap base
 621
 622                 ; --- It wasn't at the end ---
 623                 ;
 624                 ; Now, if the caller wants to reduce the block size, we can
 625                 ; manage that.
 626
 627 02heap_reAlloc  SUBS    R1,R7,R6                ;Is the old size bigger?
 628                 BLT     %03heap_reAlloc         ;No - we'll struggle on
 629                 ADD     R0,R5,R6                ;Point to end of (new) block
 630                 STR     R1,[R0,#0]              ;Store in there
 631                 STR     R6,[R5,#0]              ;Store also new size in block
 632                 ADD     R0,R0,#4                ;Point to second block
 633                 BL      heap_free               ;Attach in free chain
 634                 ADD     R0,R5,#4                ;Setup return pointer
 635                 B       %80heap_reAlloc         ;And return to the caller
 636
 637                 ; --- We're extending the block ---
 638                 ;
 639                 ; Loop through, finding either preblock or postblock (as for
 640                 ; freeing).  If we can, merge these three together, and then
 641                 ; hope the result is big enough.
 642                 ;
 643                 ; At this point, some register usage notes might be handy:
 644                 ;
 645                 ;   R2 -> end of block
 646                 ;   R4 -> start of heap
 647                 ;   R5 -> block to resize
 648                 ;   R6 == new size wanted
 649                 ;
 650                 ; We will use:
 651                 ;
 652                 ;   R0 -> preblock
 653                 ;   R1 -> postblock
 654                 ;   R3 -> list ptr
 655                 ;
 656                 ; R7 will be previous block, R8 will be used as scratch
 657                 ; space
 658                 ;
 659                 ; So, onwards ever...
 660
 661 03heap_reAlloc  LDR     R3,heap__freeList       ;Set up list pointer
 662                 MOV     R0,#-1                  ;No preblock
 663                 MOV     R1,#-1                  ;Or postblock found yet
 664                 MOV     R7,#0                   ;Previous block invalid
 665
 666                 ; --- Now for the loop ---
 667
 668 04heap_reAlloc  CMP     R3,#-1                  ;Is this the end?
 669                 BEQ     %05heap_reAlloc         ;Try and join the blocks
 670                 ADD     R3,R3,R4                ;Convert to an address
 671                 CMP     R3,R2                   ;Is this postblock?
 672                 MOVEQ   R0,R7                   ;Yes - remember it
 673                 LDR     R8,[R3,#0]              ;Get size of this block
 674                 ADD     R8,R3,R8                ;And point to the end
 675                 CMP     R5,R8                   ;Is this preblock?
 676                 MOVEQ   R1,R7                   ;Yes - remember
 677                 MOV     R7,R3                   ;Move previous pointer on
 678                 LDR     R3,[R3,#4]              ;Get next one in the list
 679                 B       %04heap_reAlloc         ;Loop round for another go
 680
 681                 ; --- Now find out if it will help to join the blocks up ---
 682
 683 05heap_reAlloc  LDR     R2,[R5,#0]              ;Current size
 684                 CMP     R0,#-1                  ;Did we find preblock?
 685                 BEQ     %06heap_reAlloc         ;No - try postblock
 686                 CMP     R0,#0                   ;Is it first block in list?
 687                 LDREQ   R3,heap__freeList       ;Yes - get offset
 688                 LDRNE   R3,[R0,#4]              ;No - get offset (!)
 689                 LDR     R7,[R3,#0]              ;Get its size
 690                 ADD     R2,R2,R7                ;Add it onto our total
 691 06heap_reAlloc  CMP     R1,#-1                  ;Did we find postblock?
 692                 BEQ     %07heap_reAlloc         ;No - check the total
 693                 CMP     R1,#0                   ;Is it first block in list?
 694                 LDREQ   R3,heap__freeList       ;Yes - get offset
 695                 LDRNE   R3,[R1,#4]              ;No - get offset (!)
 696                 LDR     R7,[R3,#0]              ;Get its size
 697                 ADD     R2,R2,R7                ;Add it onto our total
 698 07heap_reAlloc  CMP     R2,R6                   ;Is this big enough?
 699                 BCC     %11heap_reAlloc         ;No -- do it the hard way
 700
 701                 ; --- Now try and join on preblock ---
 702                 ;
 703                 ; Note - this is almost the same as the heap_free code, but
 704                 ; with different registers)
 705
 706 08heap_reAlloc  CMP     R0,#-1                  ;Did we find preblock?
 707                 BEQ     %09heap_reAlloc         ;No - try postblock
 708                 CMP     R0,#0                   ;Is it first block in list?
 709                 LDREQ   R3,heap__freeList       ;Yes - get offset
 710                 LDRNE   R3,[R0,#4]              ;No - get offset (!)
 711                 ADD     R3,R3,R4                ;Convert offset to pointer
 712                 LDR     R7,[R3,#0]              ;Get the length of the block
 713                 LDR     R8,[R5,#0]              ;Length of block to resize
 714                 ADD     R7,R7,R8                ;Add them together
 715                 STR     R7,[R3,#0]              ;Store the combined length
 716                 LDR     R7,[R3,#4]              ;Get next block in list
 717                 CMP     R0,#0                   ;Is there a previous block?
 718                 STREQ   R7,heap__freeList       ;No - start the list with it
 719                 STRNE   R7,[R0,#4]              ;Yes - link in as normal
 720
 721                 ; --- Now shift the data down into the bigger block ---
 722
 723                 STMFD   R13!,{R0-R3}            ;Store registers
 724                 ADD     R0,R3,#4                ;Destination data start
 725                 ADD     R1,R5,#4                ;Source destination start
 726                 LDR     R2,[R5,#0]              ;Size of the source block
 727                 SUBS    R2,R2,#4                ;We don't need to copy this
 728                 BLNE    fastMove                ;Does the Right Thing when
 729                                                 ;the blocks overlap
 730                 LDMFD   R13!,{R0-R3}            ;Restore our registers
 731
 732                 ; --- Some fiddling before handling postblock ---
 733
 734                 MOV     R5,R3                   ;This is now block to size
 735
 736                 CMP     R1,R3                   ;Is this prev to postblock?
 737                 MOVEQ   R1,R0                   ;Yes - show we've delinked
 738
 739                 ; --- Now process postblock in the same way ---
 740
 741 09heap_reAlloc  CMP     R1,#-1                  ;Did we find postblock?
 742                 BEQ     %10heap_reAlloc         ;No - try and resize
 743                 CMP     R1,#0                   ;Is it first block in list?
 744                 LDREQ   R3,heap__freeList       ;Yes - get offset
 745                 LDRNE   R3,[R1,#4]              ;No - get offset (!)
 746                 ADD     R3,R3,R4                ;Convert offset to pointer
 747                 LDR     R7,[R3,#0]              ;Get the length of the block
 748                 LDR     R8,[R5,#0]              ;Length of block to resize
 749                 ADD     R7,R7,R8                ;Add them together
 750                 STR     R7,[R5,#0]              ;Store the combined length
 751                 LDR     R7,[R3,#4]              ;Get next block in list
 752                 CMP     R0,#0                   ;Is there a previous block?
 753                 STREQ   R7,heap__freeList       ;No - start the list with it
 754                 STRNE   R7,[R0,#4]              ;Yes - link in as normal
 755
 756                 ; --- Now take off the bit we need ---
 757                 ;
 758                 ; We've already checked that it's big enough).  We do the
 759                 ; freeing ourselves, to avoid a pointless loop in heap_free
 760
 761 10heap_reAlloc  LDR     R7,[R5,#0]              ;Get the new length
 762                 SUB     R1,R7,R6                ;Get difference in sizes
 763                 ADD     R0,R5,R6                ;Point to end of (new) block
 764                 STR     R1,[R0,#0]              ;Store in there
 765                 STR     R6,[R5,#0]              ;Store also new size in block
 766                 LDR     R1,heap__freeList       ;Get the first block in list
 767                 STR     R1,[R0,#4]              ;Store in the new free block
 768                 SUB     R0,R0,R4                ;Convert pointer to an offset
 769                 STR     R0,heap__freeList       ;It's now linked in
 770                 ADD     R0,R5,#4                ;Setup return pointer
 771                 B       %80heap_reAlloc         ;Return to caller nicely
 772
 773                 ; --- Well, we did our best ---
 774                 ;
 775                 ; All we can do now is to try and allocate a new block, copy
 776                 ; the data, and free the old one, causing massive
 777                 ; fragmentation :-(
 778
 779 11heap_reAlloc  SUB     R0,R6,#4                ;Size of block for heap_alloc
 780                 BL      heap_alloc              ;Try and allocate
 781         [ OPT_APCS
 782                 CMP     R0,#0                   ;Did it fail?
 783                 BEQ     %90heap_reAlloc         ;Yes -- then return null
 784         |
 785                 BCS     %90heap_reAlloc         ;Failed -- return C set
 786         ]
 787                 MOV     R7,R0                   ;Remeber this pointer
 788                 ADD     R1,R5,#4                ;Source of data to copy
 789                 LDR     R2,[R5,#0]              ;Length of stuff to copy
 790                 SUBS    R2,R2,#4                ;Remove length word first
 791                 BLNE    fastMove                ;Move the data across
 792                 ADD     R0,R5,#4                ;Now free the old block
 793                 BL      heap_free               ;Do the freeing business
 794                 MOV     R0,R7                   ;Give caller his pointer
 795
 796                 ; --- Return, preserving R0 to give to the caller ---
 797
 798 80heap_reAlloc  LDMFD   R13!,{R1-R8,R12,PC}^
 799
 800                 ; --- Return, setting the C flag ---
 801
 802         [ OPT_APCS
 803 90heap_reAlloc  MOV     R0,#0
 804                 LDMFD   R13!,{R1-R8,R12,PC}^
 805         |
 806 90heap_reAlloc  LDMFD   R13!,{R1-R8,R12,R14}
 807                 ORRS    PC,R14,#C_flag
 808         ]
 809
 810                 LTORG
 811
 812 ;----- Data definitions -----------------------------------------------------
 813
 814         [ :LNOT:OPT_STANDALONE
 815
 816                 ^       0,R12
 817 heap__wStart    #       0
 818
 819                 GET     libs:sh.heapws
 820
 821 heap__wSize     EQU     {VAR}-heap__wStart
 822
 823         ]
 824
 825         [ OPT_SAPPHIRE
 826                 AREA    |Sapphire$$LibData|,CODE,READONLY
 827                 DCD     heap__wSize
 828                 DCD     heap__wSpace
 829                 DCD     0
 830                 DCD     heap_init
 831         ]
 832
 833         [ OPT_APCS
 834                 AREA    |C$$zidata|,DATA,NOINIT
 835 heap__sSpace    %       heap__wSize
 836         ]
 837
 838 ;----- That's all, folks ----------------------------------------------------
 839
 840                 END