Параллельное программирование на С++ в действии полностью

Листинг 6.13. Потокобезопасный список с поддержкой итераторов

template

class threadsafe_list {

 struct node { ←(1)

  std::mutex m;

  std::shared_ptr data;

  std::unique_ptr next;

  node() : ←(2)

   next() {}

 node(T const& value) : ←(3)

  data(std::make_shared(value)) {}

 };

 node head;

public:

 threadsafe_list() {}

 ~threadsafe_list() {

  remove_if([](node const&){return true;});

 }

 threadsafe_list(threadsafe_list const& other) = delete;

 threadsafe_list& operator=(

  threadsafe_list const& other) = delete;

 void push_front(T const& value) {

  std::unique_ptr new_node(new node(value));←(4)

  std::lock_guard lk(head.m);

  new_node->next = std::move(head.next);          ←(5)

  head.next = std::move(new_node);                ←(6)

 }

 template

 void for_each(Function f) {                     ←(7)

  node* current = &head

  std::unique_lock lk(head.m);       ←(8)

  while(node* const next = current->next.get()) {←(9)

   std::unique_lock next_lk(next->m);←(10)

   lk.unlock();            ←(11)

   f(*next->data);         ←(12)

   current = next;

   lk = std::move(next_lk);←(13)

  }

 }

 template

 std::shared_ptr find_first_if(Predicate p) {←(14)

  node* current = &head

  std::unique_lock lk(head.m);

  while (node* const next=current->next.get()) {

   std::unique_lock next_lk(next->m);

   lk.unlock();

   if (p(*next->data)) {←(15)

    return next->data;  ←(16)

   }

   current = next;

   lk = std::move(next_lk);

  }

  return std::shared_ptr();

 }

 template             ←(17)

 void remove_if(Predicate p) {

  node* current = &head

  std::unique_lock lk(head.m);

  while(node* const next = current->next.get()) {

   std::unique_lock next_lk(next->m);

   if (p(*next->data)) {                  ←(18)

    std::unique_ptr old_next = std::move(current->next);

    current->next = std::move(next->next);←(19)

    next_lk.unlock();

   }            ←(20)

   else {

    lk.unlock();←(21)

    current = next;

    lk = std::move(next_lk);

   }

  }

 }

};

Показанный в листинге 6.13 шаблон threadsafe_list<> — это реализация односвязного списка, в котором каждый элемент является структурой типа node (1). В роли головы head списка выступает сконструированный по умолчанию объект node, в котором указатель next равен NULL (2). Новые узлы добавляются в список функцией push_front(); сначала новый узел конструируется (4), при этом для хранимых в нем данных выделяется память из кучи (3), но указатель next остается равным NULL. Затем мы должны захватить мьютекс для узла head, чтобы получить нужное значение указателя next (5), после чего вставить узел в начало списка, записав в head.next указатель на новый узел (6). Пока всё хорошо: для добавления элемента в список необходимо захватить только один мьютекс, поэтому никакого риска взаимоблокировки нет. Кроме того, медленная операция выделения памяти происходит вне блокировки, так что блокировка защищает только обновление двух указателей — действия, которые не могут привести к ошибке. Переходим к функциям итерирования.