2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 * Imported into CLIB by Eliot Dresselhaus from:
18 * This file is part of
19 * MakeIndex - A formatter and format independent index processor
21 * This file is public domain software donated by
22 * Nelson Beebe (beebe@science.utah.edu).
24 * modifications copyright (c) 2003 Cisco Systems, Inc.
27 #include <vppinfra/clib.h>
30 * qsort.c: Our own version of the system qsort routine which is faster by an
31 * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
32 * the insertion sort threshold, and has been adjusted for records of size 48
33 * bytes. The MTHREShold is where we stop finding a better median.
36 #define THRESH 4 /* threshold for insertion */
37 #define MTHRESH 6 /* threshold for median */
40 word qsz; /* size of each record */
41 word thresh; /* THRESHold in chars */
42 word mthresh; /* MTHRESHold in chars */
43 int (*qcmp) (const void *, const void *); /* the comparison routine */
46 static void qst (qst_t * q, char * base, char *max);
49 * qqsort: First, set up some global parameters for qst to share.
50 * Then, quicksort with qst(), and then a cleanup insertion sort ourselves.
51 * Sound simple? It's not...
55 qsort (void * base, uword n, uword size,
56 int (*compar) (const void *, const void *))
72 q->thresh = q->qsz * THRESH;
73 q->mthresh = q->qsz * MTHRESH;
74 max = base + n * q->qsz;
77 hi = base + q->thresh;
82 * First put smallest element, which must be in the first THRESH, in the
83 * first position as a sentinel. This is done just by searching the
84 * first THRESH elements (or the first n if n < THRESH), finding the min,
85 * and swapping it into the first position.
87 for (j = lo = base; (lo += q->qsz) < hi;) {
88 if ((*compar) (j, lo) > 0)
91 if (j != base) { /* swap j into place */
92 for (i = base, hi = base + q->qsz; i < hi;) {
99 * With our sentinel in place, we now run the following hyper-fast
100 * insertion sort. For each remaining element, min, from [1] to [n-1],
101 * set hi to the index of the element AFTER which this one goes. Then, do
102 * the standard insertion sort shift on a character at a time basis for
103 * each element in the frob.
105 for (min = base; (hi = min += q->qsz) < max;) {
106 while ((*q->qcmp) (hi -= q->qsz, min) > 0);
107 if ((hi += q->qsz) != min) {
108 for (lo = min + q->qsz; --lo >= min;) {
110 for (i = j = lo; (j -= q->qsz) >= hi; i = j)
121 * qst: Do a quicksort. First, find the median element, and put that one in
122 * the first place as the discriminator. (This "median" is just the median
123 * of the first, last and middle elements). (Using this median instead of
124 * the first element is a big win). Then, the usual partitioning/swapping,
125 * followed by moving the discriminator into the right place. Then, figure
126 * out the sizes of the two partions, do the smaller one recursively and the
127 * larger one via a repeat of this code. Stopping when there are less than
128 * THRESH elements in a partition and cleaning up with an insertion sort (in
129 * our caller) is a huge win. All data swaps are done in-line, which is
130 * space-losing but time-saving. (And there are only three places where this
135 qst(qst_t *q, char *base, char *max)
148 lo = (int)(max - base); /* number of elements as chars */
151 * At the top here, lo is the number of characters of elements in the
152 * current partition. (Which should be max - base). Find the median
153 * of the first, last, and middle element and make that the middle
154 * element. Set j to largest of first and middle. If max is larger
155 * than that guy, then it's that guy, else compare max with loser of
156 * first and take larger. Things are set up to prefer the middle,
157 * then the first in case of ties.
159 mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
160 if (lo >= q->mthresh) {
161 j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
162 if ((*q->qcmp) (j, (tmp = max - qsz)) > 0) {
163 /* switch to first loser */
164 j = (j == jj ? i : jj);
165 if ((*q->qcmp) (j, tmp) < 0)
177 /* Semi-standard quicksort partitioning/swapping */
178 for (i = base, j = max - qsz;;) {
179 while (i < mid && (*q->qcmp) (i, mid) <= 0)
182 if ((*q->qcmp) (mid, j) <= 0) {
186 tmp = i + qsz; /* value of i after swap */
187 if (i == mid) { /* j <-> mid, new mid is j */
189 } else { /* i <-> j */
197 } else { /* i <-> mid, new mid is i */
199 tmp = mid = i; /* value of i after swap */
212 * Look at sizes of the two partitions, do the smaller one first by
213 * recursion, then do the larger one by making sure lo is its size,
214 * base and max are update correctly, and branching back. But only
215 * repeat (recursively or by branching) if the partition is of at
219 if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
229 } while (lo >= q->thresh);