📄 9_2_2 用户层垃圾回收算法的实现 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.htm
字号:
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
m_pAddr = r.m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
/* </SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">将新指向的内存的引用计数加</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">1 */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
p = (INT *)r.m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">－</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">1</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
*p += 1</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
return r</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> }</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="MARGIN-BOTTOM: 10pt; LINE-HEIGHT: 14pt"><SPAN
lang=EN-US style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<H4 style="MARGIN-LEFT: 0cm"><SPAN lang=EN-US>6. </SPAN><SPAN
style="FONT-FAMILY: 黑体">垃圾收集功能的实现</SPAN></H4>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 华康简宋">引用计数的功能实现后，接着要做的就是实现垃圾内存回收，也就是将引用计数为</SPAN><SPAN
lang=EN-US>0</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">的内存全部释放后，如何去访问已经分配的内存？必须用一张表来保存所有已分配的内存地址，可以在</SPAN><SPAN
lang=EN-US>GC_Malloc()</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">函数分配内存时就将分配的内存地址保存到哈希表里，然后就可以通过对哈希表的遍历来实现对内存垃圾的回收，由于牵涉哈希表的操作，除了修改</SPAN><SPAN
lang=EN-US>GC_Malloc()</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">函数外，还需要增加一个初始化函数，在初始化函数里创建哈希表，以下便是实现编码。</SPAN></P>
<P class=4><SPAN lang=EN-US>HASHTABLE *g_pTable</SPAN><SPAN
style="FONT-FAMILY: 宋体">；</SPAN><SPAN lang=EN-US>/* </SPAN><SPAN
style="FONT-FAMILY: 华康简宋">哈希表指针</SPAN><SPAN lang=EN-US> */</SPAN></P>
<P class=4><SPAN lang=EN-US>/** </SPAN><SPAN
style="FONT-FAMILY: 华康简宋">垃圾内存收集算法的初始化函数</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> @param
INT nBucketCount</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.2pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">哈希表的</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">bucket</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">的数量</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> @return
INT</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.2pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">返回</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">CAPI_SUCCESS</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">表示成功</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">返回</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">CAPI_FAILED</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">表示失败</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">*/</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><STRONG><SPAN lang=EN-US
style="FONT-SIZE: 9pt">INT GC_Init(INT nBucketCount)</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> g_pTable =
HashTable_Create(nBucketCount)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> if ( g_pTable
!= NULL )</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> {</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
return CAPI_SUCCESS</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> }</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> return
CAPI_FAILED</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN></P>
<P class=4 style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US>/**
</SPAN><SPAN style="FONT-FAMILY: 华康简宋">垃圾内存收集算法的内存分配函数</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> @param
size</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.2pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">要分派的内存大小，以字节为单位</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> </SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
@return</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.2pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">成功返回分配到的内存地址</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">失败返回</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">NULL</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">*/</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><STRONG><SPAN lang=EN-US
style="FONT-SIZE: 9pt">void *GC_Malloc(size_t size)</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> void *p =
malloc( size + INT_LEN )</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> if ( p == NULL
)</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> {</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
GC_Collect()</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
p = malloc( size + INT_LEN )</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
if ( p == NULL )</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
return NULL</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
}</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> }</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
HashTable_Insert( g_pTable, p, HashInt)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> *((INT *)p) =
0</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> return (void
*)((char *)p+INT_LEN)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN></P>
<P class=4 style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US>/**
</SPAN><SPAN style="FONT-FAMILY: 华康简宋">垃圾收集函数，遍历哈希表，将所有引用计数为</SPAN><SPAN
lang=EN-US>0</SPAN><SPAN style="FONT-FAMILY: 华康简宋">的内存释放</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> @return
void</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.2pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">无</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> </SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">*/</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><STRONG><SPAN lang=EN-US
style="FONT-SIZE: 9pt">void GC_Collect()</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14.3pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> void
*p</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
HashTable_EnumBegin(g_pTable)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> while ( (p =
HashTable_EnumNext(g_pTable)) != NULL )</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> {</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
INT *pRef = (INT *)p</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -