malloc和free的实现

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

void free(void *firstbyte)
{
    struct mem_control_block *mcb;
    /* Backup from the given pointer to find the
    * mem_control_block
    */
    mcb = firstbyte - sizeof(struct mem_control_block);
    /* Mark the block as being available */
    mcb->is_available = 1;
    /* That's It! We're done. */
    return;
}

void *malloc(long numbytes)
{
    /* Holds where we are looking in memory */　　
    void *current_location;
    　　/* This is the same as current_location, but cast to a* memory_control_block*/　　
    struct mem_control_block *current_location_mcb;
    　　/* This is the memory location we will return. It will* be set to 0 until we find something suitable*/　　
    void *memory_location;
    　　/* Initialize if we haven't already done so */　　
    if(!has_initialized)
    {
        malloc_init();
    }
    /* The memory we search for has to include the memory* control block,
    but the users of malloc don't need* to know this,
    so we'll just add it in for them.*/　　
    numbytes = numbytes + sizeof(struct mem_control_block);

    /* Set memory_location to 0 until we find a suitable* location*/　　
    memory_location = 0;

    /* Begin searching at the start of managed memory */　　
    current_location = managed_memory_start;

    /* Keep going until we have searched all allocated space */　　
    while(current_location != last_valid_address)    　　
    {
        /* current_location and current_location_mcb point* to the same address.
        However, current_location_mcb* is of the correct type, so we can use it as a struct.
        * current_location is a void pointer so we can use it* to calculate addresses.*/    　　
        current_location_mcb = (struct mem_control_block *)current_location;

        if(current_location_mcb->is_available)        　　
        {
            if(current_location_mcb->size >= numbytes)            　　
            {
                /* Woohoo! We've found an open,* appropriately-size location.*/
                /* It is no longer available */
                current_location_mcb->is_available = 0;

                /* We own it */
                memory_location = current_location;

                /* Leave the loop */
                break;
                　　
            }        　　
        }    　　
        /* If we made it here, it's because the Current memory* block not suitable; move to the next one*/    　　
        current_location = current_location + current_location_mcb->size;
    }　　

    /* If we still don't have a valid location, we'll* have to ask the operating system for more memory*/　　
    if(! memory_location)    　　
    {
        /* Move the program break numbytes further */
        sbrk(numbytes);
        /* The new memory will be where the last valid* address left off*/    　　
        memory_location = last_valid_address;
        /* We'll move the last valid address forward* numbytes*/
        last_valid_address = last_valid_address + numbytes;
        /* We need to initialize the mem_control_block */    　　
        current_location_mcb = memory_location;
        current_location_mcb->is_available = 0;
        current_location_mcb->size = numbytes;
    }　　
    /* Now, no matter what (well, except for error conditions),* memory_location has the address of the memory, including* the mem_control_block*/　　
    /* Move the pointer past the mem_control_block */　　
    memory_location = memory_location + sizeof(struct mem_control_block);

    /* Return the pointer */
    return memory_location;
}