diff options
Diffstat (limited to 'vppinfra/vppinfra/qsort.c')
| -rw-r--r-- | vppinfra/vppinfra/qsort.c | 271 |
1 files changed, 155 insertions, 116 deletions
diff --git a/vppinfra/vppinfra/qsort.c b/vppinfra/vppinfra/qsort.c index b9732aaa29c..2faa5897eb2 100644 --- a/vppinfra/vppinfra/qsort.c +++ b/vppinfra/vppinfra/qsort.c @@ -33,17 +33,18 @@ * 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. @@ -52,7 +53,7 @@ static void qst (qst_t * q, char * base, char *max); */ void -qsort (void * base, uword n, uword size, +qsort (void *base, uword n, uword size, int (*compar) (const void *, const void *)) { char *i; @@ -62,7 +63,7 @@ qsort (void * base, uword n, uword size, char *min; char c; char *max; - qst_t _q, * q = &_q; + qst_t _q, *q = &_q; if (n <= 1) return; @@ -72,29 +73,35 @@ qsort (void * base, uword n, uword size, 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], @@ -102,17 +109,20 @@ qsort (void * base, uword n, uword size, * 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; + } + } } - } } @@ -132,7 +142,7 @@ qsort (void * base, uword n, uword size, */ static void -qst(qst_t *q, char *base, char *max) +qst (qst_t * q, char *base, char *max) { char *i; char *j; @@ -140,91 +150,120 @@ qst(qst_t *q, char *base, char *max) 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: + */ |