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         .import         __hptr, __hfirst, __hlast, __hend
  64         .export         _free, hadd
  65
  66         .macpack        generic
  67
  68 ; Offsets into struct freeblock and other constant stuff
  69
  70 size            = 0
  71 next            = 2
  72 prev            = 4
  73 admin_space     = 2
  74 min_size        = 6
  75
  76
  77 ; Code
  78
  79 _free:  sta     ptr2
  80         stx     ptr2+1                  ; Save block
  81
  82 ; Is the argument NULL?
  83
  84         ora     ptr2+1                  ; Is the argument NULL?
  85         beq     @L9                     ; Jump if yes
  86
  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.
  90
  91         lda     ptr2
  92         sub     #admin_space
  93         sta     ptr2
  94         bcs     @L1
  95         dec     ptr2+1
  96 @L1:    ldy     #size+1
  97         lda     (ptr2),y                ; High byte of size
  98         sta     ptr1+1                  ; Save it
  99         dey
 100         lda     (ptr2),y
 101         sta     ptr1
 102
 103 ; Check if the block is on top of the heap
 104
 105         add     ptr2
 106         tay
 107         lda     ptr2+1
 108         adc     ptr1+1
 109         cpy     __hptr
 110         bne     hadd                    ; Add to free list
 111         cmp     __hptr+1
 112         bne     hadd
 113
 114 ; The pointer is located at the heap top. Lower the heap top pointer to
 115 ; release the block.
 116
 117 @L3:    lda     ptr2
 118         sta     __hptr
 119         lda     ptr2+1
 120         sta     __hptr+1
 121
 122 ; Check if the last block in the freelist is now at heap top. If so, remove
 123 ; this block from the freelist.
 124
 125         lda     __hlast
 126         sta     ptr1
 127         ora     __hlast+1
 128         beq     @L9                     ; Jump if free list empty
 129         lda     __hlast+1
 130         sta     ptr1+1                  ; Pointer to last block now in ptr1
 131
 132         ldy     #size
 133         lda     (ptr1),y                ; Low byte of block size
 134         add     ptr1
 135         tax
 136         iny                             ; High byte of block size
 137         lda     (ptr1),y
 138         adc     ptr1+1
 139
 140         cmp     __hptr+1
 141         bne     @L9                     ; Jump if last block not on top of heap
 142         cpx     __hptr
 143         bne     @L9                     ; Jump if last block not on top of heap
 144
 145 ; Remove the last block
 146
 147         lda     ptr1
 148         sta     __hptr
 149         lda     ptr1+1
 150         sta     __hptr+1
 151
 152 ; Correct the next pointer of the now last block
 153
 154         ldy     #prev+1                 ; Offset of ->prev field
 155         lda     (ptr1),y
 156         sta     ptr2+1                  ; Remember f->prev in ptr2
 157         sta     __hlast+1
 158         dey
 159         lda     (ptr1),y
 160         sta     ptr2                    ; Remember f->prev in ptr2
 161         sta     __hlast
 162         ora     __hlast+1               ; -> prev == 0?
 163         bne     @L8                     ; Jump if free list not empty
 164
 165 ; Free list is now empty (A = 0)
 166
 167         sta     __hfirst
 168         sta     __hfirst+1
 169
 170 ; Done
 171
 172 @L9:    rts
 173
 174 ; Block before is now last block. ptr2 points to f->prev.
 175
 176 @L8:    lda     #$00
 177         dey                             ; Points to high byte of ->next
 178         sta     (ptr2),y
 179         dey                             ; Low byte of f->prev->next
 180         sta     (ptr2),y
 181         rts                             ; Done
 182
 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
 185 ; shown here:
 186 ;
 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!
 192 ;  */
 193 ; {
 194 ;     struct freeblock* f;
 195 ;     struct freeblock* left;
 196 ;     struct freeblock* right;
 197 ;
 198 ;     if (size >= sizeof (struct freeblock)) {
 199 ;
 200 ;       /* Set the admin data */
 201 ;       f = (struct freeblock*) mem;
 202 ;       f->size = size;
 203 ;
 204 ;       /* Check if the freelist is empty */
 205 ;       if (_hfirst == 0) {
 206 ;
 207 ;           /* The freelist is empty until now, insert the block */
 208 ;           f->prev = 0;
 209 ;           f->next = 0;
 210 ;           _hfirst = f;
 211 ;           _hlast  = f;
 212 ;
 213 ;       } else {
 214 ;
 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.
 219 ;            */
 220 ;           left = 0;
 221 ;           right = _hfirst;
 222 ;           while (right && f > right) {
 223 ;               left = right;
 224 ;               right = right->next;
 225 ;           }
 226 ;
 227 ;
 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.
 231 ;            */
 232 ;           if (right) {
 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) {
 238 ;                               f->next->prev = f;
 239 ;                   } else {
 240 ;                       /* This is now the last block */
 241 ;                       _hlast = f;
 242 ;                   }
 243 ;               } else {
 244 ;                   /* No merge, just set the link */
 245 ;                   f->next = right;
 246 ;                   right->prev = f;
 247 ;               }
 248 ;           } else {
 249 ;               f->next = 0;
 250 ;               /* Special case: This is the new freelist end */
 251 ;               _hlast = f;
 252 ;           }
 253 ;           if (left) {
 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;
 260 ;                   } else {
 261 ;                       /* This is now the last block */
 262 ;                       _hlast = left;
 263 ;                   }
 264 ;               } else {
 265 ;                   /* No merge, just set the link */
 266 ;                   left->next = f;
 267 ;                   f->prev = left;
 268 ;               }
 269 ;           } else {
 270 ;               f->prev = 0;
 271 ;               /* Special case: This is the new freelist start */
 272 ;               _hfirst = f;
 273 ;           }
 274 ;       }
 275 ;     }
 276 ; }
 277 ;
 278
 279 ; Check if the free list is empty, storing _hfirst into ptr3 for later
 280
 281 hadd:   lda     __hfirst
 282         sta     ptr3
 283         lda     __hfirst+1
 284         sta     ptr3+1
 285         ora     ptr3
 286         bne     SearchFreeList
 287
 288 ; The free list is empty, so this is the first and only block. A contains
 289 ; zero if we come here.
 290
 291         ldy     #next-1
 292 @L2:    iny                     ; f->next = f->prev = 0;
 293         sta     (ptr2),y
 294         cpy     #prev+1         ; Done?
 295         bne     @L2
 296
 297         lda     ptr2
 298         ldx     ptr2+1
 299         sta     __hfirst
 300         stx     __hfirst+1      ; _hfirst = f;
 301         sta     __hlast
 302         stx     __hlast+1       ; _hlast = f;
 303
 304         rts                     ; Done
 305
 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.
 312
 313 SearchFreeList:
 314         lda     #0
 315         sta     ptr4
 316         sta     ptr4+1          ; left = 0;
 317         ldy     #next+1
 318         ldx     ptr3
 319
 320 @Loop:  lda     ptr3+1          ; High byte of right
 321         cmp     ptr2+1
 322         bne     @L1
 323         cpx     ptr2
 324         beq     @L2
 325 @L1:    bcs     CheckRightMerge
 326
 327 @L2:    stx     ptr4            ; left = right;
 328         sta     ptr4+1
 329
 330         dey                     ; Points to next
 331         lda     (ptr3),y        ; right = right->next;
 332         tax
 333         iny                     ; Points to next+1
 334         lda     (ptr3),y
 335         stx     ptr3
 336         sta     ptr3+1
 337         ora     ptr3
 338         bne     @Loop
 339
 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
 343
 344         sta     (ptr2),y        ; Clear high byte of f->next
 345         dey
 346         sta     (ptr2),y        ; Clear low byte of f->next
 347
 348         lda     ptr2            ; _hlast = f;
 349         sta     __hlast
 350         lda     ptr2+1
 351         sta     __hlast+1
 352
 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
 356
 357         jmp     CheckLeftMerge2
 358
 359 ; The given block must be inserted between left and right, and right is not
 360 ; zero.
 361
 362 CheckRightMerge:
 363         lda     ptr2
 364         add     ptr1            ; f + size
 365         tax
 366         lda     ptr2+1
 367         adc     ptr1+1
 368
 369         cpx     ptr3
 370         bne     NoRightMerge
 371         cmp     ptr3+1
 372         bne     NoRightMerge
 373
 374 ; Merge with the right block. Do f->size += right->size;
 375
 376         ldy     #size
 377         lda     ptr1
 378         add     (ptr3),y
 379         sta     (ptr2),y
 380         iny                     ; Points to size+1
 381         lda     ptr1+1
 382         adc     (ptr3),y
 383         sta     (ptr2),y
 384
 385 ; Set f->next = right->next and remember f->next in ptr1 (we don't need the
 386 ; size stored there any longer)
 387
 388         iny                     ; Points to next
 389         lda     (ptr3),y        ; Low byte of right->next
 390         sta     (ptr2),y        ; Store to low byte of f->next
 391         sta     ptr1
 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
 395         sta     ptr1+1
 396         ora     ptr1
 397         beq     @L1             ; Jump if f->next zero
 398
 399 ; f->next->prev = f;
 400
 401         iny                     ; Points to prev
 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
 408
 409 ; f->next is zero, this is now the last block
 410
 411 @L1:    lda     ptr2            ; _hlast = f;
 412         sta     __hlast
 413         lda     ptr2+1
 414         sta     __hlast+1
 415         jmp     CheckLeftMerge
 416
 417 ; No right merge, just set the link.
 418
 419 NoRightMerge:
 420         ldy     #next           ; f->next = right;
 421         lda     ptr3
 422         sta     (ptr2),y
 423         iny                     ; Points to next+1
 424         lda     ptr3+1
 425         sta     (ptr2),y
 426
 427         iny                     ; Points to prev
 428         lda     ptr2            ; right->prev = f;
 429         sta     (ptr3),y
 430         iny                     ; Points to prev+1
 431         lda     ptr2+1
 432         sta     (ptr3),y
 433
 434 ; Check if the left pointer is zero
 435
 436 CheckLeftMerge:
 437         lda     ptr4            ; left == NULL?
 438         ora     ptr4+1
 439         bne     CheckLeftMerge2 ; Jump if there is a left block
 440
 441 ; We don't have a left block, so f is actually the new freelist start
 442
 443         ldy     #prev
 444         sta     (ptr2),y        ; f->prev = 0;
 445         iny
 446         sta     (ptr2),y
 447
 448         lda     ptr2            ; _hfirst = f;
 449         sta     __hfirst
 450         lda     ptr2+1
 451         sta     __hfirst+1
 452
 453         rts                     ; Done
 454
 455 ; Check if the left block is adjacent to the following one
 456
 457 CheckLeftMerge2:
 458         ldy     #size           ; Calculate left + left->size
 459         lda     (ptr4),y        ; Low byte of left->size
 460         add     ptr4
 461         tax
 462         iny                     ; Points to size+1
 463         lda     (ptr4),y        ; High byte of left->size
 464         adc     ptr4+1
 465
 466         cpx     ptr2
 467         bne     NoLeftMerge
 468         cmp     ptr2+1
 469         bne     NoLeftMerge     ; Jump if blocks not adjacent
 470
 471 ; Merge with the left block. Do left->size += f->size;
 472
 473         dey                     ; Points to size
 474         lda     (ptr4),y
 475         add     (ptr2),y
 476         sta     (ptr4),y
 477         iny                     ; Points to size+1
 478         lda     (ptr4),y
 479         adc     (ptr2),y
 480         sta     (ptr4),y
 481
 482 ; Set left->next = f->next and remember left->next in ptr1.
 483
 484         iny                     ; Points to next
 485         lda     (ptr2),y        ; Low byte of f->next
 486         sta     (ptr4),y
 487         sta     ptr1
 488         iny                     ; Points to next+1
 489         lda     (ptr2),y        ; High byte of f->next
 490         sta     (ptr4),y
 491         sta     ptr1+1
 492         ora     ptr1            ; left->next == NULL?
 493         beq     @L1
 494
 495 ; Do left->next->prev = left
 496
 497         iny                     ; Points to prev
 498         lda     ptr4            ; Low byte of left
 499         sta     (ptr1),y
 500         iny
 501         lda     ptr4+1          ; High byte of left
 502         sta     (ptr1),y
 503         rts                     ; Done
 504
 505 ; This is now the last block, do _hlast = left
 506
 507 @L1:    lda     ptr4
 508         sta     __hlast
 509         lda     ptr4+1
 510         sta     __hlast+1
 511         rts                     ; Done
 512
 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.
 515
 516 NoLeftMerge:
 517         iny                     ; Points to next
 518         lda     ptr2            ; Low byte of left
 519         sta     (ptr4),y
 520         iny
 521         lda     ptr2+1          ; High byte of left
 522         sta     (ptr4),y
 523
 524 ; Do f->prev = left
 525
 526         iny                     ; Points to prev
 527         lda     ptr4
 528         sta     (ptr2),y
 529         iny
 530         lda     ptr4+1
 531         sta     (ptr2),y
 532         rts                     ; Done
 533
 534
 535
 536
 537