00001
00002
00003 #include "osl/ntesuki/ntesukiTable.h"
00004 #include "osl/ntesuki/ntesukiTable.tcc"
00005 #include "osl/ntesuki/ntesukiRecord.h"
00006 #include "osl/ntesuki/ntesukiSearcher.h"
00007 #include "osl/state/numEffectState.h"
00008 #include "osl/move_classifier/moveAdaptor.h"
00009 #include "osl/effect_util/effectUtil.h"
00010 #include "osl/record/csaRecord.h"
00011 #ifdef NDEBUG
00012 # include "osl/ntesuki/ntesukiRecord.tcc"
00013 #endif
00014 #include <iostream>
00015 #include <queue>
00016 #include <set>
00017
00018 int osl::ntesuki::NtesukiTable::Table::
00019 largeGCCount = 0;
00020
00021 osl::ntesuki::NtesukiTable::Table::
00022 Table(unsigned int c,
00023 unsigned int g,
00024 bool v)
00025 : ntesuki_hash_map(c), capacity(c), default_gc_size(g),
00026 verbose(v), no_gc(false), gc_request(false),
00027 numEntry(0), numCacheHit(0), gcCount(0)
00028 {
00029 }
00030
00031 osl::ntesuki::NtesukiTable::Table::
00032 ~Table()
00033 {
00034 }
00035
00036 osl::ntesuki::NtesukiRecord *
00037 osl::ntesuki::NtesukiTable::Table::
00038 allocate(const HashKey& key,
00039 const PieceStand& white_stand,
00040 signed short distance)
00041 {
00042 int full = 0;
00043 reallocate:
00044 if (numEntry < capacity || no_gc)
00045 {
00046 if (numEntry >= capacity) gc_request = true;
00047 NtesukiRecord::RecordList *record_list =
00048 &(ntesuki_hash_map::operator[](key.getSignatureKey()));
00049 for (NtesukiRecord::RecordList::iterator p = record_list->begin();
00050 p != record_list->end(); ++p)
00051 {
00052 if (p->key.getPieceStand() == key.getPieceStand())
00053 {
00054 ++numCacheHit;
00055 return &(*p);
00056 }
00057 }
00058
00059 ++numEntry;
00060 const NtesukiRecord r(distance, key, white_stand, record_list);
00061 record_list->push_front(r);
00062 NtesukiRecord *result = &(record_list->front());
00063 return result;
00064 }
00065
00066 NtesukiRecord *result = find(key);
00067 if (result == 0 && full++ == 0 && capacity)
00068 {
00069 if (default_gc_size > 0)
00070 {
00071 collectGarbage(default_gc_size);
00072 goto reallocate;
00073 }
00074 }
00075 return result;
00076 }
00077
00078 struct CompareChildSize
00079 {
00080 bool operator()(const osl::ntesuki::NtesukiRecord *lhs,
00081 const osl::ntesuki::NtesukiRecord *rhs)
00082 {
00083 return lhs->getChildCount() < rhs->getChildCount();
00084 }
00085 };
00086
00087 struct RecordPrinter
00088 {
00089
00090
00091
00092 osl::state::NumEffectState &state;
00093 osl::ntesuki::NtesukiTable::Table &table;
00094 std::vector<osl::ntesuki::NtesukiRecord*> records;
00095 std::set<HashKey> read_keys;
00096 int depth, pass_count, pass_depth;
00097
00098 RecordPrinter(osl::state::NumEffectState &s,
00099 osl::ntesuki::NtesukiTable::Table &t,
00100 osl::ntesuki::NtesukiRecord *r)
00101 : state(s), table(t),
00102 depth(-1), pass_count(0)
00103 {
00104 }
00105
00106 void enter(osl::ntesuki::NtesukiRecord *r)
00107 {
00108 read_keys.insert(r->key);
00109 records.push_back(r);
00110 ++depth;
00111 }
00112 void exit()
00113 {
00114 read_keys.erase(records.back()->key);
00115 records.pop_back();
00116 if (pass_depth) pass_count--;
00117 --depth;
00118 }
00119 bool withChildMove(const osl::ntesuki::NtesukiMove& move,
00120 osl::ntesuki::NtesukiRecord *child)
00121 {
00122 if (move.isPass())
00123 {
00124 if (pass_count) return false;
00125 pass_count++;
00126 pass_depth = depth;
00127 }
00128
00129 if (read_keys.find(child->key) != read_keys.end())
00130 {
00131 return false;
00132 }
00133
00134 int i = 0;
00135 for (; i <= depth; i++) std::cerr << "*";
00136 std::cerr << record::csa::show(move.getMove());
00137 for (; i <= 11; i++) std::cerr << " ";
00138
00139 if (child->isVisited()) std::cerr << "(*)";
00140 if (depth > 8)
00141 {
00142 std::cerr << "\t" << child->getChildCount() << "\t"
00143 << child->getValue<BLACK>(0) << " \t"
00144 << child->getValue<BLACK>(1) << " |\n";
00145 return false;
00146 }
00147 else
00148 {
00149 std::cerr << "\t" << child->getChildCount() << "\t"
00150 << child->getValue<BLACK>(0) << " \t"
00151 << child->getValue<BLACK>(1) << "\n";
00152 }
00153 return true;
00154 }
00155
00156 void noChildMove(const osl::ntesuki::NtesukiMove& move)
00157 {
00158 }
00159
00160 bool operator()(const osl::ntesuki::NtesukiMove& lhs,
00161 const osl::ntesuki::NtesukiMove& rhs)
00162 {
00163 osl::ntesuki::NtesukiRecord *record = records.back();
00164 ntesuki_assert(record);
00165 NtesukiRecord *lchild = table.find(record->key.newHashWithMove(lhs.getMove()));
00166 if (!lchild) return false;
00167 NtesukiRecord *rchild = table.find(record->key.newHashWithMove(rhs.getMove()));
00168 if (!rchild) return true;
00169
00170 if (lchild->isVisited()) return true;
00171 if (rchild->isVisited()) return false;
00172 return lchild->getChildCount() > rchild->getChildCount();
00173 }
00174 struct Compare
00175 {
00176 bool operator()(const osl::ntesuki::NtesukiMove& lhs,
00177 const osl::ntesuki::NtesukiMove& rhs)
00178 {
00179 return lhs.getMove() < rhs.getMove();
00180 }
00181 };
00182 };
00183
00184 struct RecordPrinter2
00185 {
00186
00187
00188
00189
00190 osl::state::NumEffectState &state;
00191 osl::ntesuki::NtesukiTable::Table &table;
00192 std::vector<osl::ntesuki::NtesukiRecord*> records;
00193 std::set<HashKey> read_keys;
00194 int depth, pass_count, pass_depth, depth_visited;
00195
00196 RecordPrinter2(osl::state::NumEffectState &s,
00197 osl::ntesuki::NtesukiTable::Table &t,
00198 osl::ntesuki::NtesukiRecord *r)
00199 : state(s), table(t),
00200 depth(-1), pass_count(0), pass_depth(0), depth_visited(0)
00201 {
00202 }
00203
00204 void enter(osl::ntesuki::NtesukiRecord *r)
00205 {
00206 if (r->isVisited()) ++depth_visited;
00207 read_keys.insert(r->key);
00208 records.push_back(r);
00209 ++depth;
00210 }
00211 void exit()
00212 {
00213 read_keys.erase(records.back()->key);
00214 records.pop_back();
00215 if (pass_depth) pass_count--;
00216 --depth;
00217 }
00218 bool withChildMove(const osl::ntesuki::NtesukiMove& move,
00219 osl::ntesuki::NtesukiRecord *child)
00220 {
00221 if (move.isPass())
00222 {
00223 if (pass_count) return false;
00224 pass_count++;
00225 pass_depth = depth;
00226 }
00227
00228 bool result = true;
00229
00230 if (depth < depth_visited)
00231 {
00232 return false;
00233 }
00234
00235 int i = 0;
00236 for (; i <= depth; i++) std::cerr << "*";
00237 for (; i <= 10; i++) std::cerr << " ";
00238 std::cerr << record::csa::show(move.getMove());
00239 if (child->isVisited()) std::cerr << "(*)";
00240 if (read_keys.find(child->key) != read_keys.end())
00241 {
00242 std::cerr << "loop";
00243 result = false;
00244 }
00245
00246 std::cerr << "\t" << child->getChildCount() << "\t"
00247 << child->getValue<osl::BLACK>(0) << "\t"
00248 << child->getValue<osl::BLACK>(1) << "\n";
00249
00250 return result;
00251 }
00252
00253 void noChildMove(const osl::ntesuki::NtesukiMove& move)
00254 {
00255 if (depth < depth_visited)
00256 {
00257 return;
00258 }
00259 int i = 0;
00260 for (; i <= depth; i++) std::cerr << "*";
00261 for (; i <= 10; i++) std::cerr << " ";
00262 std::cerr << record::csa::show(move.getMove())
00263 << "|\t"
00264 << move.h_a_proof << "/" << move.h_a_disproof << "\t"
00265 << move.h_d_proof << "/" << move.h_d_disproof
00266 << "\n";
00267 }
00268
00269 bool operator()(const osl::ntesuki::NtesukiMove& lhs,
00270 const osl::ntesuki::NtesukiMove& rhs)
00271 {
00272 osl::ntesuki::NtesukiRecord *record = records.back();
00273 ntesuki_assert(record);
00274 NtesukiRecord *lchild = table.find(record->key.newHashWithMove(lhs.getMove()));
00275 if (!lchild) return false;
00276 NtesukiRecord *rchild = table.find(record->key.newHashWithMove(rhs.getMove()));
00277 if (!rchild) return true;
00278
00279 if (lchild->isVisited()) return true;
00280 if (rchild->isVisited()) return false;
00281 return lchild->getChildCount() > rchild->getChildCount();
00282 }
00283
00284 struct Compare
00285 {
00286 bool operator()(const osl::ntesuki::NtesukiMove& lhs,
00287 const osl::ntesuki::NtesukiMove& rhs)
00288 {
00289 return lhs.getMove() < rhs.getMove();
00290 }
00291 };
00292 };
00293
00294 struct
00295 MarkAndSweep
00296 {
00297 osl::state::NumEffectState &state;
00298 osl::ntesuki::NtesukiTable::Table &table;
00299 std::set<HashKey> reachable_keys;
00300 int depth;
00301
00302 MarkAndSweep(osl::state::NumEffectState &s,
00303 osl::ntesuki::NtesukiTable::Table &t,
00304 osl::ntesuki::NtesukiRecord *r)
00305 : state(s), table(t)
00306 {
00307 }
00308
00309 ~MarkAndSweep()
00310 {
00311 typedef std::vector<HashKey> keys_t;
00312 keys_t garbage_list;
00313 for (osl::ntesuki::NtesukiTable::Table::iterator it = table.begin();
00314 it != table.end(); ++it)
00315 {
00316 for (NtesukiRecord::RecordList::iterator p = it->second.begin();
00317 p != it->second.end(); ++p)
00318 {
00319 NtesukiRecord *record = &(*p);
00320 if (reachable_keys.find(record->key) == reachable_keys.end())
00321 {
00322 garbage_list.push_back(record->key);
00323 }
00324 else
00325 {
00326 reachable_keys.erase(record->key);
00327 }
00328 }
00329 }
00330 for (keys_t::iterator it = garbage_list.begin();
00331 it != garbage_list.end(); ++it)
00332 {
00333 table.erase(*it);
00334 }
00335 }
00336 void enter(osl::ntesuki::NtesukiRecord *r)
00337 {
00338 reachable_keys.insert(r->key);
00339 }
00340 void exit()
00341 {
00342 }
00343
00344 bool withChildMove(const osl::ntesuki::NtesukiMove& move,
00345 osl::ntesuki::NtesukiRecord *child)
00346 {
00347 return reachable_keys.find(child->key) == reachable_keys.end();
00348 }
00349
00350 void noChildMove(const osl::ntesuki::NtesukiMove& move)
00351 {
00352 }
00353
00354 struct Compare
00355 {
00356 bool operator()(const osl::ntesuki::NtesukiMove& lhs,
00357 const osl::ntesuki::NtesukiMove& rhs)
00358 {
00359 return lhs.getMove() < rhs.getMove();
00360 }
00361 };
00362 };
00363
00364 void
00365 osl::ntesuki::NtesukiTable::Table::
00366 collectGarbage(unsigned int gc_size)
00367 {
00368 if (gc_size == 0)
00369 {
00370 throw TableFull();
00371 }
00372 if (largeGCCount >= 0 &&
00373 gcCount >= static_cast<unsigned int>(largeGCCount))
00374 {
00375 if (verbose)
00376 {
00377 std::cerr << "\ntoo many GCs, failing\n\n";
00378
00379 }
00380 throw TableFull();
00381 }
00382 ++gcCount;
00383 #if 0
00384 const unsigned int garbage_size = numEntry - gc_size;
00385 if (verbose)
00386 {
00387 std::cerr << "GC: ";
00388 for (int i = 0; i < 2; i++)
00389 {
00390 std::cerr << root->getValue<BLACK>(i) << "\t"
00391 << root->getValue<WHITE>(i) << "\t";
00392 }
00393 std::cerr << " " << numEntry << " -> ";
00394 }
00395
00396 std::priority_queue<NtesukiRecord *,
00397 std::vector<NtesukiRecord *>,
00398 CompareChildSize> garbage_list;
00399
00400 for (iterator it = begin(); it != end(); ++it)
00401 {
00402 for (NtesukiRecord::RecordList::iterator p = it->second.begin();
00403 p != it->second.end(); ++p)
00404 {
00405 NtesukiRecord *record = &(*p);
00406 if (record->isVisited()
00407
00408 )
00409 {
00410 record->addChildCount(garbage_size);
00411 continue;
00412 }
00413
00414 garbage_list.push(record);
00415 if (garbage_list.size() > garbage_size)
00416 {
00417 garbage_list.pop();
00418 }
00419 }
00420 }
00421
00422 std::cerr << "\n*before GC\n";
00423
00424 forEachRecordFromRoot<RecordPrinter2>();
00425
00426 while (!garbage_list.empty())
00427 {
00428 NtesukiRecord *garbage = garbage_list.top();
00429 erase(garbage->key);
00430 garbage_list.pop();
00431 }
00432
00433 if (verbose)
00434 {
00435 std::cerr << numEntry << "\n";
00436 }
00437 std::cerr << "*after GC\n";
00438 forEachRecordFromRoot<RecordPrinter2>();
00439
00440
00441 #else
00442 if (verbose)
00443 {
00444 std::cerr << "GC: ";
00445 for (int i = 0; i < 2; i++)
00446 {
00447 std::cerr << root->getValue<BLACK>(i) << "\t"
00448 << root->getValue<WHITE>(i) << "\t";
00449 }
00450 std::cerr << "\n";
00451 }
00452
00453
00454
00455
00456 unsigned int orig_size = numEntry;
00457 unsigned int small_subtree_size = 1,
00458 garbage_size = 0;
00459 while (numEntry > gc_size)
00460 {
00461 for (iterator list_it = begin();
00462 list_it != end(); ++list_it)
00463 {
00464
00465
00466
00467
00468
00469
00470
00471
00472 retry_collect_list:
00473 for (NtesukiRecord::RecordList::iterator r = list_it->second.begin();
00474 r != list_it->second.end(); ++r)
00475 {
00476 NtesukiRecord *record = &(*r);
00477
00478 if (record->isVisited())
00479 {
00480 continue;
00481 }
00482 if (record->getChildCount() < small_subtree_size
00483 && record->rev_refcount == 0)
00484 {
00485 ++garbage_size;
00486 --numEntry;
00487 for (NtesukiRecord::RecordPList::const_iterator pit = record->parents.begin();
00488 pit != record->parents.end(); ++pit)
00489 {
00490 (*pit)->rev_refcount--;
00491 }
00492 list_it->second.erase(r);
00493 goto retry_collect_list;
00494 }
00495 }
00496 }
00497 #ifdef MARK_AND_SWEEP_AFTER_SMALLTREEGC
00498 unsigned int before_mark_and_sweep = numEntry;
00499 forEachRecordFromRoot<MarkAndSweep>();
00500 garbage_size += before_mark_and_sweep - numEntry;
00501 #endif
00502
00503 small_subtree_size += 4;
00504 }
00505 small_subtree_size -= 4;
00506
00507 for (iterator it = begin(); it != end(); ++it)
00508 {
00509 for (NtesukiRecord::RecordList::iterator p = it->second.begin();
00510 p != it->second.end(); ++p)
00511 {
00512 NtesukiRecord *record = &(*p);
00513 if (record->isVisited())
00514 {
00515 record->addChildCount(garbage_size);
00516 }
00517 }
00518 }
00519
00520 if (verbose)
00521 {
00522 std::cerr << numEntry << "\tcollected up to " << small_subtree_size << "\n";
00523 std::cerr << " " << orig_size << " -> " << numEntry << "\n";
00524 }
00525
00526
00527
00528
00529
00530 #endif
00531 }
00532
00533 osl::ntesuki::NtesukiRecord *
00534 osl::ntesuki::NtesukiTable::Table::
00535 find(const HashKey& key)
00536 {
00537 ntesuki_hash_map::iterator hit =
00538 ntesuki_hash_map::find(key.getSignatureKey());
00539 if (hit == ntesuki_hash_map::end())
00540 {
00541 return 0;
00542 }
00543 for (NtesukiRecord::RecordList::iterator p = hit->second.begin();
00544 p != hit->second.end(); ++p)
00545 {
00546 if (p->key.getPieceStand() == key.getPieceStand())
00547 {
00548 ++numCacheHit;
00549 return &(*p);
00550 }
00551 }
00552 return 0;
00553 }
00554
00555 void
00556 osl::ntesuki::NtesukiTable::Table::
00557 erase(const HashKey key)
00558 {
00559 ntesuki_hash_map::iterator hit =
00560 ntesuki_hash_map::find(key.getSignatureKey());
00561 if (hit == ntesuki_hash_map::end())
00562 {
00563 return;
00564 }
00565 for (NtesukiRecord::RecordList::iterator p = hit->second.begin();
00566 p != hit->second.end(); ++p)
00567 {
00568 if (p->key.getPieceStand() == key.getPieceStand())
00569 {
00570 hit->second.erase(p);
00571 --numEntry;
00572 return;
00573 }
00574 }
00575 }
00576
00577 osl::ntesuki::NtesukiTable::
00578 NtesukiTable(unsigned int capacity,
00579 unsigned int gc_size,
00580 bool verbose)
00581 : table(new Table(capacity, gc_size, verbose)),
00582 verbose(verbose),
00583 depths(200,0)
00584 {}
00585
00586 osl::ntesuki::NtesukiTable::
00587 ~NtesukiTable()
00588 {
00589
00590
00591 if (verbose)
00592 {
00593 std::cerr << "~NtesukiTable size " << size()
00594 << ", cache hit " << table->numCacheHit
00595 << ", table full " << table->gcCount << "\n";
00596
00597 ntesuki_hash_map::const_iterator hit = this->begin();
00598 while (hit != this->end())
00599 {
00600 const NtesukiRecord::RecordList& record_list = hit->second;
00601 for (NtesukiRecord::RecordList::const_iterator p = record_list.begin();
00602 p != record_list.end(); ++p)
00603 {
00604 const NtesukiRecord& r = *p;
00605 const unsigned short d = r.distance;
00606 if (d >= 200)
00607 {
00608 std::cerr << d << r << "\n";
00609 }
00610 depths[d]++;
00611 }
00612 hit++;
00613 }
00614
00615 for (int depth = 0; depth < 200; depth++)
00616 {
00617 if (depths[depth] != 0)
00618 {
00619 std::cerr << "depth: " << depth << " " << depths[depth] << "\n";
00620 }
00621 }
00622 }
00623 }
00624
00625 bool osl::ntesuki::NtesukiTable::
00626 isVerbose() const
00627 {
00628 return verbose;
00629 }
00630
00631
00632
00633
00634