📄 lib0046.html
字号:
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Chapter 6: Miscellaneous Topics</title>
<link rel="STYLESHEET" type="text/css" href="images/xpolecat.css">
<link rel="STYLESHEET" type="text/css" href="images/ie.content.books24x7.css">
</head>
<body >
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<td><div STYLE="MARGIN-LEFT: 0.15in;">
<a href="toc.html"><img src="images/teamlib.gif" width="62" height="15" border="0" align="absmiddle" alt="Team LiB"></a></div></td>
<td valign="top" class="v2" align="right"><div STYLE="MARGIN-RIGHT: 0.15in"><a href="LiB0045.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0047.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
<div class="chapter">
<a name="ch06"></a>
<h1 class="chapter-title"><span class="chapter-titlelabel">Chapter 6: </span>Miscellaneous Topics</h1><a name="638"></a><a name="IDX-343"></a>
<div class="section">
<h2 class="sect2-title">
<a name="639"></a><a name="ch06lev1sec1"></a>Suballocators</h2>
<p class="first-para">Normally, memory managers have to suffer through the slings and arrows of not knowing when or how much memory will be requested by an application. There are, however, some circumstances where you will know in advance how large an application's memory requests will be or how many there will be. If this is the case, you can construct a dedicated memory manager known as a <i class="emphasis">suballocator</i> to handle memory requests and reap tremendous performance gains.</p>
<p class="para">A suballocator is an allocator that is built on top of another allocator. An example of where suballocators could be utilized is in a compiler. Specifically, one of the primary duties of a compiler is to build a <i class="emphasis">symbol table</i>. Symbol tables are memory-resident databases that serve as a repository for application data. They are typically built using a set of fixed-size structures. The fact that a symbol table's components are all fixed in size makes a compiler fertile ground for the inclusion of a suballocator. Instead of calling <span class="fixed">malloc()</span> to allocate symbol table objects, you can allocate a large pool of memory and use a suballocator to allocate symbol table objects from that pool.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note </td><td valign="top" class="admon-body">
<p class="first-para">In a sense, all of the memory management implementations in this book are suballocators because they are built on top of the Window's <span class="fixed">HeapAlloc()</span> function. Traditionally, however, when someone is talking about a suballocator, they are talking about a special-purpose application component that is implemented by the programmer and based on existing services provided by application libraries (like <span class="fixed">malloc()</span> and <span class="fixed">free()</span>).</p>
</td>
</tr>
</table>
<a name="640"></a><a name="IDX-344"></a>
<p class="para">To give you an example of how well suballocators function, I am going to offer a brief example. The following <span class="fixed">SubAllocator</span> class manages a number of fixed-sized <span class="fixed">Indices</span> structures in a list format. Each structure has a field called <span class="fixed">FREE</span> to indicate if it has been allocated. When a request for a structure is made via the <span class="fixed">allocate()</span> member function, the <span class="fixed">SubAllocator</span> class will look for the first free structure in its list and return the address of that structure. To avoid having to traverse the entire list each time a request is made, a place marker named <span class="fixed">lastAlloc</span> is used to keep track of where the last allocation was performed.</p>
<p class="para">The basic mechanism involved in allocating an <span class="fixed">Indices</span> structure is displayed in <a class="internaljump" href="#ch06fig01">Figure 6.1</a>.</p>
<div class="figure">
<a name="641"></a><a name="ch06fig01"></a><span class="figuremediaobject"><a href="images/fig372%5F01%5F0%2Ejpg" NAME="IMG_97" target="_parent"><img src="images/fig372_01.jpg" height="178" width="272" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 6.1</span></span>
</div>
<p class="para">The following source code implements the <span class="fixed">SubAllocator</span> class and a small test driver:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include<windows.h></span>
<span style="background-color:d9d9d9">#include<stdlib.h></span>
<span style="background-color:d9d9d9">#include<stdio.h></span>
<span style="background-color:d9d9d9">#define U4 unsigned long</span>
<span style="background-color:d9d9d9">#define U1 unsigned char</span>
<span style="background-color:d9d9d9">struct Indices</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">U1 free;</span>
<span style="background-color:d9d9d9">U4 index1;</span>
<span style="background-color:d9d9d9">U4 index2;</span>
<span style="background-color:d9d9d9">U4 index3;</span>
<span style="background-color:d9d9d9">};<a name="642"></a><a name="IDX-345"></a></span>
<span style="background-color:d9d9d9">class SubAllocator</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">private:</span>
<span style="background-color:d9d9d9">struct Indices *indices;</span>
<span style="background-color:d9d9d9">U4 size;</span>
<span style="background-color:d9d9d9">U4 lastAlloc;</span>
<span style="background-color:d9d9d9">public:</span>
<span style="background-color:d9d9d9">SubAllocator(U4 nElms);</span>
<span style="background-color:d9d9d9">~SubAllocator();</span>
<span style="background-color:d9d9d9">struct Indices *alloc();</span>
<span style="background-color:d9d9d9">void release(struct Indices *addr);</span>
<span style="background-color:d9d9d9">void printList();</span>
<span style="background-color:d9d9d9">};</span>
<span style="background-color:d9d9d9">SubAllocator::SubAllocator(U4 nElms)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">U4 i;</span>
<span style="background-color:d9d9d9">size = nElms;</span>
<span style="background-color:d9d9d9">indices = (struct Indices*)malloc(size*(sizeof(struct</span>
<span style="background-color:d9d9d9">Indices)));</span>
<span style="background-color:d9d9d9">if(indices==NULL)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">printf("SubAllocator::SubAllocator(%lu) :",size);</span>
<span style="background-color:d9d9d9">printf("could not allocate list\n");</span>
<span style="background-color:d9d9d9">exit(1);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">for(i=0;i<size;i++)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">indices[i].free =TRUE;</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">lastAlloc = 0;</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">} /*end constructor-----------------------------------------------*/</span>
<span style="background-color:d9d9d9">SubAllocator::~SubAllocator()</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">free(indices);</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">} /*end destructor-----------------------------------------------*/</span>
<span style="background-color:d9d9d9">struct Indices* SubAllocator::alloc()</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">U4 i;<a name="643"></a><a name="IDX-346"></a></span>
<span style="background-color:d9d9d9">if(lastAlloc==size-1){ lastAlloc=0; }</span>
<span style="background-color:d9d9d9">for(i=lastAlloc;i<size;i++)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">if(indices[i].free==TRUE)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">indices[i].free=FALSE;</span>
<span style="background-color:d9d9d9">lastAlloc = i;</span>
<span style="background-color:d9d9d9">return(&indices[i]);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">}</span>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -