git.sur5r.net Git - cc65/blob - libsrc/common/free.s

   1 ;
   2 ; Ullrich von Bassewitz, 19.03.2000
   3 ;
   4 ; Free a block on the heap.
   5 ;
   6 ; void __fastcall__ free (void* block);
   7 ;
   8 ;
   9 ; C implementation was:
  10 ;
  11 ; void free (void* block)
  12 ; /* Release an allocated memory block. The function will accept NULL pointers
  13 ; ** (and do nothing in this case).
  14 ; */
  15 ; {
  16 ;     unsigned* b;
  17 ;     unsigned size;
  18 ;     struct freeblock* f;
  19 ;
  20 ;
  21 ;     /* Allow NULL arguments */
  22 ;     if (block == 0) {
  23 ;         return;
  24 ;     }
  25 ;
  26 ;     /* Get a pointer to the real memory block, then get the size */
  27 ;     b = (unsigned*) block;
  28 ;     size = *--b;
  29 ;
  30 ;     /* Check if the block is at the top of the heap */
  31 ;     if (((int) b) + size == (int) _hptr) {
  32 ;
  33 ;         /* Decrease _hptr to release the block */
  34 ;         _hptr = (unsigned*) (((int) _hptr) - size);
  35 ;
  36 ;         /* Check if the last block in the freelist is now at heap top. If so,
  37 ;         ** remove this block from the freelist.
  38 ;         */
  39 ;         if (f = _hlast) {
  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 */
  45 ;                     f->prev->next = 0;
  46 ;                 } else {
  47 ;                     /* The freelist is empty now */
  48 ;                     _hfirst = 0;
  49 ;                 }
  50 ;             }
  51 ;         }
  52 ;
  53 ;     } else {
  54 ;
  55 ;               /* Not at heap top, enter the block into the free list */
  56 ;       _hadd (b, size);
  57 ;
  58 ;     }
  59 ; }
  60 ;
  61
  62         .importzp       ptr1, ptr2, ptr3, ptr4
  63         .export         _free, heapadd
  64
  65         .include        "_heap.inc"
  66
  67         .macpack        generic
  68
  69 ;-----------------------------------------------------------------------------
  70 ; Code
  71
  72 _free:  sta     ptr2
  73         stx     ptr2+1                  ; Save block
  74
  75 ; Is the argument NULL? If so, bail out.
  76
  77         ora     ptr2+1                  ; Is the argument NULL?
  78         bne     @L1                     ; Jump if no
  79         rts                             ; Bail out if yes
  80
  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.
  85
  86 @L1:    dec     ptr2+1                  ; Decrement high pointer byte
  87         ldy     #$FF
  88         lda     (ptr2),y                ; High byte of real block address
  89         tax
  90         dey
  91         lda     (ptr2),y
  92         stx     ptr2+1
  93         sta     ptr2                    ; Set ptr2 to start of real block
  94
  95         ldy     #usedblock::size+1
  96         lda     (ptr2),y                ; High byte of size
  97         sta     ptr1+1                  ; Save it
  98         dey
  99         lda     (ptr2),y
 100         sta     ptr1
 101
 102 ; Check if the block is on top of the heap
 103
 104         add     ptr2
 105         tay
 106         lda     ptr2+1
 107         adc     ptr1+1
 108         cpy     __heapptr
 109         bne     heapadd                 ; Add to free list
 110         cmp     __heapptr+1
 111         bne     heapadd
 112
 113 ; The pointer is located at the heap top. Lower the heap top pointer to
 114 ; release the block.
 115
 116 @L3:    lda     ptr2
 117         sta     __heapptr
 118         lda     ptr2+1
 119         sta     __heapptr+1
 120
 121 ; Check if the last block in the freelist is now at heap top. If so, remove
 122 ; this block from the freelist.
 123
 124         lda     __heaplast
 125         sta     ptr1
 126         ora     __heaplast+1
 127         beq     @L9                     ; Jump if free list empty
 128         lda     __heaplast+1
 129         sta     ptr1+1                  ; Pointer to last block now in ptr1
 130
 131         ldy     #freeblock::size
 132         lda     (ptr1),y                ; Low byte of block size
 133         add     ptr1
 134         tax
 135         iny                             ; High byte of block size
 136         lda     (ptr1),y
 137         adc     ptr1+1
 138
 139         cmp     __heapptr+1
 140         bne     @L9                     ; Jump if last block not on top of heap
 141         cpx     __heapptr
 142         bne     @L9                     ; Jump if last block not on top of heap
 143
 144 ; Remove the last block
 145
 146         lda     ptr1
 147         sta     __heapptr
 148         lda     ptr1+1
 149         sta     __heapptr+1
 150
 151 ; Correct the next pointer of the now last block
 152
 153         ldy     #freeblock::prev+1      ; Offset of ->prev field
 154         lda     (ptr1),y
 155         sta     ptr2+1                  ; Remember f->prev in ptr2
 156         sta     __heaplast+1
 157         dey
 158         lda     (ptr1),y
 159         sta     ptr2                    ; Remember f->prev in ptr2
 160         sta     __heaplast
 161         ora     __heaplast+1            ; -> prev == 0?
 162         bne     @L8                     ; Jump if free list not empty
 163
 164 ; Free list is now empty (A = 0)
 165
 166         sta     __heapfirst
 167         sta     __heapfirst+1
 168
 169 ; Done
 170
 171 @L9:    rts
 172
 173 ; Block before is now last block. ptr2 points to f->prev.
 174
 175 @L8:    lda     #$00
 176         dey                             ; Points to high byte of ->next
 177         sta     (ptr2),y
 178         dey                             ; Low byte of f->prev->next
 179         sta     (ptr2),y
 180         rts                             ; Done
 181
 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
 184 ; shown here:
 185 ;
 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!
 191 ; */
 192 ; {
 193 ;     struct freeblock* f;
 194 ;     struct freeblock* left;
 195 ;     struct freeblock* right;
 196 ;
 197 ;     if (size >= sizeof (struct freeblock)) {
 198 ;
 199 ;       /* Set the admin data */
 200 ;       f = (struct freeblock*) mem;
 201 ;       f->size = size;
 202 ;
 203 ;       /* Check if the freelist is empty */
 204 ;       if (_hfirst == 0) {
 205 ;
 206 ;           /* The freelist is empty until now, insert the block */
 207 ;           f->prev = 0;
 208 ;           f->next = 0;
 209 ;           _hfirst = f;
 210 ;           _hlast  = f;
 211 ;
 212 ;       } else {
 213 ;
 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.
 218 ;           */
 219 ;           left = 0;
 220 ;           right = _hfirst;
 221 ;           while (right && f > right) {
 222 ;               left = right;
 223 ;               right = right->next;
 224 ;           }
 225 ;
 226 ;
 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.
 230 ;           */
 231 ;           if (right) {
 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) {
 237 ;                               f->next->prev = f;
 238 ;                   } else {
 239 ;                       /* This is now the last block */
 240 ;                       _hlast = f;
 241 ;                   }
 242 ;               } else {
 243 ;                   /* No merge, just set the link */
 244 ;                   f->next = right;
 245 ;                   right->prev = f;
 246 ;               }
 247 ;           } else {
 248 ;               f->next = 0;
 249 ;               /* Special case: This is the new freelist end */
 250 ;               _hlast = f;
 251 ;           }
 252 ;           if (left) {
 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;
 259 ;                   } else {
 260 ;                       /* This is now the last block */
 261 ;                       _hlast = left;
 262 ;                   }
 263 ;               } else {
 264 ;                   /* No merge, just set the link */
 265 ;                   left->next = f;
 266 ;                   f->prev = left;
 267 ;               }
 268 ;           } else {
 269 ;               f->prev = 0;
 270 ;               /* Special case: This is the new freelist start */
 271 ;               _hfirst = f;
 272 ;           }
 273 ;       }
 274 ;     }
 275 ; }
 276 ;
 277 ;
 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
 280 ; block.
 281 ;
 282
 283 ; Check if the free list is empty, storing _hfirst into ptr3 for later
 284
 285 heapadd:
 286         lda     __heapfirst
 287         sta     ptr3
 288         lda     __heapfirst+1
 289         sta     ptr3+1
 290         ora     ptr3
 291         bne     SearchFreeList
 292
 293 ; The free list is empty, so this is the first and only block. A contains
 294 ; zero if we come here.
 295
 296         ldy     #freeblock::next-1
 297 @L2:    iny                             ; f->next = f->prev = 0;
 298         sta     (ptr2),y
 299         cpy     #freeblock::prev+1      ; Done?
 300         bne     @L2
 301
 302         lda     ptr2
 303         ldx     ptr2+1
 304         sta     __heapfirst
 305         stx     __heapfirst+1           ; _heapfirst = f;
 306         sta     __heaplast
 307         stx     __heaplast+1            ; _heaplast = f;
 308
 309         rts                             ; Done
 310
 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.
 317
 318 SearchFreeList:
 319         lda     #0
 320         sta     ptr4
 321         sta     ptr4+1                  ; left = 0;
 322         ldy     #freeblock::next+1
 323         ldx     ptr3
 324
 325 @Loop:  lda     ptr3+1                  ; High byte of right
 326         cmp     ptr2+1
 327         bne     @L1
 328         cpx     ptr2
 329         beq     @L2
 330 @L1:    bcs     CheckRightMerge
 331
 332 @L2:    stx     ptr4                    ; left = right;
 333         sta     ptr4+1
 334
 335         dey                             ; Points to next
 336         lda     (ptr3),y                ; right = right->next;
 337         tax
 338         iny                             ; Points to next+1
 339         lda     (ptr3),y
 340         stx     ptr3
 341         sta     ptr3+1
 342         ora     ptr3
 343         bne     @Loop
 344
 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
 348
 349         sta     (ptr2),y                ; Clear high byte of f->next
 350         dey
 351         sta     (ptr2),y                ; Clear low byte of f->next
 352
 353         lda     ptr2                    ; _heaplast = f;
 354         sta     __heaplast
 355         lda     ptr2+1
 356         sta     __heaplast+1
 357
 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
 361
 362         jmp     CheckLeftMerge2
 363
 364 ; The given block must be inserted between left and right, and right is not
 365 ; zero.
 366
 367 CheckRightMerge:
 368         lda     ptr2
 369         add     ptr1                    ; f + size
 370         tax
 371         lda     ptr2+1
 372         adc     ptr1+1
 373
 374         cpx     ptr3
 375         bne     NoRightMerge
 376         cmp     ptr3+1
 377         bne     NoRightMerge
 378
 379 ; Merge with the right block. Do f->size += right->size;
 380
 381         ldy     #freeblock::size
 382         lda     ptr1
 383         add     (ptr3),y
 384         sta     (ptr2),y
 385         iny                             ; Points to size+1
 386         lda     ptr1+1
 387         adc     (ptr3),y
 388         sta     (ptr2),y
 389
 390 ; Set f->next = right->next and remember f->next in ptr1 (we don't need the
 391 ; size stored there any longer)
 392
 393         iny                             ; Points to next
 394         lda     (ptr3),y                ; Low byte of right->next
 395         sta     (ptr2),y                ; Store to low byte of f->next
 396         sta     ptr1
 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
 400         sta     ptr1+1
 401         ora     ptr1
 402         beq     @L1                     ; Jump if f->next zero
 403
 404 ; f->next->prev = f;
 405
 406         iny                             ; Points to prev
 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
 413
 414 ; f->next is zero, this is now the last block
 415
 416 @L1:    lda     ptr2                    ; _heaplast = f;
 417         sta     __heaplast
 418         lda     ptr2+1
 419         sta     __heaplast+1
 420         jmp     CheckLeftMerge
 421
 422 ; No right merge, just set the link.
 423
 424 NoRightMerge:
 425         ldy     #freeblock::next        ; f->next = right;
 426         lda     ptr3
 427         sta     (ptr2),y
 428         iny                             ; Points to next+1
 429         lda     ptr3+1
 430         sta     (ptr2),y
 431
 432         iny                             ; Points to prev
 433         lda     ptr2                    ; right->prev = f;
 434         sta     (ptr3),y
 435         iny                             ; Points to prev+1
 436         lda     ptr2+1
 437         sta     (ptr3),y
 438
 439 ; Check if the left pointer is zero
 440
 441 CheckLeftMerge:
 442         lda     ptr4                    ; left == NULL?
 443         ora     ptr4+1
 444         bne     CheckLeftMerge2         ; Jump if there is a left block
 445
 446 ; We don't have a left block, so f is actually the new freelist start
 447
 448         ldy     #freeblock::prev
 449         sta     (ptr2),y                ; f->prev = 0;
 450         iny
 451         sta     (ptr2),y
 452
 453         lda     ptr2                    ; _heapfirst = f;
 454         sta     __heapfirst
 455         lda     ptr2+1
 456         sta     __heapfirst+1
 457
 458         rts                             ; Done
 459
 460 ; Check if the left block is adjacent to the following one
 461
 462 CheckLeftMerge2:
 463         ldy     #freeblock::size        ; Calculate left + left->size
 464         lda     (ptr4),y                ; Low byte of left->size
 465         add     ptr4
 466         tax
 467         iny                             ; Points to size+1
 468         lda     (ptr4),y                ; High byte of left->size
 469         adc     ptr4+1
 470
 471         cpx     ptr2
 472         bne     NoLeftMerge
 473         cmp     ptr2+1
 474         bne     NoLeftMerge             ; Jump if blocks not adjacent
 475
 476 ; Merge with the left block. Do left->size += f->size;
 477
 478         dey                             ; Points to size
 479         lda     (ptr4),y
 480         add     (ptr2),y
 481         sta     (ptr4),y
 482         iny                             ; Points to size+1
 483         lda     (ptr4),y
 484         adc     (ptr2),y
 485         sta     (ptr4),y
 486
 487 ; Set left->next = f->next and remember left->next in ptr1.
 488
 489         iny                             ; Points to next
 490         lda     (ptr2),y                ; Low byte of f->next
 491         sta     (ptr4),y
 492         sta     ptr1
 493         iny                             ; Points to next+1
 494         lda     (ptr2),y                ; High byte of f->next
 495         sta     (ptr4),y
 496         sta     ptr1+1
 497         ora     ptr1                    ; left->next == NULL?
 498         beq     @L1
 499
 500 ; Do left->next->prev = left
 501
 502         iny                             ; Points to prev
 503         lda     ptr4                    ; Low byte of left
 504         sta     (ptr1),y
 505         iny
 506         lda     ptr4+1                  ; High byte of left
 507         sta     (ptr1),y
 508         rts                             ; Done
 509
 510 ; This is now the last block, do _heaplast = left
 511
 512 @L1:    lda     ptr4
 513         sta     __heaplast
 514         lda     ptr4+1
 515         sta     __heaplast+1
 516         rts                             ; Done
 517
 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.
 520
 521 NoLeftMerge:
 522         iny                             ; Points to next
 523         lda     ptr2                    ; Low byte of left
 524         sta     (ptr4),y
 525         iny
 526         lda     ptr2+1                  ; High byte of left
 527         sta     (ptr4),y
 528
 529 ; Do f->prev = left
 530
 531         iny                             ; Points to prev
 532         lda     ptr4
 533         sta     (ptr2),y
 534         iny
 535         lda     ptr4+1
 536         sta     (ptr2),y
 537         rts                             ; Done
 538
 539
 540
 541
 542
 543
 544