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         .import         __hptr, __hfirst, __hlast, __hend
 110         .export         _malloc
 111
 112         .macpack        generic
 113
 114 ; Offsets into struct freeblock and other constant stuff
 115
 116 size            = 0
 117 next            = 2
 118 prev            = 4
 119 admin_space     = 2
 120 min_size        = 6
 121
 122
 123 ; Code
 124
 125 _malloc:
 126         sta     ptr1            ; Store size in ptr1
 127         stx     ptr1+1
 128
 129 ; Check for a size of zero, if so, return NULL
 130
 131         ora     ptr1+1
 132         beq     Done            ; a/x already contains zero
 133
 134 ; Add the administration space and round up the size if needed
 135
 136         lda     ptr1
 137         add     #admin_space
 138         sta     ptr1
 139         bcc     @L1
 140         inc     ptr1+1
 141 @L1:    ldx     ptr1+1
 142         bne     @L2
 143         cmp     #min_size+1
 144         bcs     @L2
 145         lda     #min_size
 146         sta     ptr1            ; High byte is already zero
 147
 148 ; Load a pointer to the freelist into ptr2
 149
 150 @L2:    lda     __hfirst
 151         sta     ptr2
 152         lda     __hfirst+1
 153         sta     ptr2+1
 154
 155 ; Search the freelist for a block that is big enough. We will calculate
 156 ; (f->size - size) here and keep it, since we need the value later.
 157
 158         jmp     @L4
 159
 160 @L3:    ldy     #size
 161         lda     (ptr2),y
 162         sub     ptr1
 163         tax                     ; Remember low byte for later
 164         iny                     ; Y points to size+1
 165         lda     (ptr2),y
 166         sbc     ptr1+1
 167         bcs     BlockFound      ; Beware: Contents of a/x/y are known!
 168
 169 ; Next block in list
 170
 171         iny                     ; Points to next
 172         lda     (ptr2),y
 173         tax
 174         iny                     ; Points to next+1
 175         lda     (ptr2),y
 176         stx     ptr2
 177         sta     ptr2+1
 178 @L4:    ora     ptr2
 179         bne     @L3
 180
 181 ; We did not find a block big enough. Try to use new space from the heap top.
 182
 183         lda     __hptr
 184         add     ptr1            ; _hptr + size
 185         tay
 186         lda     __hptr+1
 187         adc     ptr1+1
 188         bcs     OutOfHeapSpace  ; On overflow, we're surely out of space
 189
 190         cmp     __hend+1
 191         bne     @L5
 192         cpy     __hend
 193 @L5:    bcc     TakeFromTop
 194         beq     TakeFromTop
 195
 196 ; Out of heap space
 197
 198 OutOfHeapSpace:
 199         lda     #0
 200         tax
 201 Done:   rts
 202
 203 ; There is enough space left, take it from the heap top
 204
 205 TakeFromTop:
 206         ldx     __hptr          ; p = hptr;
 207         stx     ptr2
 208         ldx     __hptr+1
 209         stx     ptr2+1
 210
 211         sty     __hptr          ; hptr += size;
 212         sta     __hptr+1
 213         jmp     FillSizeAndRet  ; Done
 214
 215 ; We found a block big enough. If the block can hold just the
 216 ; requested size, use the block in full. Beware: When slicing blocks,
 217 ; there must be space enough to create a new one! If this is not the
 218 ; case, then use the complete block.
 219 ; On input, x/a do contain the remaining size of the block. The zero
 220 ; flag is set if the high byte of this remaining size is zero.
 221
 222 BlockFound:
 223         bne     SliceBlock      ; Block is large enough to slice
 224         cpx     #min_size+1     ; Check low byte
 225         bcs     SliceBlock      ; Jump if block is large enough to slice
 226
 227 ; The block is too small to slice it. Use the block in full. The block
 228 ; does already contain the correct size word, all we have to do is to
 229 ; remove it from the free list.
 230
 231         ldy     #prev+1         ; Load f->prev
 232         lda     (ptr2),y
 233         sta     ptr3+1
 234         dey
 235         lda     (ptr2),y
 236         sta     ptr3
 237         dey                     ; Points to next+1
 238         ora     ptr3+1
 239         beq     @L1             ; Jump if f->prev zero
 240
 241 ; We have a previous block, ptr3 contains its address.
 242 ; Do f->prev->next = f->next
 243
 244         lda     (ptr2),y        ; Load high byte of f->next
 245         sta     (ptr3),y        ; Store high byte of f->prev->next
 246         dey                     ; Points to next
 247         lda     (ptr2),y        ; Load low byte of f->next
 248         sta     (ptr3),y        ; Store low byte of f->prev->next
 249         jmp     @L2
 250
 251 ; This is the first block, correct the freelist pointer
 252 ; Do _hfirst = f->next
 253
 254 @L1:    lda     (ptr2),y        ; Load high byte of f->next
 255         sta     __hfirst+1
 256         dey                     ; Points to next
 257         lda     (ptr2),y        ; Load low byte of f->next
 258         sta     __hfirst
 259
 260 ; Check f->next. Y points always to next if we come here
 261
 262 @L2:    lda     (ptr2),y        ; Load low byte of f->next
 263         sta     ptr3
 264         iny                     ; Points to next+1
 265         lda     (ptr2),y        ; Load high byte of f->next
 266         sta     ptr3+1
 267         iny                     ; Points to prev
 268         ora     ptr3
 269         beq     @L3             ; Jump if f->next zero
 270
 271 ; We have a next block, ptr3 contains its address.
 272 ; Do f->next->prev = f->prev
 273
 274         lda     (ptr2),y        ; Load low byte of f->prev
 275         sta     (ptr3),y        ; Store low byte of f->next->prev
 276         iny                     ; Points to prev+1
 277         lda     (ptr2),y        ; Load high byte of f->prev
 278         sta     (ptr3),y        ; Store high byte of f->prev->next
 279         jmp     RetUserPtr      ; Done
 280
 281 ; This is the last block, correct the freelist pointer.
 282 ; Do _hlast = f->prev
 283
 284 @L3:    lda     (ptr2),y        ; Load low byte of f->prev
 285         sta     __hlast
 286         iny                     ; Points to prev+1
 287         lda     (ptr2),y        ; Load high byte of f->prev
 288         sta     __hlast+1
 289         jmp     RetUserPtr      ; Done
 290
 291 ; We must slice the block found. Cut off space from the upper end, so we
 292 ; can leave the actual free block chain intact.
 293
 294 SliceBlock:
 295
 296 ; Decrement the size of the block. Y points to size+1.
 297
 298         dey                     ; Points to size
 299         lda     (ptr2),y        ; Low byte of f->size
 300         sub     ptr1
 301         sta     (ptr2),y
 302         tax                     ; Save low byte of f->size in X
 303         iny                     ; Points to size+1
 304         lda     (ptr2),y        ; High byte of f->size
 305         sbc     ptr1+1
 306         sta     (ptr2),y
 307
 308 ; Set f to the space above the current block, which is the new block returned
 309 ; to the caller.
 310
 311         txa                     ; Get low byte of f->size
 312         add     ptr2
 313         tax
 314         lda     (ptr2),y        ; Get high byte of f->size
 315         adc     ptr2+1
 316         stx     ptr2
 317         sta     ptr2+1
 318
 319 ; Fill the size into the admin space of the block and return the user pointer
 320
 321 FillSizeAndRet:
 322         ldy     #size           ; *p = size;
 323         lda     ptr1            ; Low byte of block size
 324         sta     (ptr2),y
 325         iny                     ; Points to size+1
 326         lda     ptr1+1
 327         sta     (ptr2),y
 328
 329 RetUserPtr:
 330         lda     ptr2            ; return ++p;
 331         ldx     ptr2+1
 332         add     #admin_space
 333         bcc     @L9
 334         inx
 335 @L9:    rts
 336