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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
/*
** (c) 1996-2000 The Regents of the University of California (through
** E.O. Lawrence Berkeley National Laboratory), subject to approval by
** the U.S. Department of Energy. Your use of this software is under
** license -- the license agreement is attached and included in the
** directory as license.txt or you may contact Berkeley Lab's Technology
** Transfer Department at TTD@lbl.gov. NOTICE OF U.S. GOVERNMENT RIGHTS.
** The Software was developed under funding from the U.S. Government
** which consequently retains certain rights as follows: the
** U.S. Government has been granted for itself and others acting on its
** behalf a paid-up, nonexclusive, irrevocable, worldwide license in the
** Software to reproduce, prepare derivative works, and perform publicly
** and display publicly. Beginning five (5) years after the date
** permission to assert copyright is obtained from the U.S. Department of
** Energy, and subject to any subsequent five (5) year renewals, the
** U.S. Government is granted for itself and others acting on its behalf
** a paid-up, nonexclusive, irrevocable, worldwide license in the
** Software to reproduce, prepare derivative works, distribute copies to
** the public, perform publicly and display publicly, and to permit
** others to do so.
*/
//
// $Id: CArena.cpp,v 1.31 2001/12/13 23:46:08 car Exp $
//
#include <winstd.H>
#include <utility>
#include <cstring>
#include <CArena.H>
CArena::CArena (size_t hunk_size)
{
//
// Force alignment of hunksize.
//
m_hunk = Arena::align(hunk_size == 0 ? DefaultHunkSize : hunk_size);
m_used = 0;
BL_ASSERT(m_hunk >= hunk_size);
BL_ASSERT(m_hunk%sizeof(Arena::Word) == 0);
}
CArena::~CArena ()
{
for (unsigned int i = 0; i < m_alloc.size(); i++)
::operator delete(m_alloc[i]);
}
void*
CArena::alloc (size_t nbytes)
{
nbytes = Arena::align(nbytes == 0 ? 1 : nbytes);
//
// Find node in freelist at lowest memory address that'll satisfy request.
//
NL::iterator free_it = m_freelist.begin();
for ( ; free_it != m_freelist.end(); ++free_it)
if ((*free_it).size() >= nbytes)
break;
void* vp = 0;
if (free_it == m_freelist.end())
{
const size_t N = nbytes < m_hunk ? m_hunk : nbytes;
vp = ::operator new(N);
m_used += N;
m_alloc.push_back(vp);
if (nbytes < m_hunk)
{
//
// Add leftover chunk to free list.
//
// Insert with a hint -- should be largest block in the set.
//
void* block = static_cast<char*>(vp) + nbytes;
m_freelist.insert(m_freelist.end(), Node(block, m_hunk-nbytes));
}
}
else
{
BL_ASSERT((*free_it).size() >= nbytes);
BL_ASSERT(m_busylist.find(*free_it) == m_busylist.end());
vp = (*free_it).block();
if ((*free_it).size() > nbytes)
{
//
// Insert remainder of free block back into freelist.
//
// Insert with a hint -- right after the current block being split.
//
Node freeblock = *free_it;
freeblock.size(freeblock.size() - nbytes);
freeblock.block(static_cast<char*>(vp) + nbytes);
m_freelist.insert(free_it, freeblock);
}
m_freelist.erase(free_it);
}
m_busylist.insert(Node(vp, nbytes));
BL_ASSERT(!(vp == 0));
return vp;
}
void
CArena::free (void* vp)
{
if (vp == 0)
//
// Allow calls with NULL as allowed by C++ delete.
//
return;
//
// `vp' had better be in the busy list.
//
NL::iterator busy_it = m_busylist.find(Node(vp,0));
BL_ASSERT(!(busy_it == m_busylist.end()));
BL_ASSERT(m_freelist.find(*busy_it) == m_freelist.end());
void* freeblock = static_cast<char*>((*busy_it).block());
//
// Put free'd block on free list and save iterator to insert()ed position.
//
std::pair<NL::iterator,bool> pair_it = m_freelist.insert(*busy_it);
BL_ASSERT(pair_it.second == true);
NL::iterator free_it = pair_it.first;
BL_ASSERT(free_it != m_freelist.end() && (*free_it).block() == freeblock);
//
// And remove from busy list.
//
m_busylist.erase(busy_it);
//
// Coalesce freeblock(s) on lo and hi side of this block.
//
if (!(free_it == m_freelist.begin()))
{
NL::iterator lo_it = free_it;
--lo_it;
void* addr = static_cast<char*>((*lo_it).block()) + (*lo_it).size();
if (addr == (*free_it).block())
{
//
// This cast is needed as iterators to set return const values;
// i.e. we can't legally change an element of a set.
// In this case I want to change the size() of a block
// in the freelist. Since size() is not used in the ordering
// relations in the set, this won't effect the order;
// i.e. it won't muck up the ordering of elements in the set.
// I don't want to have to remove the element from the set and
// then reinsert it with a different size() as it'll just go
// back into the same place in the set.
//
Node* node = const_cast<Node*>(&(*lo_it));
BL_ASSERT(!(node == 0));
node->size((*lo_it).size() + (*free_it).size());
m_freelist.erase(free_it);
free_it = lo_it;
}
}
NL::iterator hi_it = free_it;
void* addr = static_cast<char*>((*free_it).block()) + (*free_it).size();
if (++hi_it != m_freelist.end() && addr == (*hi_it).block())
{
//
// Ditto the above comment.
//
Node* node = const_cast<Node*>(&(*free_it));
BL_ASSERT(!(node == 0));
node->size((*free_it).size() + (*hi_it).size());
m_freelist.erase(hi_it);
}
}
size_t
CArena::heap_space_used () const
{
return m_used;
}
|
