00001
00002
00003 #ifndef _ARRAY_CHECK_HASHTABLE_H
00004 #define _ARRAY_CHECK_HASHTABLE_H
00005
00006 #include "osl/checkmate/sameBoardList.h"
00007 #include "osl/checkmate/twinTable.h"
00008 #include "osl/checkmate/visitedCounter.h"
00009 #include "osl/hash/hashKey.h"
00010 #include <boost/scoped_array.hpp>
00011 #include <cassert>
00012
00013 #define BOOST_DISABLE_ASSERTS
00014 namespace osl
00015 {
00016 class PathEncoding;
00017 namespace checkmate
00018 {
00019 class CheckHashRecord;
00027 class ArrayCheckHashTable : public TwinTableHolder, public VisitedCounter
00028 {
00029 struct BoardEntry
00030 {
00031 hash::BoardKey board_key;
00032 SameBoardList colleagues;
00033 void setKey(const HashKey& key)
00034 {
00035 board_key = key.getSignatureKey().getBoardKey();
00036 }
00037 bool unused() const { return colleagues.empty(); }
00039 bool equalKey(const HashKey& key) const
00040 {
00041 return board_key == key.getSignatureKey().getBoardKey();
00042 }
00043 CheckHashRecord *find(const HashKey& key)
00044 {
00045 return colleagues.find(key.blackStand());
00046 }
00047 const CheckHashRecord *find(const HashKey& key) const
00048 {
00049 return colleagues.find(key.blackStand());
00050 }
00051 template <Player Attacker>
00052 CheckHashRecord *allocate(const HashKey& key,
00053 const PieceStand& white_stand,
00054 const PathEncoding& path, size_t& counter)
00055 {
00056 return colleagues.template allocate<Attacker>
00057 (key.blackStand(), white_stand, path, counter);
00058 }
00059 };
00060 typedef slist<BoardEntry> list_t;
00061 struct ElementList
00062 {
00063 BoardEntry elem;
00064 list_t list;
00065
00066 template <Player Attacker>
00067 CheckHashRecord *allocate(const HashKey& key,
00068 const PieceStand& white_stand,
00069 const PathEncoding& path, size_t& counter)
00070 {
00071 if (elem.equalKey(key))
00072 return elem.template allocate<Attacker>(key, white_stand, path, counter);
00073 if (elem.unused())
00074 {
00075 elem.setKey(key);
00076 return elem.template allocate<Attacker>(key, white_stand, path, counter);
00077 }
00078 for (list_t::iterator p=list.begin(); p!=list.end(); ++p)
00079 {
00080 if (p->equalKey(key))
00081 return (*p).template allocate<Attacker>(key, white_stand, path, counter);
00082 }
00083 list.push_front(BoardEntry());
00084 list.front().setKey(key);
00085 return list.front().template allocate<Attacker>(key, white_stand, path, counter);
00086 }
00087
00088 CheckHashRecord *find(const HashKey& key)
00089 {
00090 if (elem.equalKey(key))
00091 return elem.find(key);
00092 for (list_t::iterator p=list.begin(); p!=list.end(); ++p)
00093 {
00094 if (p->equalKey(key))
00095 return p->find(key);
00096 }
00097 return 0;
00098 }
00099 const CheckHashRecord *find(const HashKey& key) const
00100 {
00101 if (elem.equalKey(key))
00102 return elem.find(key);
00103 for (list_t::const_iterator p=list.begin(); p!=list.end(); ++p)
00104 {
00105 if (p->equalKey(key))
00106 return p->find(key);
00107 }
00108 return 0;
00109 }
00110 };
00111 static const size_t bucketSize = 786433ul;
00112 boost::scoped_array<ElementList> buckets;
00113 size_t numElements;
00114 const Player attacker;
00115 static unsigned int makeHash(const HashKey& key)
00116 {
00117 return key.getSignature() % bucketSize;
00118 }
00119 CheckHashRecord rootNode;
00120 public:
00121 explicit ArrayCheckHashTable(Player attacker);
00122 ~ArrayCheckHashTable();
00123 CheckHashRecord *find(const HashKey& key);
00124 CheckHashRecord *allocate(const HashKey& key,
00125 const PieceStand& white_stand,
00126 const PathEncoding& path);
00127 CheckHashRecord *root() { return &rootNode; }
00128 void clear();
00129
00130 const CheckHashRecord *find(const HashKey& key) const;
00131 size_t size() const { return numElements; }
00132 Player getAttacker() const { return attacker; }
00133 void confirmNoVisitedRecords() const;
00134 };
00135
00136 inline
00137 const CheckHashRecord* ArrayCheckHashTable::find(const HashKey& key) const
00138 {
00139 const ElementList& e = buckets[makeHash(key)];
00140 return e.find(key);
00141 }
00142 inline
00143 CheckHashRecord* ArrayCheckHashTable::find(const HashKey& key)
00144 {
00145 ElementList& e = buckets[makeHash(key)];
00146 return e.find(key);
00147 }
00148 inline
00149 CheckHashRecord* ArrayCheckHashTable::
00150 allocate(const HashKey& key, const PieceStand& white_stand,
00151 const PathEncoding& path)
00152 {
00153 ElementList& e = buckets[makeHash(key)];
00154 if (attacker == BLACK)
00155 return e.allocate<BLACK>(key, white_stand, path, numElements);
00156 else
00157 return e.allocate<WHITE>(key, white_stand, path, numElements);
00158 }
00159
00160 }
00161 }
00162
00163 #endif
00164
00165
00166
00167