page430.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 128 行
HTML
128 行
<HTML>
<HEAD>
<TITLE>Acquiring 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="tex2html7233" HREF="page431.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page431.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="tex2html7231" HREF="page427.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page427.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="tex2html7227" HREF="page429.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page429.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="tex2html7235" 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="tex2html7236" 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="SECTION0014313000000000000000">Acquiring an Area</A></H3>
<P>
The <tt>Acquire</tt> function of the <tt>DoublyLinkedPool</tt> class
is defined in Program <A HREF="page430.html#progpool5c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page430.html#progpool5c"><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>.
This function takes a single integer-valued argument
that specifies the size (in bytes) of the area to be allocated.
<tt>Acquire</tt> returns a pointer to the storage if there is sufficient
space left in the pool to accommodate the request.
Otherwise, a <tt>badalloc</tt> exception is thrown.
<P>
<P><A NAME="31406"> </A><A NAME="progpool5c"> </A> <IMG WIDTH=575 HEIGHT=678 ALIGN=BOTTOM ALT="program31350" SRC="img1762.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1762.gif" ><BR>
<STRONG>Program:</STRONG> <tt>DoublyLinkedPool</tt> Class <tt>Acquire</tt> Member Function Definition<BR>
<P>
<P>
In order to find a suitable area in which to allocate space,
the <tt>Acquire</tt> function must traverse the free list.
In this case, we choose again to use the <em>first-fit allocation strategy</em>.
I.e., storage is allocated in the first area that is large enough.
<P>
Recall that the <tt>Release</tt> function given in the preceding section
does not combine adjacent free areas.
Therefore, it is the responsibility of the <tt>Acquire</tt> function to do this.
The algorithmic trick is this:
Adjacent free areas are recombined while the free list is traversed
in search of a free area large enough to accommodate the allocation request!
<P>
The <tt>Acquire</tt> function begins by computing the number of blocks
required using the formula
<P> <IMG WIDTH=408 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath68119" SRC="img1763.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1763.gif" ><P>
I.e., we need enough space for the requested number of bytes <em>plus</em>
a <tt>Header</tt> (lines 3-5).
<P>
Then the <tt>Acquire</tt> function traverses the free list in search
of an area that is large enough (lines 7-21).
As each area in the free list is visited,
the area that immediately follows the given area in memory
is examined to see if it too is free and, therefore,
if it should be combined with the given area.
Since the size of an area is recorded in its header,
we can easily find the area which follows it in memory
as shown in Figure <A HREF="page430.html#figpool5" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page430.html#figpool5"><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>.
And since the <em>status</em> of an area (<tt>free</tt> or <tt>reserved</tt>)
is recorded in the area itself,
we can determine whether the following area is free.
<P>
<P><A NAME="31599"> </A><A NAME="figpool5"> </A> <IMG WIDTH=575 HEIGHT=237 ALIGN=BOTTOM ALT="figure31374" SRC="img1764.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1764.gif" ><BR>
<STRONG>Figure:</STRONG> Using a Doubly-Linked (Unsorted) Free List<BR>
<P>
<P>
If the area which follows a given area is indeed free,
then it must in be the free list!
And because the free list is doubly-linked,
we can easily extract that area from the free list in constant time.
This is what the <tt>Unlink</tt> function on line 16 does.
<P>
When combining a given area with the area that follows it in memory,
we obtain an area the size of which is equal to the sum of the sizes
of the areas that were combined (line 17).
After the combining it is possible that the area that follows
the new larger area is also free.
Therefore we need to repeat the combining process again.
This is what the loop on lines 11-18 does--it keeps combining adjacent free areas until the area that follows
is a <tt>reserved</tt> area (lines 14-15).
<P>
The search for a free area to satisfy the
<tt>Acquire</tt> request terminates at the first area
that is large enough (lines 19-20).
Notice that if the entire free list is traversed
all the adjacent areas that can be merged will have been merged.
If the free list is traversed and an area is not found that is large enough
to satisfy the request,
then the request cannot be satisfied
because there is insufficient contiguous memory to do so.
In this case a <tt>badalloc</tt>
exception is thrown (lines 22-23).
<P>
When the free area is larger than needed, it is split in two.
The size of the first area is set to the number of blocks requested
and the size of the second area is equal to the number of blocks that remain.
The second area is then inserted into the free list by calling the
the <tt>InsertAfter</tt> member function (lines 24-31).
<P>
In all cases, by the time execution reaches line 32,
the free area is exactly the correct size.
The area is unlinked from the free list and marked <tt>reserved</tt>
(lines 32-33).
Finally, a pointer to the <tt>userPart</tt> of the area is returned (line 34).
<P>
At first glance it might seem that the nested <tt>for</tt> loops
(lines 8 and 11) would result in a worst-case running time of <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.gif" >
where <I>n</I> is the number of blocks in the storage pool.
However, the outer loop traverses the free list while
every complete iteration of the inner loop removes one
element from the free list.
As a result, the worst-case running time for the nested loops
is actually only <I>O</I>(<I>n</I>).
<P>
The nice thing about this approach is that the asymptotic running time
of the <tt>Acquire</tt> function would be <I>O</I>(<I>n</I>) even if it did not
combine adjacent free areas.
In particular, this asymptotic bound is the same as for the
singly-linked storage pool.
On the other hand, the running time of the <tt>Release</tt> function
is <I>O</I>(1) for the doubly-linked pool
which is certainly better than the <I>O</I>(<I>n</I>) worst-case running time
of the singly-linked pool.
Finally, since the free list is not kept sorted,
there is not the same tendency for the short areas
to accumulate at the head of the free list
as there is in the singly-linked pool.
<P>
<HR><A NAME="tex2html7233" HREF="page431.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page431.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="tex2html7231" HREF="page427.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page427.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="tex2html7227" HREF="page429.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page429.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="tex2html7235" 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="tex2html7236" 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 © 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>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?