Thread Safe Iteration in Combinatorial Maps

[khansson]

The iteration operations for combinatorial maps are currently not thread-safe. The issue is that more of the iteration object use marks that are global to the mesh. There is a race condition for freeing the marks that lead to a series of problems. Ideally, these functions should act like read-only functions.

Example (which fails):

#include <CGAL/Combinatorial_map.h>
#include <iostream>
#include <vector>
#include "omp.h"

using Mesh = typename CGAL::Combinatorial_map<2>;

using Dart = typename Mesh::Dart_handle;

int main()
{

    Mesh mesh;
    Dart dart;

    dart = mesh.make_combinatorial_polygon(4);

    omp_set_dynamic(0); 
    #pragma omp parallel for num_threads(4)
    for (int i = 0; i < 100; i++)
    {

        int j = 0;
        for (typename Mesh::template One_dart_per_incident_cell_range<1, 2>::iterator
                 it = mesh.template one_dart_per_incident_cell<1, 2>(dart).begin(),
                 itend = mesh.template one_dart_per_incident_cell<1, 2>(dart).end();
             it != itend; ++it)
        {

            j++;
        }

        std::cout << j << " on Thread:" << omp_get_thread_num() << " of " << omp_get_num_threads() << "\n"; 
    }


    std::cout << "sucess\n";    
    return 0;
}

I'll start a fix. It seems the best course of action is to leave some of the dart marks private for each thread and then pass a thread id into the iteration fuctor i.e.

one_dart_per_incident_cell<1, 2>(dart, omp_get_thread_num());

Unless someone has a nicer solution.

[gdamiand]

The example above failed because the method get_new_mark used internally by the constructor of One_dart_per_incident_cell is not thread safe.
Adding a mutex to protect this method (and the method that free a reserved mak) is probably the best solution.

Another problem: std::bitset (used internally to store Boolean marks) seems not thread safe. Maybe there exist some implementation thread safe ?