2 ; Ullrich von Bassewitz, 19.03.2000
4 ; Free a block on the heap.
6 ; void __fastcall__ free (void* block);
9 ; C implementation was:
11 ; void free (void* block)
12 ; /* Release an allocated memory block. The function will accept NULL pointers
13 ; * (and do nothing in this case).
18 ; struct freeblock* f;
21 ; /* Allow NULL arguments */
26 ; /* Get a pointer to the real memory block, then get the size */
27 ; b = (unsigned*) block;
30 ; /* Check if the block is at the top of the heap */
31 ; if (((int) b) + size == (int) _hptr) {
33 ; /* Decrease _hptr to release the block */
34 ; _hptr = (unsigned*) (((int) _hptr) - size);
36 ; /* Check if the last block in the freelist is now at heap top. If so,
37 ; * remove this block from the freelist.
40 ; if (((int) f) + f->size == (int) _hptr) {
41 ; /* Remove the last block */
42 ; _hptr = (unsigned*) (((int) _hptr) - f->size);
43 ; if (_hlast = f->prev) {
44 ; /* Block before is now last block */
47 ; /* The freelist is empty now */
55 ; /* Not at heap top, enter the block into the free list */
62 .importzp ptr1, ptr2, ptr3, ptr4
63 .import __hptr, __hfirst, __hlast, __hend
68 ; Offsets into struct freeblock and other constant stuff
80 stx ptr2+1 ; Save block
82 ; Is the argument NULL?
84 ora ptr2+1 ; Is the argument NULL?
87 ; Decrement the given pointer by the admin space amount, so it points to the
88 ; real block allocated. The size of the block is stored in the admin space.
89 ; Remember the block size in ptr1.
97 lda (ptr2),y ; High byte of size
103 ; Check if the block is on top of the heap
110 bne hadd ; Add to free list
114 ; The pointer is located at the heap top. Lower the heap top pointer to
122 ; Check if the last block in the freelist is now at heap top. If so, remove
123 ; this block from the freelist.
128 beq @L9 ; Jump if free list empty
130 sta ptr1+1 ; Pointer to last block now in ptr1
133 lda (ptr1),y ; Low byte of block size
136 iny ; High byte of block size
141 bne @L9 ; Jump if last block not on top of heap
143 bne @L9 ; Jump if last block not on top of heap
145 ; Remove the last block
152 ; Correct the next pointer of the now last block
154 ldy #prev+1 ; Offset of ->prev field
156 sta ptr2+1 ; Remember f->prev in ptr2
160 sta ptr2 ; Remember f->prev in ptr2
162 ora __hlast+1 ; -> prev == 0?
163 bne @L8 ; Jump if free list not empty
165 ; Free list is now empty (A = 0)
174 ; Block before is now last block. ptr2 points to f->prev.
177 dey ; Points to high byte of ->next
179 dey ; Low byte of f->prev->next
183 ; The block is not on top of the heap. Add it to the free list. This was
184 ; formerly a separate function called __hadd that was implemented in C as
187 ; void _hadd (void* mem, size_t size)
188 ; /* Add an arbitrary memory block to the heap. This function is used by
189 ; * free(), but it does also allow usage of otherwise unused memory
190 ; * blocks as heap space. The given block is entered in the free list
191 ; * without any checks, so beware!
194 ; struct freeblock* f;
195 ; struct freeblock* left;
196 ; struct freeblock* right;
198 ; if (size >= sizeof (struct freeblock)) {
200 ; /* Set the admin data */
201 ; f = (struct freeblock*) mem;
204 ; /* Check if the freelist is empty */
205 ; if (_hfirst == 0) {
207 ; /* The freelist is empty until now, insert the block */
215 ; /* We have to search the free list. As we are doing so, we check
216 ; * if it is possible to combine this block with another already
217 ; * existing block. Beware: The block may be the "missing link"
218 ; * between *two* other blocks.
222 ; while (right && f > right) {
224 ; right = right->next;
228 ; /* Ok, the current block must be inserted between left and right (but
229 ; * beware: one of the two may be zero!). Also check for the condition
230 ; * that we have to merge two or three blocks.
233 ; /* Check if we must merge the block with the right one */
234 ; if (((unsigned) f) + size == (unsigned) right) {
235 ; /* Merge with the right block */
236 ; f->size += right->size;
237 ; if (f->next = right->next) {
240 ; /* This is now the last block */
244 ; /* No merge, just set the link */
250 ; /* Special case: This is the new freelist end */
254 ; /* Check if we must merge the block with the left one */
255 ; if ((unsigned) f == ((unsigned) left) + left->size) {
256 ; /* Merge with the left block */
257 ; left->size += f->size;
258 ; if (left->next = f->next) {
259 ; left->next->prev = left;
261 ; /* This is now the last block */
265 ; /* No merge, just set the link */
271 ; /* Special case: This is the new freelist start */
279 ; Check if the free list is empty, storing _hfirst into ptr3 for later
288 ; The free list is empty, so this is the first and only block. A contains
289 ; zero if we come here.
292 @L2: iny ; f->next = f->prev = 0;
300 stx __hfirst+1 ; _hfirst = f;
302 stx __hlast+1 ; _hlast = f;
306 ; We have to search the free list. As we are doing so, check if it is possible
307 ; to combine this block with another, already existing block. Beware: The
308 ; block may be the "missing link" between two blocks.
309 ; ptr3 contains _hfirst (the start value of the search) when execution reaches
310 ; this point, Y contains size+1. We do also know that _hfirst (and therefore
311 ; ptr3) is not zero on entry.
316 sta ptr4+1 ; left = 0;
320 @Loop: lda ptr3+1 ; High byte of right
325 @L1: bcs CheckRightMerge
327 @L2: stx ptr4 ; left = right;
331 lda (ptr3),y ; right = right->next;
333 iny ; Points to next+1
340 ; If we come here, the right pointer is zero, so we don't need to check for
341 ; a merge. The new block is the new freelist end.
342 ; A is zero when we come here, Y points to next+1
344 sta (ptr2),y ; Clear high byte of f->next
346 sta (ptr2),y ; Clear low byte of f->next
348 lda ptr2 ; _hlast = f;
353 ; Since we have checked the case that the freelist is empty before, if the
354 ; right pointer is NULL, the left *cannot* be NULL here. So skip the
355 ; pointer check and jump right to the left block merge
359 ; The given block must be inserted between left and right, and right is not
374 ; Merge with the right block. Do f->size += right->size;
380 iny ; Points to size+1
385 ; Set f->next = right->next and remember f->next in ptr1 (we don't need the
386 ; size stored there any longer)
389 lda (ptr3),y ; Low byte of right->next
390 sta (ptr2),y ; Store to low byte of f->next
392 iny ; Points to next+1
393 lda (ptr3),y ; High byte of right->next
394 sta (ptr2),y ; Store to high byte of f->next
397 beq @L1 ; Jump if f->next zero
402 lda ptr2 ; Low byte of f
403 sta (ptr1),y ; Low byte of f->next->prev
404 iny ; Points to prev+1
405 lda ptr2+1 ; High byte of f
406 sta (ptr1),y ; High byte of f->next->prev
407 jmp CheckLeftMerge ; Done
409 ; f->next is zero, this is now the last block
411 @L1: lda ptr2 ; _hlast = f;
417 ; No right merge, just set the link.
420 ldy #next ; f->next = right;
423 iny ; Points to next+1
428 lda ptr2 ; right->prev = f;
430 iny ; Points to prev+1
434 ; Check if the left pointer is zero
437 lda ptr4 ; left == NULL?
439 bne CheckLeftMerge2 ; Jump if there is a left block
441 ; We don't have a left block, so f is actually the new freelist start
444 sta (ptr2),y ; f->prev = 0;
448 lda ptr2 ; _hfirst = f;
455 ; Check if the left block is adjacent to the following one
458 ldy #size ; Calculate left + left->size
459 lda (ptr4),y ; Low byte of left->size
462 iny ; Points to size+1
463 lda (ptr4),y ; High byte of left->size
469 bne NoLeftMerge ; Jump if blocks not adjacent
471 ; Merge with the left block. Do left->size += f->size;
477 iny ; Points to size+1
482 ; Set left->next = f->next and remember left->next in ptr1.
485 lda (ptr2),y ; Low byte of f->next
488 iny ; Points to next+1
489 lda (ptr2),y ; High byte of f->next
492 ora ptr1 ; left->next == NULL?
495 ; Do left->next->prev = left
498 lda ptr4 ; Low byte of left
501 lda ptr4+1 ; High byte of left
505 ; This is now the last block, do _hlast = left
513 ; No merge of the left block, just set the link. Y points to size+1 if
514 ; we come here. Do left->next = f.
518 lda ptr2 ; Low byte of left
521 lda ptr2+1 ; High byte of left