Ну, вы уже определили тот, который я обычно предлагал бы - параллельный пропускающий список, но отсутствие других специфических требований, кроме трех приведенных выше, думаю, будет работать простой связанный список с мьютексами для каждого узла:
Каждый узел содержит один элемент (или ссылку) и один простой мьютекс. Я предполагаю Java здесь, потому что это помогает избежать условий гонки вокруг восстановления узла.
Поиск по списку состоит из итерации по узлам из головы, нет необходимости получать какие-либо блокировки (хотя вам нужно будет обеспечить видимость между потоками в какой-то момент - вы можете выбрать, как часто это происходит - один раз за поиск может будь достаточно хорош).
Чтобы добавить элемент, выполняйте поиск, пока не найдете непосредственные узлы предшественника и преемника для значения, которое вы хотите вставить, заблокируйте мьютекс, связанный с предыдущим узлом, снова проверьте узел-преемник (он мог измениться из-под вы), затем соедините новый узел.
Удаление работает аналогично - найдите узел-предшественник для узла, который вы хотите удалить, заблокируйте узел-предшественник, убедитесь, что он все еще является узлом-предшественником, и извлеките его из дерева.
Эта структура отсортирована (в той степени, в которой она правильная - я этого не доказал!).
Эта структура явно позволяет нескольким читателям (читатели никогда не блокируются по любой причине) и множеству писателей, хотя писатели, пытающиеся манипулировать одной и той же частью списка (например, два потока, вставляющие узлы, имеющие одинаковую точку соединения), будут ждать друг на друга.
Кажется, структура относительно проста: она основана на одном связанном списке, с довольно простой структурой блокировки и несколькими простыми инвариантами. Однако я потратил не более нескольких минут, рассуждая о его правильности. Вы можете упростить рассуждения ценой производительности, сделав политику блокировки более тяжелой - для вставки и удаления блокируйте каждый узел во время итерации, а затем блокируйте преемник перед разблокировкой предыдущего узла - таким образом вы будете заблокируйте оба узла, когда вы найдете точку сращивания или удаления, поэтому «двойная проверка, возврат назад» не требуется.
Возможно, вам удастся полностью избавиться от блокировок и использовать список без блокировок, сохраняя при этом ваше условие «должны быть отсортированы», но я не задумывался об этом подробно - как минимум я подозреваю, что это будет «Труднее рассуждать».
В C ++ структура более сложна, так как вы не можете полагаться на то, что GC будет держать узлы так долго, как читатели могут на них смотреть, поэтому простая стратегия - позволить читателям перемещаться в замке. свободный способ не летит, если вы когда-нибудь захотите удалить узлы. Вы можете настроить его, заставив читателей захватить блокировку каждого посещенного узла, но это отстой как для производительности (очевидной), так и для параллелизма (потому что хотя у вас может быть несколько читателей и писателей в некотором базовом смысле, они больше никогда не смогут проходить друг друга, поэтому практический параллелизм сильно ограничен).
Альтернативой может быть использование rwlocks в каждом узле, считыватели берут только блокировки чтения, а инсерторы / удалители берут блокировки чтения, чтобы найти положение для работы, а затем переходят в режим записи. Валюта, по крайней мере, улучшена, поскольку читатели могут передавать читателей, но писатели по-прежнему блокируют читателей (поэтому все читатели, которые выполняют итерацию в позиции перед каким-либо узлом, на котором начинается операция записи, не смогут выполнять итерацию мимо этого узла, пока операция не завершится).
Теперь, все сказанное (вот так!) Я должен упомянуть, что другая, «легко рассуждающая» об этой структуре, во всех существенных отношениях кажется значительно уступающей списку одновременных пропусков, с возможным исключением чуть меньшего использования памяти ( может быть). В частности, он не имеет поведения поиска по log (N). Он не полностью свободен от блокировки (в некоторых случаях авторы могут ждать писателей). Я даже не уверен, что гораздо проще рассуждать о параллелизме, хотя основная структура проста.
Я думаю, что если вы действительно хотите, вы можете расширить этот тип блокировки для каждого узла на что-то вроде rb-дерева, если хотите, но это не так просто. В частности, вам нужно найти какой-то узел для блокировки перед любым поворотом дерева, который является «достаточно высоким», чтобы вы могли быть уверены, что любой поток, желающий выполнить модификацию, которая повлияет на правильность вашего вращения, также попытается заблокировать тот же узел. В связанном списке это «узел-предшественник» - в AVL или RB-дереве это не так просто.