Задача 2. Coarse-grained list/tree

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:8  

Условие

Задание: Атомарное дерево или список с блокировками грубой огранки.

Требуется разработать тривиальную реализацию блокировки для списка и дерева и многопоточные нагрузочные тесты, замеряется производительность. Именно тесты являют собой основную сложность в задании.

Итераторы захватывают весь контейнер на время выполнения какой-то операции. В то же время нет не обходимости держать блокировку всё время жизни итератора.

Кроме того, уже здесь мы будем использовать rwlock для возможности параллельного чтения.

Дополнительно можно проделать оптимизацию (+1 балл): вертикальное зонирование блокировок, где изменение refcount не блокируется чтением/изменением ссылок на смежные узлы. Тем не менее будьте бдительны: разделение одной блокировки на две даёт отенциальную возможность для гонок и атак! Нужно обязательно покрыть это тестами.

Как и ранее, гарантируется, что все операции всегда приводят к консистентному состоянию.

Формат входных данных

Отправьте ссылку на конкретный коммит в репозитории на Github, например

https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a

В качестве среды разработки укажите Answer text.

Примеры тестов

Стандартный вход Стандартный выход
1
0
1

0.077s 0.020s 13