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

   1 ;
   2 ; Ullrich von Bassewitz, 17.7.2000
   3 ;
   4 ; Allocate a block from the heap.
   5 ;
   6 ; void* __fastcall__ malloc (size_t size);
   7 ;
   8 ;
   9 ; C implementation was:
  10 ;
  11 ; void* malloc (size_t size)
  12 ; /* Allocate memory from the given heap. The function returns a pointer to the
  13 ;  * allocated memory block or a NULL pointer if not enough memory is available.
  14 ;  * Allocating a zero size block is not allowed.
  15 ;  */
  16 ; {
  17 ;     struct freeblock* f;
  18 ;     unsigned* p;
  19 ;
  20 ;
  21 ;     /* Check for a size of zero, then add the administration space and round
  22 ;      * up the size if needed.
  23 ;      */
  24 ;     if (size == 0) {
  25 ;       return 0;
  26 ;     }
  27 ;     size += HEAP_ADMIN_SPACE;
  28 ;     if (size < sizeof (struct freeblock)) {
  29 ;         size = sizeof (struct freeblock);
  30 ;     }
  31 ;
  32 ;     /* Search the freelist for a block that is big enough */
  33 ;     f = _hfirst;
  34 ;     while (f && f->size < size) {
  35 ;         f = f->next;
  36 ;     }
  37 ;
  38 ;     /* Did we find one? */
  39 ;     if (f) {
  40 ;
  41 ;         /* We found a block big enough. If the block can hold just the
  42 ;          * requested size, use the block in full. Beware: When slicing blocks,
  43 ;          * there must be space enough to create a new one! If this is not the
  44 ;          * case, then use the complete block.
  45 ;          */
  46 ;         if (f->size - size < sizeof (struct freeblock)) {
  47 ;
  48 ;             /* Use the actual size */
  49 ;             size = f->size;
  50 ;
  51 ;             /* Remove the block from the free list */
  52 ;             if (f->prev) {
  53 ;                 /* We have a previous block */
  54 ;                 f->prev->next = f->next;
  55 ;             } else {
  56 ;                 /* This is the first block, correct the freelist pointer */
  57 ;                 _hfirst = f->next;
  58 ;             }
  59 ;             if (f->next) {
  60 ;                 /* We have a next block */
  61 ;                 f->next->prev = f->prev;
  62 ;             } else {
  63 ;                 /* This is the last block, correct the freelist pointer */
  64 ;                 _hlast = f->prev;
  65 ;             }
  66 ;
  67 ;         } else {
  68 ;
  69 ;             /* We must slice the block found. Cut off space from the upper
  70 ;            * end, so we can leave the actual free block chain intact.
  71 ;            */
  72 ;
  73 ;           /* Decrement the size of the block */
  74 ;           f->size -= size;
  75 ;
  76 ;           /* Set f to the now unused space above the current block */
  77 ;           f = (struct freeblock*) (((unsigned) f) + f->size);
  78 ;
  79 ;         }
  80 ;
  81 ;         /* Setup the pointer for the block */
  82 ;         p = (unsigned*) f;
  83 ;
  84 ;     } else {
  85 ;
  86 ;         /* We did not find a block big enough. Try to use new space from the
  87 ;          * heap top.
  88 ;          */
  89 ;       if (((unsigned) _hend) - ((unsigned) _hptr) < size) {
  90 ;             /* Out of heap space */
  91 ;             return 0;
  92 ;       }
  93 ;
  94 ;
  95 ;       /* There is enough space left, take it from the heap top */
  96 ;       p = _hptr;
  97 ;               _hptr = (unsigned*) (((unsigned) _hptr) + size);
  98 ;
  99 ;     }
 100 ;
 101 ;     /* New block is now in p. Fill in the size and return the user pointer */
 102 ;     *p++ = size;
 103 ;     return p;
 104 ; }
 105 ;
 106
 107
 108         .importzp       ptr1, ptr2, ptr3
 109         .export         _malloc
 110
 111         .include        "_heap.inc"
 112
 113         .macpack        generic
 114
 115 ;-----------------------------------------------------------------------------
 116 ; Code
 117
 118 _malloc:
 119         sta     ptr1                    ; Store size in ptr1
 120         stx     ptr1+1
 121
 122 ; Check for a size of zero, if so, return NULL
 123
 124         ora     ptr1+1
 125         beq     Done                    ; a/x already contains zero
 126
 127 ; Add the administration space and round up the size if needed
 128
 129         lda     ptr1
 130         add     #HEAP_ADMIN_SPACE
 131         sta     ptr1
 132         bcc     @L1
 133         inc     ptr1+1
 134 @L1:    ldx     ptr1+1
 135         bne     @L2
 136         cmp     #HEAP_MIN_BLOCKSIZE+1
 137         bcs     @L2
 138         lda     #HEAP_MIN_BLOCKSIZE
 139         sta     ptr1                    ; High byte is already zero
 140
 141 ; Load a pointer to the freelist into ptr2
 142
 143 @L2:    lda     __heapfirst
 144         sta     ptr2
 145         lda     __heapfirst+1
 146         sta     ptr2+1
 147
 148 ; Search the freelist for a block that is big enough. We will calculate
 149 ; (f->size - size) here and keep it, since we need the value later.
 150
 151         jmp     @L4
 152
 153 @L3:    ldy     #freeblock::size
 154         lda     (ptr2),y
 155         sub     ptr1
 156         tax                             ; Remember low byte for later
 157         iny                             ; Y points to freeblock::size+1
 158         lda     (ptr2),y
 159         sbc     ptr1+1
 160         bcs     BlockFound              ; Beware: Contents of a/x/y are known!
 161
 162 ; Next block in list
 163
 164         iny                             ; Points to freeblock::next
 165         lda     (ptr2),y
 166         tax
 167         iny                             ; Points to freeblock::next+1
 168         lda     (ptr2),y
 169         stx     ptr2
 170         sta     ptr2+1
 171 @L4:    ora     ptr2
 172         bne     @L3
 173
 174 ; We did not find a block big enough. Try to use new space from the heap top.
 175
 176         lda     __heapptr
 177         add     ptr1                    ; _heapptr + size
 178         tay
 179         lda     __heapptr+1
 180         adc     ptr1+1
 181         bcs     OutOfHeapSpace          ; On overflow, we're surely out of space
 182
 183         cmp     __heapend+1
 184         bne     @L5
 185         cpy     __heapend
 186 @L5:    bcc     TakeFromTop
 187         beq     TakeFromTop
 188
 189 ; Out of heap space
 190
 191 OutOfHeapSpace:
 192         lda     #0
 193         tax
 194 Done:   rts
 195
 196 ; There is enough space left, take it from the heap top
 197
 198 TakeFromTop:
 199         ldx     __heapptr               ; p = _heapptr;
 200         stx     ptr2
 201         ldx     __heapptr+1
 202         stx     ptr2+1
 203
 204         sty     __heapptr               ; _heapptr += size;
 205         sta     __heapptr+1
 206         jmp     FillSizeAndRet          ; Done
 207
 208 ; We found a block big enough. If the block can hold just the
 209 ; requested size, use the block in full. Beware: When slicing blocks,
 210 ; there must be space enough to create a new one! If this is not the
 211 ; case, then use the complete block.
 212 ; On input, x/a do contain the remaining size of the block. The zero
 213 ; flag is set if the high byte of this remaining size is zero.
 214
 215 BlockFound:
 216         bne     SliceBlock              ; Block is large enough to slice
 217         cpx     #HEAP_MIN_BLOCKSIZE     ; Check low byte
 218         bcs     SliceBlock              ; Jump if block is large enough to slice
 219
 220 ; The block is too small to slice it. Use the block in full. The block
 221 ; does already contain the correct size word, all we have to do is to
 222 ; remove it from the free list.
 223
 224         ldy     #freeblock::prev+1      ; Load f->prev
 225         lda     (ptr2),y
 226         sta     ptr3+1
 227         dey
 228         lda     (ptr2),y
 229         sta     ptr3
 230         dey                             ; Points to freeblock::next+1
 231         ora     ptr3+1
 232         beq     @L1                     ; Jump if f->prev zero
 233
 234 ; We have a previous block, ptr3 contains its address.
 235 ; Do f->prev->next = f->next
 236
 237         lda     (ptr2),y                ; Load high byte of f->next
 238         sta     (ptr3),y                ; Store high byte of f->prev->next
 239         dey                             ; Points to next
 240         lda     (ptr2),y                ; Load low byte of f->next
 241         sta     (ptr3),y                ; Store low byte of f->prev->next
 242         jmp     @L2
 243
 244 ; This is the first block, correct the freelist pointer
 245 ; Do _hfirst = f->next
 246
 247 @L1:    lda     (ptr2),y                ; Load high byte of f->next
 248         sta     __heapfirst+1
 249         dey                             ; Points to next
 250         lda     (ptr2),y                ; Load low byte of f->next
 251         sta     __heapfirst
 252
 253 ; Check f->next. Y points always to next if we come here
 254
 255 @L2:    lda     (ptr2),y                ; Load low byte of f->next
 256         sta     ptr3
 257         iny                             ; Points to next+1
 258         lda     (ptr2),y                ; Load high byte of f->next
 259         sta     ptr3+1
 260         iny                             ; Points to prev
 261         ora     ptr3
 262         beq     @L3                     ; Jump if f->next zero
 263
 264 ; We have a next block, ptr3 contains its address.
 265 ; Do f->next->prev = f->prev
 266
 267         lda     (ptr2),y                ; Load low byte of f->prev
 268         sta     (ptr3),y                ; Store low byte of f->next->prev
 269         iny                             ; Points to prev+1
 270         lda     (ptr2),y                ; Load high byte of f->prev
 271         sta     (ptr3),y                ; Store high byte of f->prev->next
 272         jmp     RetUserPtr              ; Done
 273
 274 ; This is the last block, correct the freelist pointer.
 275 ; Do _hlast = f->prev
 276
 277 @L3:    lda     (ptr2),y                ; Load low byte of f->prev
 278         sta     __heaplast
 279         iny                             ; Points to prev+1
 280         lda     (ptr2),y                ; Load high byte of f->prev
 281         sta     __heaplast+1
 282         jmp     RetUserPtr              ; Done
 283
 284 ; We must slice the block found. Cut off space from the upper end, so we
 285 ; can leave the actual free block chain intact.
 286
 287 SliceBlock:
 288
 289 ; Decrement the size of the block. Y points to size+1.
 290
 291         dey                             ; Points to size
 292         lda     (ptr2),y                ; Low byte of f->size
 293         sub     ptr1
 294         sta     (ptr2),y
 295         tax                             ; Save low byte of f->size in X
 296         iny                             ; Points to size+1
 297         lda     (ptr2),y                ; High byte of f->size
 298         sbc     ptr1+1
 299         sta     (ptr2),y
 300
 301 ; Set f to the space above the current block, which is the new block returned
 302 ; to the caller.
 303
 304         txa                             ; Get low byte of f->size
 305         add     ptr2
 306         tax
 307         lda     (ptr2),y                ; Get high byte of f->size
 308         adc     ptr2+1
 309         stx     ptr2
 310         sta     ptr2+1
 311
 312 ; Fill the size and start address into the admin space of the block
 313 ; (struct usedblock) and return the user pointer
 314
 315 FillSizeAndRet:
 316         ldy     #usedblock::size        ; p->size = size;
 317         lda     ptr1                    ; Low byte of block size
 318         sta     (ptr2),y
 319         iny                             ; Points to freeblock::size+1
 320         lda     ptr1+1
 321         sta     (ptr2),y
 322
 323 RetUserPtr:
 324         ldy     #usedblock::start       ; p->start = p
 325         lda     ptr2
 326         sta     (ptr2),y
 327         iny
 328         lda     ptr2+1
 329         sta     (ptr2),y
 330
 331 ; Return the user pointer, which points behind the struct usedblock
 332
 333         lda     ptr2                    ; return ++p;
 334         ldx     ptr2+1
 335         add     #HEAP_ADMIN_SPACE
 336         bcc     @L9
 337         inx
 338 @L9:    rts
 339