FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
qsort.c
Go to the documentation of this file.
1 /*
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:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15 /*
16  * Imported into CLIB by Eliot Dresselhaus from:
17  *
18  * This file is part of
19  * MakeIndex - A formatter and format independent index processor
20  *
21  * This file is public domain software donated by
22  * Nelson Beebe (beebe@science.utah.edu).
23  *
24  * modifications copyright (c) 2003 Cisco Systems, Inc.
25  */
26 
27 #include <vppinfra/clib.h>
28 
29 /*
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.
34  */
35 
36 #define THRESH 4 /* threshold for insertion */
37 #define MTHRESH 6 /* threshold for median */
38 
39 typedef struct
40 {
41  word qsz; /* size of each record */
42  word thresh; /* THRESHold in chars */
43  word mthresh; /* MTHRESHold in chars */
44  int (*qcmp) (const void *, const void *); /* the comparison routine */
45 } qst_t;
46 
47 static void qst (qst_t * q, char *base, char *max);
48 
49 /*
50  * qqsort: First, set up some global parameters for qst to share.
51  * Then, quicksort with qst(), and then a cleanup insertion sort ourselves.
52  * Sound simple? It's not...
53  */
54 
55 void
56 qsort (void *base, uword n, uword size,
57  int (*compar) (const void *, const void *))
58 {
59  char *i;
60  char *j;
61  char *lo;
62  char *hi;
63  char *min;
64  char c;
65  char *max;
66  qst_t _q, *q = &_q;
67 
68  if (n <= 1)
69  return;
70 
71  q->qsz = size;
72  q->qcmp = compar;
73  q->thresh = q->qsz * THRESH;
74  q->mthresh = q->qsz * MTHRESH;
75  max = base + n * q->qsz;
76  if (n >= THRESH)
77  {
78  qst (q, base, max);
79  hi = base + q->thresh;
80  }
81  else
82  {
83  hi = max;
84  }
85  /*
86  * First put smallest element, which must be in the first THRESH, in the
87  * first position as a sentinel. This is done just by searching the
88  * first THRESH elements (or the first n if n < THRESH), finding the min,
89  * and swapping it into the first position.
90  */
91  for (j = lo = base; (lo += q->qsz) < hi;)
92  {
93  if ((*compar) (j, lo) > 0)
94  j = lo;
95  }
96  if (j != base)
97  { /* swap j into place */
98  for (i = base, hi = base + q->qsz; i < hi;)
99  {
100  c = *j;
101  *j++ = *i;
102  *i++ = c;
103  }
104  }
105  /*
106  * With our sentinel in place, we now run the following hyper-fast
107  * insertion sort. For each remaining element, min, from [1] to [n-1],
108  * set hi to the index of the element AFTER which this one goes. Then, do
109  * the standard insertion sort shift on a character at a time basis for
110  * each element in the frob.
111  */
112  for (min = base; (hi = min += q->qsz) < max;)
113  {
114  while ((*q->qcmp) (hi -= q->qsz, min) > 0);
115  if ((hi += q->qsz) != min)
116  {
117  for (lo = min + q->qsz; --lo >= min;)
118  {
119  c = *lo;
120  for (i = j = lo; (j -= q->qsz) >= hi; i = j)
121  *i = *j;
122  *i = c;
123  }
124  }
125  }
126 }
127 
128 
129 
130 /*
131  * qst: Do a quicksort. First, find the median element, and put that one in
132  * the first place as the discriminator. (This "median" is just the median
133  * of the first, last and middle elements). (Using this median instead of
134  * the first element is a big win). Then, the usual partitioning/swapping,
135  * followed by moving the discriminator into the right place. Then, figure
136  * out the sizes of the two partitions, do the smaller one recursively and the
137  * larger one via a repeat of this code. Stopping when there are less than
138  * THRESH elements in a partition and cleaning up with an insertion sort (in
139  * our caller) is a huge win. All data swaps are done in-line, which is
140  * space-losing but time-saving. (And there are only three places where this
141  * is done).
142  */
143 
144 static void
145 qst (qst_t * q, char *base, char *max)
146 {
147  char *i;
148  char *j;
149  char *jj;
150  char *mid;
151  int ii;
152  char c;
153  char *tmp;
154  int lo;
155  int hi;
156  int qsz = q->qsz;
157 
158  lo = (int) (max - base); /* number of elements as chars */
159  do
160  {
161  /*
162  * At the top here, lo is the number of characters of elements in the
163  * current partition. (Which should be max - base). Find the median
164  * of the first, last, and middle element and make that the middle
165  * element. Set j to largest of first and middle. If max is larger
166  * than that guy, then it's that guy, else compare max with loser of
167  * first and take larger. Things are set up to prefer the middle,
168  * then the first in case of ties.
169  */
170  mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
171  if (lo >= q->mthresh)
172  {
173  j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
174  if ((*q->qcmp) (j, (tmp = max - qsz)) > 0)
175  {
176  /* switch to first loser */
177  j = (j == jj ? i : jj);
178  if ((*q->qcmp) (j, tmp) < 0)
179  j = tmp;
180  }
181  if (j != i)
182  {
183  ii = qsz;
184  do
185  {
186  c = *i;
187  *i++ = *j;
188  *j++ = c;
189  }
190  while (--ii);
191  }
192  }
193  /* Semi-standard quicksort partitioning/swapping */
194  for (i = base, j = max - qsz;;)
195  {
196  while (i < mid && (*q->qcmp) (i, mid) <= 0)
197  i += qsz;
198  while (j > mid)
199  {
200  if ((*q->qcmp) (mid, j) <= 0)
201  {
202  j -= qsz;
203  continue;
204  }
205  tmp = i + qsz; /* value of i after swap */
206  if (i == mid)
207  { /* j <-> mid, new mid is j */
208  mid = jj = j;
209  }
210  else
211  { /* i <-> j */
212  jj = j;
213  j -= qsz;
214  }
215  goto swap;
216  }
217  if (i == mid)
218  {
219  break;
220  }
221  else
222  { /* i <-> mid, new mid is i */
223  jj = mid;
224  tmp = mid = i; /* value of i after swap */
225  j -= qsz;
226  }
227  swap:
228  ii = qsz;
229  do
230  {
231  c = *i;
232  *i++ = *jj;
233  *jj++ = c;
234  }
235  while (--ii);
236  i = tmp;
237  }
238  /*
239  * Look at sizes of the two partitions, do the smaller one first by
240  * recursion, then do the larger one by making sure lo is its size,
241  * base and max are update correctly, and branching back. But only
242  * repeat (recursively or by branching) if the partition is of at
243  * least size THRESH.
244  */
245  i = (j = mid) + qsz;
246  if ((lo = (int) (j - base)) <= (hi = (int) (max - i)))
247  {
248  if (lo >= q->thresh)
249  qst (q, base, j);
250  base = i;
251  lo = hi;
252  }
253  else
254  {
255  if (hi >= q->thresh)
256  qst (q, i, max);
257  max = j;
258  }
259  }
260  while (lo >= q->thresh);
261 }
262 
263 /*
264  * fd.io coding-style-patch-verification: ON
265  *
266  * Local Variables:
267  * eval: (c-set-style "gnu")
268  * End:
269  */
tmp
u32 * tmp
Definition: interface_output.c:1078
clib.h
THRESH
#define THRESH
Definition: qsort.c:36
MTHRESH
#define MTHRESH
Definition: qsort.c:37
qst_t::qsz
word qsz
Definition: qsort.c:41
hi
vl_api_ip4_address_t hi
Definition: arp.api:37
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
uword
u64 uword
Definition: types.h:112
qst
static void qst(qst_t *q, char *base, char *max)
Definition: qsort.c:145
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
size
u32 size
Definition: vhost_user.h:125
qst_t::qcmp
int(* qcmp)(const void *, const void *)
Definition: qsort.c:44
qst_t::mthresh
word mthresh
Definition: qsort.c:43
word
i64 word
Definition: types.h:111
qsort
void qsort(void *base, uword n, uword size, int(*compar)(const void *, const void *))
Definition: qsort.c:56
qst_t::thresh
word thresh
Definition: qsort.c:42
qst_t
Definition: qsort.c:39
lo
lo
Definition: vector_altivec.h:95