diff options
author | 2020-04-24 16:07:37 -0400 | |
---|---|---|
committer | 2020-08-13 17:20:47 +0000 | |
commit | 3b49dc6cc80e1a373363b2ff055327dda89e50db (patch) | |
tree | 8aba4de78be63336e5225abb9df5afc4b235f4d2 /src/vppinfra | |
parent | eaef2de7f92da67b6f47afdeac85d9d793d47470 (diff) |
vppinfra: finish deprecating qsort.c
Minor change to vec_sort_with_function(...): don't depend on the qsort
implementation to deal with null, zero-long, or 1-long vectors
Type: fix
Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: I7bd7b0421673d2a025363089562aa7c6266fba66
(cherry picked from commit f593b5792031b3797cdcdfd3fbb33ac4de8c9a5d)
Diffstat (limited to 'src/vppinfra')
-rw-r--r-- | src/vppinfra/qsort.c | 269 | ||||
-rw-r--r-- | src/vppinfra/vec.h | 10 |
2 files changed, 7 insertions, 272 deletions
diff --git a/src/vppinfra/qsort.c b/src/vppinfra/qsort.c deleted file mode 100644 index 145ae40fe91..00000000000 --- a/src/vppinfra/qsort.c +++ /dev/null @@ -1,269 +0,0 @@ -/* - * Copyright (c) 2015 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* - * Imported into CLIB by Eliot Dresselhaus from: - * - * 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). - * - * modifications copyright (c) 2003 Cisco Systems, Inc. - */ - -#include <vppinfra/clib.h> - -/* - * 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. - */ - -#define THRESH 4 /* threshold for insertion */ -#define MTHRESH 6 /* threshold for median */ - -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 */ -} qst_t; - -static void qst (qst_t * q, 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 -qsort (void *base, uword n, uword size, - int (*compar) (const void *, const void *)) -{ - char *i; - char *j; - char *lo; - char *hi; - char *min; - char c; - char *max; - qst_t _q, *q = &_q; - - if (n <= 1) - return; - - q->qsz = size; - q->qcmp = compar; - 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; - } - /* - * 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; - } - } - /* - * 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 += 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; - } - } - } -} - - - -/* - * 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 partitions, 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 (qst_t * q, char *base, char *max) -{ - char *i; - char *j; - char *jj; - char *mid; - int ii; - char c; - 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; - } - 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; - } - } - while (lo >= q->thresh); -} - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h index 461c0de3347..da7d0896109 100644 --- a/src/vppinfra/vec.h +++ b/src/vppinfra/vec.h @@ -974,12 +974,16 @@ do { \ /** \brief Sort a vector using the supplied element comparison function + Does not depend on the underlying implementation to deal correctly + with null, zero-long, or 1-long vectors + @param vec vector to sort @param f comparison function */ -#define vec_sort_with_function(vec,f) \ -do { \ - qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \ +#define vec_sort_with_function(vec,f) \ +do { \ + if (vec_len (vec) > 1) \ + qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \ } while (0) /** \brief Make a vector containing a NULL terminated c-string. |