page435.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 101 行

HTML
101 行
字号 
<HTML>
<HEAD>
<TITLE>Releasing an Area</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
 <img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms 
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7293" HREF="page436.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page436.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7291" HREF="page432.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page432.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7287" HREF="page434.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page434.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7295" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7296" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0014413000000000000000">Releasing an Area</A></H3>
<P>
To release an area of size  <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif"  >,
we first examine its buddy to see if it is reserved or free.
If the area and its buddy are both free,
the two free areas can be combined into a single area of size  <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif"  >.
We then repeat the process to release the combined area of size  <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif"  >.
Eventually we get an area whose buddy is reserved
or, if <I>k</I>=<I>m</I>, the area does not have a buddy.
When this occurs,
we simply insert the area into the appropriate free list.
Program&nbsp;<A HREF="page435.html#progpool9c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page435.html#progpool9c"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows how this algorithm can be implemented.
<P>
<P><A NAME="32231">&#160;</A><A NAME="progpool9c">&#160;</A> <IMG WIDTH=575 HEIGHT=410 ALIGN=BOTTOM ALT="program32035" SRC="img1793.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1793.gif"  ><BR>
<STRONG>Program:</STRONG> <tt>BuddyPool</tt> Class <tt>Release</tt> 	Member Function Definition<BR>
<P>
<P>
The <tt>Release</tt> member function of the <tt>BuddyPool</tt> class
takes a pointer to the user part of a reserved area
and it frees the area as described above.
The <tt>Release</tt> function begins by determining the block which corresponds
to the given area and checking that this block is indeed a part
of the memory pool (lines&nbsp;3-7).
Then the block is marked <tt>free</tt> (line&nbsp;9).
<P>
Each iteration of the main loop (lines&nbsp;11-19)
determines whether the buddy of the area to be released 
is also free and combines the two areas as needed.
The buddy of the area is determined
by calling the private member function <tt>Buddy</tt> (line&nbsp;13).
This function takes as its lone argument
a reference to the first block of the area whose buddy we seek.
The <tt>Buddy</tt> function returns a reference to the first block of the buddy.
(Since the size of the block, <tt>k</tt>,
is found in the block itself,
it is not necessary to pass it as a parameter to the <tt>Buddy</tt> function).
If the buddy is found to be <tt>reserved</tt>,
no more combinations are possible and the main loop terminates (lines&nbsp;14-15).
<P>
If the area and its buddy are both free,
the buddy is withdrawn from its free list using the private
member function <tt>Unlink</tt> (line&nbsp;16).
Since the free lists are all doubly-linked lists,
it is possible to withdraw the buddy from its free list in constant time.
After combining the two areas of size  <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif"  >,
the combined area has size  <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif"  >
and is represented by the buddy with the smaller address
(lines&nbsp;17-18).
Eventually, when no more combining is possible,
the main loop terminates
and we insert the area into the appropriate free list (line&nbsp;20).
This insertion makes use of the private member function <tt>InsertAfter</tt>
which runs in constant time.
<P>
The running time of the <tt>Release</tt> function depends on the
number of iterations of the main loop.
If the buddy of the area to be released is <tt>reserved</tt>,
then the <tt>Release</tt> function runs in constant time.
In the worst case,
there is only one reserved area of size  <IMG WIDTH=14 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68313" SRC="img1791.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1791.gif"  > in the storage pool.
If we release this area, <I>m</I> iterations of the main loop are required.
Therefore, the worst-case running time for the <tt>Release</tt>
function is  <IMG WIDTH=121 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68321" SRC="img1792.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1792.gif"  >,
where <I>N</I> is the number of blocks in the storage pool.
<P>
In the preceding analysis (and in the implementation)
we have assumed the smallest area has size  <IMG WIDTH=14 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68313" SRC="img1791.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1791.gif"  >.
However, since every area must contain a <tt>Header</tt>,
the smallest area that will ever occur has size
 <IMG WIDTH=129 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68347" SRC="img1794.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1794.gif"  >.
For example,
on a 32-bit machine the size of the header is likely to be four bytes.
Since we cannot have an area of size  <IMG WIDTH=14 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68313" SRC="img1791.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1791.gif"  > or  <IMG WIDTH=14 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68351" SRC="img1795.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1795.gif"  >,
the corresponding free lists are never used.
<P>
It is also quite common to limit the maximum size of an area
to a size  <IMG WIDTH=21 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline68353" SRC="img1796.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1796.gif"  > where <I>m</I>'<I>&lt;</I><I>m</I>.
Consequently, since there are never any blocks of sizes between
 <IMG WIDTH=38 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline68357" SRC="img1797.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1797.gif"  > and  <IMG WIDTH=17 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68241" SRC="img1780.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1780.gif"  >,
the corresponding free lists are never used.
Limiting the maximum size of the free lists improves matters slightly,
since the worst-case running times for both the <tt>Acquire</tt> and
the <tt>Release</tt> functions become <I>O</I>(<I>m</I>').
<P>
<HR><A NAME="tex2html7293" HREF="page436.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page436.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7291" HREF="page432.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page432.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7287" HREF="page434.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page434.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7295" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7296" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>

page435.html - 源码说明

本页面展示了「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」中的 page435.html 源码文件，采用 HTML 编程语言编写，共 101 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与jkhrjqwhrwq相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?