/*--------------------------------------------------------------------*/
int main(int argc, char* argv[]) {
  long thread;
  pthread_t* thread_handles; 
  double start, finish;

  suppress_output = 0;
  // for (int i = 0; i < argc; ++i){
  //   printf("Command line args === argv[%d]: %s\n", i, argv[i]);
  // }  

  if (argc == 5) { 
  } else if (argc == 6 && (strcmp(argv[5], "n") == 0)) {
	  // printf("==== %s\n", argv[5]);
	  suppress_output = 1;
  } else {
	Usage(argv[0]);
  }
  
  thread_count = strtol(argv[1], NULL, 10);
  sample_size = strtol(argv[2], NULL, 10);
  list_size = strtol(argv[3], NULL, 10);
  input_file = argv[4];

  // Allocate memory for variables
  thread_handles = malloc(thread_count*sizeof(pthread_t));
  list = malloc(list_size * sizeof(int));
  tmp_list = malloc(list_size * sizeof(int));
  sorted_list = malloc(list_size * sizeof(int));
  sample_keys = malloc(sample_size * sizeof(int));
  sorted_keys = malloc(sample_size * sizeof(int));
  splitters = malloc(thread_count * sizeof(int));
  
  // One dimensional distribution arrays
  raw_dist = malloc(thread_count * thread_count * sizeof(int));
  col_dist = malloc(thread_count * sizeof(int));
  prefix_dist = malloc(thread_count * thread_count * sizeof(int));
  prefix_col_dist = malloc(thread_count * sizeof(int));
  
	
  // pthread_mutex_init(&barrier_mutex, NULL);
  // pthread_cond_init(&ok_to_proceed, NULL);
  pthread_barrier_init(&barrier, NULL, thread_count);
  

  // Read list content from input file
  FILE *fp = fopen(input_file, "r+");
  for (i = 0; i < list_size; i++) {
  	  if (!fscanf(fp, "%d", &list[i])) {
    	  break;
      }
  }
  Print_list(list, list_size, "original list");
  
  GET_TIME(start);
  
  for (thread = 0; thread < thread_count; thread++)
     pthread_create(&thread_handles[thread], NULL,
         Thread_work, (void*) thread);

  for (thread = 0; thread < thread_count; thread++) 
     pthread_join(thread_handles[thread], NULL);
  
  GET_TIME(finish);
  
  // Print_list(sample_keys, sample_size, "Sample keys (unsorted)");
  Print_list(sorted_keys, sample_size, "Sample keys (sorted)");
  Print_list(splitters, thread_count, "Splitters");
  Print_list(raw_dist, thread_count * thread_count, "Raw dist");
  Print_list(prefix_dist, thread_count * thread_count, "Prefix dist");
  Print_list(col_dist, thread_count, "Colsum dist");
  Print_list(prefix_col_dist, thread_count, "Prefix colsum dist");
  Print_list(tmp_list, list_size, "Temp list");
  
  // Only print list data if not suppressed
  if (suppress_output == 0) {
	  Print_list(sorted_list, list_size, "Sorted list");
  }
  
  // Print elapsed time regardless
  printf("Elapsed time = %e seconds\n", finish - start);


  pthread_barrier_destroy(&barrier);
  // pthread_mutex_destroy(&barrier_mutex);
  // pthread_cond_destroy(&ok_to_proceed);

  free(thread_handles);
  
  return 0;
}  /* main */

int main ( void )
{
  pthread_barrier_t *bar1, *bar2, *bar3, *bar4, *bar5;
  pthread_t thr1, thr2;
  int r;

  /* possibly set up a watchdog timer thread here. */











  /* initialise a barrier with a zero count */
  fprintf(stderr, "\ninitialise a barrier with zero count\n");
  bar1 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar1, NULL, 0);

  /* initialise a barrier twice */
  fprintf(stderr, "\ninitialise a barrier twice\n");
  bar2 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar2, NULL, 1);
  pthread_barrier_init(bar2, NULL, 1);

  /* initialise a barrier which has threads waiting on it.
     This isn't too simple. */
  fprintf(stderr, "\ninitialise a barrier which has threads waiting on it\n");
  bar3 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar3, NULL, 2);
  /* create a thread, whose only purpose is to block on the barrier */
  pthread_create(&thr1, NULL, child1, (void*)bar3);
  /* guarantee that it gets there first */
  sleep(1);
  /* and now reinitialise */
  pthread_barrier_init(bar3, NULL, 3);

  /* destroy a barrier that has threads waiting at it */
  fprintf(stderr, "\ndestroy a barrier that has waiting threads\n");
  /* once again, create a thread, whose only purpose is to block. */
  bar4 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar4, NULL, 2);
  /* create a thread, whose only purpose is to block on the barrier */
  pthread_create(&thr2, NULL, child1, (void*)bar4);
  /* guarantee that it gets there first */
  sleep(1);
  /* and now destroy */
  pthread_barrier_destroy(bar4);

  /* destroy a barrier that was never initialised.  This is a bit
     tricky, in that we have to fill the barrier with bytes which
     ensure that the pthread_barrier_destroy call doesn't hang for
     some reason.  Zero-fill seems to work ok on amd64-linux (glibc
     2.8). */
  fprintf(stderr, "\ndestroy a barrier that was never initialised\n");
  bar5 = malloc(sizeof(pthread_barrier_t));
  assert(bar5);
  memset(bar5, 0, sizeof(*bar5));
  pthread_barrier_destroy(bar5);

  /* now we need to clean up the mess .. */
  r= pthread_cancel(thr1); assert(!r);
  r= pthread_cancel(thr2); assert(!r);

  free(bar1); free(bar2); free(bar3); free(bar4); free(bar5);

  return 0;
}

void magma_zapplyQ_data_destroy(
    magma_zapplyQ_data *zapplyQ_data)
{
    pthread_barrier_destroy(&(zapplyQ_data->barrier));
}

//.........这里部分代码省略.........
				return -1;
			}
			if(pthread_barrier_init(&internal_barr_stage1, NULL, nt+1))
			{
				printf("Could not create a barrier\n");
				return -1;
			}
			if(pthread_barrier_init(&internal_barr_stage2, NULL, nt))
			{
				printf("Could not create a barrier\n");
				return -1;
			}

			result.tv_sec=0; result.tv_usec=0;
			for (j=0; j</*NUMTHRDS*/nt; j++){
				x[j].id = j;
				x[j].nrT = nt; // number of threads in this round
				#ifdef BENCHMARK
					x[j].lenA = n;  //input size
					x[j].lenB = n;
				#else
					x[j].lenA = LEN_A;  //input size
					x[j].lenB = LEN_B;
				#endif
				pthread_create(&callThd[j], &attr, parallel_pthreads, (void *)&x[j]);
			}

			gettimeofday (&startt, NULL);
			for (t=0; t<TIMES; t++)
			{
				reinit(C_pthreads, lenC);
				pthread_barrier_wait(&internal_barr_stage1);
				pthread_barrier_wait(&barr);
			}

#if !defined(BENCHMARK)
			printf("\nResult array C pthreads:\t");
			for(int idx = 0; idx < lenC; idx++)
				printf("%d ", C_pthreads[idx]);
			printf("\n");
#endif

			/* Wait on the other threads */
			for(j=0; j</*NUMTHRDS*/nt; j++)
			{
				pthread_join(callThd[j], &status);
			}
			gettimeofday(&endt, NULL);

			for(int idx = 0; idx < lenC; idx++)
			{
				if(C_pthreads[idx] != C_seq[idx])
					printf("Difference at idx %d, SEQ vs PAR: %d vs %d\n", idx, C_seq[idx], C_pthreads[idx]);
			}

			if (pthread_barrier_destroy(&barr)) {
				printf("Could not destroy the barrier\n");
				return -1;
			}
			if (pthread_barrier_destroy(&internal_barr_stage1)) {
				printf("Could not destroy the barrier\n");
				return -1;
			}
			if (pthread_barrier_destroy(&internal_barr_stage2)) {
				printf("Could not destroy the barrier\n");
				return -1;
			}
			result.tv_usec += (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
			printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);
		}
		for(int nt = 1; nt < NUM_THREADS; nt=nt<<1){
			result.tv_sec=0; 
			result.tv_usec=0;
			gettimeofday (&startt, NULL);	
			for (t=0; t<TIMES; t++)
			{
				reinit(C_OMP, lenC);
				parallel_OMP(nt, lengthA, lengthB);
			}
			gettimeofday (&endt, NULL);
			result.tv_usec += (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
			printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);
#if !defined(BENCHMARK)
			printf("\nResult array C OMP:\t\t");
			for(int idx = 0; idx < lenC; idx++)
				printf("%d ", C_OMP[idx]);
#endif
			for(int idx = 0; idx < lenC; idx++)
			{
				if(C_OMP[idx] != C_seq[idx])
					printf("Difference at idx %d, SEQ vs PAR OMP: %d vs %d\n", idx, C_seq[idx], C_OMP[idx]);
			}
		}
		printf("\n");
#ifdef BENCHMARK
	}
#endif
	// freeArrays();	
	pthread_exit(NULL);
}

int main ( void )
{
  pthread_barrier_t *bar1, *bar2, *bar3, *bar4, *bar5;
  /* int r; unused since pthread_cancel are commented out */
  pthread_t thr1, thr2, slp1, slp2, ext1;

  /* initialise a barrier with a zero count */
  fprintf(stderr, "\ninitialise a barrier with zero count\n");
  bar1 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar1, NULL, 0);

  /* initialise a barrier twice */
  fprintf(stderr, "\ninitialise a barrier twice\n");
  bar2 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar2, NULL, 1);
  pthread_barrier_init(bar2, NULL, 1);

  /* initialise a barrier which has threads waiting on it.
     This isn't too simple. */
  fprintf(stderr, "\ninitialise a barrier which has threads waiting on it\n");
  bar3 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar3, NULL, 2);
  /* create a thread, whose purpose is to "unblock" the barrier after
     some sleeping in case it keeps being blocked.  */
  pthread_create(&slp1, NULL, sleep1, (void*)bar3);
  /* create a thread, whose only purpose is to block on the barrier */
  pthread_create(&thr1, NULL, child1, (void*)bar3);
  /* guarantee that it gets there first */
  sleep(1);
  /* and now reinitialise */
  pthread_barrier_init(bar3, NULL, 3);

  /* destroy a barrier that has threads waiting at it */
  fprintf(stderr, "\ndestroy a barrier that has waiting threads\n");
  /* once again, create a thread, whose only purpose is to block. */
  bar4 = malloc(sizeof(pthread_barrier_t));
  pthread_barrier_init(bar4, NULL, 2);
  /* create a thread, whose purpose is to "unblock" the barrier after
     some sleeping in case it keeps being blocked. We hope it isn't
     needed, but if it is, because pthread_barier_destroy hangs
     and we will get an extra warning about the barrier being already
     destroyed. */
  pthread_create(&slp2, NULL, sleep1, (void*)bar4);
  /* create a thread, whose only purpose is to block on the barrier */
  pthread_create(&thr2, NULL, child1, (void*)bar4);
  /* guarantee that it gets there first */
  sleep(1);
  /* and now destroy */
  pthread_barrier_destroy(bar4);

  pthread_cancel(slp2);

  /* destroy a barrier that was never initialised.  This is a bit
     tricky, in that we have to fill the barrier with bytes which
     ensure that the pthread_barrier_destroy call doesn't crash for
     some reason.  One-fill seems to work ok on amd64-linux (glibc
     2.8). */
  fprintf(stderr, "\ndestroy a barrier that was never initialised\n");
  /* Create a thread that just exits the process after some sleep.
     We are really done at this point, even if we hang. */
  pthread_create(&ext1, NULL, exit1, NULL);
  bar5 = malloc(sizeof(pthread_barrier_t));
  assert(bar5);
  memset(bar5, 1, sizeof(*bar5));
  pthread_barrier_destroy(bar5);

  /* now we need to clean up the mess .. But skip canceling threads.  */
  /* r= pthread_cancel(thr1); assert(!r); // drd doesn't like it. Just exit.
  r= pthread_cancel(thr2); assert(!r); */

  free(bar1); free(bar2); free(bar3); free(bar4); free(bar5);

  /* Use exit, we want to kill any "sleeper threads". */
  exit (0);
}

/**
 * Appelle les thread en fonction du nombre demande
 * @author Chloe
 */
int lancerThreads(MatriceInfo *matInfo, int nbThread){
    int taille=matInfo->taille;

    //Identifiants thread
    pthread_t *thread_ids;
    thread_ids=(pthread_t *)malloc(nbThread*sizeof(pthread_t));
    int i, j;
    for (i=0;i<nbThread;i++){
        pthread_t thread_id;
        thread_ids[i]= thread_id;
    }

    //Barriere
    int ret;
    if(pthread_barrier_init(&barrier,NULL,nbThread)){
        printf("Impossible de creer la barriere\n");
        return -1;
    }

    //Calcul du nombre de cases par thread
    double val= taille * taille / nbThread;
    int nbCaseParThread = sqrt((double)val);
    if (nbThread>taille){
        printf("Nombre de thread trop important par rapport a la taille.\n");
        return -1;
    }

    //Copies de matInfo pour chaque thread 
    MatriceInfo **copies;
    copies=(MatriceInfo **)malloc(nbThread*sizeof(MatriceInfo*));

    //Appel au thread en creant les copies et ajoutant les bons arguments
    int k=0;
    for(i = 0 ; i<taille ; i += nbCaseParThread){
        for(j = 0 ; j< taille ; j += nbCaseParThread){
            MatriceInfo *copie1;
            copie1=(MatriceInfo *)malloc(sizeof(MatriceInfo));
            copie1->matrice = matInfo->matrice;
            copie1->taille = matInfo->taille;
            copie1->TEMP_FROID = matInfo->TEMP_FROID ;   
            copie1->deb_i=i;
            copie1->deb_j=j;
            copie1->fin_i=i+nbCaseParThread;
            copie1->fin_j=j+nbCaseParThread;
            copies[k]=copie1;
           // printf("--> Ici je vais de : %d-%d à %d-%d \n", copie1->deb_i, copie1->deb_j, copie1->fin_i, copie1->fin_j);
            ret=pthread_create(&thread_ids[k],NULL,&uneIterationV2,(void*)copie1);
            if(ret!=0) {
                printf("Impossible de creer le thread.\n");
                return -1;
            }
            k++; 
        }
    }

    //Attentes des autres threads
    for (i=0; i<nbThread;i++){
        if(pthread_join(thread_ids[i],NULL)){
            printf("Impossible de joindre le thread.%d\n", i);
            return -1;
        }   
    }

    //destructions de la barriere et liberation memoire 
    pthread_barrier_destroy(&barrier);
    free(thread_ids);
    for (i=0; i<nbThread;i++){
        free(copies[i]);
    }
    free(copies);
    return 0;
}

void magma_dbulge_data_destroy(magma_dbulge_data *dbulge_data_S)
{
    pthread_barrier_destroy(&(dbulge_data_S->barrier));
}

int main(int argc, char *argv[])
{
	int node_id = 0;
	int arrival_lambda = 10;
	int thread_cpu_map[N_THREADS];
	int i,j,k;
	int n_threads;
	int n_left;
	int n_right;
	int next_index_left = 3;
	int next_index_right = 7;
	float local_square = 0.0, remote_square = 0.0;


	/***************** make sure #args is correct and get the n_threads, n_left and n_right */
	if(argc < 4)
	{
		printf("Usage: ./test_numa_comb n_of_threads n_of_threads_on_node0 n_of_threads_on_node1\n");
		exit(-1);
	}
	n_threads = atoi(argv[1]);
	n_left = atoi(argv[2]);
	n_right = atoi(argv[3]);
	/******************* Set the thread_cpu_map according to the n_left and n_right */
	printf("n_threads: %d, n_left: %d, n_right: %d\n",n_threads,n_left,n_right);
	for(i = 0; i < n_left; i++)
	{
		thread_cpu_map[i] = next_index_left;
		next_index_left--;
	}
	for(i = n_left; i < n_threads; i++)
	{
		thread_cpu_map[i] = next_index_right;
		next_index_right--;
	}
	for(i = 0; i < n_threads; i++)
	{
		printf("Thread %d is on cpu %d\n",i,thread_cpu_map[i]);
	}



	thread_params para[n_threads]; //The parameters to pass to the threads

	//printf("The return value of numa_get_run_node_mask(void) is %d\n",numa_get_run_node_mask());
	//printf("The return value of numa_max_node(void) is %d\n",numa_max_node());
	//numa_tonode_memory((void *)spinlock_ptr,sizeof(pthread_spinlock_t),node_id); //This doesn't work

	//initilize the spinlock pointer and put it on a specific node
	pthread_spinlock_t *spinlock_ptr = numa_alloc_onnode(sizeof(pthread_spinlock_t),node_id);

	if(spinlock_ptr == NULL) //error handling of the allocating of a spinlock pointer on a specific node
	{
		printf("alloc of spinlock on a node failed.\n");
		exit(-1);
	}

	/* initialise  syncs */
	pthread_barrier_init(&fin_barrier, NULL, n_threads);
	pthread_spin_init(spinlock_ptr,0);
	int rc;
	//create the threads
	for(i = 0; i < n_threads; i++)
	{

		para[i].thread_id = i;
		para[i].arrival_lambda = arrival_lambda;
		para[i].spinlock_ptr = spinlock_ptr;
		CPU_ZERO(&cpuset[i]);
		CPU_SET(thread_cpu_map[i],&cpuset[i]);
		rc = pthread_create(&threads[i],NULL,work,(void*)&para[i]);
		E (rc);


	}
	start_work_flag = 1; 

	/* wait here */
	for(i = 0; i < n_threads; i++)
	    pthread_join(threads[i],NULL);


	pthread_barrier_destroy(&fin_barrier);

	/*
	for(i = 0; i < n_threads; i++)
	{
		printf("The time to get one lock for thread %d is : %.9f\n",i,time_in_cs[i]/num_access_each_thread[i]);
		printf("The number of lock accesses for thread %d is : %d\n",i,num_access_each_thread[i]);
	}
	*/

	qsort((void*)g_tss,(size_t)access_count,(size_t)sizeof(timestamp),cmp_timestamp);
	/*
	for (i = 0; i < access_count; i++)
		printf("%lu with id %d\n",g_tss[i].ts,g_tss[i].id);
	*/

	/* for (i = 0; i < access_count; i++)
	 * {
//.........这里部分代码省略.........

/* Sets up and runs the threads
*/
void relaxationThreaded(float** inArray,
						float** outArray,
						int arraySize,
						float precision,
						int numThreads)
{
	if (numThreads > 0)
	{
		// Calculate granularity
		int currPos = 0;
		// plus 2 because we want to overlap and edges are
		// kept constant by the functions.
		int threadChunk = (arraySize / numThreads) + 2;

		// To store the data for the thread function
		LoopData	loopDataArray[numThreads];
		pthread_t 	threads[numThreads];

		// All threads must reach the barrier before we continue
		pthread_barrier_t theBarrier;
		pthread_barrier_init(&theBarrier, NULL, numThreads);

		// Shared counter so processes know when they're finished
		int finishedThreads = 0;

		// Lock for the counter
		pthread_mutex_t theLock;
		pthread_mutex_init(&theLock, NULL);

		// Loop and create/start threads
		int i;
		for ( i = 0; i < numThreads; i++)
		{
			// The last chunk is a bit of a special case
			if ( i == (numThreads - 1) )
			{
				int columnsRemaining 		= (arraySize - currPos);
				loopDataArray[i].arrayX 	= columnsRemaining;
				threadChunk 				= columnsRemaining;
			}
			else // It shouldn't be possible for any chunk but the last to go
			{   //  OOB, so keep that assumption (maybe bad practice, but
				//  protections higher up should hide it)
				loopDataArray[i].arrayX 	= threadChunk;
			}

			loopDataArray[i].inArray 		= &inArray[currPos];
			loopDataArray[i].outArray		= &outArray[currPos];

			loopDataArray[i].arrayY 		= arraySize;
			loopDataArray[i].precision 		= precision;
			loopDataArray[i].barrier		= &theBarrier;
			loopDataArray[i].numThreads		= numThreads;
			loopDataArray[i].finishedThreads= &finishedThreads;
			loopDataArray[i].finLock		= &theLock;

			if (__VERBOSE)
			{
				printf("Starting thread %d.\n", i);
			}

			pthread_create(&threads[i], NULL,
							threadLoop, (void*)&loopDataArray[i]);

			currPos += threadChunk - 2;

		}

		// join will block if the thread is going, otherwise doesn't block.
		for( i = 0; i < numThreads; i++)
		{
			pthread_join(threads[i], NULL);
		}

		// Cleanup
		pthread_barrier_destroy(&theBarrier);
		pthread_mutex_destroy(&theLock);
	}
	else
	{
		//== Serial Computation ==
		LoopData data;
		int finishedThreads = 0;

		data.inArray 	= inArray;
		data.outArray 	= outArray;
		data.arrayX 	= arraySize;
		data.arrayY		= arraySize;
		data.precision 	= precision;
		data.barrier 	= NULL;
		data.finLock	= NULL;
		data.numThreads = 1;
		data.finishedThreads = &finishedThreads;

		threadLoop((void*)&data);
	}
}

/* Do the forward Fast Fourier Transform either on two input images
   (the padded image and kernel) or on one image (the multiplication
   of the FFT of the two). In the second case, it is assumed that we
   are looking at the complex conjugate of the array so in practice
   this will be a backward transform. */
void
twodimensionfft(struct convolveparams *p, struct fftonthreadparams *fp,
                int forward1backwardn1)
{
  int err;
  pthread_t t;          /* All thread ids saved in this, not used. */
  pthread_attr_t attr;
  pthread_barrier_t b;
  size_t i, nb, *indexs, thrdcols;
  size_t nt=p->cp.numthreads, multiple=0;

  /* First we are going to get the 1D fourier transform on the rows of
     both images. */
  if(forward1backwardn1==1)       multiple=2;
  else if(forward1backwardn1==-1) multiple=1;
  else
    error(EXIT_FAILURE, 0, "%s: a bug! The value of the variable "
          "`forward1backwardn1' is %d not 1 or 2. Please contact us at %s "
          "so we can find the cause of the problem and fix it", __func__,
          forward1backwardn1, PACKAGE_BUGREPORT);


  /* ==================== */
  /* 1D FFT on each row. */
  /* ==================== */
  gal_threads_dist_in_threads(multiple*p->ps0, nt, &indexs, &thrdcols);
  if(nt==1)
    {
      fp[0].stride=1;
      fp[0].indexs=&indexs[0];
      fp[0].forward1backwardn1=forward1backwardn1;
      onedimensionfft(&fp[0]);
    }
  else
    {
      /* Initialize the attributes. Note that this running thread
         (that spinns off the nt threads) is also a thread, so the
         number the barrier should be one more than the number of
         threads spinned off. */
      if( multiple*p->ps0 < nt ) nb=multiple*p->ps0+1;
      else nb=nt+1;
      gal_threads_attr_barrier_init(&attr, &b, nb);

      /* Spin off the threads: */
      for(i=0;i<nt;++i)
        if(indexs[i*thrdcols]!=GAL_BLANK_SIZE_T)
          {
            fp[i].id=i;
            fp[i].b=&b;
            fp[i].stride=1; /* On each row, stride=1 */
            fp[i].indexs=&indexs[i*thrdcols];
            fp[i].forward1backwardn1=forward1backwardn1;
            err=pthread_create(&t, &attr, onedimensionfft, &fp[i]);
            if(err)
              error(EXIT_FAILURE, 0, "%s: can't create thread %zu for rows",
                    __func__, i);
          }

      /* Wait for all threads to finish and free the spaces. */
      pthread_barrier_wait(&b);
      pthread_attr_destroy(&attr);
      pthread_barrier_destroy(&b);
    }
  free(indexs);



  /* ====================== */
  /* 1D FFT on each column. */
  /* ====================== */
  /* No comments, exact duplicate, except the p->ps1s! */
  gal_threads_dist_in_threads(multiple*p->ps1, nt, &indexs, &thrdcols);
  if(nt==1)
    {
      fp[0].stride=p->ps1;
      fp[0].indexs=indexs;
      fp[0].forward1backwardn1=forward1backwardn1;
      onedimensionfft(&fp[0]);
    }
  else
    {
      if( multiple*p->ps1 < nt ) nb=multiple*p->ps1+1;
      else nb=nt+1;
      gal_threads_attr_barrier_init(&attr, &b, nb);
      for(i=0;i<nt;++i)
        if(indexs[i*thrdcols]!=GAL_BLANK_SIZE_T)
          {
            fp[i].b=&b;
            fp[i].stride=p->ps1; /* On each column, stride is p->ps1 */
            fp[i].indexs=&indexs[i*thrdcols];
            fp[i].forward1backwardn1=forward1backwardn1;
            err=pthread_create(&t, &attr, onedimensionfft, &fp[i]);
            if(err)
              error(EXIT_FAILURE, 0, "%s: can't create thread %zu for columns",
                    __func__, i);
//.........这里部分代码省略.........

 ~magma_sapplyQ_m_data()
 {
     pthread_barrier_destroy(&barrier);
 }

static void *
tf (void *arg)
{
  pthread_t th = (pthread_t) arg;

  int r = pthread_barrier_wait (&b);
  if (r != 0 && r != PTHREAD_BARRIER_SERIAL_THREAD)
    {
      puts ("parent thread: barrier_wait failed");
      exit (1);
    }

  sleep (1);

  r = pthread_kill (th, SIGHUP);
  if (r)
    {
      errno = r;
      printf ("pthread_kill failed %m\n");
      exit (1);
    }

  while (in_sh_body == 0)
    sleep (1);

  if (pthread_cancel (th) != 0)
    {
      puts ("cancel failed");
      exit (1);
    }

  /* This will cause the read in the initial thread to return.  */
  close (fd[0]);
  close (fd[1]);
  close (fd[2]);
  close (fd[3]);

  void *ret;
  if (pthread_join (th, &ret) != 0)
    {
      puts ("join failed");
      exit (1);
    }

  if (ret != PTHREAD_CANCELED)
    {
      puts ("result is wrong");
      exit (1);
    }

  if (cleanups != 0x1234L)
    {
      printf ("called cleanups %lx\n", cleanups);
      exit (1);
    }

  if (pthread_barrier_destroy (&b))
    {
      puts ("barrier destroy failed");
      exit (1);
    }

  exit (0);
}

static
uintptr_t
load_ppp_module()
{
    if (module_dl_handler) {
        // already loaded
        return 0;
    }

    // allocate auxiliary instance
    if (!aux_instance) {
        aux_instance = calloc(1, sizeof(*aux_instance));
        if (!aux_instance)
            return 1;

        aux_instance->id = tables_generate_new_pp_instance_id();
        tables_add_pp_instance(aux_instance->id, aux_instance);
    }

    // allocate message loop for browser thread
    if (ppb_message_loop_get_current() == 0) {
        PP_Resource message_loop = ppb_message_loop_create(aux_instance->id);
        ppb_message_loop_attach_to_current_thread(message_loop);
        ppb_message_loop_proclaim_this_thread_browser();
    }

    // allocate message loop for plugin thread (main thread)
    if (ppb_message_loop_get_for_main_thread() == 0) {
        pthread_barrier_init(&aux_instance->main_thread_barrier, NULL, 2);
        pthread_create(&aux_instance->main_thread, NULL, fresh_wrapper_main_thread, aux_instance);
        pthread_detach(aux_instance->main_thread);
        pthread_barrier_wait(&aux_instance->main_thread_barrier);
        pthread_barrier_destroy(&aux_instance->main_thread_barrier);
    }

    fpp_config_initialize();

    if (tried_files) {
        g_list_free_full(tried_files, g_free);
        tried_files = NULL;
    }

    if (fpp_config_get_plugin_path()) {
        const char *ptr = fpp_config_get_plugin_path();
        const char *last = strchr(ptr, ':');
        uintptr_t   ret;

        // parse ':'-separated list
        while (last != NULL) {
            // try entries one by one
            char *entry = strndup(ptr, last - ptr);
            ret = do_load_ppp_module(entry);
            free(entry);
            if (ret == 0)
                return 0;

            ptr = last + 1;
            last = strchr(ptr, ':');
        }

        // and the last entry
        ret = do_load_ppp_module(ptr);
        if (ret == 0)
            return 0;

        goto failure;
    }

    // try all paths
    const char **path_list = fpp_config_get_plugin_path_list();
    while (*path_list) {
        gchar *fname = g_strdup_printf("%s/%s", *path_list, fpp_config_get_plugin_file_name());
        uintptr_t ret = do_load_ppp_module(fname);
        g_free(fname);
        if (ret == 0)
            return 0;
        path_list ++;
    }

failure:
    config.quirks.plugin_missing = 1;
    use_fallback_version_strings();
    trace_error("%s, can't find %s\n", __func__, fpp_config_get_plugin_file_name());
    return 1;
}

//.........这里部分代码省略.........
	printf("|NSize|Iterations|    Seq   |    Th01   |    Th02   |    Th04   |    Th08   |   Par16   |\n");

	// for each input size
	for(c=0; c<NSIZE; c++){
		n=Ns[c];
		printf("| %3d | %8d |",n,TIMES);

		/* Run sequential algorithm */
		result.tv_usec=0;
		gettimeofday (&startt, NULL);
		for (t=0; t<TIMES; t++) {
			init(n);
			seq_function(n);
		}
		gettimeofday (&endt, NULL);
		// printResult("Sequential", n);

		result.tv_usec = (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
		printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);

		/* Run threaded algorithm(s) */
		for(nt=1; nt<NUM_THREADS; nt=nt<<1){

			if(pthread_barrier_init(&barr, NULL, nt+1))
			{
				printf("Could not create a barrier\n");
				return -1;
			}

			if(pthread_barrier_init(&internal_barr, NULL, nt))
			{
				printf("Could not create a barrier\n");
				return -1;
			}

			result.tv_sec=0; result.tv_usec=0;
			gettimeofday (&startt, NULL);

			for (t=0; t<TIMES; t++) //threaded execution
			{			
				init(n);
				totalTasks = n - 1;
				tasksCurrentLevel = n/2;
				task = 0;
				r = 2;
				

				while (task < totalTasks) {
					id = 1; spawnedThreadsThisLevel = 0; min_i = 0;

					while(spawnedThreadsThisLevel < tasksCurrentLevel) { // spawn threads
						task++;
						spawnedThreadsThisLevel++;
						max_i = min_i + r - 1;
						
						x[id-1].min_i = min_i;
						x[id-1].max_i = max_i;
						pthread_create(&callThd[id-1], &attr, par_function, (void *)&x[id-1]);
						// printf("Spawn thread %d/%d (index: %d -> %d). %d/%d/%d tasks assigned.\n",id,spawnedThreadsThisLevel,min_i,max_i,task,tasksCurrentLevel,totalTasks);
						id++;
										
						if(id > nt) {
							for (id = 1; id <= nt; id++) { // join all threads
								// printf("Ran out of threads! Join thread %d\n",id);
								pthread_join(callThd[id-1], &status);
							}
							id = 1;
						}
						min_i = max_i + 1;
					}

					for (j = 1; j < id; j++) { // join threads
						// printf("Finished level. Join thread %d\n",j);
						pthread_join(callThd[j-1], &status);
					}


					r *= 2;
					tasksCurrentLevel /= 2;
					// printf("\n");
				}
			}
			// printResult("Threaded", n);
			gettimeofday (&endt, NULL);

			if (pthread_barrier_destroy(&barr)) {
					printf("Could not destroy the barrier\n");
					return -1;
			}
			if (pthread_barrier_destroy(&internal_barr)) {
					printf("Could not destroy the barrier\n");
					return -1;
			}
 			result.tv_usec += (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
			printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);
		}
		printf("\n");
	}
	pthread_exit(NULL);
}

//.........这里部分代码省略.........
		return PTS_UNRESOLVED;
	}
	
	/* Expect the child to block*/
	cnt = 0;
	do{
		sleep(1);
	}while (thread_state !=EXITING_THREAD && cnt++ < 2); 
	
	if(thread_state == EXITING_THREAD)
	{
		/* child thread did not block */
		printf("Test FAILED: child thread did not block on "
			"pthread_barrier_wait()\n");
		exit(PTS_FAIL);
	}
	else if(thread_state != ENTERED_THREAD)
	{
		printf("Unexpected thread state: %d\n", thread_state);
		exit(PTS_UNRESOLVED);
	}

	printf("main: send SIGUSR1 to child thread\n");
	if(pthread_kill(child_thread, SIGUSR1) != 0)
	{
		printf("main: Error at pthread_kill()\n");
		exit(PTS_UNRESOLVED);
	}

	/* Expect the child to continue blocking */
	cnt = 0;
	do{
		sleep(1);
	}while (thread_state !=EXITING_THREAD && cnt++ < 2); 
	
	if(sig_rcvd != 1)
	{
		printf("child did not handle SIGUSR1\n");
		exit(PTS_UNRESOLVED);
	}
	
	if(thread_state == EXITING_THREAD)
	{
		/* child thread did not block */
		printf("Test FAILED: child thread should still block on "
			"pthread_barrier_wait() when interrupted by signal\n");
		exit(PTS_FAIL);
	}
	else if(thread_state != ENTERED_THREAD)
	{
		printf("Unexpected thread state: %d\n", thread_state);
		exit(PTS_UNRESOLVED);
	}
	printf("main: thread continued blocking after handling SIGUSR1\n");
	
	printf("main: call barrier wait\n");
	rc = pthread_barrier_wait(&barrier);
	
	if(rc != 0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
	{
		printf("Test FAILED: main: pthread_barrier_wait() got unexpected "
			"return code : %d\n" , rc);
		exit(PTS_FAIL);
	} 
	else if(rc == PTHREAD_BARRIER_SERIAL_THREAD)
		printf("main: get PTHREAD_BARRIER_SERIAL_THREAD\n");
	
	/* We expected the child returned from barrier wait */
	cnt = 0;	
	do{
		sleep(1);
	}while (thread_state != EXITING_THREAD && cnt++ < 3); 
	
	if(thread_state == ENTERED_THREAD)
	{
		printf("Test FAILED: child thread still blocked on "
			"barrier wait\n");
		return PTS_FAIL;
	}
	else if(thread_state != EXITING_THREAD)
	{
		printf("main: Unexpected thread state: %d\n", thread_state);
		return PTS_UNRESOLVED;
	}

	if(pthread_join(child_thread, NULL) != 0)
	{
		printf("main: Error at pthread_join()\n");
		exit(PTS_UNRESOLVED);
	}

	if(pthread_barrier_destroy(&barrier) != 0)
	{
		printf("Error at pthread_barrier_destroy()");
		return PTS_UNRESOLVED;
	}	

	printf("Test PASSED\n");
	return PTS_PASS;
}

//.........这里部分代码省略.........

	printf("OpenMP:\n");
	printf("|NSize|Iterations| Seq | Th01 | Th02 | Th04 | Th08 | Par16|\n");

	// for each input size
	for(c=0; c<NSIZE; c++){
		n=Ns[c];
		printf("| %d | %d |",n,TIMES);

		/* Run sequential algorithm */
		result.tv_usec=0;
		gettimeofday (&startt, NULL);
		for (t=0; t<TIMES; t++) {
			init(n);
			seq_function(n, 0);
		}
		gettimeofday (&endt, NULL);
		result.tv_usec = (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
		printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);

		/* Run OpenMP algorithm */
		for(nt=1; nt<NUM_THREADS; nt=nt<<1){
			result.tv_sec=0; 
			result.tv_usec=0;
			gettimeofday (&startt, NULL);
			for (t=0; t<TIMES; t++) 
			{
				init(n);
				openmp_function(n, 0, nt);
			}
			gettimeofday (&endt, NULL);
			result.tv_usec += (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
			printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);
		}
		printf("\n");
	}

	/* Initialize and set thread detached attribute */
	pthread_attr_init(&attr);
	pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

	printf("Pthread:\n");
	printf("|NSize|Iterations| Seq | Th01 | Th02 | Th04 | Th08 | Par16|\n");

	// for each input size
	for(c=0; c<NSIZE; c++){
		n=Ns[c];
		printf("| %d | %d |",n,TIMES);

		/* Run sequential algorithm */
		result.tv_usec=0;
		gettimeofday (&startt, NULL);
		for (t=0; t<TIMES; t++) {
			init(n);
			seq_function(n, 0);
		}
		gettimeofday (&endt, NULL);
		result.tv_usec = (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
		printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);

		/* Run pthread algorithm(s) */
		for(nt=1; nt<NUM_THREADS; nt=nt<<1){
			if(pthread_barrier_init(&barr, NULL, nt+1))
			{
				printf("Could not create a barrier\n");
				return -1;
			}
			if(pthread_barrier_init(&internal_barr, NULL, nt))
			{
				printf("Could not create a barrier\n");
				return -1;
			}

			result.tv_sec=0; 
			result.tv_usec=0;

			gettimeofday (&startt, NULL);
			for (t=0; t<TIMES; t++) 
			{
				init(n);
				par_function(n, nt);
				// pthread_barrier_wait(&barr);
			}
			gettimeofday (&endt, NULL);

			if (pthread_barrier_destroy(&barr)) {
				printf("Could not destroy the barrier\n");
				return -1;
			}
			if (pthread_barrier_destroy(&internal_barr)) {
				printf("Could not destroy the barrier\n");
				return -1;
			}
			result.tv_usec += (endt.tv_sec*1000000+endt.tv_usec) - (startt.tv_sec*1000000+startt.tv_usec);
			printf(" %ld.%06ld | ", result.tv_usec/1000000, result.tv_usec%1000000);
		}
		printf("\n");
	}
	pthread_exit(NULL);
}

int main (int argc, char **argv) 
{
    int i;
    unsigned int total_len = 0;
    struct timeval begtime,endtime;
    FILE *sfd,*pfd;
    char sfilename[20] = "string";
    char pfilename[20] = "pattern";

	
//=============================================== 
    if (argc < 4)
    {
        fprintf (stderr,"Usage: acsmx stringfile patternfile ...  -nocase\n");
        exit (0);
    }
    strcpy (sfilename, argv[1]);
    sfd = fopen(sfilename,"r");
    if(sfd == NULL)
    {
        fprintf(stderr,"Open file error!\n");
        exit(1);
    }

    strcpy(pfilename,argv[2]);
    pfd = fopen(pfilename,"r");
    if(sfd == NULL)
    {
        fprintf(stderr,"Open file error!\n");
        exit(1);
    }
    thread_num = atoi(argv[3]);
   	acsm = acsmNew (thread_num); 
   
//read patterns    
	i = 0;
    while(fgets(pattern,MAXPATTERNLEN,pfd))
    {
    	int len = strlen(pattern);
    	acsmAddPattern (acsm, pattern, len-1);
		i++;
    }
    fclose(pfd);
    printf("\n\nread %d patterns\n\n===============================",i);
    /* Generate GtoTo Table and Fail Table */
    acsmCompile (acsm);
//========================================================= 

    /*read string*/
    for(i = 0;i < MAXLINE;i++)
    {
    	if(!fgets(text[i],MAXLEN,sfd))
    		break;
   		total_len += strlen(text[i]) - 1; //ignore the last char '\n'
    }
    line = i;
    fclose(sfd);
    printf("\n\nreading finished...\n=============================\n\n");
    printf("%d lines\t%d bytes",line,total_len);
    printf("\n\n=============================\n");
    
    gettimeofday(&begtime,0);
    //create multi_thread
    thread_array = calloc(thread_num,sizeof(pthread_t));
	valid_len_array = calloc(thread_num,sizeof(unsigned int));
    pthread_barrier_init(&barrier_thread,NULL,thread_num);
    pthread_barrier_init(&barrier_validation,NULL,thread_num);
 
    for(i = 0;i < thread_num; i++)
	{
		pthread_create(&thread_array[i], NULL, SearchThread, (void*)i);
    }
//=========================================================== 
    int err;
    for(i = 0;i < thread_num;i++)
    {
        err = pthread_join(thread_array[i],NULL);
        if(err != 0)
        {
            printf("can not join with thread %d:%s\n", i,strerror(err));
        }
    }
    gettimeofday(&endtime,0);

    PrintSummary(acsm);
    acsmFree (acsm);

    printf ("\n### AC Match Finished ###\n");
    printf("\nTime Cost: %lu us\n\n",(endtime.tv_sec - begtime.tv_sec)*1000000 + (endtime.tv_usec - begtime.tv_usec));
    printf ("\n====================================\n\n");
    printf ("Validation Stage Len:\n\n");
    for(i = 0;i < thread_num;i++)
        printf("rank%d\t%u\n",i,valid_len_array[i]);
    printf ("\n====================================\n\n");
   
    free(thread_array);
    free(valid_len_array);
    pthread_barrier_destroy(&barrier_thread);
    pthread_barrier_destroy(&barrier_validation);
    return 0;
//.........这里部分代码省略.........

/**
 * @brief destroys a created barrier
 *
 * @param bar     pointer to the barrier

 * @returns SMELT_SUCCESS or e