cindex.c

Go to the documentation of this file.

 
#include <stdlib.h>
 
/* Prototype binary search function */
int dichotomy(int nT, int *T, int e);
 
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);
    }
    return 0;
}
 
 
#ifdef W_OPENMP
#include <omp.h>
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;
}