Debian Codegraph @

old-sample/legacy-checkmate/lib/arrayCheckHashTable.h

raw
1 /* arrayCheckHashTable.h
2 */
3 #ifndef _ARRAY_CHECK_HASHTABLE_H
4 #define _ARRAY_CHECK_HASHTABLE_H
5
6 #include "sameBoardList.h"
7 #include "twinTable.h"
8 #include "visitedCounter.h"
9 #include "osl/hash/hashKey.h"
10 #include <boost/scoped_array.hpp>
11 #include <cassert>
12
13 #define BOOST_DISABLE_ASSERTS
14 namespace osl
15 {
16 class PathEncoding;
17 namespace checkmate
18 {
19 class CheckHashRecord;
20 /**
21 * 詰将棋用のテーブル
22 * SimpleCheckHashTable の置換
23 *
24 * - bucket の先頭に要素を一つ配置しているところが普通のchain hash と違う
25 * - 類似局面を利用するために、まず盤上の駒で分類し、次に持駒で分類する
26 */
27 class ArrayCheckHashTable : public TwinTableHolder, public VisitedCounter
28 {
29 struct BoardEntry
30 {
31 hash::BoardKey board_key;
32 SameBoardList colleagues;
33 void setKey(const HashKey& key)
34 {
35 board_key = key.boardKey();
36 }
37 bool unused() const { return colleagues.empty(); }
38 /** value(1)は比較済であることが前提 */
39 bool equalKey(const HashKey& key) const
40 {
41 return board_key == key.boardKey();
42 }
43 CheckHashRecord *find(const HashKey& key)
44 {
45 return colleagues.find(key.blackStand());
46 }
47 const CheckHashRecord *find(const HashKey& key) const
48 {
49 return colleagues.find(key.blackStand());
50 }
51 template <Player Attacker>
52 CheckHashRecord *allocate(const HashKey& key,
53 const PieceStand& white_stand,
54 const PathEncoding& path, size_t& counter)
55 {
56 return colleagues.template allocate<Attacker>
57 (key.blackStand(), white_stand, path, counter);
58 }
59 };
60 typedef slist<BoardEntry> list_t;
61 struct ElementList
62 {
63 BoardEntry elem;
64 list_t list;
65
66 template <Player Attacker>
67 CheckHashRecord *allocate(const HashKey& key,
68 const PieceStand& white_stand,
69 const PathEncoding& path, size_t& counter)
70 {
71 if (elem.equalKey(key))
72 return elem.template allocate<Attacker>(key, white_stand, path, counter);
73 if (elem.unused())
74 {
75 elem.setKey(key);
76 return elem.template allocate<Attacker>(key, white_stand, path, counter);
77 }
78 for (list_t::iterator p=list.begin(); p!=list.end(); ++p)
79 {
80 if (p->equalKey(key))
81 return (*p).template allocate<Attacker>(key, white_stand, path, counter);
82 }
83 list.push_front(BoardEntry());
84 list.front().setKey(key);
85 return list.front().template allocate<Attacker>(key, white_stand, path, counter);
86 }
87
88 CheckHashRecord *find(const HashKey& key)
89 {
90 if (elem.equalKey(key))
91 return elem.find(key);
92 for (list_t::iterator p=list.begin(); p!=list.end(); ++p)
93 {
94 if (p->equalKey(key))
95 return p->find(key);
96 }
97 return 0;
98 }
99 const CheckHashRecord *find(const HashKey& key) const
100 {
101 if (elem.equalKey(key))
102 return elem.find(key);
103 for (list_t::const_iterator p=list.begin(); p!=list.end(); ++p)
104 {
105 if (p->equalKey(key))
106 return p->find(key);
107 }
108 return 0;
109 }
110 };
111 static const size_t bucketSize = 786433ul; // 1572869ul;
112 boost::scoped_array<ElementList> buckets;
113 size_t numElements;
114 const Player attacker;
115 static unsigned int makeHash(const HashKey& key)
116 {
117 return key.signature() % bucketSize;
118 }
119 CheckHashRecord rootNode;
120 public:
121 explicit ArrayCheckHashTable(Player attacker);
122 ~ArrayCheckHashTable();
123 CheckHashRecord *find(const HashKey& key);
124 CheckHashRecord *allocate(const HashKey& key,
125 const PieceStand& white_stand,
126 const PathEncoding& path);
127 CheckHashRecord *root() { return &rootNode; }
128 void clear();
129
130 const CheckHashRecord *find(const HashKey& key) const;
131 size_t size() const { return numElements; }
132 Player getAttacker() const { return attacker; }
133 void confirmNoVisitedRecords() const;
134 };
135
136 inline
137 const CheckHashRecord* ArrayCheckHashTable::find(const HashKey& key) const
138 {
139 const ElementList& e = buckets[makeHash(key)];
140 return e.find(key);
141 }
142 inline
143 CheckHashRecord* ArrayCheckHashTable::find(const HashKey& key)
144 {
145 ElementList& e = buckets[makeHash(key)];
146 return e.find(key);
147 }
148 inline
149 CheckHashRecord* ArrayCheckHashTable::
150 allocate(const HashKey& key, const PieceStand& white_stand,
151 const PathEncoding& path)
152 {
153 ElementList& e = buckets[makeHash(key)];
154 if (attacker == BLACK)
155 return e.allocate<BLACK>(key, white_stand, path, numElements);
156 else
157 return e.allocate<WHITE>(key, white_stand, path, numElements);
158 }
159
160 } // namespace checkmate
161 } // namespace osl
162
163 #endif /* _ARRAY_CHECK_HASHTABLE_H_ */
164 // ;;; Local Variables:
165 // ;;; mode:c++
166 // ;;; c-basic-offset:2
167 // ;;; End: