📄 group__hash.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>Othello Solver: Hash table module</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="modules.html">Modules</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a></div><h1>Hash table module</h1><table border=0 cellpadding=0 cellspacing=0><tr><td></td></tr><tr><td colspan=2><br><h2>Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>unsigned long </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga0">hash_random</a> (void)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Pseudo-random number generator. <a href="#ga0"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga1">hash_init</a> (<a class="el" href="structHashTable.html">HashTable</a> *hash_table, int n_bits)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Initialise the hashtable. <a href="#ga1"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga2">hash_clear</a> (<a class="el" href="structHashTable.html">HashTable</a> *hash_table)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Clear the hashtable. <a href="#ga2"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga3">hash_free</a> (<a class="el" href="structHashTable.html">HashTable</a> *hash_table)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Free the hashtable. <a href="#ga3"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga4">hash_update</a> (<a class="el" href="structHashTable.html">HashTable</a> *hash_table, const <a class="el" href="structBoard.html">Board</a> *board, int alpha, int beta, int score, int move)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Update an hashtable entry. <a href="#ga4"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top><a class="el" href="structHash.html">Hash</a> * </td><td class="memItemRight" valign=bottom><a class="el" href="group__hash.html#ga5">hash_get</a> (<a class="el" href="structHashTable.html">HashTable</a> *hash_table, const <a class="el" href="structBoard.html">Board</a> *board)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find an hash table entry according to the evaluated board hash codes. <a href="#ga5"></a><br><br></td></tr></table><hr><a name="_details"></a><h2>Detailed Description</h2>The hash table is an efficient memory system to remember the previously analysed positions and re-use the collected data when needed. The hash table contains entries of analysed data where the board is uniquely identified through a 32-bit key and the results of the analysis recorded are two score bounds, the depth of the analysis and the best move found.<p>For more information about how this hash table implementation works, you may read: Breuker D.M., Uiterwijk J.W.H.M. & van den Herik H.J. (1996) Replacement Schemes and Two-Level Tables. ICCA J 19-3 p 183-193. <hr><h2>Function Documentation</h2><a class="anchor" name="ga2" doxytag="solver.c::hash_clear" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void hash_clear </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="structHashTable.html">HashTable</a> * </td> <td class="mdname1" valign="top" nowrap> <em>hash_table</em> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Clear the hashtable. <p>Set all hash table entries to zero. <dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>hash_table</em> </td><td>hash table to clear. </td></tr> </table></dl><p><div class="fragment"><pre>00652 {00653 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> i;00654 <span class="keyword">static</span> <span class="keyword">const</span> <a class="code" href="structHashEntry.html">HashEntry</a> init_entry = {00655 {0, -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>, +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>, 0, 0},00656 {0, -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>, +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>, 0, 0}};00657 00658 <span class="keywordflow">if</span> (<a class="code" href="group__mac.html#ga51">HASH_TABLE_OK</a>(hash_table)) {00659 <span class="keywordflow">for</span> (i = 0; i <= hash_table-><a class="code" href="structHashTable.html#o1">hash_mask</a>; i++) {00660 hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a>[i] = init_entry;00661 }00662 }00663 }</pre></div> </td> </tr></table><a class="anchor" name="ga3" doxytag="solver.c::hash_free" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void hash_free </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="structHashTable.html">HashTable</a> * </td> <td class="mdname1" valign="top" nowrap> <em>hash_table</em> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Free the hashtable. <p>Free the memory allocated by the hash table entries <dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>hash_table</em> </td><td>hash_table to free. </td></tr> </table></dl><p><div class="fragment"><pre>00672 {00673 free(hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a>);00674 hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> = NULL;00675 }</pre></div> </td> </tr></table><a class="anchor" name="ga5" doxytag="solver.c::hash_get" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> <a class="el" href="structHash.html">Hash</a>* hash_get </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="structHashTable.html">HashTable</a> * </td> <td class="mdname" nowrap> <em>hash_table</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const <a class="el" href="structBoard.html">Board</a> * </td> <td class="mdname" nowrap> <em>board</em></td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Find an hash table entry according to the evaluated board hash codes. <p>The data recorded within the entry will then be used to reframe the alpha beta bounds and set the move to search first. In some cases, an alphabeta cut will be immediately found so avoiding the entire search and gaining a (lot of) time.<p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>hash_table</em> </td><td>: hash table. </td></tr> <tr><td valign=top><em>board</em> </td><td>: evaluated board. </td></tr> </table></dl><dl compact><dt><b>Returns:</b></dt><dd>: an hash table entry if the board was found, NULL otherwise. </dd></dl><p><div class="fragment"><pre>00759 {00760 <a class="code" href="structHashEntry.html">HashEntry</a> *hash_entry;00761 00762 <span class="keywordflow">if</span> (<a class="code" href="group__mac.html#ga51">HASH_TABLE_OK</a>(hash_table)) {00763 hash_entry = hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> + board-><a class="code" href="structBoard.html#o5">hash_code</a>[0];00764 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o5">hash_code</a>[1] == hash_entry-><a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o0">lock</a>)00765 <span class="keywordflow">return</span> &(hash_entry-><a class="code" href="structHashEntry.html#o0">deepest</a>);00766 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o5">hash_code</a>[1] == hash_entry-><a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o0">lock</a>)00767 <span class="keywordflow">return</span> &(hash_entry-><a class="code" href="structHashEntry.html#o1">newest</a>);00768 }00769 <span class="keywordflow">return</span> NULL;00770 }</pre></div> </td> </tr></table><a class="anchor" name="ga1" doxytag="solver.c::hash_init" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void hash_init </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="structHashTable.html">HashTable</a> * </td> <td class="mdname" nowrap> <em>hash_table</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>int </td> <td class="mdname" nowrap> <em>n_bits</em></td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -