cindex.c

Go to the documentation of this file.

#include <stdlib.h>
int sindex(int *T, int nT, int *A, int nA){
  int i, tmp;
  i=0;
  for(i=0; i<nA; i++){
    tmp = A[i];
    A[i] =dichotomy(nT, T, tmp);
  }
}


#ifdef W_OPENMP

int omp_pindex(int *T, int nT, int *A, int nA){
//  printf("\nomp_pindex");
  int i;
  int *count, *disp;
  int q, r;
  int tid, nths;

  #pragma omp parallel private(tid) shared(nths)
  {//---fork---just to get the number of threads
    nths = omp_get_num_threads();
    tid = omp_get_thread_num();
//    printf("\ntid %d nths %d", tid, nths);
  }//---join--- 

  q = nA/nths;
  r = nA%nths; 

  count = (int *) malloc(nths *sizeof(int));
  disp = (int *) malloc(nths *sizeof(int));

  for(i=0; i<nths; i++){
    if(i<r){
      count[i] = q+1;
    }
    else{
      count[i] = q;
    }
  }
  
  disp[0] = 0;
  for(i=0; i<nths-1; i++){
    disp[i+1] = disp[i] + count[i];
  }
  
  #pragma omp parallel private(tid) shared(T, nT, A, disp, count)
  {//---fork---1st step, sort on local chunk
    tid = omp_get_thread_num();
    sindex(T, nT, A+disp[tid], count[tid]);
  }//---join---
  free(count);
  free(disp); 
  return 0; 
}
#endif



int dichotomy(int nT, int *T, int e){
  int min, max, pivot;
  min=0;
  max=nT-1;
  pivot=(max-min)/2;
  while(e != T[pivot] && max > min ){
    if(T[pivot]<e){
      min=pivot+1;
    }
    else{
      max=pivot;
    }
    pivot= min + (max-min)/2;
  }
  return pivot;
}