* bytes. The MTHREShold is where we stop finding a better median.
*/
-#define THRESH 4 /* threshold for insertion */
-#define MTHRESH 6 /* threshold for median */
+#define THRESH 4 /* threshold for insertion */
+#define MTHRESH 6 /* threshold for median */
-typedef struct {
+typedef struct
+{
word qsz; /* size of each record */
word thresh; /* THRESHold in chars */
word mthresh; /* MTHRESHold in chars */
- int (*qcmp) (const void *, const void *); /* the comparison routine */
+ int (*qcmp) (const void *, const void *); /* the comparison routine */
} qst_t;
-static void qst (qst_t * q, char * base, char *max);
+static void qst (qst_t * q, char *base, char *max);
/*
* qqsort: First, set up some global parameters for qst to share.
*/
void
-qsort (void * base, uword n, uword size,
+qsort (void *base, uword n, uword size,
int (*compar) (const void *, const void *))
{
char *i;
char *min;
char c;
char *max;
- qst_t _q, * q = &_q;
+ qst_t _q, *q = &_q;
if (n <= 1)
return;
q->thresh = q->qsz * THRESH;
q->mthresh = q->qsz * MTHRESH;
max = base + n * q->qsz;
- if (n >= THRESH) {
- qst(q, base, max);
- hi = base + q->thresh;
- } else {
- hi = max;
- }
+ if (n >= THRESH)
+ {
+ qst (q, base, max);
+ hi = base + q->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 += q->qsz) < hi;) {
- if ((*compar) (j, lo) > 0)
- j = lo;
- }
- if (j != base) { /* swap j into place */
- for (i = base, hi = base + q->qsz; i < hi;) {
- c = *j;
- *j++ = *i;
- *i++ = c;
+ for (j = lo = base; (lo += q->qsz) < hi;)
+ {
+ if ((*compar) (j, lo) > 0)
+ j = lo;
+ }
+ if (j != base)
+ { /* swap j into place */
+ for (i = base, hi = base + q->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],
* the standard insertion sort shift on a character at a time basis for
* each element in the frob.
*/
- for (min = base; (hi = min += q->qsz) < max;) {
- while ((*q->qcmp) (hi -= q->qsz, min) > 0);
- if ((hi += q->qsz) != min) {
- for (lo = min + q->qsz; --lo >= min;) {
- c = *lo;
- for (i = j = lo; (j -= q->qsz) >= hi; i = j)
- *i = *j;
- *i = c;
- }
+ for (min = base; (hi = min += q->qsz) < max;)
+ {
+ while ((*q->qcmp) (hi -= q->qsz, min) > 0);
+ if ((hi += q->qsz) != min)
+ {
+ for (lo = min + q->qsz; --lo >= min;)
+ {
+ c = *lo;
+ for (i = j = lo; (j -= q->qsz) >= hi; i = j)
+ *i = *j;
+ *i = c;
+ }
+ }
}
- }
}
*/
static void
-qst(qst_t *q, char *base, char *max)
+qst (qst_t * q, char *base, char *max)
{
char *i;
char *j;
char *mid;
int ii;
char c;
- char *tmp;
- int lo;
- int hi;
+ char *tmp;
+ int lo;
+ int hi;
int qsz = q->qsz;
- lo = (int)(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 >= q->mthresh) {
- j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
- if ((*q->qcmp) (j, (tmp = max - qsz)) > 0) {
- /* switch to first loser */
- j = (j == jj ? i : jj);
- if ((*q->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 && (*q->qcmp) (i, mid) <= 0)
- i += qsz;
- while (j > mid) {
- if ((*q->qcmp) (mid, j) <= 0) {
- j -= qsz;
- continue;
+ lo = (int) (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 >= q->mthresh)
+ {
+ j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
+ if ((*q->qcmp) (j, (tmp = max - qsz)) > 0)
+ {
+ /* switch to first loser */
+ j = (j == jj ? i : jj);
+ if ((*q->qcmp) (j, tmp) < 0)
+ j = tmp;
+ }
+ if (j != i)
+ {
+ ii = qsz;
+ do
+ {
+ c = *i;
+ *i++ = *j;
+ *j++ = c;
+ }
+ while (--ii);
+ }
}
- 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;
+ /* Semi-standard quicksort partitioning/swapping */
+ for (i = base, j = max - qsz;;)
+ {
+ while (i < mid && (*q->qcmp) (i, mid) <= 0)
+ i += qsz;
+ while (j > mid)
+ {
+ if ((*q->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 update 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 = (int) (j - base)) <= (hi = (int) (max - i)))
+ {
+ if (lo >= q->thresh)
+ qst (q, base, j);
+ base = i;
+ lo = hi;
+ }
+ else
+ {
+ if (hi >= q->thresh)
+ qst (q, i, max);
+ max = j;
}
- 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 update 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 = (int)(j - base)) <= (hi = (int)(max - i))) {
- if (lo >= q->thresh)
- qst(q, base, j);
- base = i;
- lo = hi;
- } else {
- if (hi >= q->thresh)
- qst(q, i, max);
- max = j;
}
- } while (lo >= q->thresh);
+ while (lo >= q->thresh);
}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff