~mdw / ssr / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Initial revision
[ssr] / 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
The Straylight Source Distribution (obsolete software for RISC OS)