OSDev.org

Code: Select all

SPACE1 = malloc (1024);

Code: Select all

SPACE2 = malloc(256);

Code: Select all

free(SPACE1);

Code: Select all

SPACE3 = malloc(512);

Code: Select all

SPACE3 = realloc(SPACE3, 1256);

Code: Select all

struct _alloc_t {
    unsigned long address;
    unsigned long size;        // bytes
    BOOL used;
    struct _alloc_t *next;             // next struct
};


typedef struct _alloc_t alloc_t;
#define BIALLOC sizeof(alloc_t)

alloc_t lAlloc;
alloc_t *alloc_curr = &lAlloc;
alloc_t *alloc_top = &lAlloc;

int heap = 0;

void AddMem(size_t bytes);

void *malloc(size_t bytes) {
    unsigned long tempsize, retaddr;
    alloc_curr = alloc_top;
    
    do { // loop as long as there is a next entry
        if (bytes + BIALLOC < alloc_curr->size && alloc_curr->used == FALSE) {  // is this free and enough space?
            tempsize = alloc_curr->size;                      // save the size of the free block in a temporary variable
            
            alloc_curr->next = (alloc_t *) alloc_curr->address;      // point next to the next list
            alloc_curr->address = retaddr = alloc_curr->address + BIALLOC;   // before it there comes a new entry for the linked list
            alloc_curr->size = bytes;                            // put the size in size
            alloc_curr->used = TRUE;                           // raise the used flag
            
            alloc_curr = alloc_curr->next;                 // create free space block
            alloc_curr->address = retaddr + bytes + BIALLOC;                    // and put the space for the linked list before it again..
            alloc_curr->size = tempsize - bytes - BIALLOC;
            alloc_curr->used = FALSE;
            
            heap -= bytes + BIALLOC;                      // substract the used bytes from the heap
            return (void *) retaddr;                          // return the address
        }
        
        alloc_curr = alloc_curr->next;
    } while (alloc_curr != 0);
    
    // if we didn't succeed, ask for extra money and try it again
    AddMem(bytes);
    return malloc(bytes);
}    

void AddMem(size_t bytes) {
    int realaddr, pageaddr;
    
    pageaddr = palloc(bytes);                        // get free space and put it in pageaddr
    realaddr = page_to_byte(pageaddr);               // convert the page address to bytes
        
    alloc_curr->address = realaddr + BIALLOC;        // put the address of the new free block in address
    alloc_curr->size = bytes_to_pages(bytes);        // put the size of it in size
    alloc_curr->used = FALSE;                        // it is free space, so make used FALSE
        
    heap += alloc_curr->size;                        // add the new space to heap
}    


void free(void *address) {
    alloc_curr = alloc_top;
    unsigned long addr_deep;
    alloc_t *alloc_curr2;
    BOOL addr_deep_found = FALSE;
    
    do { // loop through the linked list
        if (alloc_curr->address == (unsigned long) address) { // the address is found
            addr_deep = alloc_curr->address + alloc_curr->size + BIALLOC; // what should the next address be (for joining them together)
            alloc_curr2 = alloc_top; // alloc_curr2 points to alloc_top
            addr_deep_found = FALSE; // make sure the addr_deep_found is FALSE
            /* try to find an address which begins at the end of the last one */
            do {    // loop through the linked list again
                if (alloc_curr2->address == addr_deep && alloc_curr2->used == FALSE) { // does the next address come exactly after the one to free and has used = FALSE?
                    bAddr_deep2 = TRUE; // set the flag TRUE
                    break; // leave the loop
                }
                    
                alloc_curr2 = alloc_curr2->next;
            } while (alloc_curr2 != 0);
            
            if (bAddr_deep2 == TRUE) { // next piece of memory comes exactly after the one to free
                alloc_curr->next = alloc_curr->next->next; // skip one of them, the second will get lost anyway
                alloc_curr->used = FALSE; // set the used flag FALSE
                // :o that's all! Was just thinking about what next.. lol..
            } else {
                alloc_curr->used = FALSE; // just set the flag used on false...
            }        
        }
        
        alloc_curr = alloc_curr->next;
    } while (alloc_curr != 0);
}