- // Breadcrumbs are used to mark nodes as being searched by a given thread
- struct Breadcrumb {
- std::atomic<Thread*> thread;
- std::atomic<Key> key;
- };
- std::array<Breadcrumb, 1024> breadcrumbs;
-
- // ThreadHolding structure keeps track of which thread left breadcrumbs at the given
- // node for potential reductions. A free node will be marked upon entering the moves
- // loop by the constructor, and unmarked upon leaving that loop by the destructor.
- struct ThreadHolding {
- explicit ThreadHolding(Thread* thisThread, Key posKey, int ply) {
- location = ply < 8 ? &breadcrumbs[posKey & (breadcrumbs.size() - 1)] : nullptr;
- otherThread = false;
- owning = false;
- if (location)
- {
- // See if another already marked this location, if not, mark it ourselves
- Thread* tmp = (*location).thread.load(std::memory_order_relaxed);
- if (tmp == nullptr)
- {
- (*location).thread.store(thisThread, std::memory_order_relaxed);
- (*location).key.store(posKey, std::memory_order_relaxed);
- owning = true;
- }
- else if ( tmp != thisThread
- && (*location).key.load(std::memory_order_relaxed) == posKey)
- otherThread = true;
- }
- }
-
- ~ThreadHolding() {
- if (owning) // Free the marked location
- (*location).thread.store(nullptr, std::memory_order_relaxed);
- }
-
- bool marked() { return otherThread; }
-
- private:
- Breadcrumb* location;
- bool otherThread, owning;
- };
-
- template <NodeType NT>