X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libsrc%2Fcommon%2Ffree.s;h=b6b77aae81eea4a2f1d10e473182753964767661;hb=f16516047a551319c82debd339ded8bc2b587212;hp=4ac96f1af67cc779d66252aca2440edd16280d20;hpb=18e3e7cb11ba3dc34232d576e8118427c9d3cd3a;p=cc65 diff --git a/libsrc/common/free.s b/libsrc/common/free.s index 4ac96f1af..b6b77aae8 100644 --- a/libsrc/common/free.s +++ b/libsrc/common/free.s @@ -41,7 +41,7 @@ ; /* Remove the last block */ ; _hptr = (unsigned*) (((int) _hptr) - f->size); ; if (_hlast = f->prev) { -; /* Block before is now last block */ +; /* Block before is now last block */ ; f->prev->next = 0; ; } else { ; /* The freelist is empty now */ @@ -52,30 +52,30 @@ ; ; } else { ; -; /* Not at heap top, enter the block into the free list */ -; _hadd (b, size); +; /* Not at heap top, enter the block into the free list */ +; _hadd (b, size); ; ; } ; } ; - .importzp ptr1, ptr2, ptr3, ptr4 - .export _free, heapadd + .importzp ptr1, ptr2, ptr3, ptr4 + .export _free, heapadd .include "_heap.inc" - .macpack generic + .macpack generic ;----------------------------------------------------------------------------- ; Code -_free: sta ptr2 - stx ptr2+1 ; Save block +_free: sta ptr2 + stx ptr2+1 ; Save block ; Is the argument NULL? If so, bail out. - ora ptr2+1 ; Is the argument NULL? - bne @L1 ; Jump if no + ora ptr2+1 ; Is the argument NULL? + bne @L1 ; Jump if no rts ; Bail out if yes ; There's a pointer below the user space that points to the real start of the @@ -84,7 +84,7 @@ _free: sta ptr2 ; block. Remember the block size in ptr1. @L1: dec ptr2+1 ; Decrement high pointer byte - ldy #$FF + ldy #$FF lda (ptr2),y ; High byte of real block address tax dey @@ -93,91 +93,91 @@ _free: sta ptr2 sta ptr2 ; Set ptr2 to start of real block ldy #usedblock::size+1 - lda (ptr2),y ; High byte of size - sta ptr1+1 ; Save it - dey - lda (ptr2),y - sta ptr1 + lda (ptr2),y ; High byte of size + sta ptr1+1 ; Save it + dey + lda (ptr2),y + sta ptr1 ; Check if the block is on top of the heap - add ptr2 - tay - lda ptr2+1 - adc ptr1+1 - cpy __heapptr - bne heapadd ; Add to free list - cmp __heapptr+1 - bne heapadd + add ptr2 + tay + lda ptr2+1 + adc ptr1+1 + cpy __heapptr + bne heapadd ; Add to free list + cmp __heapptr+1 + bne heapadd ; The pointer is located at the heap top. Lower the heap top pointer to ; release the block. -@L3: lda ptr2 - sta __heapptr - lda ptr2+1 - sta __heapptr+1 +@L3: lda ptr2 + sta __heapptr + lda ptr2+1 + sta __heapptr+1 ; Check if the last block in the freelist is now at heap top. If so, remove ; this block from the freelist. - lda __heaplast - sta ptr1 - ora __heaplast+1 - beq @L9 ; Jump if free list empty - lda __heaplast+1 - sta ptr1+1 ; Pointer to last block now in ptr1 - - ldy #freeblock::size - lda (ptr1),y ; Low byte of block size - add ptr1 - tax - iny ; High byte of block size - lda (ptr1),y - adc ptr1+1 - - cmp __heapptr+1 - bne @L9 ; Jump if last block not on top of heap - cpx __heapptr - bne @L9 ; Jump if last block not on top of heap + lda __heaplast + sta ptr1 + ora __heaplast+1 + beq @L9 ; Jump if free list empty + lda __heaplast+1 + sta ptr1+1 ; Pointer to last block now in ptr1 + + ldy #freeblock::size + lda (ptr1),y ; Low byte of block size + add ptr1 + tax + iny ; High byte of block size + lda (ptr1),y + adc ptr1+1 + + cmp __heapptr+1 + bne @L9 ; Jump if last block not on top of heap + cpx __heapptr + bne @L9 ; Jump if last block not on top of heap ; Remove the last block - lda ptr1 - sta __heapptr - lda ptr1+1 - sta __heapptr+1 + lda ptr1 + sta __heapptr + lda ptr1+1 + sta __heapptr+1 ; Correct the next pointer of the now last block - ldy #freeblock::prev+1 ; Offset of ->prev field - lda (ptr1),y - sta ptr2+1 ; Remember f->prev in ptr2 - sta __heaplast+1 - dey - lda (ptr1),y - sta ptr2 ; Remember f->prev in ptr2 - sta __heaplast - ora __heaplast+1 ; -> prev == 0? - bne @L8 ; Jump if free list not empty + ldy #freeblock::prev+1 ; Offset of ->prev field + lda (ptr1),y + sta ptr2+1 ; Remember f->prev in ptr2 + sta __heaplast+1 + dey + lda (ptr1),y + sta ptr2 ; Remember f->prev in ptr2 + sta __heaplast + ora __heaplast+1 ; -> prev == 0? + bne @L8 ; Jump if free list not empty ; Free list is now empty (A = 0) - sta __heapfirst - sta __heapfirst+1 + sta __heapfirst + sta __heapfirst+1 ; Done -@L9: rts +@L9: rts ; Block before is now last block. ptr2 points to f->prev. -@L8: lda #$00 - dey ; Points to high byte of ->next - sta (ptr2),y - dey ; Low byte of f->prev->next - sta (ptr2),y - rts ; Done +@L8: lda #$00 + dey ; Points to high byte of ->next + sta (ptr2),y + dey ; Low byte of f->prev->next + sta (ptr2),y + rts ; Done ; The block is not on top of the heap. Add it to the free list. This was ; formerly a separate function called __hadd that was implemented in C as @@ -196,81 +196,81 @@ _free: sta ptr2 ; ; if (size >= sizeof (struct freeblock)) { ; -; /* Set the admin data */ -; f = (struct freeblock*) mem; -; f->size = size; +; /* Set the admin data */ +; f = (struct freeblock*) mem; +; f->size = size; ; -; /* Check if the freelist is empty */ -; if (_hfirst == 0) { +; /* Check if the freelist is empty */ +; if (_hfirst == 0) { ; -; /* The freelist is empty until now, insert the block */ -; f->prev = 0; -; f->next = 0; -; _hfirst = f; -; _hlast = f; +; /* The freelist is empty until now, insert the block */ +; f->prev = 0; +; f->next = 0; +; _hfirst = f; +; _hlast = f; ; -; } else { +; } else { ; -; /* We have to search the free list. As we are doing so, we check -; * if it is possible to combine this block with another already -; * existing block. Beware: The block may be the "missing link" +; /* We have to search the free list. As we are doing so, we check +; * if it is possible to combine this block with another already +; * existing block. Beware: The block may be the "missing link" ; * between *two* other blocks. -; */ -; left = 0; -; right = _hfirst; -; while (right && f > right) { -; left = right; -; right = right->next; -; } +; */ +; left = 0; +; right = _hfirst; +; while (right && f > right) { +; left = right; +; right = right->next; +; } ; ; -; /* Ok, the current block must be inserted between left and right (but -; * beware: one of the two may be zero!). Also check for the condition -; * that we have to merge two or three blocks. -; */ -; if (right) { -; /* Check if we must merge the block with the right one */ -; if (((unsigned) f) + size == (unsigned) right) { -; /* Merge with the right block */ -; f->size += right->size; -; if (f->next = right->next) { -; f->next->prev = f; -; } else { -; /* This is now the last block */ -; _hlast = f; -; } -; } else { -; /* No merge, just set the link */ -; f->next = right; -; right->prev = f; -; } -; } else { -; f->next = 0; -; /* Special case: This is the new freelist end */ -; _hlast = f; -; } -; if (left) { -; /* Check if we must merge the block with the left one */ -; if ((unsigned) f == ((unsigned) left) + left->size) { -; /* Merge with the left block */ -; left->size += f->size; -; if (left->next = f->next) { -; left->next->prev = left; -; } else { -; /* This is now the last block */ -; _hlast = left; -; } -; } else { -; /* No merge, just set the link */ -; left->next = f; -; f->prev = left; -; } -; } else { -; f->prev = 0; -; /* Special case: This is the new freelist start */ -; _hfirst = f; -; } -; } +; /* Ok, the current block must be inserted between left and right (but +; * beware: one of the two may be zero!). Also check for the condition +; * that we have to merge two or three blocks. +; */ +; if (right) { +; /* Check if we must merge the block with the right one */ +; if (((unsigned) f) + size == (unsigned) right) { +; /* Merge with the right block */ +; f->size += right->size; +; if (f->next = right->next) { +; f->next->prev = f; +; } else { +; /* This is now the last block */ +; _hlast = f; +; } +; } else { +; /* No merge, just set the link */ +; f->next = right; +; right->prev = f; +; } +; } else { +; f->next = 0; +; /* Special case: This is the new freelist end */ +; _hlast = f; +; } +; if (left) { +; /* Check if we must merge the block with the left one */ +; if ((unsigned) f == ((unsigned) left) + left->size) { +; /* Merge with the left block */ +; left->size += f->size; +; if (left->next = f->next) { +; left->next->prev = left; +; } else { +; /* This is now the last block */ +; _hlast = left; +; } +; } else { +; /* No merge, just set the link */ +; left->next = f; +; f->prev = left; +; } +; } else { +; f->prev = 0; +; /* Special case: This is the new freelist start */ +; _hfirst = f; +; } +; } ; } ; } ; @@ -283,30 +283,30 @@ _free: sta ptr2 ; Check if the free list is empty, storing _hfirst into ptr3 for later heapadd: - lda __heapfirst - sta ptr3 - lda __heapfirst+1 - sta ptr3+1 - ora ptr3 - bne SearchFreeList + lda __heapfirst + sta ptr3 + lda __heapfirst+1 + sta ptr3+1 + ora ptr3 + bne SearchFreeList ; The free list is empty, so this is the first and only block. A contains ; zero if we come here. - ldy #freeblock::next-1 -@L2: iny ; f->next = f->prev = 0; - sta (ptr2),y - cpy #freeblock::prev+1 ; Done? - bne @L2 + ldy #freeblock::next-1 +@L2: iny ; f->next = f->prev = 0; + sta (ptr2),y + cpy #freeblock::prev+1 ; Done? + bne @L2 - lda ptr2 - ldx ptr2+1 - sta __heapfirst - stx __heapfirst+1 ; _heapfirst = f; - sta __heaplast - stx __heaplast+1 ; _heaplast = f; + lda ptr2 + ldx ptr2+1 + sta __heapfirst + stx __heapfirst+1 ; _heapfirst = f; + sta __heaplast + stx __heaplast+1 ; _heaplast = f; - rts ; Done + rts ; Done ; We have to search the free list. As we are doing so, check if it is possible ; to combine this block with another, already existing block. Beware: The @@ -316,225 +316,225 @@ heapadd: ; ptr3) is not zero on entry. SearchFreeList: - lda #0 - sta ptr4 - sta ptr4+1 ; left = 0; - ldy #freeblock::next+1 - ldx ptr3 - -@Loop: lda ptr3+1 ; High byte of right - cmp ptr2+1 - bne @L1 - cpx ptr2 - beq @L2 -@L1: bcs CheckRightMerge - -@L2: stx ptr4 ; left = right; - sta ptr4+1 - - dey ; Points to next - lda (ptr3),y ; right = right->next; - tax - iny ; Points to next+1 - lda (ptr3),y - stx ptr3 - sta ptr3+1 - ora ptr3 - bne @Loop + lda #0 + sta ptr4 + sta ptr4+1 ; left = 0; + ldy #freeblock::next+1 + ldx ptr3 + +@Loop: lda ptr3+1 ; High byte of right + cmp ptr2+1 + bne @L1 + cpx ptr2 + beq @L2 +@L1: bcs CheckRightMerge + +@L2: stx ptr4 ; left = right; + sta ptr4+1 + + dey ; Points to next + lda (ptr3),y ; right = right->next; + tax + iny ; Points to next+1 + lda (ptr3),y + stx ptr3 + sta ptr3+1 + ora ptr3 + bne @Loop ; If we come here, the right pointer is zero, so we don't need to check for ; a merge. The new block is the new freelist end. ; A is zero when we come here, Y points to next+1 - sta (ptr2),y ; Clear high byte of f->next - dey - sta (ptr2),y ; Clear low byte of f->next + sta (ptr2),y ; Clear high byte of f->next + dey + sta (ptr2),y ; Clear low byte of f->next - lda ptr2 ; _heaplast = f; - sta __heaplast - lda ptr2+1 - sta __heaplast+1 + lda ptr2 ; _heaplast = f; + sta __heaplast + lda ptr2+1 + sta __heaplast+1 ; Since we have checked the case that the freelist is empty before, if the ; right pointer is NULL, the left *cannot* be NULL here. So skip the ; pointer check and jump right to the left block merge - jmp CheckLeftMerge2 + jmp CheckLeftMerge2 ; The given block must be inserted between left and right, and right is not ; zero. CheckRightMerge: - lda ptr2 - add ptr1 ; f + size - tax - lda ptr2+1 - adc ptr1+1 + lda ptr2 + add ptr1 ; f + size + tax + lda ptr2+1 + adc ptr1+1 - cpx ptr3 - bne NoRightMerge - cmp ptr3+1 - bne NoRightMerge + cpx ptr3 + bne NoRightMerge + cmp ptr3+1 + bne NoRightMerge ; Merge with the right block. Do f->size += right->size; - ldy #freeblock::size - lda ptr1 - add (ptr3),y - sta (ptr2),y - iny ; Points to size+1 - lda ptr1+1 - adc (ptr3),y - sta (ptr2),y + ldy #freeblock::size + lda ptr1 + add (ptr3),y + sta (ptr2),y + iny ; Points to size+1 + lda ptr1+1 + adc (ptr3),y + sta (ptr2),y ; Set f->next = right->next and remember f->next in ptr1 (we don't need the ; size stored there any longer) - iny ; Points to next - lda (ptr3),y ; Low byte of right->next - sta (ptr2),y ; Store to low byte of f->next - sta ptr1 - iny ; Points to next+1 - lda (ptr3),y ; High byte of right->next - sta (ptr2),y ; Store to high byte of f->next - sta ptr1+1 - ora ptr1 - beq @L1 ; Jump if f->next zero + iny ; Points to next + lda (ptr3),y ; Low byte of right->next + sta (ptr2),y ; Store to low byte of f->next + sta ptr1 + iny ; Points to next+1 + lda (ptr3),y ; High byte of right->next + sta (ptr2),y ; Store to high byte of f->next + sta ptr1+1 + ora ptr1 + beq @L1 ; Jump if f->next zero ; f->next->prev = f; - iny ; Points to prev - lda ptr2 ; Low byte of f - sta (ptr1),y ; Low byte of f->next->prev - iny ; Points to prev+1 - lda ptr2+1 ; High byte of f - sta (ptr1),y ; High byte of f->next->prev - jmp CheckLeftMerge ; Done + iny ; Points to prev + lda ptr2 ; Low byte of f + sta (ptr1),y ; Low byte of f->next->prev + iny ; Points to prev+1 + lda ptr2+1 ; High byte of f + sta (ptr1),y ; High byte of f->next->prev + jmp CheckLeftMerge ; Done ; f->next is zero, this is now the last block -@L1: lda ptr2 ; _heaplast = f; - sta __heaplast - lda ptr2+1 - sta __heaplast+1 - jmp CheckLeftMerge +@L1: lda ptr2 ; _heaplast = f; + sta __heaplast + lda ptr2+1 + sta __heaplast+1 + jmp CheckLeftMerge ; No right merge, just set the link. NoRightMerge: - ldy #freeblock::next ; f->next = right; - lda ptr3 - sta (ptr2),y - iny ; Points to next+1 - lda ptr3+1 - sta (ptr2),y - - iny ; Points to prev - lda ptr2 ; right->prev = f; - sta (ptr3),y - iny ; Points to prev+1 - lda ptr2+1 - sta (ptr3),y + ldy #freeblock::next ; f->next = right; + lda ptr3 + sta (ptr2),y + iny ; Points to next+1 + lda ptr3+1 + sta (ptr2),y + + iny ; Points to prev + lda ptr2 ; right->prev = f; + sta (ptr3),y + iny ; Points to prev+1 + lda ptr2+1 + sta (ptr3),y ; Check if the left pointer is zero CheckLeftMerge: - lda ptr4 ; left == NULL? - ora ptr4+1 - bne CheckLeftMerge2 ; Jump if there is a left block + lda ptr4 ; left == NULL? + ora ptr4+1 + bne CheckLeftMerge2 ; Jump if there is a left block ; We don't have a left block, so f is actually the new freelist start - ldy #freeblock::prev - sta (ptr2),y ; f->prev = 0; - iny - sta (ptr2),y + ldy #freeblock::prev + sta (ptr2),y ; f->prev = 0; + iny + sta (ptr2),y - lda ptr2 ; _heapfirst = f; - sta __heapfirst - lda ptr2+1 - sta __heapfirst+1 + lda ptr2 ; _heapfirst = f; + sta __heapfirst + lda ptr2+1 + sta __heapfirst+1 - rts ; Done + rts ; Done ; Check if the left block is adjacent to the following one CheckLeftMerge2: - ldy #freeblock::size ; Calculate left + left->size - lda (ptr4),y ; Low byte of left->size - add ptr4 - tax - iny ; Points to size+1 - lda (ptr4),y ; High byte of left->size - adc ptr4+1 - - cpx ptr2 - bne NoLeftMerge - cmp ptr2+1 - bne NoLeftMerge ; Jump if blocks not adjacent + ldy #freeblock::size ; Calculate left + left->size + lda (ptr4),y ; Low byte of left->size + add ptr4 + tax + iny ; Points to size+1 + lda (ptr4),y ; High byte of left->size + adc ptr4+1 + + cpx ptr2 + bne NoLeftMerge + cmp ptr2+1 + bne NoLeftMerge ; Jump if blocks not adjacent ; Merge with the left block. Do left->size += f->size; - dey ; Points to size - lda (ptr4),y - add (ptr2),y - sta (ptr4),y - iny ; Points to size+1 - lda (ptr4),y - adc (ptr2),y - sta (ptr4),y + dey ; Points to size + lda (ptr4),y + add (ptr2),y + sta (ptr4),y + iny ; Points to size+1 + lda (ptr4),y + adc (ptr2),y + sta (ptr4),y ; Set left->next = f->next and remember left->next in ptr1. - iny ; Points to next - lda (ptr2),y ; Low byte of f->next - sta (ptr4),y - sta ptr1 - iny ; Points to next+1 - lda (ptr2),y ; High byte of f->next - sta (ptr4),y - sta ptr1+1 - ora ptr1 ; left->next == NULL? - beq @L1 + iny ; Points to next + lda (ptr2),y ; Low byte of f->next + sta (ptr4),y + sta ptr1 + iny ; Points to next+1 + lda (ptr2),y ; High byte of f->next + sta (ptr4),y + sta ptr1+1 + ora ptr1 ; left->next == NULL? + beq @L1 ; Do left->next->prev = left - iny ; Points to prev - lda ptr4 ; Low byte of left - sta (ptr1),y - iny - lda ptr4+1 ; High byte of left - sta (ptr1),y - rts ; Done + iny ; Points to prev + lda ptr4 ; Low byte of left + sta (ptr1),y + iny + lda ptr4+1 ; High byte of left + sta (ptr1),y + rts ; Done ; This is now the last block, do _heaplast = left -@L1: lda ptr4 - sta __heaplast - lda ptr4+1 - sta __heaplast+1 - rts ; Done +@L1: lda ptr4 + sta __heaplast + lda ptr4+1 + sta __heaplast+1 + rts ; Done ; No merge of the left block, just set the link. Y points to size+1 if ; we come here. Do left->next = f. NoLeftMerge: - iny ; Points to next - lda ptr2 ; Low byte of left - sta (ptr4),y - iny - lda ptr2+1 ; High byte of left - sta (ptr4),y + iny ; Points to next + lda ptr2 ; Low byte of left + sta (ptr4),y + iny + lda ptr2+1 ; High byte of left + sta (ptr4),y ; Do f->prev = left - iny ; Points to prev - lda ptr4 - sta (ptr2),y - iny - lda ptr4+1 - sta (ptr2),y - rts ; Done + iny ; Points to prev + lda ptr4 + sta (ptr2),y + iny + lda ptr4+1 + sta (ptr2),y + rts ; Done