Мне нужна параллельная структура данных, которая работает как односвязный список и требует только операций append и remove_iterator. В конце концов, один поток будет iterate всех узлов. Из моего исследования я получил реализацию , которая имеет операции append, remove_value и search_value с односвязными списками. Он основан на алгоритме Харриса .
Проблема заключается в том, что в алгоритме Харриса remove_value помечает только логически удаленный узел, но фактически не удаляет его. search_value фактически выполняет работу по удалению логически удаленных узлов. Но так как у меня нет операции search для моего варианта использования. Я держу длинный список с большим количеством логически удаленных узлов. Это просто неэффективно для скорости в многопоточности, потому что вся работа по удалению узлов помещается в операцию iterate внутри одного потока.
Интересно, есть ли другие реализации , которыесоответствуют моим потребностям . Любая рекомендация приветствуется.
Если не , мне интересно, могу ли я реализовать что-то для этого особого случая, используя free-list с реализацией стека без блокировки. В этом случае операция append становится pop free-list, либо помещая значение в узел, либо добавляя в наш список, если он пуст. Операция remove_iterator становится отмечением логически удаленного узла, а push указателем узла на свободный список.
Я думаю, что стек без блокировки достаточно прост в реализации. Я могу использовать некоторые реализации онлайн.
Некоторый код в памяти.
struct node_t {
node_t *next;
int deleted;
val_t val;
};
struct list_t {
node_t *head;
};
struct fl_node_t {
node_t *padding_1;
int padding_2;
fl_node_t *next; // assume sizeof(val_t) >= sizeof(fl_node_t*);
};
struct free_list_t {
fl_node_t * head;
};
void append(val_t val) {
fl_node_t *fl_head;
fl_node_t *fl_next;
node_t *head;
node_t *new_node
/* Try insert to one of the node in free-list */
if (free_list.head) {
do {
fl_head = free_list.head;
next = fl_head->next;
} while(!CAS(&free_list.head, fl_head, fl_next));
if (fl_head) {
fl_head->node->val = val;
return;
}
}
/* Append to head */
new_node = malloc(sizeof(node_t));
new_node.val = val;
new_node.deleted = 0;
do {
head = list.head;
new_node.next = head;
} while(!CAS(&list.head, head, new_node));
}
void remove(node_t *node) {
fl_node_t *fl_node;
fl_node_t *fl_head;
/* Mark logically deleted */
node->deleted = 1;
fl_node = (fl_node_t*) node;
/* Add to free-list */
do {
fl_head = free_list.head;
fl_node->next =fl_head;
} while(!CAS(&free_list.head, fl_head, fl_node));
}