-
Notifications
You must be signed in to change notification settings - Fork 0
/
free_list.cpp
135 lines (112 loc) · 2.9 KB
/
free_list.cpp
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include "master.hpp"
namespace factor
{
void free_list::clear_free_list()
{
for(cell i = 0; i < free_list_count; i++)
small_blocks[i].clear();
large_blocks.clear();
free_block_count = 0;
free_space = 0;
}
void free_list::initial_free_list(cell start, cell end, cell occupied)
{
clear_free_list();
if(occupied != end - start)
{
free_heap_block *last_block = (free_heap_block *)(start + occupied);
last_block->make_free(end - (cell)last_block);
add_to_free_list(last_block);
}
}
void free_list::add_to_free_list(free_heap_block *block)
{
cell size = block->size();
free_block_count++;
free_space += size;
if(size < free_list_count * data_alignment)
small_blocks[size / data_alignment].push_back(block);
else
large_blocks.insert(block);
}
free_heap_block *free_list::find_free_block(cell size)
{
/* Check small free lists */
if(size / data_alignment < free_list_count)
{
std::vector<free_heap_block *> &blocks = small_blocks[size / data_alignment];
if(blocks.size() == 0)
{
/* Round up to a multiple of 'size' */
cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
/* Allocate a block this big */
free_heap_block *large_block = find_free_block(large_block_size);
if(!large_block) return NULL;
large_block = split_free_block(large_block,large_block_size);
/* Split it up into pieces and add each piece back to the free list */
for(cell offset = 0; offset < large_block_size; offset += size)
{
free_heap_block *small_block = large_block;
large_block = (free_heap_block *)((cell)large_block + size);
small_block->make_free(size);
add_to_free_list(small_block);
}
}
free_heap_block *block = blocks.back();
blocks.pop_back();
free_block_count--;
free_space -= block->size();
return block;
}
else
{
/* Check large free list */
free_heap_block key;
key.make_free(size);
large_block_set::iterator iter = large_blocks.lower_bound(&key);
large_block_set::iterator end = large_blocks.end();
if(iter != end)
{
free_heap_block *block = *iter;
large_blocks.erase(iter);
free_block_count--;
free_space -= block->size();
return block;
}
return NULL;
}
}
free_heap_block *free_list::split_free_block(free_heap_block *block, cell size)
{
if(block->size() != size)
{
/* split the block in two */
free_heap_block *split = (free_heap_block *)((cell)block + size);
split->make_free(block->size() - size);
block->make_free(size);
add_to_free_list(split);
}
return block;
}
bool free_list::can_allot_p(cell size)
{
return largest_free_block() >= std::max(size,allocation_page_size);
}
cell free_list::largest_free_block()
{
if(large_blocks.size())
{
large_block_set::reverse_iterator last = large_blocks.rbegin();
return (*last)->size();
}
else
{
for(int i = free_list_count - 1; i >= 0; i--)
{
if(small_blocks[i].size())
return small_blocks[i].back()->size();
}
return 0;
}
}
}