utilities-pthread/mergesort-pthread/mergesort-pthread.c
static void *mergesort_thread(void *arg){
  size_t q;
  mergesort_arg_t *msa = arg;
  mergesort_arg_t child_msas[2];
  pthread_t child_ids[2];
  merge_arg_t ma;
  if (msa->r - msa->p + 1 <= msa->sbase_count){
    qsort(elt_ptr(msa->elts, msa->p, msa->elt_size),
	  msa->r - msa->p + 1,
	  msa->elt_size,
	  msa->cmp);
  }else{
    
    /* sort recursion */
    q = (msa->p + msa->r) / 2; /* rounds down */
    child_msas[0].p = msa->p;
    child_msas[0].r = q;
    child_msas[0].sbase_count = msa->sbase_count;
    child_msas[0].mbase_count = msa->mbase_count;
    child_msas[0].elt_size = msa->elt_size;
    child_msas[0].num_onthread_rec = 0;
    child_msas[0].cat_elts = msa->cat_elts;
    child_msas[0].elts = msa->elts;
    child_msas[0].cmp = msa->cmp;
    child_msas[1].p = q + 1;
    child_msas[1].r = msa->r;
    child_msas[1].sbase_count = msa->sbase_count;
    child_msas[1].mbase_count = msa->mbase_count;
    child_msas[1].elt_size = msa->elt_size;
    child_msas[1].cat_elts = msa->cat_elts;
    child_msas[1].elts = msa->elts;
    child_msas[1].cmp = msa->cmp;
    thread_create_perror(&child_ids[0], mergesort_thread, &child_msas[0]);
    if (msa->num_onthread_rec < MERGESORT_PTHREAD_MAX_ONTHREAD_REC){
      /* keep putting mergesort_thread calls on the current thread stack */
      child_msas[1].num_onthread_rec = msa->num_onthread_rec + 1;
      mergesort_thread(&child_msas[1]);
    }else{
      child_msas[1].num_onthread_rec = 0;
      thread_create_perror(&child_ids[1], mergesort_thread, &child_msas[1]);
      thread_join_perror(child_ids[1], NULL);
    }
    thread_join_perror(child_ids[0], NULL);

    /* merge recursion */
    ma.ap = msa->p;
    ma.ar = q;
    ma.bp = q + 1;
    ma.br = msa->r;
    ma.cs = 0;
    ma.mbase_count = msa->mbase_count;
    ma.elt_size = msa->elt_size;
    ma.num_onthread_rec = msa->num_onthread_rec;
    ma.cat_seg_elts = elt_ptr(msa->cat_elts, msa->p, msa->elt_size);
    ma.elts = msa->elts;
    ma.cmp = msa->cmp;
    merge_thread(&ma);
    /* copy the merged result into the input array */
    memcpy(elt_ptr(msa->elts, msa->p, msa->elt_size),
	   elt_ptr(ma.cat_seg_elts, 0, msa->elt_size),
	   (msa->r - msa->p + 1) * msa->elt_size);
  }
  return NULL;
}
/**
   Enters a mergesort thread that spawns mergesort threads recursively.
   The total number of threads is reduced and an additional speedup is
   provided by placing O(logn) recursive calls on a thread stack, with the
   tightness of the bound set by MERGESORT_PTHREAD_MAX_ONTHREAD_REC.
*/
Enters a mergesort thread that spawns mergesort threads recursively.
The total number of threads is reduced and an additional speedup is
provided by placing O(logn) recursive calls on a thread stack, with the
tightness of the bound set by MERGESORT_PTHREAD_MAX_ONTHREAD_REC.
Enters a mergesort thread that spawns mergesort threads recursively . The total number of threads is reduced and an additional speedup is provided by placing O ( logn ) recursive calls on a thread stack with the tightness of the bound set by MERGESORT_PTHREAD_MAX_ONTHREAD_REC .
static void *mergesort_thread(void *arg){
  size_t q;
  mergesort_arg_t *msa = arg;
  mergesort_arg_t child_msas[2];
  pthread_t child_ids[2];
  merge_arg_t ma;
  if (msa->r - msa->p + 1 <= msa->sbase_count){
    qsort(elt_ptr(msa->elts, msa->p, msa->elt_size),
	  msa->r - msa->p + 1,
	  msa->elt_size,
	  msa->cmp);
  }else{
    q = (msa->p + msa->r) / 2; 
    child_msas[0].p = msa->p;
    child_msas[0].r = q;
    child_msas[0].sbase_count = msa->sbase_count;
    child_msas[0].mbase_count = msa->mbase_count;
    child_msas[0].elt_size = msa->elt_size;
    child_msas[0].num_onthread_rec = 0;
    child_msas[0].cat_elts = msa->cat_elts;
    child_msas[0].elts = msa->elts;
    child_msas[0].cmp = msa->cmp;
    child_msas[1].p = q + 1;
    child_msas[1].r = msa->r;
    child_msas[1].sbase_count = msa->sbase_count;
    child_msas[1].mbase_count = msa->mbase_count;
    child_msas[1].elt_size = msa->elt_size;
    child_msas[1].cat_elts = msa->cat_elts;
    child_msas[1].elts = msa->elts;
    child_msas[1].cmp = msa->cmp;
    thread_create_perror(&child_ids[0], mergesort_thread, &child_msas[0]);
    if (msa->num_onthread_rec < MERGESORT_PTHREAD_MAX_ONTHREAD_REC){
      child_msas[1].num_onthread_rec = msa->num_onthread_rec + 1;
      mergesort_thread(&child_msas[1]);
    }else{
      child_msas[1].num_onthread_rec = 0;
      thread_create_perror(&child_ids[1], mergesort_thread, &child_msas[1]);
      thread_join_perror(child_ids[1], NULL);
    }
    thread_join_perror(child_ids[0], NULL);
    ma.ap = msa->p;
    ma.ar = q;
    ma.bp = q + 1;
    ma.br = msa->r;
    ma.cs = 0;
    ma.mbase_count = msa->mbase_count;
    ma.elt_size = msa->elt_size;
    ma.num_onthread_rec = msa->num_onthread_rec;
    ma.cat_seg_elts = elt_ptr(msa->cat_elts, msa->p, msa->elt_size);
    ma.elts = msa->elts;
    ma.cmp = msa->cmp;
    merge_thread(&ma);
    memcpy(elt_ptr(msa->elts, msa->p, msa->elt_size),
	   elt_ptr(ma.cat_seg_elts, 0, msa->elt_size),
	   (msa->r - msa->p + 1) * msa->elt_size);
  }
  return NULL;
}
static void * mergesort_thread ( void * arg ) { size_t q ; mergesort_arg_t * msa = arg ; mergesort_arg_t child_msas [ 2 ] ; pthread_t child_ids [ 2 ] ; merge_arg_t ma ; if ( msa -> r - msa -> p + 1 <= msa -> sbase_count ) { qsort ( elt_ptr ( msa -> elts , msa -> p , msa -> elt_size ) , msa -> r - msa -> p + 1 , msa -> elt_size , msa -> cmp ) ; } else { q = ( msa -> p + msa -> r ) / 2 ; child_msas [ 0 ] . p = msa -> p ; child_msas [ 0 ] . r = q ; child_msas [ 0 ] . sbase_count = msa -> sbase_count ; child_msas [ 0 ] . mbase_count = msa -> mbase_count ; child_msas [ 0 ] . elt_size = msa -> elt_size ; child_msas [ 0 ] . num_onthread_rec = 0 ; child_msas [ 0 ] . cat_elts = msa -> cat_elts ; child_msas [ 0 ] . elts = msa -> elts ; child_msas [ 0 ] . cmp = msa -> cmp ; child_msas [ 1 ] . p = q + 1 ; child_msas [ 1 ] . r = msa -> r ; child_msas [ 1 ] . sbase_count = msa -> sbase_count ; child_msas [ 1 ] . mbase_count = msa -> mbase_count ; child_msas [ 1 ] . elt_size = msa -> elt_size ; child_msas [ 1 ] . cat_elts = msa -> cat_elts ; child_msas [ 1 ] . elts = msa -> elts ; child_msas [ 1 ] . cmp = msa -> cmp ; thread_create_perror ( & child_ids [ 0 ] , mergesort_thread , & child_msas [ 0 ] ) ; if ( msa -> num_onthread_rec < MERGESORT_PTHREAD_MAX_ONTHREAD_REC ) { child_msas [ 1 ] . num_onthread_rec = msa -> num_onthread_rec + 1 ; mergesort_thread ( & child_msas [ 1 ] ) ; } else { child_msas [ 1 ] . num_onthread_rec = 0 ; thread_create_perror ( & child_ids [ 1 ] , mergesort_thread , & child_msas [ 1 ] ) ; thread_join_perror ( child_ids [ 1 ] , NULL ) ; } thread_join_perror ( child_ids [ 0 ] , NULL ) ; ma . ap = msa -> p ; ma . ar = q ; ma . bp = q + 1 ; ma . br = msa -> r ; ma . cs = 0 ; ma . mbase_count = msa -> mbase_count ; ma . elt_size = msa -> elt_size ; ma . num_onthread_rec = msa -> num_onthread_rec ; ma . cat_seg_elts = elt_ptr ( msa -> cat_elts , msa -> p , msa -> elt_size ) ; ma . elts = msa -> elts ; ma . cmp = msa -> cmp ; merge_thread ( & ma ) ; memcpy ( elt_ptr ( msa -> elts , msa -> p , msa -> elt_size ) , elt_ptr ( ma . cat_seg_elts , 0 , msa -> elt_size ) , ( msa -> r - msa -> p + 1 ) * msa -> elt_size ) ; } return NULL ; }
Enters a mergesort thread that spawns mergesort threads recursively.
Enters a mergesort thread that spawns mergesort threads recursively .
/* sort recursion */ /* rounds down */ /* keep putting mergesort_thread calls on the current thread stack */ /* merge recursion */ /* copy the merged result into the input array */