diff options
author | Denis Bitouzé <dbitouze@wanadoo.fr> | 2021-02-25 18:23:07 +0000 |
---|---|---|
committer | Denis Bitouzé <dbitouze@wanadoo.fr> | 2021-02-25 18:23:07 +0000 |
commit | c6101f91d071883b48b1b4b51e5eba0f36d9a78d (patch) | |
tree | 1bf7f5a881d7a4f5c5bf59d0b2821943dd822372 /Build/source/texk/mendexk/qsort.c | |
parent | 07ee7222e389b0777456b427a55c22d0e6ffd267 (diff) |
French translation for tlmgr updated
git-svn-id: svn://tug.org/texlive/trunk@57912 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/mendexk/qsort.c')
-rw-r--r-- | Build/source/texk/mendexk/qsort.c | 206 |
1 files changed, 0 insertions, 206 deletions
diff --git a/Build/source/texk/mendexk/qsort.c b/Build/source/texk/mendexk/qsort.c deleted file mode 100644 index df95890e68b..00000000000 --- a/Build/source/texk/mendexk/qsort.c +++ /dev/null @@ -1,206 +0,0 @@ -/* - * - * This file is part of - * MakeIndex - A formatter and format independent index processor - * - * This file is public domain software donated by - * Nelson Beebe (beebe@science.utah.edu). - * - */ - -/* - * qsort.c: Our own version of the system qsort routine which is faster by an - * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is - * the insertion sort threshold, and has been adjusted for records of size 48 - * bytes. The MTHREShold is where we stop finding a better median. - */ -#include "qsort.h" /* qq_compar_fn_t type and qqsort() prototype */ - -#define THRESH 4 /* threshold for insertion */ -#define MTHRESH 6 /* threshold for median */ - -static int qsz; /* size of each record */ -static int thresh; /* THRESHold in chars */ -static int mthresh; /* MTHRESHold in chars */ - -static qq_compar_fn_t qcmp; /* the comparison routine */ -static void qst(char *base, char *max); -/* - * qqsort: First, set up some global parameters for qst to share. Then, - * quicksort with qst(), and then a cleanup insertion sort ourselves. Sound - * simple? It's not... - */ - -void -qqsort(void *base, size_t n, size_t size, qq_compar_fn_t compar) -{ - register char *i; - register char *j; - register char *lo; - register char *hi; - register char *min; - register char c; - char *max; - - if (n <= 1) - return; - qsz = size; - qcmp = compar; - thresh = qsz * THRESH; - mthresh = qsz * MTHRESH; - max = (char *)base + n * qsz; - if (n >= THRESH) { - qst(base, max); - hi = (char *)base + thresh; - } else { - hi = max; - } - /* - * First put smallest element, which must be in the first THRESH, in the - * first position as a sentinel. This is done just by searching the - * first THRESH elements (or the first n if n < THRESH), finding the min, - * and swapping it into the first position. - */ - for (j = lo = base; (lo += qsz) < hi;) { - if ((*qcmp) (j, lo) > 0) - j = lo; - } - if (j != base) { /* swap j into place */ - for (i = base, hi = i + qsz; i < hi;) { - c = *j; - *j++ = *i; - *i++ = c; - } - } - /* - * With our sentinel in place, we now run the following hyper-fast - * insertion sort. For each remaining element, min, from [1] to [n-1], - * set hi to the index of the element AFTER which this one goes. Then, do - * the standard insertion sort shift on a character at a time basis for - * each element in the frob. - */ - for (min = base; (hi = min += qsz) < max;) { - while ((*qcmp) (hi -= qsz, min) > 0); - if ((hi += qsz) != min) { - for (lo = min + qsz; --lo >= min;) { - c = *lo; - for (i = j = lo; (j -= qsz) >= hi; i = j) - *i = *j; - *i = c; - } - } - } -} - - - -/* - * qst: Do a quicksort. First, find the median element, and put that one in - * the first place as the discriminator. (This "median" is just the median - * of the first, last and middle elements). (Using this median instead of - * the first element is a big win). Then, the usual partitioning/swapping, - * followed by moving the discriminator into the right place. Then, figure - * out the sizes of the two partions, do the smaller one recursively and the - * larger one via a repeat of this code. Stopping when there are less than - * THRESH elements in a partition and cleaning up with an insertion sort (in - * our caller) is a huge win. All data swaps are done in-line, which is - * space-losing but time-saving. (And there are only three places where this - * is done). - */ - -static void -qst(char *base, char *max) -{ - register char *i; - register char *j; - register char *jj; - register char *mid; - register int ii; - register char c; - void *tmp; - int lo; - int hi; - - lo = max - base; /* number of elements as chars */ - do { - /* - * At the top here, lo is the number of characters of elements in the - * current partition. (Which should be max - base). Find the median - * of the first, last, and middle element and make that the middle - * element. Set j to largest of first and middle. If max is larger - * than that guy, then it's that guy, else compare max with loser of - * first and take larger. Things are set up to prefer the middle, - * then the first in case of ties. - */ - mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1); - if (lo >= mthresh) { - j = ((*qcmp) ((jj = base), i) > 0 ? jj : i); - if ((*qcmp) (j, (tmp = max - qsz)) > 0) { - /* switch to first loser */ - j = (j == jj ? i : jj); - if ((*qcmp) (j, tmp) < 0) - j = tmp; - } - if (j != i) { - ii = qsz; - do { - c = *i; - *i++ = *j; - *j++ = c; - } while (--ii); - } - } - /* Semi-standard quicksort partitioning/swapping */ - for (i = base, j = max - qsz;;) { - while (i < mid && (*qcmp) (i, mid) <= 0) - i += qsz; - while (j > mid) { - if ((*qcmp) (mid, j) <= 0) { - j -= qsz; - continue; - } - tmp = i + qsz; /* value of i after swap */ - if (i == mid) { /* j <-> mid, new mid is j */ - mid = jj = j; - } else { /* i <-> j */ - jj = j; - j -= qsz; - } - goto swap; - } - if (i == mid) { - break; - } else { /* i <-> mid, new mid is i */ - jj = mid; - tmp = mid = i; /* value of i after swap */ - j -= qsz; - } - swap: - ii = qsz; - do { - c = *i; - *i++ = *jj; - *jj++ = c; - } while (--ii); - i = tmp; - } - /* - * Look at sizes of the two partitions, do the smaller one first by - * recursion, then do the larger one by making sure lo is its size, - * base and max are updated correctly, and branching back. But only - * repeat (recursively or by branching) if the partition is of at - * least size THRESH. - */ - i = (j = mid) + qsz; - if ((lo = j - base) <= (hi = max - i)) { - if (lo >= thresh) - qst(base, j); - base = i; - lo = hi; - } else { - if (hi >= thresh) - qst(i, max); - max = j; - } - } while (lo >= thresh); -} |