Function partition

common/algorithms/parallel_partition.h:145–214

    }

    __forceinline size_t partition(V& leftReduction, V& rightReduction)
    {
      /* partition the individual ranges for each task */
      parallel_for(numTasks,[&] (const size_t taskID) {
          const size_t startID = (taskID+0)*N/numTasks;
          const size_t endID   = (taskID+1)*N/numTasks;
          V local_left(identity);
          V local_right(identity);
          const size_t mid = serial_partitioning(array,startID,endID,local_left,local_right,is_left,reduction_t);
          counter_start[taskID] = startID;
          counter_left [taskID] = mid-startID;
          leftReductions[taskID]  = local_left;
          rightReductions[taskID] = local_right;
        });
      counter_start[numTasks] = N;
      counter_left[numTasks]  = 0;
      
      /* finalize the reductions */
      for (size_t i=0; i<numTasks; i++) {
        reduction_v(leftReduction,leftReductions[i]);
        reduction_v(rightReduction,rightReductions[i]);
      }

      /* calculate mid point for partitioning */
      size_t mid = counter_left[0];
      for (size_t i=1; i<numTasks; i++)
        mid += counter_left[i];
      const range<ssize_t> globalLeft (0,mid);
      const range<ssize_t> globalRight(mid,N);

      /* calculate all left and right ranges that are on the wrong global side */
      size_t numMisplacedRangesLeft  = 0;
      size_t numMisplacedRangesRight = 0;
      size_t numMisplacedItemsLeft  MAYBE_UNUSED = 0;
      size_t numMisplacedItemsRight MAYBE_UNUSED = 0;

      for (size_t i=0; i<numTasks; i++)
      {	    
        const range<ssize_t> left_range (counter_start[i], counter_start[i] + counter_left[i]);
        const range<ssize_t> right_range(counter_start[i] + counter_left[i], counter_start[i+1]);
        const range<ssize_t> left_misplaced  = globalLeft. intersect(right_range);
        const range<ssize_t> right_misplaced = globalRight.intersect(left_range);

        if (!left_misplaced.empty())  
        {
          numMisplacedItemsLeft += left_misplaced.size();
          leftMisplacedRanges[numMisplacedRangesLeft++] = left_misplaced;
        }

        if (!right_misplaced.empty()) 
        {
          numMisplacedItemsRight += right_misplaced.size();
          rightMisplacedRanges[numMisplacedRangesRight++] = right_misplaced;
        }
      }
      assert( numMisplacedItemsLeft == numMisplacedItemsRight );

      /* if no items are misplaced we are done */