src/vppinfra/qsort.c

   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  */