Подскажите какую структуру данных выбрать
Сделать отдельную структуру, из служебных полей и номера маркера, сортированную по служебным полям.
Бинарным поиском находишь маркер в добавочной структуре, потом по номеру маркера начального пакета можно вычислить необходимое смещение.
Острые углы: блокировка, переполнение маркера.
fnd* lnk_prev;
int sl_1,sl_2;
int marker; // или void* lnk_message;
fnd* lnk_next;
};
При поиске придется просматривать все по порядку, но очередь не надо блокирывать.
Для добавления новнового эл-та в цепочку так же придется пройтись поиском.
Метод вставки. создаем новую fnd. Ищем то место где она должна быть. Заполняем поля новой fnd. Меняем ссылочные поля соседей.
Максимальная ошибка: поток поиска не найдет элемент, вставляемый в данный момент.
Метод удаления. Удаляем fnd, на которую указывает буферный указатель (fnd с прошлрго шага). Ищем удаляемую fnd. Присваиваем буферному указателю ссылку на неё. Меняем ссылочные поля соседей.
Структура таким образом живет до удаления следуюшего сообщения.
Ошибка: поток поиска будет на структуре в момент удаления. После удаления из цепи lnk_next и lnk_prev по прежнему указывают на существующие элементы. Поиск продолжится.
С основной очередью можно поступить так же (я про буфер удаления).
Написал много текста и только сейчас понял суть вопроса.
Сделать по одному буферу удаления удаления в каждом потоке. Поток А проверяет буфер потока Б после вывода fnd из цепочки. Двойной вывод не страшен, а при выполнении условия дублирующая ссылка затирается. Косяк может возникнуть если поток А вклинится в поток Б между проверкой условия и занулением ссылки (обе ссылки занулятся -- утечка памяти), но по мойму это решаемо.
Максимальная ошибка: поток поиска не найдет элемент, вставляемый в данный момент.
Рассмотрим пример. Поток заполнения нашел место куда вставлять (определенный элемент). И тут его вытиснили. В это время поток поиска наткнулся на этот же элемент и "выковырял" его. Когда первый поток очнется он вставит, оставшийся хвостик к этому элементу, но елемент уже убрали из очереди и вся цепочка за ним потеряется.
Пример 2. Поток заполнения уже меняет ссылки и тут опять его обломали, но он успел хотябы предыдущего соседа направить на себя. Поток поиска проходит все до нашего нового елемента, но так как мы не успели поменять все ссылки, всё что идет за ним нам не известно. В лучшем случае когда вернется первый поток он доделает то, что закончил, и целостность очереди востановится. В худшем случае поток поиска захватит наш новый елемент. Тогда все что было за ним просто пропадет. Зато когда первый опять включится он пропавший конец привяжет к себе (найденому) елементу))))) Про то что после обработки память освобождается и первый поток ко всему еще испортит еще какито данные. Замена должна выполнятся атомарно.
Про буфера удаления вообще ничего непонял, чесно)
fnd* lnk_prev;
int sl_1,sl_2;
int marker; // или void* lnk_message;
fnd* lnk_next;
};
fnd a,b,c,d,e,*buff;
// исходное состояние
b.lnk_prev=&a; b.lnk_next=&d;
d.lnk_prev=&b; d.lnk_next=&e;
// добавляем c между d и b
/* step 1 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&d;// d и b остадись как были
d.lnk_prev=&b; d.lnk_next=&e;
/* step 2 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&с;// b изменилось
d.lnk_prev=&b; d.lnk_next=&e;
/* step 3 */
c.lnk_prev=&b; c.lnk_next=&d;
b.lnk_prev=&a; b.lnk_next=&с;// d изменилось
d.lnk_prev=&c; d.lnk_next=&e;
//Удаляем c
/* step 1 */
buff=&c;// как бы нашли в цепочке
/* step 2 */
b.lnk_next=buff->lnk_next;// те &d
/* step 3 */
d.lnk_prev=buff->lnk_prev;// те &b
// buff живет до следуюшего step 1
Вот так я себе это представлял.
Пример 2 однозначно отработает нормально, если считать изменение ссылки атонарной операцией.
С примером 1 сложнее. Тут нужно чтоб у каждого потока был свой буфер.
поток заполнения нашел место куда вставлять и создал новый элемент (допустим С)
поток поиска "выковыривает" элемент В (соседний) в свой буфер удаления. (цепочка будет A-D-E)
поток заполнения меняет ссылки соседей С (B и D) цепочка получится влево (прямой просмотр) A-D-E, а вправо E-D-C-B-A.
Вот тут нас спасет проверка не находится ли один из соседей в буфере удаления другого потока. Ну, а поскольку В в буфере удаления, но еще не удален (те память не очищена), то можно вернуть цепочку в приемлимое состояние.
Буфера придумывались на случай если потоку поиска и потоку удаления приглянется один и тот же элемент. Оба потока помещают элемент в свои буфера удаления, правят ссылки соседей (одинаковым образом), а потом поток поиска смотрит, что забрал элемент, который уже обрабатывется потоком удаления, и зануляет свой буфер (например).
Еще я помню, что видел где-то конструкцию, в которую можно заключить операторы, чтоб они выполнялись без прерывания потока.
теперь какие я виже проблемы.
1. Буфер удаления должен существовать пока поток заполнения не востановил очередь. А когда он это сделает неизвестно, и поток поиска вместо того чтоб вернуть элемент какой он нашел, должен сидеть и ждать пока поток вставки разберется со своими проблемами и можно будет очистить свой буфер удаления.
2. Запускаем еще один поиск элемента асинхронно. Пока 1 поток поиска и поток заполнения решают свои разногласия, 2 поток поиска спокойно передвигается по изначальной очереди. Поток заполнения должен знать обо всех потоках поиска. А если их будет N штук он просто срехнется пока обшарит их буфера и добавит этот несчасный элемент, а вместе с ним и я чтоб придумать как это сделать побыстрее.
Я тут коечто придумал, но чуствую критики будет...
Если мы не можем сделать общий случай, нужно рассмотреть частные.
2 служебки, 1 - адрес отправителя, 2 - идентификатор сообщения.
Адрес отправителя задается в виде номера в таблице клиентов, потому что число клиентов конечно, а их ip могут совпадать, если 2 клиента на 1 машине работают.
Идентификатор сообщения тоже можно ограничеть - кто будет использовать все 4 милиарда для идентификации сообщения. Например 32 идентификатора.
структура сообщение
{
//тут разные поля, заголовок, идентификатор, отправитель, информация различная
};
теперь контейнер для него
{
_msg_data data;
_msg_owner *nextAddr,*prevAddr;
_msg_owner *nextID,*prevID;
_msg_owner *nextAddrID,*prevAddrID;
};
делаем 3 очереди
_msg_owner *ID[32+1];
_msg_owner *AddrID[Количество клиентов][32+1];
Только масивы будут динаическими так как количество клиентов узнаются уже после создания сессии.
Поток обработки заполнения
1. Читаем данные из источника (сокет, канал,...)
2. Создается структура _msg_owner и заполняется ее поле с данными - нужно пропарсите же поток считанной инфы и разложить по полям.
3. Вход в критическую секцию
4. Правка ссылок 3х очередей
5. Выход из секции.
Поток поиска
1. Вход в крит секцию
2. Берем нужный элемент и правим ссылки в очередях.
3. Выход из секции.
Минусы
1. Нужно поддерживать сразу 3 очереди
2. Раход памяти на очереди
Плюсы
1. Находжение элемента за 1 обращение при любых размерах очереди:
если ищем по адресу
Addr[Адрес]
так же и по идентификатору
ID[идентификатор]
по обоим полям
AddrID[Адрес][идентификатор]
Если используется идентификатор больше 32 то помещаем его в 33 ячейку по порядку, для этого и создавалось 32+1. Но я очень сомневаюсь что хотябы 10 идентикаторов будут использовать, а кто будет спецально брать их такими 99999, будет сидеть и ждать дольше.
Начет минусов - для современных процессоров думаю непроблема 3 раза исправить по 2 ссылки, тем более потоков заполнения можно сделать 2 и тогда пока один получает и парсит данные, другой правит ссылки. Расход памяти по сравнению с современными програмамми (вот щас у меня панель с гаджетами весит 130 Мб) просто ничтожно - при 1000 пользователях и 32 идентификаторов - 129 Кб. Я конечно всегда стараюсь не тратить зря даже 1 байта, но поиск за 1 ображение при ЛЮБЫХ размерах того стоят.
Думаю такая схема будет работать быстрее чем любой поиск в 1 очереди даже с сортировкой.
Что думаете (вообщето я почти уже запрограммировал), я сума сошел уже пока ламал голову?)))))