Thread-safe double linked list
Код:
class List;
class ListItem {
public:
constexpr ListItem(): m_next(nullptr), m_prev(nullptr), m_list(nullptr) {
}
~ListItem() {
assert(m_list == nullptr);
}
bool remove();
ListItem* next() const {
return m_next;
}
List* list() const {
return m_list;
}
bool inList() const {
return list() != nullptr;
}
bool inList(List* l) const {
return list() == l;
}
private:
friend class List;
ListItem* m_next;
ListItem* m_prev;
List* m_list;
};
class List {
public:
constexpr List(): m_head(nullptr), m_tail(nullptr), m_count(0) {
}
~List() {
assert(m_count == 0);
}
bool insertAfter(ListItem* item, ListItem* after);
bool insertBefore(ListItem* item, ListItem* before);
bool insertHead(ListItem* item) {
return insertBefore(item, nullptr);
}
bool insertTail(ListItem* item) {
return insertAfter(item, nullptr);
}
bool remove(ListItem* item) {
if (item->m_list == this) {
return item->remove();
}
return false;
}
ListItem* removeHead() {
ListItem* item = m_head;
if (item) {
item->remove();
}
return item;
}
ListItem* removeTail() {
ListItem* item = m_tail;
if (item) {
bool retval = item->remove();
assert(retval);
}
return item;
}
ListItem* head() const {
return m_head;
}
ListItem* tail() const {
return m_tail;
}
unsigned int count() const {
return m_count;
}
bool empty() const {
return count() == 0;
}
private:
friend class ListItem;
ListItem* m_head;
ListItem* m_tail;
unsigned int m_count;
};
inline bool List::insertAfter(ListItem* item, ListItem* after) {
assert(item != nullptr);
if (after && (after->m_list != this)) {
return false;
}
if (after) {
item->m_prev = after;
item->m_next = after->m_next;
after->m_next = item;
if (item->m_next) {
item->m_next->m_prev = item;
} else {
m_tail = item;
}
} else {
item->m_next = nullptr;
item->m_prev = m_tail;
if (item->m_prev) {
item->m_prev->m_next = item;
} else {
m_head = item;
}
m_tail = item;
}
item->m_list = this;
m_count++;
return true;
}
inline bool List::insertBefore(ListItem* item, ListItem* before) {
assert(item != nullptr);
if (before && (before->m_list != this)) {
return false;
}
if (before) {
item->m_next = before;
item->m_prev = before->m_prev;
before->m_prev = item;
if (item->m_prev) {
item->m_prev->m_next = item;
} else {
m_head = item;
}
} else {
item->m_prev = nullptr;
item->m_next = m_head;
if (item->m_next) {
item->m_next->m_prev = item;
} else {
m_tail = item;
}
m_head = item;
}
item->m_list = this;
m_count++;
return true;
}
inline bool ListItem::remove() {
List* list = m_list;
if (list == nullptr) {
return false;
}
if (m_next) {
m_next->m_prev = m_prev;
} else {
list->m_tail = m_prev;
}
if (m_prev) {
m_prev->m_next = m_next;
} else {
list->m_head = m_next;
}
list->m_count--;
m_list = nullptr;
return true;
}
class ListItem {
public:
constexpr ListItem(): m_next(nullptr), m_prev(nullptr), m_list(nullptr) {
}
~ListItem() {
assert(m_list == nullptr);
}
bool remove();
ListItem* next() const {
return m_next;
}
List* list() const {
return m_list;
}
bool inList() const {
return list() != nullptr;
}
bool inList(List* l) const {
return list() == l;
}
private:
friend class List;
ListItem* m_next;
ListItem* m_prev;
List* m_list;
};
class List {
public:
constexpr List(): m_head(nullptr), m_tail(nullptr), m_count(0) {
}
~List() {
assert(m_count == 0);
}
bool insertAfter(ListItem* item, ListItem* after);
bool insertBefore(ListItem* item, ListItem* before);
bool insertHead(ListItem* item) {
return insertBefore(item, nullptr);
}
bool insertTail(ListItem* item) {
return insertAfter(item, nullptr);
}
bool remove(ListItem* item) {
if (item->m_list == this) {
return item->remove();
}
return false;
}
ListItem* removeHead() {
ListItem* item = m_head;
if (item) {
item->remove();
}
return item;
}
ListItem* removeTail() {
ListItem* item = m_tail;
if (item) {
bool retval = item->remove();
assert(retval);
}
return item;
}
ListItem* head() const {
return m_head;
}
ListItem* tail() const {
return m_tail;
}
unsigned int count() const {
return m_count;
}
bool empty() const {
return count() == 0;
}
private:
friend class ListItem;
ListItem* m_head;
ListItem* m_tail;
unsigned int m_count;
};
inline bool List::insertAfter(ListItem* item, ListItem* after) {
assert(item != nullptr);
if (after && (after->m_list != this)) {
return false;
}
if (after) {
item->m_prev = after;
item->m_next = after->m_next;
after->m_next = item;
if (item->m_next) {
item->m_next->m_prev = item;
} else {
m_tail = item;
}
} else {
item->m_next = nullptr;
item->m_prev = m_tail;
if (item->m_prev) {
item->m_prev->m_next = item;
} else {
m_head = item;
}
m_tail = item;
}
item->m_list = this;
m_count++;
return true;
}
inline bool List::insertBefore(ListItem* item, ListItem* before) {
assert(item != nullptr);
if (before && (before->m_list != this)) {
return false;
}
if (before) {
item->m_next = before;
item->m_prev = before->m_prev;
before->m_prev = item;
if (item->m_prev) {
item->m_prev->m_next = item;
} else {
m_head = item;
}
} else {
item->m_prev = nullptr;
item->m_next = m_head;
if (item->m_next) {
item->m_next->m_prev = item;
} else {
m_tail = item;
}
m_head = item;
}
item->m_list = this;
m_count++;
return true;
}
inline bool ListItem::remove() {
List* list = m_list;
if (list == nullptr) {
return false;
}
if (m_next) {
m_next->m_prev = m_prev;
} else {
list->m_tail = m_prev;
}
if (m_prev) {
m_prev->m_next = m_next;
} else {
list->m_head = m_next;
}
list->m_count--;
m_list = nullptr;
return true;
}
В итоге при многопоточной работе срабатывает assert(retval) в методе removeTail (при этом у списка m_count равен 1, m_head и m_tail указывают на этот элемент, а у самого элемента m_next и m_prev обнулены). То есть получается, что в списке оказывается элемент, у которого m_list == nullptr, хотя такого быть не должно, потому что обе функции добавления элемента присваивают ему правильное значение.
Что происходит? У меня ошибка в реализации алгоритма связанного списка (в однопоточных тестах вроде всё нормально)? Или для корректной работы недостаточного просто захватывать mutex?
Если что, любая модификация списка (вызовы insert и remove) происходят подобным образом:
Код:
pthread_mutex_lock(&my_mutex);
...
какие-то действия со списком ...
...
pthread_mutex_unlock(&my_mutex);
...
какие-то действия со списком ...
...
pthread_mutex_unlock(&my_mutex);
Возможно поможет эта тема - http://stackoverflow.com/questions/11640681/thread...
Или вы имеете ввиду, что я должен обернуть все поля этих классов в std::atomic?
Разумнее выполнять захват мьютекса (либо критические секции - не важно) выполнять в методе - именно это гарантирует потокобезопасность. Под атомарностью я понимаю гарантированное выполнение конкретного кода одним и только одним процессом от начала и до конца. Использовать ли для этго std::atomic - на ваше усмотрение
думаю надо смотреть в сторону
recursive_mutex
скорее всего ошибка где-то в других структурах данных, которые неверно испольуют List в многопоточном режиме.