I wrote the following implementation of a bidirectional linked list in C ++:

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; }

I produce any work with the list only through the public methods of these classes; before any call to the add / remove method, I capture pthread_mutex_t , after calling the method, I release it.

As a result, when multithreaded work, assert(retval) is triggered in the removeTail() method (in this case, the m_count is 1, m_head and m_tail point to this element, and m_next and m_prev ). That is, it turns out that in the list there is an element for which m_list == nullptr , although this should not be, because both functions of adding an element assign it the correct value.

What's happening? I have an error in the implementation of the linked list algorithm (in single-threaded tests everything seems to be normal)? Or, for insufficient work, just grab pthread_mutex_t ?

Minimum working error example:

 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; List list; void* thread_func(void* arg) { ListItem item; while (true) { pthread_mutex_lock(&mutex); list.insertHead(&item); pthread_mutex_unlock(&mutex); } } int main() { pthread_t threads[2]; pthread_create(&threads[0], nullptr, thread_func, nullptr); pthread_create(&threads[1], nullptr, thread_func, nullptr); while (true) { pthread_mutex_lock(&mutex); ListItem* item; do { item = list.removeTail(); } while (item); pthread_mutex_unlock(&mutex); } return 0; }
  • Why not use ready-made solutions based on the function InterlockedExchange , InterlockedCompareExchange - nick_n_a
  • one
    This is WinAPI, and I would like a cross-platform solution. In addition, the lock-free double-linked list needs a double word CAS, which is not supported everywhere, plus there are no strict speed requirements, so I decided to get by with locks. But for some reason they are missing ... - kiv_apple
  • one
    There is an assumption that you forget to call a mutex somewhere. For example, the list is passed to the function, and the copy constructor is not overridden correctly. And all ... arrived. Or, for example, a destructor is called for a list (and it is not always possible to wrap it in an obvious way in a mutex). Well and the third option - for different threads different mutexes are used. As an option - mutext can be part of the class and hide. Outside will only stick out lock / unlock. - KoVadim
  • Plus for the answer above: add a class implementation with a mutex. - isnullxbh
  • You have a race condition between threads. In general, all operations with the list must be done under the protection of the mutex. If you want to create a list that is safe for use in many threads, then it is recommended. look book ozon.ru/context/detail/id/17636939 , it just understands this problem. - Unick

1 answer 1

Take a closer look at this cycle:

 ListItem item; while (true) { pthread_mutex_lock(&mutex); list.insertHead(&item); pthread_mutex_unlock(&mutex); }

Here you add the same element to the list many times - and nowhere in the code do you have any protection from this! No wonder everything fell apart.

It is necessary to do the following:

  1. Add an assert element or conditional operator to the insert methods, which will verify that the element has not yet been inserted into any list.

  2. Add the private copy constructor and the assignment operator to the classes — so that no one accidentally copies and assigns, trying to avoid checking from clause 1.