diff options
Diffstat (limited to 'docs/doxygen/nel/a05781.html')
| -rw-r--r-- | docs/doxygen/nel/a05781.html | 291 |
1 files changed, 291 insertions, 0 deletions
diff --git a/docs/doxygen/nel/a05781.html b/docs/doxygen/nel/a05781.html new file mode 100644 index 00000000..9408956e --- /dev/null +++ b/docs/doxygen/nel/a05781.html @@ -0,0 +1,291 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> +<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> +<title>NeL: heap_memory.cpp Source File</title> +<link href="doxygen.css" rel="stylesheet" type="text/css"> +</head><body> +<!-- Generated by Doxygen 1.3.6 --> +<div class="qindex"> <form class="search" action="search.php" method="get"> +<a class="qindex" href="main.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a> | <a class="qindex" href="pages.html">Related Pages</a> | <span class="search"><u>S</u>earch for <input class="search" type="text" name="query" value="" size="20" accesskey="s"/></span></form></div> +<h1>heap_memory.cpp</h1><a href="a04358.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 +00007 <span class="comment">/* Copyright, 2001 Nevrax Ltd.</span> +00008 <span class="comment"> *</span> +00009 <span class="comment"> * This file is part of NEVRAX NEL.</span> +00010 <span class="comment"> * NEVRAX NEL is free software; you can redistribute it and/or modify</span> +00011 <span class="comment"> * it under the terms of the GNU General Public License as published by</span> +00012 <span class="comment"> * the Free Software Foundation; either version 2, or (at your option)</span> +00013 <span class="comment"> * any later version.</span> +00014 <span class="comment"></span> +00015 <span class="comment"> * NEVRAX NEL is distributed in the hope that it will be useful, but</span> +00016 <span class="comment"> * WITHOUT ANY WARRANTY; without even the implied warranty of</span> +00017 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span> +00018 <span class="comment"> * General Public License for more details.</span> +00019 <span class="comment"></span> +00020 <span class="comment"> * You should have received a copy of the GNU General Public License</span> +00021 <span class="comment"> * along with NEVRAX NEL; see the file COPYING. If not, write to the</span> +00022 <span class="comment"> * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,</span> +00023 <span class="comment"> * MA 02111-1307, USA.</span> +00024 <span class="comment"> */</span> +00025 +00026 <span class="preprocessor">#include "<a class="code" href="a05021.html">stdmisc.h</a>"</span> +00027 +00028 <span class="preprocessor">#include "<a class="code" href="a04359.html">nel/misc/heap_memory.h</a>"</span> +00029 +00030 <span class="keyword">using</span> <span class="keyword">namespace </span>std; +00031 +00032 +00033 <span class="keyword">namespace </span>NLMISC +00034 { +00035 +00036 +00037 <span class="comment">// ***************************************************************************</span> +<a name="l00038"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya1">00038</a> CHeapMemory::CHeapMemory() +00039 { +00040 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya6">reset</a>(); +00041 <span class="comment">// For allocate to work even if the heap is not initialized.</span> +00042 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr0">_Alignment</a>= 4; +00043 } +00044 <span class="comment">// ***************************************************************************</span> +<a name="l00045"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya7">00045</a> CHeapMemory::~CHeapMemory() +00046 { +00047 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya6">reset</a>(); +00048 } +00049 +00050 +00051 <span class="comment">// ***************************************************************************</span> +<a name="l00052"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya6">00052</a> <span class="keywordtype">void</span> CHeapMemory::reset() +00053 { +00054 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.clear(); +00055 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr2">_EmptySpaceMap</a>.clear(); +00056 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr1">_AllocatedSpaceMap</a>.clear(); +00057 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr4">_HeapPtr</a>= NULL; +00058 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr5">_HeapSize</a>= 0; +00059 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr6">_HeapSizeUsed</a>= 0; +00060 } +00061 +00062 +00063 <span class="comment">// ***************************************************************************</span> +<a name="l00064"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya5">00064</a> <span class="keywordtype">void</span> CHeapMemory::initHeap(<span class="keywordtype">void</span> *heap, <a class="code" href="a04558.html#a15">uint</a> <a class="code" href="a04223.html#a587">size</a>, <a class="code" href="a04558.html#a15">uint</a> align) +00065 { +00066 <span class="comment">// setup alignement.</span> +00067 <span class="keywordflow">if</span>(align!=4 && align!=8 && align!=16 && align!=32) +00068 { +00069 <a class="code" href="a04199.html#a12">nlstop</a>; +00070 align= 4; +00071 } +00072 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr0">_Alignment</a>= align; +00073 +00074 <span class="comment">// Manage alignement.</span> +00075 <a class="code" href="a04223.html#a587">size</a>= (<a class="code" href="a04223.html#a587">size</a>) & (~(<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr0">_Alignment</a>-1)); +00076 +00077 <span class="comment">// clear container.</span> +00078 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya6">reset</a>(); +00079 <span class="keywordflow">if</span>(heap==0 || <a class="code" href="a04223.html#a587">size</a>==0) +00080 <span class="keywordflow">return</span>; +00081 +00082 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr4">_HeapPtr</a>= (<a class="code" href="a04558.html#a7">uint8</a>*)heap; +00083 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr5">_HeapSize</a>= <a class="code" href="a04223.html#a587">size</a>; +00084 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr6">_HeapSizeUsed</a>= 0; +00085 +00086 <span class="comment">// Add the only one empty space.</span> +00087 <a class="code" href="a02628.html">CEmptySpace</a> space; +00088 space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr4">_HeapPtr</a>; +00089 space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr5">_HeapSize</a>; +00090 +00091 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd0">addEmptySpace</a>(space); +00092 } +00093 +00094 +00095 <span class="comment">// ***************************************************************************</span> +<a name="l00096"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd1">00096</a> <span class="keywordtype">void</span> CHeapMemory::removeEmptySpace(<a class="code" href="a02628.html">CEmptySpace</a> &space) +00097 { +00098 <span class="comment">// remove the iterator on the spaceMap.</span> +00099 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr2">_EmptySpaceMap</a>.erase( space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo2">SizeIt</a> ); +00100 +00101 <span class="comment">// remove from the list of EmptySpaces. NB: must fo it after all, because "space" may be deleted.</span> +00102 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.erase( space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a> ); +00103 } +00104 +00105 +00106 <span class="comment">// ***************************************************************************</span> +<a name="l00107"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd0">00107</a> <span class="keywordtype">void</span> CHeapMemory::addEmptySpace(<a class="code" href="a02628.html">CEmptySpace</a> &space) +00108 { +00109 <span class="comment">// insert and get the iterator on the spaceMap.</span> +00110 space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo2">SizeIt</a>= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr2">_EmptySpaceMap</a>.insert( make_pair(space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>, space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>)); +00111 +00112 <span class="comment">// insert into the list of EmptySpaces.</span> +00113 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.insert( make_pair(space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>, space) ); +00114 } +00115 +00116 +00117 <span class="comment">// ***************************************************************************</span> +<a name="l00118"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya0">00118</a> <span class="keywordtype">void</span> *CHeapMemory::allocate(<a class="code" href="a04558.html#a15">uint</a> <a class="code" href="a04223.html#a587">size</a>) +00119 { +00120 <span class="keywordflow">if</span>(<a class="code" href="a04223.html#a587">size</a>==0) +00121 <span class="keywordflow">return</span> NULL; +00122 +00123 <span class="comment">// Manage alignement.</span> +00124 <a class="code" href="a04223.html#a587">size</a>= (<a class="code" href="a04223.html#a587">size</a> + (<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr0">_Alignment</a>-1)) & (~(<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr0">_Alignment</a>-1)); +00125 +00126 +00127 <span class="comment">// retrieve the best block.</span> +00128 <span class="comment">//=========================</span> +00129 <a class="code" href="a02628.html">CEmptySpace</a> bestSpace; +00130 <span class="comment">// NB: do a copy, because of removeEmptySpace() which delete the space.</span> +00131 +00132 <span class="comment">// Find the smaller space which is >= than size.</span> +00133 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryy2">ItEmptySpaceSizeMap</a> it; +00134 it= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr2">_EmptySpaceMap</a>.lower_bound(<a class="code" href="a04223.html#a587">size</a>); +00135 +00136 <span class="comment">// if not found, alloc fails.</span> +00137 <span class="keywordflow">if</span>(it == <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr2">_EmptySpaceMap</a>.end()) +00138 <span class="keywordflow">return</span> NULL; +00139 <span class="keywordflow">else</span> +00140 { +00141 <span class="comment">// NB: this space must exist in the "array".</span> +00142 bestSpace= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>[it->second]; +00143 } +00144 +00145 +00146 <span class="comment">// remove this empty space from list.</span> +00147 <span class="comment">//=========================</span> +00148 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd1">removeEmptySpace</a>(bestSpace); +00149 +00150 +00151 <span class="comment">// if any, add the space unused to the list.</span> +00152 <span class="comment">//=========================</span> +00153 <span class="keywordflow">if</span>(bestSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a> > <a class="code" href="a04223.html#a587">size</a>) +00154 { +00155 <a class="code" href="a02628.html">CEmptySpace</a> space; +00156 space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>= bestSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a> + <a class="code" href="a04223.html#a587">size</a>; +00157 space.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>= bestSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a> - <a class="code" href="a04223.html#a587">size</a>; +00158 +00159 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd0">addEmptySpace</a>(space); +00160 } +00161 +00162 +00163 <span class="comment">// return / insert the allocated space.</span> +00164 <span class="comment">//=========================</span> +00165 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr1">_AllocatedSpaceMap</a>.insert(make_pair(bestSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>, <a class="code" href="a04223.html#a587">size</a>)); +00166 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr6">_HeapSizeUsed</a>+= <a class="code" href="a04223.html#a587">size</a>; +00167 +00168 <span class="comment">// return the ptr of start of this empty space.</span> +00169 <span class="keywordflow">return</span> bestSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>; +00170 } +00171 +00172 <span class="comment">// ***************************************************************************</span> +<a name="l00173"></a><a class="code" href="a02627.html#NLMISC_1_1CHeapMemorya2">00173</a> <span class="keywordtype">void</span> CHeapMemory::free(<span class="keywordtype">void</span> *ptr) +00174 { +00175 <span class="keywordflow">if</span>(ptr==NULL) +00176 <span class="keywordflow">return</span>; +00177 +00178 <span class="comment">// Must find the array in allocated spaces.</span> +00179 <span class="comment">//==========================</span> +00180 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryy0">ItAllocatedSpaceMap</a> itAlloc= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr1">_AllocatedSpaceMap</a>.find((<a class="code" href="a04558.html#a7">uint8</a>*)ptr); +00181 <span class="keywordflow">if</span>(itAlloc == <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr1">_AllocatedSpaceMap</a>.end()) +00182 { +00183 <a class="code" href="a04199.html#a12">nlstop</a>; +00184 <span class="keywordflow">return</span>; +00185 } +00186 <a class="code" href="a04558.html#a15">uint</a> <a class="code" href="a04223.html#a587">size</a>= itAlloc->second; +00187 +00188 <span class="comment">// free this space from allocated Spaces.</span> +00189 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr1">_AllocatedSpaceMap</a>.erase(itAlloc); +00190 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr6">_HeapSizeUsed</a>-= <a class="code" href="a04223.html#a587">size</a>; +00191 +00192 +00193 <span class="comment">// Must find previous or/and next empty space, if any.</span> +00194 <span class="comment">//==========================</span> +00195 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryy1">ItEmptySpacePtrMap</a> itPrevious, itNext; +00196 +00197 <span class="comment">// find the empty space which is immediately >= than ptr.</span> +00198 itNext= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.lower_bound((<a class="code" href="a04558.html#a7">uint8</a>*)ptr); +00199 <span class="comment">// NB: it may be end(), if it is the last block (very rare).</span> +00200 +00201 <span class="comment">// some check. next empty space ptr must be after ptr.</span> +00202 <span class="keywordflow">if</span>(itNext!=<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00203 { +00204 <a class="code" href="a04199.html#a6">nlassert</a>(itNext->second.Ptr >= (<a class="code" href="a04558.html#a7">uint8</a>*)ptr + <a class="code" href="a04223.html#a587">size</a>); +00205 } +00206 +00207 <span class="comment">// if itNext is not the first empty space, there is an empty space before us.</span> +00208 <span class="keywordflow">if</span>( itNext!= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.begin() ) +00209 { +00210 <span class="comment">// NB: work even if itNext==end().</span> +00211 itPrevious= itNext; +00212 itPrevious--; +00213 <span class="comment">// some check. previous empty space ptr must be before ptr.</span> +00214 <a class="code" href="a04199.html#a6">nlassert</a>(itPrevious!=<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()); +00215 <a class="code" href="a04199.html#a6">nlassert</a>(itPrevious->second.Ptr + itPrevious->second.Size <= (<a class="code" href="a04558.html#a7">uint8</a>*)ptr ); +00216 } +00217 <span class="keywordflow">else</span> +00218 itPrevious= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end(); +00219 +00220 +00221 <span class="comment">// if next exist.</span> +00222 <span class="keywordflow">if</span>(itNext!=<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00223 { +00224 <span class="comment">// If Previous is not just after allocated ptr, it means that there is some allocated blocks beetween,</span> +00225 <span class="comment">// so it is not a valid empty space to concat.</span> +00226 <span class="keywordflow">if</span>(itNext->second.Ptr != (<a class="code" href="a04558.html#a7">uint8</a>*)ptr + <a class="code" href="a04223.html#a587">size</a>) +00227 itNext= <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end(); +00228 } +00229 <span class="comment">// if previous exist.</span> +00230 <span class="keywordflow">if</span>(itPrevious!=<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00231 { +00232 <span class="comment">// If Previous is not just before allocated ptr, it means that there is some allocated blocks beetween,</span> +00233 <span class="comment">// so it is not a valid empty space to concat.</span> +00234 <span class="keywordflow">if</span>(itPrevious->second.Ptr + itPrevious->second.Size != (<a class="code" href="a04558.html#a7">uint8</a>*)ptr ) +00235 itPrevious=<a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end(); +00236 } +00237 +00238 +00239 +00240 <span class="comment">// According to configuration, build the new empty space, mreging previous and next, and remove old ones.</span> +00241 <span class="comment">//==========================</span> +00242 <a class="code" href="a02628.html">CEmptySpace</a> newSpace; +00243 +00244 <span class="comment">// if no previous empty space, then newSpace start at ptr.</span> +00245 <span class="keywordflow">if</span>(itPrevious == <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00246 { +00247 <span class="comment">// Start with old allocated block.</span> +00248 newSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>= (<a class="code" href="a04558.html#a7">uint8</a>*)ptr; +00249 newSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>= <a class="code" href="a04223.html#a587">size</a>; +00250 } +00251 <span class="comment">// else, start at previous Ptr.</span> +00252 <span class="keywordflow">else</span> +00253 { +00254 <span class="comment">// Start with previous block. size is previous size + allocated block size.</span> +00255 newSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo0">Ptr</a>= itPrevious->second.Ptr; +00256 newSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>= itPrevious->second.Size + <a class="code" href="a04223.html#a587">size</a>; +00257 } +00258 +00259 <span class="comment">// if next empty space, must inc size.</span> +00260 <span class="keywordflow">if</span>(itNext != <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00261 { +00262 newSpace.<a class="code" href="a02628.html#NLMISC_1_1CHeapMemory_1_1CEmptySpaceo1">Size</a>+= itNext->second.Size; +00263 } +00264 +00265 +00266 <span class="comment">// remove old empty space, and add new one.</span> +00267 <span class="comment">//==========================</span> +00268 +00269 <span class="comment">// remove old empty spaces.</span> +00270 <span class="keywordflow">if</span>(itPrevious != <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00271 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd1">removeEmptySpace</a>(itPrevious->second); +00272 <span class="keywordflow">if</span>(itNext != <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryr3">_EmptySpaces</a>.end()) +00273 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd1">removeEmptySpace</a>(itNext->second); +00274 +00275 +00276 <span class="comment">// Add the new concatenated empty space.</span> +00277 <a class="code" href="a02627.html#NLMISC_1_1CHeapMemoryd0">addEmptySpace</a>(newSpace); +00278 } +00279 +00280 +00281 +00282 } <span class="comment">// NLMISC</span> +</pre></div><hr size="1"><address style="align: right;"><small>Generated on Tue Mar 16 06:26:07 2004 for NeL by +<a href="http://www.doxygen.org/index.html"> +<img src="doxygen.png" alt="doxygen" align="middle" border=0 > +</a>1.3.6 </small></address> +</body> +</html> |