![][1] Lock-free list является основой многих интересных структур данных, — простейшего [hash map][2], где lock-free list используется как список коллизий, [split-ordered list][3], построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого [skip list][4], являющегося по сути иерархическим списком списков. В [предыдущей][5] статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).
Можно ли такой подход распространить на lock-free list?.. Посмотрим…
[Читать дальше →][6]

[1]: https://habrastorage.org/files/817/b38/f79/817b38f7937a41259c48998f2cb990a0.png
[2]: https://habrahabr.ru/post/250383/#MichaelList
[3]: https://habrahabr.ru/post/250523/
[4]: https://habrahabr.ru/post/250815/
[5]: https://habrahabr.ru/post/314948/
[6]: https://habrahabr.ru/post/317882/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut