static int archive_compare_files(const void *a, const void *b, void *thunk) {
#else
// OSX, *BSD
static int archive_compare_files(void *thunk, const void *a, const void *b) {
#endif
    return english_compare_natural((((struct archive *)thunk)->names[*((int*)a)]),
                                   (((struct archive *)thunk)->names[*((int*)b)]));
}

static void archive_make_map(struct archive *ar) {
    for (int i = 0; i < ar->files; i++)
        ar->map[i] = i;

#ifdef __gnu_linux__
    qsort_r(&(ar->map), ar->files, sizeof(int), archive_compare_files, (void*)ar);
#else
    // OSX, *BSD
    qsort_r(&(ar->map), ar->files, sizeof(int), (void*)ar, archive_compare_files);
#endif
}

//////////////////////////////////////////////////////////////////////

static void archive_free(struct archive *ar) {
    free(ar);
}

void qsort_r( int* ar, int start, int end )
{
	int l = start;
	int r = end;
	int p = ar[start];

	if( start >= end )
		return;

	while( l < r )
	{
		if( ar[l] <= p )
			l++;
		else if( ar[r] >= p )
			r--;
		else
			swap( ar+l, ar+r );
	}

	if( ar[l] < p )
	{
		swap( ar+start, ar+l );
		l--;
	}
	else
	{
		l--;
		swap( ar+start, ar+l );
	}

	qsort_r( ar, start, l );
	qsort_r( ar, r, end );

	return;
}

void crowd_cut(list** l, size_t nn, size_t n, size_t m, double* xs, double* ys) {
    double* dis = (double*) malloc(sizeof(double) * nn);
    size_t* a = (size_t*) malloc(sizeof(size_t) * n);
    list* tmp;
    int k = 0;

    for (size_t i=0; i<nn; i++) dis[i] = 0;

    while (*l) {
        a[k++] = (*l)->data;
        tmp = *l;
        *l = (*l)->next;
        free(tmp);
    }


    qsort_r(a, n, sizeof(size_t), cmp_l, xs);
    dis[a[0]] = dis[a[n-1]] = INF;
    if (xs[a[n-1]] != xs[a[0]])
        for (size_t i=1; i<n-1; i++)
            dis[a[i]] += (xs[a[i+1]] - xs[a[i-1]]) / (xs[a[n-1]] - xs[a[0]]);

    qsort_r(a, n, sizeof(size_t), cmp_l, ys);
    dis[a[0]] = dis[a[n-1]] = INF;
    if (ys[a[n-1]] != ys[a[0]])
        for (size_t i=1; i<n-1; i++)
            dis[a[i]] += (ys[a[i+1]] - ys[a[i-1]]) / (ys[a[n-1]] - ys[a[0]]);

    qsort_r(a, n, sizeof(size_t), cmp_l, dis);
    for (size_t i=1; i<=m; i++)
        add_item(l, a[n-i]);

    free(a);
    free(dis);
}

void
tvh_qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg)
{
#if defined(PLATFORM_FREEBSD) || defined(PLATFORM_DARWIN)
    struct tvh_qsort_data swap_arg = {arg, compar};
    qsort_r(base, nmemb, size, &swap_arg, tvh_qsort_swap);
#else
    qsort_r(base, nmemb, size, compar, arg);
#endif
}

void QuickSort( void *base, size_t num, size_t width, void *context,
							int ( *compare )(void *, const void *, const void *) ) {
#if OG_WIN32
	qsort_s( base, num, width, compare, context );
#elif OG_MACOS_X
	qsort_r( base, num, width, context, compare );
#elif OG_LINUX
	CompareWrapper data(context, compare);
	qsort_r( base, num, width, CompareWrapper::Compare, &data );
#endif
}

static int compare_for_sort_index (const void *v1, const void *v2)
{
#elif defined(HAVE_QSORT_R)
static int compare_for_sort_index (void *thunk, const void *v1, const void *v2)
{
  const int *tab_to_sort = thunk;
#else 
#error "please provide some kind of thread-local storage"
#endif
  
  int dt = tab_to_sort[*(int *)v1] - tab_to_sort[*(int *)v2];
  if (dt) 
    return dt;
  return *(int *)v1 - *(int *)v2;
}


void ivec_sort_index (const int *tab, int n, int *perm) 
{
  int i;

  for (i = 0 ; i < n ; i++) 
    perm[i] = i;

#ifdef HAVE_TLS
  tab_to_sort = tab;
  qsort (perm, n, sizeof(int), compare_for_sort_index);
#elif defined(HAVE_QSORT_R)
  qsort_r (perm, n, sizeof(int), (void*)tab, compare_for_sort_index);
#endif
}

void polygon(POINT *points[], size_t n)
{
    // According to Wikipedia, a polygon of one point is a point and a polygon
    // of two is a straight line and they are both valid.
    assert (n >= 1);

    // Extracts the leftmost point and swaps it with the first point of the
    // array.
    for (size_t i = 1; i < n; i++) {
        if (points[i]->x < points[0]->x) {
            POINT *tmp = points[i];
            points[i] = points[0];
            points[0] = tmp;
        }
    }

    // Uses the leftmost point as the first point of the polygon.
    // Sort the remainder of the vector by comparing the relative slope of each
    // point to this first point.
    qsort_r(points + 1, n - 1, sizeof (POINT *), point_cmp, (void *) points[0]);

    // By selecting the leftmost point, I'm able to compare points by their
    // slopes instead of their angles (because I don't care in which side of the
    // first point they sit).
    // This is way faster because I avoid expensive trigonometric computations.
    // Moreover, as the computation and comparison of two slopes is fast, I
    // don't cache them.
}

static FTSENT *
fts_sort(FTS *sp, FTSENT *head, size_t nitems)
{
	FTSENT **ap, *p;

	/*
	 * Construct an array of pointers to the structures and call qsort(3).
	 * Reassemble the array in the order returned by qsort.  If unable to
	 * sort for memory reasons, return the directory entries in their
	 * current order.  Allocate enough space for the current needs plus
	 * 40 so don't realloc one entry at a time.
	 */
	if (nitems > sp->fts_nitems) {
		sp->fts_nitems = nitems + 40;
		if ((sp->fts_array = reallocf(sp->fts_array,
		    sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
			sp->fts_nitems = 0;
			return (head);
		}
	}
	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
		*ap++ = p;
	if (ISSET(FTS_COMPAR_B))
		qsort_r(sp->fts_array, nitems, sizeof(FTSENT *),
			sp->fts_compar_b, fts_compar_b);
	else
		qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
	for (head = *(ap = sp->fts_array); --nitems; ++ap)
		ap[0]->fts_link = ap[1];
	ap[0]->fts_link = NULL;
	return (head);
}

/* Compute (and allocate) migration price matrix for optimization */
static void
price_routes(PRICEMAT *pm, const RBFNODE *from_rbf, const RBFNODE *to_rbf)
{
	FVECT	*vto = (FVECT *)malloc(sizeof(FVECT) * to_rbf->nrbf);
	int	i, j;

	pm->nrows = from_rbf->nrbf;
	pm->ncols = to_rbf->nrbf;
	pm->price = (float *)malloc(sizeof(float) * pm->nrows*pm->ncols);
	pm->sord = (short *)malloc(sizeof(short) * pm->nrows*pm->ncols);
	
	if ((pm->price == NULL) | (pm->sord == NULL) | (vto == NULL)) {
		fprintf(stderr, "%s: Out of memory in migration_costs()\n",
				progname);
		exit(1);
	}
	for (j = to_rbf->nrbf; j--; )		/* save repetitive ops. */
		ovec_from_pos(vto[j], to_rbf->rbfa[j].gx, to_rbf->rbfa[j].gy);

	for (i = from_rbf->nrbf; i--; ) {
	    const double	from_ang = R2ANG(from_rbf->rbfa[i].crad);
	    FVECT		vfrom;
	    ovec_from_pos(vfrom, from_rbf->rbfa[i].gx, from_rbf->rbfa[i].gy);
	    for (j = to_rbf->nrbf; j--; ) {
		double		dprod = DOT(vfrom, vto[j]);
		pricerow(pm,i)[j] = ((dprod >= 1.) ? .0 : acos(dprod)) +
				fabs(R2ANG(to_rbf->rbfa[j].crad) - from_ang);
		psortrow(pm,i)[j] = j;
	    }
	    qsort_r(psortrow(pm,i), pm->ncols, sizeof(short), pm, &msrt_cmp);
	}
	free(vto);
}

int main() {
    int array;
    int baton;
    qsort_r(&array, 1, sizeof(int), &baton, cmp);
    //printf("#define NEED_QSORT_R 0\n");
    return 0;
}

void wget_vector_sort(wget_vector_t *v)
{
	if (v && v->cmp) {
		qsort_r(v->entry, v->cur, sizeof(void *), _compare, v);
		v->sorted = 1;
	}
}

void
qsort_b(void *base, size_t nel, size_t width,
	DECLARE_BLOCK(int, compar, const void *, const void *))
{
	qsort_r(base, nel, width, compar,
		(int (*)(void *, const void *, const void *))
		GET_BLOCK_FUNCTION(compar));
}

void Q_SSetReverseSort(sset_t *ss, qboolean caseSensitive) {
    int (*func)(void *, const void *, const void *) = caseSensitive ? revtokcmp : revtokcasecmp;
#ifdef WIN32
    qsort_s(&ss->tokens[0], ss->currentSize, sizeof(int32_t), func, (void *)&ss->table);
#else
    qsort_r(&ss->tokens[0], ss->currentSize, sizeof(int32_t), (void *)&ss->table, func);
#endif
}

static void printObj(CFPropertyListRef obj, struct printContext* c) {
	CFTypeID typeID = CFGetTypeID(obj);
	if (typeID == _CFKeyedArchiverUIDGetTypeID()) {
		unsigned uid = _CFKeyedArchiverUIDGetValue(obj);
		CFPropertyListRef refObj = CFArrayGetValueAtIndex(c->objs, uid);
		if (CFEqual(refObj, CFSTR("$null")))
			printf("nil");
		else if (c->refCount[uid] > 1 && isComplexObj(refObj))
			printf("{CF$UID = %u;}", uid);
		else
			printObj(refObj, c);
	} else if (typeID == CFArrayGetTypeID()) {
		printf("(\n");
		++ c->tabs;
		CFArrayApplyFunction(obj, CFRangeMake(0, CFArrayGetCount(obj)), (CFArrayApplierFunction)&printObjAsArrayEntry, c);
		-- c->tabs;
		for (unsigned i = 0; i < c->tabs; ++ i)
			printf("\t");
		printf(")");
	} else if (typeID == CFDictionaryGetTypeID()) {
		CFStringRef className = CFDictionaryGetValue(obj, CFSTR("$classname"));
		if (className != NULL)
			printObjAsClassName(className);
		else {
			printf("{\n");
			++ c->tabs;
			CFIndex dictCount = CFDictionaryGetCount(obj);
			
			struct dictionarySorterContext sc;
			sc.keys = malloc(sizeof(CFStringRef)*dictCount);
			sc.values = malloc(sizeof(CFPropertyListRef)*dictCount);
			unsigned* mapping = malloc(sizeof(unsigned)*dictCount);
			for (unsigned i = 0; i < dictCount; ++ i)
				mapping[i] = i;
			CFDictionaryGetKeysAndValues(obj, (const void**)sc.keys, sc.values);
			qsort_r(mapping, dictCount, sizeof(unsigned), &sc, (int(*)(void*,const void*,const void*))&dictionaryComparer);
			for (unsigned i = 0; i < dictCount; ++ i)
				printObjAsDictionaryEntry(sc.keys[mapping[i]], sc.values[mapping[i]], c);
			free(mapping);
			free(sc.keys);
			free(sc.values);
			-- c->tabs;
			for (unsigned i = 0; i < c->tabs; ++ i)
				printf("\t");
			printf("}");
		}
	} else if (typeID == CFDataGetTypeID())
		printObjAsData(obj);
	else if (typeID == CFNumberGetTypeID())
		printObjAsNumber(obj);
	else if (typeID == CFStringGetTypeID())
		printObjAsString(obj);
	else if (typeID == CFBooleanGetTypeID())
		printf(CFBooleanGetValue(obj) ? "true" : "false");
	else if (typeID == CFDateGetTypeID()) 
		printf("/*date*/ %0.09g", CFDateGetAbsoluteTime(obj));

}

void color_table_sort(color_table table, axis component)
{
	
	/* Condition d'erreur qui permetent de quitter la focntion si necessaire*/
	assert(table != NULL);
	
	qsort_r(table->colors, color_table_get_nb_color(table), sizeof(color), compare, &component);
	
}

puzzle_size compute_puzzle_size(IplImage *puzzle, IplImage **annotated) {
    IplImage *threshold_image = _grid(puzzle);

    *annotated = cvCloneImage(puzzle);
    cvCvtColor(threshold_image, *annotated, CV_GRAY2RGB);

    // the logic here is to "rank" the possible sizes, by computing the average pixel intensity
    // in the vicinity of where the lines should be.
    unsigned short guess_id = 0;
    puzzle_size guesses[PUZZLE_SIZE_MAX - PUZZLE_SIZE_MIN + 1];
    unsigned long means[PUZZLE_SIZE_MAX + 1];

    const int fuzz = threshold_image->width / 50;
    for (puzzle_size guess_size = PUZZLE_SIZE_MIN; guess_size <= PUZZLE_SIZE_MAX; ++guess_size) {
        guesses[guess_id++] = guess_size;
        means[guess_size] = 0;

        for (unsigned short i = 1; i < guess_size; ++i) {
            int center = i * (threshold_image->width / guess_size);
            for (int x = 0; x < threshold_image->width; ++x) {
                for (int y = center - fuzz; y < center + fuzz; ++y) {
                    CvScalar s = cvGet2D(threshold_image, y, x);
                    means[guess_size] += s.val[0];
                }
            }
            for (int x = center - fuzz; x < center + fuzz; ++x) {
                for (int y = 0; y < threshold_image->height; ++y) {
                    CvScalar s = cvGet2D(threshold_image, y, x);
                    means[guess_size] += s.val[0];
                }
            }
        }
        means[guess_size] /= (guess_size - 1);
    }

    qsort_r(guesses, sizeof(guesses) / sizeof(puzzle_size), sizeof(puzzle_size), (void *)means, _compare_means);

    puzzle_size size = guesses[0];

    // evenly divisible sizes are easily confused. Err on the side of the larger size puzzle.
    puzzle_size confusable[][2] = { { 4, 8 }, { 3, 9 }, { 3, 6 } };
    for (int i = 0; i < (sizeof(confusable) / sizeof(puzzle_size) / 2); ++i) {
        if ((guesses[0] == confusable[i][0]) && (guesses[1] == confusable[i][1]) && (means[guesses[0]] - means[guesses[1]] < means[guesses[1]] - means[guesses[2]])) {
            size = confusable[i][1];
            break;
        }
    }

    for (unsigned short i = 1; i < size; ++i) {
        int center = i * (threshold_image->width / size);
        cvRectangle(*annotated, cvPoint(0, center - fuzz), cvPoint(threshold_image->width, center + fuzz), CV_RGB(255, 0, 0), 2, 8, 0);
        cvRectangle(*annotated, cvPoint(center - fuzz, 0), cvPoint(center + fuzz, threshold_image->height), CV_RGB(255, 0, 0), 2, 8, 0);
    }
    cvReleaseImage(&threshold_image);

    return size;
}

/**
 * Sort endpoints in place in descending order of preference.
 * @param endpoints array of endpoint pointers.
 */
static void
endpoints_preference_sort(const as_endpoint* endpoints[], size_t n_endpoints)
{
	// Random tie breaker to load balance between two equivalent endpoints.
	int tie_breaker = rand();

	qsort_r(endpoints, n_endpoints, sizeof(as_endpoint*),
		endpoint_preference_compare, &tie_breaker);
}

/** Sorts all observations by j,i so that they can be processed in a single
 * cycle over horizontal grid cells.
 */
static void das_sortobs_byij(dasystem* das)
{
    observations* obs = das->obs;
    int o, e;

    if (das->sort_mode == OBS_SORTMODE_IJ)
        return;
    if (obs->nobs == 0)
        return;

    enkf_printf("    sorting obs by ij:\n");
    qsort_r(obs->data, obs->nobs, sizeof(observation), cmp_obs_byij, das);

    if (das->s_f != NULL) {
        double* s = calloc(obs->nobs, sizeof(double));

        for (o = 0; o < obs->nobs; ++o)
            s[o] = das->s_f[obs->data[o].id];
        memcpy(das->s_f, s, obs->nobs * sizeof(double));

        for (o = 0; o < obs->nobs; ++o)
            s[o] = das->std_f[obs->data[o].id];
        memcpy(das->std_f, s, obs->nobs * sizeof(double));

        free(s);
    }

    if (das->s_a != NULL) {
        double* s = calloc(obs->nobs, sizeof(double));

        for (o = 0; o < obs->nobs; ++o)
            s[o] = das->s_a[obs->data[o].id];
        memcpy(das->s_a, s, obs->nobs * sizeof(double));

        for (o = 0; o < obs->nobs; ++o)
            s[o] = das->std_a[obs->data[o].id];
        memcpy(das->std_a, s, obs->nobs * sizeof(double));

        free(s);
    }

    {
        ENSOBSTYPE* S = calloc(obs->nobs, sizeof(ENSOBSTYPE));

        for (e = 0; e < das->nmem; ++e) {
            ENSOBSTYPE* Se = das->S[e];

            for (o = 0; o < obs->nobs; ++o)
                S[o] = Se[obs->data[o].id];
            memcpy(Se, S, obs->nobs * sizeof(ENSOBSTYPE));
        }
        free(S);
    }

    das->sort_mode = OBS_SORTMODE_IJ;
}

void d_argsort(double *vec, int *idxs, int N)
{
    int i;
    for(i = 0; i < N; i++) {
        idxs[i] = i;
    }

    /* perform qsort */
    qsort_r(idxs, N, sizeof(int), d_argsort_compare, (void *)vec);
}

void
qsort_r (void *base, size_t nmemb, size_t size,
         int (*cmp) (void const *, void const *, void *),
         void *arg)
{
# undef qsort_r
  struct thunk thunk;
  thunk.cmp = cmp;
  thunk.arg = arg;
  qsort_r (base, nmemb, size, &thunk, thunk_cmp);
}