📄 page426.html
字号:
<HTML>
<HEAD>
<TITLE>Doubly Linked Free Storage</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="tex2html7185" HREF="page427.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page427.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="tex2html7183" HREF="page416.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page416.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="tex2html7177" HREF="page425.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page425.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="tex2html7187" 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="tex2html7188" 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>
<H1><A NAME="SECTION0014300000000000000000">Doubly Linked Free Storage</A></H1>
<A NAME="secheapdoubly"> </A>
<P>
The singly-linked free list used in the preceding section is kept sorted
in order to facilitate the coalescing of adjacent free areas.
The only way to determine whether a particular area is free
is to see if it appears in the free list.
Since we need to examine <em>adjacent</em> areas to determine
whether they can be combined,
the free list is kept sorted.
That way, adjacent areas appear next to one another in the free list.
<P>
Unfortunately since the free list must be kept sorted,
every time an area is released it must be inserted into the list
at the correct position.
This means that the running time of the <tt>Release</tt> operation is <I>O</I>(<I>n</I>)
in the worst case,
where <I>n</I> is the number of blocks in the storage pool.
<P>
The essence of the problem is that we cannot tell by looking at an area
whether it is reserved or free.
So, the solution must be to record the allocation status of the area
<em>in the area itself</em>.
<P>
A secondary problem with the use of a singly-linked free list is that,
given a pointer to an area,
we cannot extract that area from the free list
without traversing the list.
This is because in order to extract an element from a linked list,
we need to know the predecessor of that element.
And in a singly-linked list we must search from the head of the list
to find the predecessor.
The solution is, of course, to use a <em>doubly-linked</em> free list.
<P>
Finally, we shall play an interesting algorithmic trick:
In order to coalesce adjacent free areas,
we need to traverse the free list.
However, since we must traverse the free list in the <tt>Acquire</tt> operation,
in order to find a free area of a suitable size,
we shall do the coalescing in the <tt>Acquire</tt> operation
and not in the <tt>Release</tt> operation.
While this does increase slightly the running time for <tt>Acquire</tt>,
it means that <tt>Release</tt> can run in constant time.
<P>
Figure <A HREF="page426.html#figpool2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page426.html#figpool2"><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 a memory map of
a storage pool managed using a doubly-linked list.
The reserved areas in Figure <A HREF="page426.html#figpool2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page426.html#figpool2"><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> are exactly the same as those
shown in Figure <A HREF="page417.html#figpool1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page417.html#figpool1"><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>.
The figure clearly indicates that there are adjacent
uncoalesced free areas in the free list.
What the figure cannot show is that the areas in the free list
are not sorted.
<P>
<P><A NAME="30969"> </A><A NAME="figpool2"> </A> <IMG WIDTH=575 HEIGHT=557 ALIGN=BOTTOM ALT="figure30965" SRC="img1756.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1756.gif" ><BR>
<STRONG>Figure:</STRONG> Memory Map of a Doubly-Linked Storage Pool<BR>
<P>
<P>
As before, we implement the storage pool as an array of <tt>Block</tt>s.
The structure of a <tt>Block</tt> is shown in Figure <A HREF="page426.html#figblock2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page426.html#figblock2"><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>.
A sequence of consecutive,
contiguous blocks in the array constitutes an <em>area</em>.
Only the first block in each area is used to keep track of the entire area.
<P>
<P><A NAME="31389"> </A><A NAME="figblock2"> </A> <IMG WIDTH=575 HEIGHT=171 ALIGN=BOTTOM ALT="figure30976" SRC="img1757.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1757.gif" ><BR>
<STRONG>Figure:</STRONG> <tt>DoublyLinkedPool::Block</tt> Structure Layout<BR>
<P>
<P>
Notice that we now encode two pieces of information in the block header:
A single-bit is used to indicate whether the area is reserved or free
and the remaining bits are used to record the length of the area (in blocks).
By packing this information in a single word,
we have not increased the space overhead associated with reserved areas.
<P>
Free areas are linked in a <em>doubly-linked free list</em>.
Two pointers are required to accomplish this--<tt>prev</tt> and <tt>next</tt>.
The effect of the extra pointer is to increase the minimum block size.
However, since the pointers occupy space
in the pool which would otherwise be unused,
we do not require any additional space.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html7189" HREF="page427.html#SECTION0014310000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page427.html#SECTION0014310000000000000000">Implementation</A>
</UL>
<HR><A NAME="tex2html7185" HREF="page427.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page427.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="tex2html7183" HREF="page416.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page416.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="tex2html7177" HREF="page425.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page425.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="tex2html7187" 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="tex2html7188" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -