- Generated by
1.15.0
|
PBeFS
Parallel Best-First Search
|
Header file for the class template ConcurrentClosed of the set of data structures of ADS [see Structures.h]: the nodes are kept in the ConcurrentFlatTable of ADS as a set of pointers compared by their states, a word of 8 bytes for each, which a lookup reads and an insertion fills by a compare-and-swap with no lock. More...
#include <atomic>#include <cstddef>#include <cstdint>#include <memory>#include <mutex>#include <variant>#include "ADS/concurrent/ConcurrentFlatTable.h"#include "PBeFS/astar/Domain.h"#include "PBeFS/astar/Node.h"#include "PBeFS/core/SearchUtils.h"Go to the source code of this file.
Classes | |
| class | ConcurrentClosed< D, Lock > |
| the closed list shared by the workers, a lock-free set of the nodes More... | |
| struct | ConcurrentClosed< D, Lock >::Local |
| the nodes that a worker allocates, and its spare node More... | |
| struct | ConcurrentClosed< D, Lock >::Successor |
| a state generated, with its g, its h and its hash More... | |
Namespaces | |
| namespace | PBeFS_di_unipi_it |
| namespace for the Parallel Best-First Search library | |
Header file for the class template ConcurrentClosed of the set of data structures of ADS [see Structures.h]: the nodes are kept in the ConcurrentFlatTable of ADS as a set of pointers compared by their states, a word of 8 bytes for each, which a lookup reads and an insertion fills by a compare-and-swap with no lock.
The fields that change are protected by 256 locks, the lock of a node chosen by its address, and update() takes it only when the state is already in the table and g is smaller than its g read without the lock: since the g of a node only decreases, a g read without the lock is never smaller than the one under it, and a duplicate, the most frequent case, takes no lock. The g of a node is read without the lock, and written under it, as an std::atomic_ref. A worker fills a spare node with the state before inserting it, and keeps it for the next update() if the state was in the table, so that the node is allocated once per state inserted. prefetch() fetches the line of the tags and that of the word of the place of a hash, as the ConcurrentFlatTable does.
1.15.0