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 .export _free, heapadd
69 ;-----------------------------------------------------------------------------
73 stx ptr2+1 ; Save block
75 ; Is the argument NULL? If so, bail out.
77 ora ptr2+1 ; Is the argument NULL?
81 ; There's a pointer below the user space that points to the real start of the
82 ; raw block. We will decrement the high pointer byte and use an offset of 254
83 ; to save some code. The first word of the raw block is the total size of the
84 ; block. Remember the block size in ptr1.
86 @L1: dec ptr2+1 ; Decrement high pointer byte
88 lda (ptr2),y ; High byte of real block address
93 sta ptr2 ; Set ptr2 to start of real block
95 ldy #usedblock::size+1
96 lda (ptr2),y ; High byte of size
102 ; Check if the block is on top of the heap
109 bne heapadd ; Add to free list
113 ; The pointer is located at the heap top. Lower the heap top pointer to
121 ; Check if the last block in the freelist is now at heap top. If so, remove
122 ; this block from the freelist.
127 beq @L9 ; Jump if free list empty
129 sta ptr1+1 ; Pointer to last block now in ptr1
132 lda (ptr1),y ; Low byte of block size
135 iny ; High byte of block size
140 bne @L9 ; Jump if last block not on top of heap
142 bne @L9 ; Jump if last block not on top of heap
144 ; Remove the last block
151 ; Correct the next pointer of the now last block
153 ldy #freeblock::prev+1 ; Offset of ->prev field
155 sta ptr2+1 ; Remember f->prev in ptr2
159 sta ptr2 ; Remember f->prev in ptr2
161 ora __heaplast+1 ; -> prev == 0?
162 bne @L8 ; Jump if free list not empty
164 ; Free list is now empty (A = 0)
173 ; Block before is now last block. ptr2 points to f->prev.
176 dey ; Points to high byte of ->next
178 dey ; Low byte of f->prev->next
182 ; The block is not on top of the heap. Add it to the free list. This was
183 ; formerly a separate function called __hadd that was implemented in C as
186 ; void _hadd (void* mem, size_t size)
187 ; /* Add an arbitrary memory block to the heap. This function is used by
188 ; * free(), but it does also allow usage of otherwise unused memory
189 ; * blocks as heap space. The given block is entered in the free list
190 ; * without any checks, so beware!
193 ; struct freeblock* f;
194 ; struct freeblock* left;
195 ; struct freeblock* right;
197 ; if (size >= sizeof (struct freeblock)) {
199 ; /* Set the admin data */
200 ; f = (struct freeblock*) mem;
203 ; /* Check if the freelist is empty */
204 ; if (_hfirst == 0) {
206 ; /* The freelist is empty until now, insert the block */
214 ; /* We have to search the free list. As we are doing so, we check
215 ; * if it is possible to combine this block with another already
216 ; * existing block. Beware: The block may be the "missing link"
217 ; * between *two* other blocks.
221 ; while (right && f > right) {
223 ; right = right->next;
227 ; /* Ok, the current block must be inserted between left and right (but
228 ; * beware: one of the two may be zero!). Also check for the condition
229 ; * that we have to merge two or three blocks.
232 ; /* Check if we must merge the block with the right one */
233 ; if (((unsigned) f) + size == (unsigned) right) {
234 ; /* Merge with the right block */
235 ; f->size += right->size;
236 ; if (f->next = right->next) {
239 ; /* This is now the last block */
243 ; /* No merge, just set the link */
249 ; /* Special case: This is the new freelist end */
253 ; /* Check if we must merge the block with the left one */
254 ; if ((unsigned) f == ((unsigned) left) + left->size) {
255 ; /* Merge with the left block */
256 ; left->size += f->size;
257 ; if (left->next = f->next) {
258 ; left->next->prev = left;
260 ; /* This is now the last block */
264 ; /* No merge, just set the link */
270 ; /* Special case: This is the new freelist start */
278 ; On entry, ptr2 must contain a pointer to the block, which must be at least
279 ; HEAP_MIN_BLOCKSIZE bytes in size, and ptr1 contains the total size of the
283 ; Check if the free list is empty, storing _hfirst into ptr3 for later
293 ; The free list is empty, so this is the first and only block. A contains
294 ; zero if we come here.
296 ldy #freeblock::next-1
297 @L2: iny ; f->next = f->prev = 0;
299 cpy #freeblock::prev+1 ; Done?
305 stx __heapfirst+1 ; _heapfirst = f;
307 stx __heaplast+1 ; _heaplast = f;
311 ; We have to search the free list. As we are doing so, check if it is possible
312 ; to combine this block with another, already existing block. Beware: The
313 ; block may be the "missing link" between two blocks.
314 ; ptr3 contains _hfirst (the start value of the search) when execution reaches
315 ; this point, Y contains size+1. We do also know that _heapfirst (and therefore
316 ; ptr3) is not zero on entry.
321 sta ptr4+1 ; left = 0;
322 ldy #freeblock::next+1
325 @Loop: lda ptr3+1 ; High byte of right
330 @L1: bcs CheckRightMerge
332 @L2: stx ptr4 ; left = right;
336 lda (ptr3),y ; right = right->next;
338 iny ; Points to next+1
345 ; If we come here, the right pointer is zero, so we don't need to check for
346 ; a merge. The new block is the new freelist end.
347 ; A is zero when we come here, Y points to next+1
349 sta (ptr2),y ; Clear high byte of f->next
351 sta (ptr2),y ; Clear low byte of f->next
353 lda ptr2 ; _heaplast = f;
358 ; Since we have checked the case that the freelist is empty before, if the
359 ; right pointer is NULL, the left *cannot* be NULL here. So skip the
360 ; pointer check and jump right to the left block merge
364 ; The given block must be inserted between left and right, and right is not
379 ; Merge with the right block. Do f->size += right->size;
385 iny ; Points to size+1
390 ; Set f->next = right->next and remember f->next in ptr1 (we don't need the
391 ; size stored there any longer)
394 lda (ptr3),y ; Low byte of right->next
395 sta (ptr2),y ; Store to low byte of f->next
397 iny ; Points to next+1
398 lda (ptr3),y ; High byte of right->next
399 sta (ptr2),y ; Store to high byte of f->next
402 beq @L1 ; Jump if f->next zero
407 lda ptr2 ; Low byte of f
408 sta (ptr1),y ; Low byte of f->next->prev
409 iny ; Points to prev+1
410 lda ptr2+1 ; High byte of f
411 sta (ptr1),y ; High byte of f->next->prev
412 jmp CheckLeftMerge ; Done
414 ; f->next is zero, this is now the last block
416 @L1: lda ptr2 ; _heaplast = f;
422 ; No right merge, just set the link.
425 ldy #freeblock::next ; f->next = right;
428 iny ; Points to next+1
433 lda ptr2 ; right->prev = f;
435 iny ; Points to prev+1
439 ; Check if the left pointer is zero
442 lda ptr4 ; left == NULL?
444 bne CheckLeftMerge2 ; Jump if there is a left block
446 ; We don't have a left block, so f is actually the new freelist start
449 sta (ptr2),y ; f->prev = 0;
453 lda ptr2 ; _heapfirst = f;
460 ; Check if the left block is adjacent to the following one
463 ldy #freeblock::size ; Calculate left + left->size
464 lda (ptr4),y ; Low byte of left->size
467 iny ; Points to size+1
468 lda (ptr4),y ; High byte of left->size
474 bne NoLeftMerge ; Jump if blocks not adjacent
476 ; Merge with the left block. Do left->size += f->size;
482 iny ; Points to size+1
487 ; Set left->next = f->next and remember left->next in ptr1.
490 lda (ptr2),y ; Low byte of f->next
493 iny ; Points to next+1
494 lda (ptr2),y ; High byte of f->next
497 ora ptr1 ; left->next == NULL?
500 ; Do left->next->prev = left
503 lda ptr4 ; Low byte of left
506 lda ptr4+1 ; High byte of left
510 ; This is now the last block, do _heaplast = left
518 ; No merge of the left block, just set the link. Y points to size+1 if
519 ; we come here. Do left->next = f.
523 lda ptr2 ; Low byte of left
526 lda ptr2+1 ; High byte of left