Может ли кто-нибудь указать мне на алгоритм для сортированного поточно-безопасного атомарного (без блокировки) связанного списка / очереди приоритетов? Я знаю, как сделать сам связанный список, но теперь мне нужен отсортированный список. Я не уверен, является ли это незначительным изменением или значительным изменением дизайна по сравнению с несортированным списком, поэтому хотел бы увидеть существующий алгоритм, прежде чем я сделаю свой собственный.
Это не обязательно должен быть список (или технически отсортированный), но он ведет себя как приоритетная очередь со следующими свойствами:
- нижний элемент - это элемент с минимальным целочисленным значением поля
- доступ к низшему элементу в постоянное время
- модификация только через атомарные операции (без блокировок)
- вставка / удаление по линейному времени
Содержимое, скорее всего, будет указателем на структуру. Целочисленное поле для сортировки является одним из членов этой структуры.
Это для программы на C ++, но мне не нужны примеры кода, описание алгоритма в порядке. Алгоритмы, которые близки, но не совершенны, также приветствуются.