ConcurrentClosed.h

Header of the layer astar, in the group Data structures; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
ConcurrentClosed	The closed list shared by the workers, a lock-free set of the nodes

Description of the header

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.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright