Implementing a memory manager with resizable blocks

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Implementing a memory manager with resizable blocks

Post by Twilighte »

The problem
One of the main problems with a dynamic editor like a Music Tracker is that either...

memory areas for the music are fixed, making it much easier to manage all music area or changing the size of these objects but the disadvantage that the memory and file size remains the same (Thats why Sonix files are always the same size, regardless of the size of the song).

or...

memory areas for the music are kept tightly bound to one another. the program must manage inserting changes back into the music memory. This requires a super precise insertion and memory move routine that can expand or contract the memory window and the memory above(i did this for UGE, which was used for the Times of Lore Map).
The disadvantage is speed of operation. the bigger the music area the longer one has to wait for the process to finish.

A potential solution
But i had a rather interesting idea. I wonder if i can use a link list to manage a total memory allocation for music. A memory management system would decide where to place changed (example)patterns (if the space they were extracted from is equal or larger they return their or if smaller they go elsewhere) and the link list would be updated appropriately.

Some form of Defrag process would need to either be actioned at save point or through an option if more memory is required.

The music would always contain a header section that would point to the starting nodes and some song info.

...

Example of implementation
So i now have some routines and have developed a format for the nodes in the link list.
A Node is an entry in the link list.
Each Node uses 8 bytes and the link list only moves up in memory.

The gap between the nodes is called the Aparture and this is where the Item data goes and a possible fragmented area.

Code: Select all

Code: 
Link List Node structure 
00-01 offset to next Node in link list 
02-02 Type of link listed item. 
     B0-6 
        0 Spare Aparture 
        1 Pattern 
        2 Position List 
        3 Effect Sequence 
     B6 Fragmented Flag (Set when the aparture is larger than the item data) 
     B7 End of Link List 
03-03 Link listed Item ID (For example Pattern Number or Effect Number) 
      0 for Spare aparture 
04-05 Item Size 
06-07 Fragmentation Size 
08-   Item Data 
At the start, their is just one node and it is a Spare Aparture Type.

When I want to store a new pattern, the program will scan the link list for a spare aparture equal or more in size to the pattern i want to insert.
If it reaches the end of the link list without finding one then it will allocate a new node to the last node found.
This process is very simple. the Last node in the link list is always spare.
So i update this node and aparture with the item data and create a new spare node above. I then link the current node to it through the "offset to next Node in link list" word in 00-01.
  • When i take an existing pattern and after editing it, it is found to be of the same size as the aparture it resided in, i simply write it back to the aparture.
  • When i take an existing pattern and after editing it, it is found to be smaller than the aparture it resided in, i write it back to the aparture, flag the Node as Fragmented, update the item and Fragmentation size.
  • When i take an existing pattern and after editing it, it is found to be larger than the aparture it resided in, i scan all nodes in the link list for a spare aparture that is equal to or larger than the pattern and write it their.
    I also update the Node with the new Item Data details (including Fragmentation details).
    If it reaches the end of the link list without finding one then it will allocate a new node to the last node found(Same as new pattern process).
  • When i try to add a new node but find that it has reached the end of music memory, i must defragment the complete music memory area.
This is where i am now.

The first routine locates an Item and Number in the link list.
The g location is for the first node in the list.

Code: Select all

Code: 
;A == Item Type 
;X == Item ID 
locate_item 
        ldy gMusicFirstllNode_lo 
        sty LinkListNode 
        ldy gMusicFirstllNode_hi 
        sty LinkListNode+1 
locate_next_item 
        sta ItemType 
        ldy #02 
loop_01 
        ;Fetch Type 
        lda (LinkListNode),y 

        ;Branch if end of Link List 
        bmi ItemNotFound 

        ;Exclude Fragmented flag 
        and #63 

        ;Compare to locating type 
        cmp ItemType 

        ;Branch if not it 
        bne NotFound 

        iny 

        ;Fetch Locating ID 
        txa 

        ;Compare with ll id 
        cmp (LinkListNode),y 

        ;Branch if it 
        beq ItemFound 

NotFound 
        ldy #00 
        lda (LinkListNode),y 
        sta temp_01 
        iny 
        lda (LinkListNode),y 
        sta LinkListNode+1 
        lda temp_01 
        sta LinkListNode 
        iny 
        jmp loop_01 
ItemFound 
        clc 
        rts 
ItemNotFound 
        sec 
        rts 
The second routine locates an aparture in the link list that is equal to or larger than the item data length passed and sets or clears carry as the result of the operation.

Code: Select all

locate_aparture 
        lda #00 
        tax 
        jsr locate_item 
        bcs NotFound 

loop1   ldy #05 
        ; 
        lda (LinkListNode),y 
        cmp ItemDataLength+1 
        beq CompareLow 
        bcc NotEnough 
Enough  clc 
        rts 
CompareLow 
        dey 
        lda (LinkListNode),y 
        cmp ItemDataLength 
        bcs Enough 
NotEnough 
        ;Continue scan 
        lda #00 
        tax 
        jsr Locate_next_item 
        bcc loop1 
NotFound 
        rts 
The third and final routine (for now) is not complete (mostly pseudo code) but demonstrates the process of inserting a new or existing pattern into music memory.

Code: Select all

;ItemDataLength+0/+1 
;Locate aparture in link list 
; if not found 
;   Attempt add new node with item data length 
;   if not enough memory 
;     defrag 
;     Attempt add new node with item data length 
;     if not enough memory 
;       NOT ENOUGH MEMORY 
;     else 
;       write item data to new node 
;     end if 
;   else 
;     write item data to new node 
;   end if 
; else 
;   write item data to found node 
; end if 
        jsr locate_aparture 
        bcc skip1 
        jsr TryNewNode 
        bcc skip1 
        jsr Defragment 
        jsr TryNewNode 
        bcs NoMemoryLeft 
skip1   jmp StoreItemData 



locate_aparture 
        lda #00 
        tax 
        jsr locate_item 
        bcs NotFound 

loop1   ldy #05 
        ; 
        lda (LinkListNode),y 
        cmp ItemDataLength+1 
        beq CompareLow 
        bcc NotEnough 
Enough  clc 
        rts 
CompareLow 
        dey 
        lda (LinkListNode),y 
        cmp ItemDataLength 
        bcs Enough 
NotEnough 
        ;Continue scan 
        lda #00 
        tax 
        jsr Locate_next_item 
        bcc loop1 
NotFound 
        rts