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     @L0                     ; 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. The first word of the raw block is the total size of the block.
  83 ; Remember the block size in ptr1.
  84
  85 @L0:    lda     ptr2
  86         sub     #2
  87         sta     ptr2
  88         bcs     @L1
  89         dec     ptr2+1
  90 @L1:    ldy     #1
  91         lda     (ptr2),y                ; High byte of real block address
  92         tax
  93         dey
  94         lda     (ptr2),y
  95         stx     ptr2+1
  96         sta     ptr2                    ; Set ptr2 to start of real block
  97
  98         ldy     #usedblock::size+1
  99         lda     (ptr2),y                ; High byte of size
 100         sta     ptr1+1                  ; Save it
 101         dey
 102         lda     (ptr2),y
 103         sta     ptr1
 104
 105 ; Check if the block is on top of the heap
 106
 107         add     ptr2
 108         tay
 109         lda     ptr2+1
 110         adc     ptr1+1
 111         cpy     __heapptr
 112         bne     heapadd                 ; Add to free list
 113         cmp     __heapptr+1
 114         bne     heapadd
 115
 116 ; The pointer is located at the heap top. Lower the heap top pointer to
 117 ; release the block.
 118
 119 @L3:    lda     ptr2
 120         sta     __heapptr
 121         lda     ptr2+1
 122         sta     __heapptr+1
 123
 124 ; Check if the last block in the freelist is now at heap top. If so, remove
 125 ; this block from the freelist.
 126
 127         lda     __heaplast
 128         sta     ptr1
 129         ora     __heaplast+1
 130         beq     @L9                     ; Jump if free list empty
 131         lda     __heaplast+1
 132         sta     ptr1+1                  ; Pointer to last block now in ptr1
 133
 134         ldy     #freeblock::size
 135         lda     (ptr1),y                ; Low byte of block size
 136         add     ptr1
 137         tax
 138         iny                             ; High byte of block size
 139         lda     (ptr1),y
 140         adc     ptr1+1
 141
 142         cmp     __heapptr+1
 143         bne     @L9                     ; Jump if last block not on top of heap
 144         cpx     __heapptr
 145         bne     @L9                     ; Jump if last block not on top of heap
 146
 147 ; Remove the last block
 148
 149         lda     ptr1
 150         sta     __heapptr
 151         lda     ptr1+1
 152         sta     __heapptr+1
 153
 154 ; Correct the next pointer of the now last block
 155
 156         ldy     #freeblock::prev+1      ; Offset of ->prev field
 157         lda     (ptr1),y
 158         sta     ptr2+1                  ; Remember f->prev in ptr2
 159         sta     __heaplast+1
 160         dey
 161         lda     (ptr1),y
 162         sta     ptr2                    ; Remember f->prev in ptr2
 163         sta     __heaplast
 164         ora     __heaplast+1            ; -> prev == 0?
 165         bne     @L8                     ; Jump if free list not empty
 166
 167 ; Free list is now empty (A = 0)
 168
 169         sta     __heapfirst
 170         sta     __heapfirst+1
 171
 172 ; Done
 173
 174 @L9:    rts
 175
 176 ; Block before is now last block. ptr2 points to f->prev.
 177
 178 @L8:    lda     #$00
 179         dey                             ; Points to high byte of ->next
 180         sta     (ptr2),y
 181         dey                             ; Low byte of f->prev->next
 182         sta     (ptr2),y
 183         rts                             ; Done
 184
 185 ; The block is not on top of the heap. Add it to the free list. This was
 186 ; formerly a separate function called __hadd that was implemented in C as
 187 ; shown here:
 188 ;
 189 ; void _hadd (void* mem, size_t size)
 190 ; /* Add an arbitrary memory block to the heap. This function is used by
 191 ;  * free(), but it does also allow usage of otherwise unused memory
 192 ;  * blocks as heap space. The given block is entered in the free list
 193 ;  * without any checks, so beware!
 194 ;  */
 195 ; {
 196 ;     struct freeblock* f;
 197 ;     struct freeblock* left;
 198 ;     struct freeblock* right;
 199 ;
 200 ;     if (size >= sizeof (struct freeblock)) {
 201 ;
 202 ;       /* Set the admin data */
 203 ;       f = (struct freeblock*) mem;
 204 ;       f->size = size;
 205 ;
 206 ;       /* Check if the freelist is empty */
 207 ;       if (_hfirst == 0) {
 208 ;
 209 ;           /* The freelist is empty until now, insert the block */
 210 ;           f->prev = 0;
 211 ;           f->next = 0;
 212 ;           _hfirst = f;
 213 ;           _hlast  = f;
 214 ;
 215 ;       } else {
 216 ;
 217 ;           /* We have to search the free list. As we are doing so, we check
 218 ;            * if it is possible to combine this block with another already
 219 ;            * existing block. Beware: The block may be the "missing link"
 220 ;              * between *two* other blocks.
 221 ;            */
 222 ;           left = 0;
 223 ;           right = _hfirst;
 224 ;           while (right && f > right) {
 225 ;               left = right;
 226 ;               right = right->next;
 227 ;           }
 228 ;
 229 ;
 230 ;           /* Ok, the current block must be inserted between left and right (but
 231 ;            * beware: one of the two may be zero!). Also check for the condition
 232 ;            * that we have to merge two or three blocks.
 233 ;            */
 234 ;           if (right) {
 235 ;               /* Check if we must merge the block with the right one */
 236 ;                       if (((unsigned) f) + size == (unsigned) right) {
 237 ;                   /* Merge with the right block */
 238 ;                   f->size += right->size;
 239 ;                   if (f->next = right->next) {
 240 ;                               f->next->prev = f;
 241 ;                   } else {
 242 ;                       /* This is now the last block */
 243 ;                       _hlast = f;
 244 ;                   }
 245 ;               } else {
 246 ;                   /* No merge, just set the link */
 247 ;                   f->next = right;
 248 ;                   right->prev = f;
 249 ;               }
 250 ;           } else {
 251 ;               f->next = 0;
 252 ;               /* Special case: This is the new freelist end */
 253 ;               _hlast = f;
 254 ;           }
 255 ;           if (left) {
 256 ;               /* Check if we must merge the block with the left one */
 257 ;               if ((unsigned) f == ((unsigned) left) + left->size) {
 258 ;                   /* Merge with the left block */
 259 ;                   left->size += f->size;
 260 ;                   if (left->next = f->next) {
 261 ;                       left->next->prev = left;
 262 ;                   } else {
 263 ;                       /* This is now the last block */
 264 ;                       _hlast = left;
 265 ;                   }
 266 ;               } else {
 267 ;                   /* No merge, just set the link */
 268 ;                   left->next = f;
 269 ;                   f->prev = left;
 270 ;               }
 271 ;           } else {
 272 ;               f->prev = 0;
 273 ;               /* Special case: This is the new freelist start */
 274 ;               _hfirst = f;
 275 ;           }
 276 ;       }
 277 ;     }
 278 ; }
 279 ;
 280
 281 ; Check if the free list is empty, storing _hfirst into ptr3 for later
 282
 283 heapadd:
 284         lda     __heapfirst
 285         sta     ptr3
 286         lda     __heapfirst+1
 287         sta     ptr3+1
 288         ora     ptr3
 289         bne     SearchFreeList
 290
 291 ; The free list is empty, so this is the first and only block. A contains
 292 ; zero if we come here.
 293
 294         ldy     #freeblock::next-1
 295 @L2:    iny                             ; f->next = f->prev = 0;
 296         sta     (ptr2),y
 297         cpy     #freeblock::prev+1      ; Done?
 298         bne     @L2
 299
 300         lda     ptr2
 301         ldx     ptr2+1
 302         sta     __heapfirst
 303         stx     __heapfirst+1           ; _heapfirst = f;
 304         sta     __heaplast
 305         stx     __heaplast+1            ; _heaplast = f;
 306
 307         rts                             ; Done
 308
 309 ; We have to search the free list. As we are doing so, check if it is possible
 310 ; to combine this block with another, already existing block. Beware: The
 311 ; block may be the "missing link" between two blocks.
 312 ; ptr3 contains _hfirst (the start value of the search) when execution reaches
 313 ; this point, Y contains size+1. We do also know that _heapfirst (and therefore
 314 ; ptr3) is not zero on entry.
 315
 316 SearchFreeList:
 317         lda     #0
 318         sta     ptr4
 319         sta     ptr4+1                  ; left = 0;
 320         ldy     #freeblock::next+1
 321         ldx     ptr3
 322
 323 @Loop:  lda     ptr3+1                  ; High byte of right
 324         cmp     ptr2+1
 325         bne     @L1
 326         cpx     ptr2
 327         beq     @L2
 328 @L1:    bcs     CheckRightMerge
 329
 330 @L2:    stx     ptr4                    ; left = right;
 331         sta     ptr4+1
 332
 333         dey                             ; Points to next
 334         lda     (ptr3),y                ; right = right->next;
 335         tax
 336         iny                             ; Points to next+1
 337         lda     (ptr3),y
 338         stx     ptr3
 339         sta     ptr3+1
 340         ora     ptr3
 341         bne     @Loop
 342
 343 ; If we come here, the right pointer is zero, so we don't need to check for
 344 ; a merge. The new block is the new freelist end.
 345 ; A is zero when we come here, Y points to next+1
 346
 347         sta     (ptr2),y                ; Clear high byte of f->next
 348         dey
 349         sta     (ptr2),y                ; Clear low byte of f->next
 350
 351         lda     ptr2                    ; _heaplast = f;
 352         sta     __heaplast
 353         lda     ptr2+1
 354         sta     __heaplast+1
 355
 356 ; Since we have checked the case that the freelist is empty before, if the
 357 ; right pointer is NULL, the left *cannot* be NULL here. So skip the
 358 ; pointer check and jump right to the left block merge
 359
 360         jmp     CheckLeftMerge2
 361
 362 ; The given block must be inserted between left and right, and right is not
 363 ; zero.
 364
 365 CheckRightMerge:
 366         lda     ptr2
 367         add     ptr1                    ; f + size
 368         tax
 369         lda     ptr2+1
 370         adc     ptr1+1
 371
 372         cpx     ptr3
 373         bne     NoRightMerge
 374         cmp     ptr3+1
 375         bne     NoRightMerge
 376
 377 ; Merge with the right block. Do f->size += right->size;
 378
 379         ldy     #freeblock::size
 380         lda     ptr1
 381         add     (ptr3),y
 382         sta     (ptr2),y
 383         iny                             ; Points to size+1
 384         lda     ptr1+1
 385         adc     (ptr3),y
 386         sta     (ptr2),y
 387
 388 ; Set f->next = right->next and remember f->next in ptr1 (we don't need the
 389 ; size stored there any longer)
 390
 391         iny                             ; Points to next
 392         lda     (ptr3),y                ; Low byte of right->next
 393         sta     (ptr2),y                ; Store to low byte of f->next
 394         sta     ptr1
 395         iny                             ; Points to next+1
 396         lda     (ptr3),y                ; High byte of right->next
 397         sta     (ptr2),y                ; Store to high byte of f->next
 398         sta     ptr1+1
 399         ora     ptr1
 400         beq     @L1                     ; Jump if f->next zero
 401
 402 ; f->next->prev = f;
 403
 404         iny                             ; Points to prev
 405         lda     ptr2                    ; Low byte of f
 406         sta     (ptr1),y                ; Low byte of f->next->prev
 407         iny                             ; Points to prev+1
 408         lda     ptr2+1                  ; High byte of f
 409         sta     (ptr1),y                ; High byte of f->next->prev
 410         jmp     CheckLeftMerge          ; Done
 411
 412 ; f->next is zero, this is now the last block
 413
 414 @L1:    lda     ptr2                    ; _heaplast = f;
 415         sta     __heaplast
 416         lda     ptr2+1
 417         sta     __heaplast+1
 418         jmp     CheckLeftMerge
 419
 420 ; No right merge, just set the link.
 421
 422 NoRightMerge:
 423         ldy     #freeblock::next        ; f->next = right;
 424         lda     ptr3
 425         sta     (ptr2),y
 426         iny                             ; Points to next+1
 427         lda     ptr3+1
 428         sta     (ptr2),y
 429
 430         iny                             ; Points to prev
 431         lda     ptr2                    ; right->prev = f;
 432         sta     (ptr3),y
 433         iny                             ; Points to prev+1
 434         lda     ptr2+1
 435         sta     (ptr3),y
 436
 437 ; Check if the left pointer is zero
 438
 439 CheckLeftMerge:
 440         lda     ptr4                    ; left == NULL?
 441         ora     ptr4+1
 442         bne     CheckLeftMerge2         ; Jump if there is a left block
 443
 444 ; We don't have a left block, so f is actually the new freelist start
 445
 446         ldy     #freeblock::prev
 447         sta     (ptr2),y                ; f->prev = 0;
 448         iny
 449         sta     (ptr2),y
 450
 451         lda     ptr2                    ; _heapfirst = f;
 452         sta     __heapfirst
 453         lda     ptr2+1
 454         sta     __heapfirst+1
 455
 456         rts                             ; Done
 457
 458 ; Check if the left block is adjacent to the following one
 459
 460 CheckLeftMerge2:
 461         ldy     #freeblock::size        ; Calculate left + left->size
 462         lda     (ptr4),y                ; Low byte of left->size
 463         add     ptr4
 464         tax
 465         iny                             ; Points to size+1
 466         lda     (ptr4),y                ; High byte of left->size
 467         adc     ptr4+1
 468
 469         cpx     ptr2
 470         bne     NoLeftMerge
 471         cmp     ptr2+1
 472         bne     NoLeftMerge             ; Jump if blocks not adjacent
 473
 474 ; Merge with the left block. Do left->size += f->size;
 475
 476         dey                             ; Points to size
 477         lda     (ptr4),y
 478         add     (ptr2),y
 479         sta     (ptr4),y
 480         iny                             ; Points to size+1
 481         lda     (ptr4),y
 482         adc     (ptr2),y
 483         sta     (ptr4),y
 484
 485 ; Set left->next = f->next and remember left->next in ptr1.
 486
 487         iny                             ; Points to next
 488         lda     (ptr2),y                ; Low byte of f->next
 489         sta     (ptr4),y
 490         sta     ptr1
 491         iny                             ; Points to next+1
 492         lda     (ptr2),y                ; High byte of f->next
 493         sta     (ptr4),y
 494         sta     ptr1+1
 495         ora     ptr1                    ; left->next == NULL?
 496         beq     @L1
 497
 498 ; Do left->next->prev = left
 499
 500         iny                             ; Points to prev
 501         lda     ptr4                    ; Low byte of left
 502         sta     (ptr1),y
 503         iny
 504         lda     ptr4+1                  ; High byte of left
 505         sta     (ptr1),y
 506         rts                             ; Done
 507
 508 ; This is now the last block, do _heaplast = left
 509
 510 @L1:    lda     ptr4
 511         sta     __heaplast
 512         lda     ptr4+1
 513         sta     __heaplast+1
 514         rts                             ; Done
 515
 516 ; No merge of the left block, just set the link. Y points to size+1 if
 517 ; we come here. Do left->next = f.
 518
 519 NoLeftMerge:
 520         iny                             ; Points to next
 521         lda     ptr2                    ; Low byte of left
 522         sta     (ptr4),y
 523         iny
 524         lda     ptr2+1                  ; High byte of left
 525         sta     (ptr4),y
 526
 527 ; Do f->prev = left
 528
 529         iny                             ; Points to prev
 530         lda     ptr4
 531         sta     (ptr2),y
 532         iny
 533         lda     ptr4+1
 534         sta     (ptr2),y
 535         rts                             ; Done
 536
 537
 538
 539
 540
 541
 542